NAME

treereg - Compiler for Tree Regular Expressions

SYNOPSIS

            

              
              
treereg [-m packagename] [[no]syntax] [[no]numbers] [-severity 0|1|2|3] \
        [-p treeprefix] [-o outputfile] [-lib /path/to/library/] -i filename[.trg] 
treereg [-m packagename] [[no]syntax] [[no]numbers] [-severity 0|1|2|3] \
        [-p treeprefix] [-lib /path/to/library/] [-o outputfile] filename[.trg] 
treereg -v 
treereg -h
            
          

OPTIONS

Options can be used both with one dash and double dash. It is not necessary to write the full name of the option. A disambiguation prefix suffices.

• -i[n] filename

  Input file. Extension .trg is assumed if no extension is provided.

• -o[ut] filename

  Output file. By default is the name of the input file (concatenated with .pm)

• -m[od] packagename

  Name of the package containing the generated subroutines. By default is the longest prefix of the input file name that conforms to the classic definition of integer [a-z_A-Z]\w*.

• -l[ib] /path/to/library/

  Specifies that /path/to/library/ will be included in @INC. Useful when the syntax option is on. Can be inserted as many times as necessary.

• -p[refix] treeprefix

  Tree nodes automatically generated using Parse::Eyapp are objects blessed into the name of the production. To avoid crashes the programmer may prefix the class names with a given prefix when calling the parser; for example:

  
              
  
                
                
  $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error, yyprefix => __PACKAGE__."::")
              
            

  The -prefix treeprefix option simplifies the process of writing the tree grammar so that instead of writing with the full names

  
              
  
                
                
  CLASS::TIMES(CLASS::NUM, $x) and { $NUM->{VAL} == 0) => { $NUM }
              
            

  it can be written:

  
              
  
                
                
  TIMES(NUM, $x) and { $NUM->{VAL} == 0) => { $NUM }
              
            

• -n[umbers]

  Produces #line directives.

• -non[umbers]

  Disable source file line numbering embedded in your parser

• -sy[ntax]

  Checks that Perl code is syntactically correct.

• -nosy[ntax]

  Does not check the syntax of Perl code

• -se[verity] number

  - 0 = Don't check arity (default). Matching does not check the arity. The actual node being visited may have more children.

  - 1 = Check arity. Matching requires the equality of the number of children and the actual node and the pattern.

  - 2 = Check arity and give a warning

  - 3 = Check arity, give a warning and exit

• -v[ersion]

  Gives the version

• -u[sage]

  Prints the usage info

• -h[elp]

  Print this help

DESCRIPTION

Treereg translates a tree grammar specification file (default extension .trg describing a set of tree patterns and the actions to modify them using tree-terms like:

            

              
              
TIMES(NUM, $x) and { $NUM->{VAL} == 0) => { $NUM }
            
          

which says that wherever an abstract syntax tree representing the product of a numeric expression with value 0 times any other kind of expression, the TIMES tree can be substituted by its left child.

The compiler produces a Perl module containing the subroutines implementing those sets of pattern-actions.

EXAMPLE

Consider the following eyapp grammar (see the Parse::Eyapp documentation to know more about Parse::Eyapp grammars):

            

              
              
----------------------------------------------------------
nereida:~/LEyapp/examples> cat Rule6.yp
%{
use Data::Dumper;
%}
%right  '='
%left   '-' '+'
%left   '*' '/'
%left   NEG
%tree
%%
line: exp  { $_[1] }
;
exp:      %name NUM
     NUM
 | %name VAR
   VAR
 | %name ASSIGN
   VAR '=' exp
 | %name PLUS
   exp '+' exp
 | %name MINUS
   exp '-' exp
 | %name TIMES
   exp '*' exp
 | %name DIV
   exp '/' exp
 | %name UMINUS
   '-' exp %prec NEG
 |   '(' exp ')'  { $_[2] } /* Let us simplify a bit the tree */
;
%%
sub _Error {
    die  "Syntax error.\n";
}
sub _Lexer {
    my($parser)=shift;
 $parser->YYData->{INPUT}
    or  $parser->YYData->{INPUT} = <STDIN>
    or  return('',undef);
    $parser->YYData->{INPUT}=~s/^\s+//;
    for ($parser->YYData->{INPUT}) {
 s/^([0-9]+(?:\.[0-9]+)?)// and return('NUM',$1);
 s/^([A-Za-z][A-Za-z0-9_]*)// and return('VAR',$1);
 s/^(.)//s and return($1,$1);
    }
}
sub Run {
    my($self)=shift;
    $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error );
}
----------------------------------------------------------
            
          

