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

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.

       o   "-i[n] filename"

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

       o   "-o[ut] filename"

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

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

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

       o   "-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 }

       o   "-n[umbers]"

	   Produces "#line" directives.

       o   "-non[umbers]"

	   Disable source file line numbering embedded in your parser

       o   "-sy[ntax]"

	   Checks that Perl code is syntactically correct.

       o   "-nosy[ntax]"

	   Does not check the syntax of Perl code

       o   "-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
       o   "-v[ersion]"

	   Gives the version

       o   "-u[sage]"

	   Prints the usage info

       o   "-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.
";
	 }

	 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 "
***** Before ******
";
	 print Dumper($t);
	 $t->s(@Transform2::all);
	 print "
***** After ******
";
	 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

       o   Parse::Eyapp,

       o   eyapptut

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

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

       o   eyapp,

       o   treereg,

       o   Parse::yapp,

       o   yacc(1),

       o   bison(1),

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

       o   Jeffrey D. Ullman (Addison-Wesley 1986)

       o   Parse::RecDescent.

AUTHOR

       Casiano Rodriguez-Leon

LICENSE AND COPYRIGHT

       Copyright (C) 2006 by Casiano Rodriguez-Leon

       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.

perl v5.16.2							    2009-11-06								TREEREG(1)