TREEREG(1) User Contributed Perl Documentation TREEREG(1)

treereg - Compiler for Tree Regular Expressions

  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 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.

- 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

"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.

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.

Casiano Rodriguez-Leon

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.

Hey! The above document had some coding errors, which are explained below:

Non-ASCII character seen before =encoding in '©'. Assuming UTF-8
2017-06-14 perl v5.34.0