Compile it using eyapp:

            

              
              
----------------------------------------------------------
nereida:~/LEyapp/examples> eyapp Rule6.yp
nereida:~/LEyapp/examples> ls -ltr | tail -1
-rw-rw----  1 pl users  4976 2006-09-15 19:56 Rule6.pm
----------------------------------------------------------
            
          

Now consider this tree grammar:

            

              
              
----------------------------------------------------------
nereida:~/LEyapp/examples> cat Transform2.trg
%{
my %Op = (PLUS=>'+', MINUS => '-', TIMES=>'*', DIV => '/');
%}
fold: 'TIMES|PLUS|DIV|MINUS':bin(NUM($n), NUM($m))
  => {
    my $op = $Op{ref($bin)};
    $n->{attr} = eval  "$n->{attr} $op $m->{attr}";
    $_[0] = $NUM[0];
  }
zero_times_whatever: TIMES(NUM($x), .) and { $x->{attr} == 0 } => { $_[0] = $NUM }
whatever_times_zero: TIMES(., NUM($x)) and { $x->{attr} == 0 } => { $_[0] = $NUM }
/* rules related with times */
times_zero = zero_times_whatever whatever_times_zero;
----------------------------------------------------------
            
          

Compile it with treereg:

            

              
              
----------------------------------------------------------
nereida:~/LEyapp/examples> treereg Transform2.trg
nereida:~/LEyapp/examples> ls -ltr | tail -1
-rw-rw----  1 pl users  1948 2006-09-15 19:57 Transform2.pm
----------------------------------------------------------
            
          

The following program makes use of both modules Rule6.pm and Transform2.pm:

            

              
              
----------------------------------------------------------
nereida:~/LEyapp/examples> cat foldand0rule6_3.pl
#!/usr/bin/perl -w
use strict;
use Rule6;
use Parse::Eyapp::YATW;
use Data::Dumper;
use Transform2;
$Data::Dumper::Indent = 1;
my $parser = new Rule6();
my $t = $parser->Run;
print "\n***** Before ******\n";
print Dumper($t);
$t->s(@Transform2::all);
print "\n***** After ******\n";
print Dumper($t);
----------------------------------------------------------
            
          

When the program runs with input b*(2-2) produces the following output:

            

              
              
 ----------------------------------------------------------
 nereida:~/LEyapp/examples> foldand0rule6_3.pl
 b*(2-2)
 ***** Before ******
 $VAR1 = bless( {
   'children' => [
     bless( {
'children' => [
  bless( { 'children' => [], 'attr' => 'b', 'token' => 'VAR' }, 'TERMINAL' )
]
     }, 'VAR' ),
     bless( {
'children' => [
  bless( { 'children' => [
      bless( { 'children' => [], 'attr' => '2', 'token' => 'NUM' }, 'TERMINAL' )
    ]
  }, 'NUM' ),
  bless( {
    'children' => [
      bless( { 'children' => [], 'attr' => '2', 'token' => 'NUM' }, 'TERMINAL' )
    ]
  }, 'NUM' )
]
     }, 'MINUS' )
   ]
 }, 'TIMES' );
 ***** After ******
 $VAR1 = bless( {
   'children' => [
     bless( { 'children' => [], 'attr' => 0, 'token' => 'NUM' }, 'TERMINAL' )
   ]
 }, 'NUM' );
 ----------------------------------------------------------
            
          

See also the section "Compiling: More Options" in Parse::Eyapp for a more contrived example.

SEE ALSO

• Parse::Eyapp,

• eyapptut

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

• http://nereida.deioc.ull.es/~pl/perlexamples/section_eyappts.html (Spanish),

• eyapp,

• treereg,

• Parse::yapp,

• yacc(1),

• bison(1),

• the classic book "Compilers: Principles, Techniques, and Tools" by Alfred V. Aho, Ravi Sethi and

• Jeffrey D. Ullman (Addison-Wesley 1986)

• Parse::RecDescent.

AUTHOR

Casiano Rodriguez-Leon

LICENSE AND COPYRIGHT

Copyright © 2006, 2007, 2008, 2009, 2010, 2011, 2012 Casiano Rodriguez-Leon. Copyright © 2017 William N. Braswell, Jr. All Rights Reserved.

Parse::Yapp is Copyright © 1998, 1999, 2000, 2001, Francois Desarmenien. Parse::Yapp is Copyright © 2017 William N. Braswell, Jr. All Rights Reserved.

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.8 or, at your option, any later version of Perl 5 you may have available.

cpanm Parse::Eyapp

perl -MCPAN -e shell
install Parse::Eyapp