Construcción del Árbol Sintáctico

El siguiente ejemplo usa yapp para construir el árbol sintáctico de una expresión en infijo:
$ cat -n Infixtree_bless.yp
 1  #
 2  # Infixtree.yp
 3  #
 4
 5  %{
 6  use Data::Dumper;
 7  %}
 8  %right  '='
 9  %left   '-' '+'
10  %left   '*' '/'
11  %left   NEG
12
13  %%
14  input:  #empty
15          |   input line
16  ;
17
18  line:     '\n'         { $_[1] }
19          | exp '\n'     { print Dumper($_[1]); }
20          | error '\n'   { $_[0]->YYErrok }
21  ;
22
23  exp:        NUM
24          |   VAR                 { $_[1] }
25          |   VAR '=' exp         { bless [$_[1], $_[3]], 'ASSIGN' }
26          |   exp '+' exp         { bless [$_[1], $_[3] ], 'PLUS'}
27          |   exp '-' exp         { bless [$_[1], $_[3] ], 'MINUS'}
28          |   exp '*' exp         { bless [$_[1], $_[3]], 'TIMES' }
29          |   exp '/' exp         { bless [$_[1], $_[3]], 'DIVIDE' }
30          |   '-' exp %prec NEG   { bless [$_[2]], 'NEG' }
31          |   '(' exp ')'         { $_[2] }
32  ;
33
34  %%
35
36  sub _Error {
37          exists $_[0]->YYData->{ERRMSG}
38      and do {
39          print $_[0]->YYData->{ERRMSG};
40          delete $_[0]->YYData->{ERRMSG};
41          return;
42      };
43      print "Syntax error.\n";
44  }
45
46  sub _Lexer {
47      my($parser)=shift;
48
49          defined($parser->YYData->{INPUT})
50      or  $parser->YYData->{INPUT} = <STDIN>
51      or  return('',undef);
52
53      $parser->YYData->{INPUT}=~s/^[ \t]//;
54
55      for ($parser->YYData->{INPUT}) {
56          s/^([0-9]+(?:\.[0-9]+)?)//
57                  and return('NUM',$1);
58          s/^([A-Za-z][A-Za-z0-9_]*)//
59                  and return('VAR',$1);
60          s/^(.)//s
61                  and return($1,$1);
62      }
63  }
64
65  sub Run {
66      my($self)=shift;
67      $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error );
68  }
Para compilar hacemos:
$ yapp -m Infixtree Infixtree_bless.yp
El guión que usa el analizador anterior es similar al que vimos en la sección 35.1:
$ cat -n ./useinfixtree.pl
     1  #!/usr/bin/perl -w
     2
     3  use Infixtree;
     4
     5  $parser = new Infixtree();
     6  $parser->Run;
Veamos un ejemplo de ejecución:
$ ./useinfixtree.pl
a = 2+3
$VAR1 = bless( [
                 'a',
                 bless( [
                          '2',
                          '3'
                        ], 'PLUS' )
               ], 'ASSIGN' );
b = a*4+a
$VAR1 = bless( [
                 'b',
                 bless( [
                          bless( [
                                   'a',
                                   '4'
                                 ], 'TIMES' ),
                          'a'
                        ], 'PLUS' )
               ], 'ASSIGN' );

Casiano Rodríguez León
2013-04-23