treereg - Compiler for Tree Regular Expressions
treereg [-m packagename] [[no]syntax] [[no]numbers] [-severity 0|1|2|3] \ [-p treeprefix] [-o outputfile] -i filename[.trg] treereg [-m packagename] [[no]syntax] [[no]numbers] [-severity 0|1|2|3] \ [-p treeprefix] [-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.
-i[n] filename
Input file. Extension .trg is assumed if no extension is provided.
.trg
-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*.
[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.
/path/to/library/
@INC
syntax
-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:
Parse::Eyapp
$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
-prefix treeprefix
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.
#line
-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 syntaxis of Perl code
-se[verity] number
-v[ersion]
Gives the version
-u[sage]
Prints the usage info
-h[elp]
Print this help
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:
Treereg
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.
TIMES
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):
eyapp
---------------------------------------------------------- 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:
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:
Rule6.pm
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:
b*(2-2)
---------------------------------------------------------- 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' ); ----------------------------------------------------------
Parse::Eyapp,
eyapptut
The pdf files in http://nereida.deioc.ull.es/~pl/perlexamples/Eyapp.pdf and http://nereida.deioc.ull.es/~pl/perlexamples/eyapptut.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.
Casiano Rodriguez-Leon
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.
To install Parse::Eyapp, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Parse::Eyapp
CPAN shell
perl -MCPAN -e shell install Parse::Eyapp
For more information on module installation, please visit the detailed CPAN module installation guide.