Страницы справочника OS X

Эта страница руководства для  версии 10.9 Mac OS X

Читать страницы руководства

Parse::Eyapp::MatchingTrees(3)       User Contributed Perl Documentation      Parse::Eyapp::MatchingTrees(3)



NAME
       Parse::Eyapp::treematchingtut - Tree Matching and Tree substitution: an introduction

TREE MATCHING AND TREE SUBSTITUTION
       Most of the examples in this section can be found in the directory "examples/MatchingTrees" that
       comes with the distribution of Parse::Eyapp.

   Matching Trees
       Both the transformation objects in "Parse::Eyapp::YATW" and the nodes in "Parse::Eyapp::Node" have a
       method named "m" for matching.  For a "Parse::Eyapp::YATW" object, the method -when called in a list
       context- returns a list of "Parse::Eyapp::Node::Match" nodes.

                           @R = $t->m($yatw1, $yatw2, $yatw3, ...)

       A "Parse::Eyapp::Node::Match" object describes the nodes of the actual tree that have matched.  The
       nodes in the returned list are organized in a hierarchy.  They appear in the list sorted according to
       a depth-first visit of the actual tree $t.  In a scalar context "m" returns the first element of the
       list.

       Let us denote by $t the actual tree being searched and $r one of the "Parse::Eyapp::Node::Match"
       nodes in the resulting forest @R.  Then we have the following methods:

       •   The method "$r->node" return the node $t of the actual tree that matched

       •   The method "$r->father" returns the father of $r in the matching forest.  The father of $r is
           defined by this property: "$r->father->node" is the nearest ancestor of "$r->node" that matched
           with the treeregexp pattern.  That is, there is no ancestor that matched between "$r->node" and
           "$r->father->node".  Otherwise "$r->father" is "undef"

       •   The method "$r->coord" returns the coordinates of "$r->node" relative to $t.  For example, the
           coordinate ".1.3.2" denotes the node "$t->child(1)->child(3)->child(2)", where $t is the root of
           the search.

       •   The method "$r->depth" returns the depth of "$r->node" in $t.

       •   When "m" was called as a "Parse::Eyapp::Node" method, i. e.  with potentially more than one
           "YATW" treeregexp, the method "$r->names" returns the array of names of the transformations that
           matched with "$r->node".

       Use of "m" as a Parse::Eyapp::Node Method

       The example in "examples/MatchingTrees/m2.pl" shows the use of "m" as a "Parse::Eyapp::Node" method.

         examples/MatchingTrees$ cat -n m2.pl
            1  #!/usr/bin/perl -w
            2  use strict;
            3  use Rule6;
            4  use Parse::Eyapp::Treeregexp;
            5
            6  Parse::Eyapp::Treeregexp->new( STRING => q{
            7    fold: /TIMES|PLUS|DIV|MINUS/(NUM, NUM)
            8    zxw: TIMES(NUM($x), .) and { $x->{attr} == 0 }
            9    wxz: TIMES(., NUM($x)) and { $x->{attr} == 0 }
           10  })->generate();
           11
           12  # Syntax analysis
           13  my $parser = new Rule6();
           14  my $input = "0*0*0";
           15  my $t = $parser->Run(\$input);
           16  print "Tree:",$t->str,"\n";
           17
           18  # Search
           19  my $m = $t->m(our ($fold, $zxw, $wxz));
           20  print "Match Node:\n",$m->str,"\n";

       When executed with input "0*0*0" the program generates this output:

         examples/MatchingTrees$ m2.pl
         Tree:TIMES(TIMES(NUM(TERMINAL),NUM(TERMINAL)),NUM(TERMINAL))
         Match Node:
         Match[[TIMES:0:wxz]](Match[[TIMES:1:fold,zxw,wxz]])

       The representation of "Match" nodes by "str" deserves a comment.  "Match" nodes have their own "info"
       method. It returns a string containing the concatenation of the class of "$r->node" (i.e. the actual
       node that matched), the depth ("$r->depth") and the names of the transformations that matched (as
       provided by the method "$r->names")

       Use of "m" as a Parse::Eyapp::YATW Method

       A second example can be found inside the file "examples/typechecking/Simple-Types-XXX.tar.gz".  It
       illustrates a use of "m" as a "Parse::Eyapp:YATW" method.  It solves a problem of scope analysis in a
       C compiler: matching each "RETURN" statement with the function that surrounds it. The parsing was
       already done, the AST was built and left in $t. The treeregexp used (see "lib/Simple/Trans.trg") is:

         retscope: /FUNCTION|RETURN/

       and the code that solves the problem (see subroutine "compile" in file "lib/Simple/Types.eyp" is:

        # Associate each "return exp" with its "function"
        my @returns = $retscope->m($t);
        for (@returns) {
          my $node = $_->node;
          if (ref($node) eq 'RETURN') {
            my $function = $_->father->node;
            $node->{function}  = $function;
            $node->{t} = $function->{t};
          }
        }

       The first line gets a list of "Parse::Eyapp::Node::Match" nodes describing  the actual nodes that
       matched "/FUNCTION|RETURN/".  If the node described by $_ is a 'RETURN' node, the expresion "
       $_->father->node" must necessarily point to the function node that encloses it.

   The "SEVERITY" option of "Parse::Eyapp::Treeregexp::new"
       The "SEVERITY" option of "Parse::Eyapp::Treeregexp::new" controls the way matching succeeds regarding
       the number of children.  To illustrate its use let us consider the following example.  The grammar
       used "Rule6.yp" is similar to the example in the section "SYNOPSIS" in Parse::Eyapp::Node.

         examples/MatchingTrees$ cat -n numchildren.pl
            1  #!/usr/bin/perl -w
            2  use strict;
            3  use Rule6;
            4  use Parse::Eyapp::Treeregexp;
            5
            6  sub TERMINAL::info { $_[0]{attr} }
            7
            8  my $severity = shift || 0;
            9  my $input = shift || '0*2';
           10
           11  my $parser = new Rule6();
           12  my $t = $parser->Run(\$input);
           13
           14  my $transform = Parse::Eyapp::Treeregexp->new(
           15    STRING => q{
           16      zero_times_whatever: TIMES(NUM($x)) and { $x->{attr} == 0 } => { $_[0] = $NUM }
           17    },
           18    SEVERITY => $severity,
           19    FIRSTLINE => 14,
           20  )->generate;
           21
           22  $t->s(our @all);
           23
           24  print $t->str,"\n";

       The program gets the severity level from the command line (line 9).  The specification of the term
       "TIMES(NUM($x))" inside the transformation "zero_times_whatever" does not clearly state that "TIMES"
       must have two children.  There are several interpretations of the treregexp depending on the level
       fixed for "SEVERITY":

       •   0: "TIMES" must have at least one child. Don't care if it has more.

       •   1: "TIMES" must have exactly one child.

       •   2: "TIMES" must have exactly one child. When visit a "TIMES" node with a different number of
           children issue a warning.

       •   3: "TIMES" must have exactly one child.  When visit a "TIMES" node with a different number of
           children issue an error.

       Observe the change in behavior according to the level of "SEVERITY":

         pl@nereida:~/LEyapp/examples/MatchingTrees$ numchildren.pl 0 '0*2'
         NUM(TERMINAL[0])
         pl@nereida:~/LEyapp/examples/MatchingTrees$ numchildren.pl 1 '0*2'
         TIMES(NUM(TERMINAL[0]),NUM(TERMINAL[2]))
         pl@nereida:~/LEyapp/examples/MatchingTrees$ numchildren.pl 2 '0*2'
         Warning! found node TIMES with 2 children.
         Expected 1 children (see line 15 of ./numchildren.pl)"
         TIMES(NUM(TERMINAL[0]),NUM(TERMINAL[2]))
         pl@nereida:~/LEyapp/examples/MatchingTrees$ numchildren.pl 3 '0*2'
         Error! found node TIMES with 2 children.
         Expected 1 children (see line 15 of ./numchildren.pl)"
          at (eval 3) line 29

   Tree Substitution: The "s" methods
       Both "Parse::Eyapp:Node" and "Parse::Eyapp::YATW" objects (i.e.  nodes and tree transformations) are
       provided with a "s" method.

       In the case of a "Parse::Eyapp::YATW" object the method "s" applies the tree transformation using a
       single bottom-up traversing: the transformation is recursively applied to the children and then to
       the current node.

       For "Parse::Eyapp:Node" nodes the set of transformations is applied to each node until no
       transformation matches any more.  The example in the section "SYNOPSIS" in Parse::Eyapp::Node
       illustrates the use:

         1  # Let us transform the tree. Define the tree-regular expressions ..
         2  my $p = Parse::Eyapp::Treeregexp->new( STRING => q{
         3    { #  Example of support code
         4      my %Op = (PLUS=>'+', MINUS => '-', TIMES=>'*', DIV => '/');
         5    }
         6    constantfold: /TIMES|PLUS|DIV|MINUS/:bin(NUM($x), NUM($y))
         7      => {
         8        my $op = $Op{ref($_[0])};
         9        $x->{attr} = eval  "$x->{attr} $op $y->{attr}";
        10        $_[0] = $NUM[0];
        11      }
        12    uminus: UMINUS(NUM($x)) => { $x->{attr} = -$x->{attr}; $_[0] = $NUM }
        13    zero_times_whatever: TIMES(NUM($x), .) and { $x->{attr} == 0 } => { $_[0] = $NUM }
        14    whatever_times_zero: TIMES(., NUM($x)) and { $x->{attr} == 0 } => { $_[0] = $NUM }
        15    },
        16    OUTPUTFILE=> 'main.pm'
        17  );
        18  $p->generate(); # Create the tranformations
        19
        20  $t->s($uminus); # Transform UMINUS nodes
        21  $t->s(@all);    # constant folding and mult. by zero

       The call at line 20 can be substituted by "$uminus->s($t)" without changes.

SEE ALSO
       •   The project home is at http://code.google.com/p/parse-eyapp/ <http://code .google.com/p/parse-
           eyapp/>.  Use a subversion client to anonymously check out the latest project source code:

              svn checkout http://parse-eyapp.googlecode.com/svn/trunk/ parse-eyapp-read-only

       •   The tutorial Parsing Strings and Trees with "Parse::Eyapp" (An Introduction to Compiler
           Construction in seven pages) in <http://nereida.deioc.ull.es/~pl/eyapsimple/>

       •   Parse::Eyapp, Parse::Eyapp::eyapplanguageref, Parse::Eyapp::debuggingtut,
           Parse::Eyapp::defaultactionsintro, Parse::Eyapp::translationschemestut, Parse::Eyapp::Driver,
           Parse::Eyapp::Node, Parse::Eyapp::YATW, Parse::Eyapp::Treeregexp, Parse::Eyapp::Scope,
           Parse::Eyapp::Base, Parse::Eyapp::datagenerationtut

       •   The pdf file in <http://nereida.deioc.ull.es/~pl/perlexamples/languageintro.pdf>

       •   The pdf file in <http://nereida.deioc.ull.es/~pl/perlexamples/debuggingtut.pdf>

       •   The pdf file in <http://nereida.deioc.ull.es/~pl/perlexamples/eyapplanguageref.pdf>

       •   The pdf file in <http://nereida.deioc.ull.es/~pl/perlexamples/Treeregexp.pdf>

       •   The pdf file in <http://nereida.deioc.ull.es/~pl/perlexamples/Node.pdf>

       •   The pdf file in <http://nereida.deioc.ull.es/~pl/perlexamples/YATW.pdf>

       •   The pdf file in <http://nereida.deioc.ull.es/~pl/perlexamples/Eyapp.pdf>

       •   The pdf file in <http://nereida.deioc.ull.es/~pl/perlexamples/Base.pdf>

       •   The pdf file in <http://nereida.deioc.ull.es/~pl/perlexamples/translationschemestut.pdf>

       •   The pdf file in <http://nereida.deioc.ull.es/~pl/perlexamples/treematchingtut.pdf>

       •   perldoc eyapp,

       •   perldoc treereg,

       •   perldoc vgg,

       •   The Syntax Highlight file for vim at <http://www.vim.org/scripts/script.php?script_id=2453> and
           <http://nereida.deioc.ull.es/~vim/>

       •   Analisis Lexico y Sintactico, (Notes for a course in compiler construction) by  Casiano
           Rodriguez-Leon.  Available at  <http://nereida.deioc.ull.es/~pl/perlexamples/> Is the more
           complete and reliable source for Parse::Eyapp. However is in Spanish.

       •   Parse::Yapp,

       •   Man pages of yacc(1) and bison(1), <http://www.delorie.com/gnu/docs/bison/bison.html>

       •   Language::AttributeGrammar

       •   Parse::RecDescent.

       •   HOP::Parser

       •   HOP::Lexer

       •   ocamlyacc tutorial at
           http://plus.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-tutorial/ocamlyacc-tutorial.html
           <http://plus .kaist.ac.kr / ~ shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-tutorial/ocamlyacc-
           tutorial.html>

REFERENCES
       •   The classic Dragon's book Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Ravi
           Sethi and Jeffrey D. Ullman (Addison-Wesley 1986)

       •   CS2121: The Implementation and Power of Programming Languages (See
           <http://www.cs.man.ac.uk/~pjj>, <http://www.cs.man.ac.uk/~pjj/complang/g2lr.html> and
           <http://www.cs.man.ac.uk/~pjj/cs2121/ho/ho.html>) by Pete Jinks

CONTRIBUTORS
       • Hal Finkel <http://www.halssoftware.com/>

       • G. Williams <http://kasei.us/>

       • Thomas L. Shinnick <http://search.cpan.org/~tshinnic/>

       • Frank Leray

AUTHOR
       Casiano Rodriguez-Leon (casiano@ull.es)

ACKNOWLEDGMENTS
       This work has been supported by CEE (FEDER) and the Spanish Ministry of Educacion y Ciencia through
       Plan Nacional I+D+I number TIN2005-08818-C04-04 (ULL::OPLINK project <http://www.oplink.ull.es/>).
       Support from Gobierno de Canarias was through GC02210601 (Grupos Consolidados).  The University of La
       Laguna has also supported my work in many ways and for many years.

       A large percentage of  code is verbatim taken from Parse::Yapp 1.05.  The author of Parse::Yapp is
       Francois Desarmenien.

       I wish to thank Francois Desarmenien for his Parse::Yapp module, to my students at La Laguna and to
       the Perl Community. Thanks to the people who have contributed to improve the module (see
       "CONTRIBUTORS" in Parse::Eyapp).  Thanks to Larry Wall for giving us Perl.  Special thanks to Juana.

LICENCE AND COPYRIGHT
       Copyright (c) 2006-2008 Casiano Rodriguez-Leon (casiano@ull.es). All rights reserved.

       Parse::Yapp copyright is of Francois Desarmenien, all rights reserved. 1998-2001

       These modules are free software; you can redistribute it and/or modify it under the same terms as
       Perl itself. See perlartistic.

       This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without
       even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.



perl v5.16.2                                     2012-03-23                   Parse::Eyapp::MatchingTrees(3)