Parse::Eyapp::defaultactionsintro - Introduction to Default Actions and Grammar Reuse
The examples used in this tutorial can be found in the directory examples/recycle accompanying this distribution
examples/recycle
When no action is specified both yapp and eyapp implicitly insert the semantic action { $_[1] }. In Parse::Eyapp you can modify such behavior using the %defaultaction { Perl code } directive. The { Perl code } clause that follows the %defaultaction directive is executed when reducing by any production for which no explicit action was specified.
yapp
eyapp
{ $_[1] }
Parse::Eyapp
%defaultaction { Perl code }
{ Perl code }
%defaultaction
See the example in examples/eyapplanguageref/Postfix.eyp that translates an infix expression like a=b*-3 into a postfix expression like a b 3 NEG * = :
examples/eyapplanguageref/Postfix.eyp
a=b*-3
a b 3 NEG * =
Parse-Eyapp/examples/eyapplanguageref$ cat -n Postfix.eyp 1 # File Postfix.eyp 2 %right '=' 3 %left '-' '+' 4 %left '*' '/' 5 %left NEG 6 7 %defaultaction { return "$left $right $op"; } 8 9 %% 10 line: $exp { print "$exp\n" } 11 ; 12 13 exp: $NUM { $NUM } 14 | $VAR { $VAR } 15 | VAR.left '='.op exp.right 16 | exp.left '+'.op exp.right 17 | exp.left '-'.op exp.right 18 | exp.left '*'.op exp.right 19 | exp.left '/'.op exp.right 20 | '-' $exp %prec NEG { "$exp NEG" } 21 | '(' $exp ')' { $exp } 22 ; 23 24 %% 25 26 sub _Error { 27 my($token)=$_[0]->YYCurval; 28 my($what)= $token ? "input: '$token'" : "end of input"; 29 my @expected = $_[0]->YYExpect(); 30 31 local $" = ', '; 32 die "Syntax error near $what. Expected one of these tokens: @expected\n"; 33 } 34 35 my $x; 36 37 sub _Lexer { 38 my($parser)=shift; 39 40 for ($x) { 41 s/^\s+//; 42 $_ eq '' and return('',undef); 43 44 s/^([0-9]+(?:\.[0-9]+)?)// and return('NUM',$1); 45 s/^([A-Za-z][A-Za-z0-9_]*)// and return('VAR',$1); 46 s/^(.)//s and return($1,$1); 47 } 48 } 49 50 sub Run { 51 my($self)=shift; 52 my $debug = shift @ARGV; 53 $debug = 0x1F if $debug; 54 print "Infix to postfix translator. Write an arithmetic expression: "; 55 $x = <STDIN>; 56 $self->YYParse( 57 yylex => \&_Lexer, 58 yyerror => \&_Error, 59 yydebug => $debug, 60 ); 61 } 62 63 # Modulino 64 __PACKAGE__->new()->Run unless caller();
The file containing the Eyapp program must be compiled with eyapp:
Eyapp
Parse-Eyapp/examples/eyapplanguageref$ eyapp Postfix.eyp
Next, you have to write a client program:
Parse-Eyapp/examples/eyapplanguageref$ cat -n usepostfix.pl 1 #!/usr/bin/perl -w 2 use strict; 3 use Postfix; 4 5 my $parser = new Postfix(); 6 $parser->Run;
Now we can run the client program:
Parse-Eyapp/examples/eyapplanguageref$ usepostfix.pl Infix to postfix translator. Write an arithmetic expression: -(2*a-b*-3) 2 a * b 3 NEG * - NEG
An alternative is to use the generated module as a modulino, compiling the grammar using option -b:
-b
Parse-Eyapp/examples/eyapplanguageref$ eyapp -b '' Postfix.eyp
This way, we can directly use the modulo as a script:
Parse-Eyapp/examples/eyapplanguageref$ ./Postfix.pm Infix to postfix translator. Write an arithmetic expression: 2*3+b 2 3 * b +
%name
YYName
In eyapp each production rule has a name. The name of a rule can be explicitly given by the programmer using the %name directive. For example, in the piece of code that follows the name ASSIGN is given to the rule exp: VAR '=' exp.
ASSIGN
exp: VAR '=' exp
When no explicit name is given the rule has an implicit name. The implicit name of a rule is shaped by concatenating the name of the syntactic variable on its left, an underscore and the ordinal number of the production rule Lhs_# as it appears in the .output file. Avoid giving names matching such pattern to production rules. The patterns /${lhs}_\d+$/ where ${lhs} is the name of the syntactic variable are reserved for internal use by eyapp.
Lhs_#
.output
/${lhs}_\d+$/
${lhs}
pl@nereida:~/LEyapp/examples$ cat -n Lhs.eyp 1 # Lhs.eyp 2 3 %right '=' 4 %left '-' '+' 5 %left '*' '/' 6 %left NEG 7 8 %defaultaction { 9 my $self = shift; 10 my $name = $self->YYName(); 11 bless { children => [ grep {ref($_)} @_] }, $name; 12 } 13 14 %% 15 input: 16 /* empty */ 17 { [] } 18 | input line 19 { 20 push @{$_[1]}, $_[2] if defined($_[2]); 21 $_[1] 22 } 23 ; 24 25 line: '\n' { } 26 | exp '\n' { $_[1] } 27 ; 28 29 exp: 30 NUM { $_[1] } 31 | VAR { $_[1] } 32 | %name ASSIGN 33 VAR '=' exp 34 | %name PLUS 35 exp '+' exp 36 | %name MINUS 37 exp '-' exp 38 | %name TIMES 39 exp '*' exp 40 | %name DIV 41 exp '/' exp 42 | %name UMINUS 43 '-' exp %prec NEG 44 | '(' exp ')' { $_[2] } 45 ;
Inside a semantic action the name of the current rule can be recovered using the method YYName of the parser object.
The default action (lines 8-12) computes as attribute of the left hand side a reference to an object blessed in the name of the rule. The object has an attribute children which is a reference to the list of children of the node. The call to grep
children
grep
11 bless { children => [ grep {ref($_)} @_] }, $name;
excludes children that aren't references. Notice that the lexical analyzer only returns references for the NUM and VAR terminals:
NUM
VAR
59 sub _Lexer { 60 my($parser)=shift; 61 62 for ($parser->YYData->{INPUT}) { 63 s/^[ \t]+//; 64 return('',undef) unless $_; 65 s/^([0-9]+(?:\.[0-9]+)?)// 66 and return('NUM', bless { attr => $1}, 'NUM'); 67 s/^([A-Za-z][A-Za-z0-9_]*)// 68 and return('VAR',bless {attr => $1}, 'VAR'); 69 s/^(.)//s 70 and return($1, $1); 71 } 72 return('',undef); 73 }
follows the client program:
pl@nereida:~/LEyapp/examples$ cat -n uselhs.pl 1 #!/usr/bin/perl -w 2 use Lhs; 3 use Data::Dumper; 4 5 $parser = new Lhs(); 6 my $tree = $parser->Run; 7 $Data::Dumper::Indent = 1; 8 if (defined($tree)) { print Dumper($tree); } 9 else { print "Cadena no válida\n"; }
When executed with input a=(2+3)*b the parser produces the following tree:
a=(2+3)*b
ASSIGN(TIMES(PLUS(NUM[2],NUM[3]), VAR[b]))
See the result of an execution:
pl@nereida:~/LEyapp/examples$ uselhs.pl a=(2+3)*b $VAR1 = [ bless( { 'children' => [ bless( { 'attr' => 'a' }, 'VAR' ), bless( { 'children' => [ bless( { 'children' => [ bless( { 'attr' => '2' }, 'NUM' ), bless( { 'attr' => '3' }, 'NUM' ) ] }, 'PLUS' ), bless( { 'attr' => 'b' }, 'VAR' ) ] }, 'TIMES' ) ] }, 'ASSIGN' ) ];
The name of a production rule can be changed at execution time. See the following example:
29 exp: 30 NUM { $_[1] } 31 | VAR { $_[1] } 32 | %name ASSIGN 33 VAR '=' exp 34 | %name PLUS 35 exp '+' exp 36 | %name MINUS 37 exp '-' exp 38 { 39 my $self = shift; 40 $self->YYName('SUBTRACT'); # rename it 41 $self->YYBuildAST(@_); # build the node 42 } 43 | %name TIMES 44 exp '*' exp 45 | %name DIV 46 exp '/' exp 47 | %name UMINUS 48 '-' exp %prec NEG 49 | '(' exp ')' { $_[2] } 50 ;
When the client program is executed we can see the presence of the SUBTRACT nodes:
SUBTRACT
pl@nereida:~/LEyapp/examples$ useyynamedynamic.pl 2-b $VAR1 = [ bless( { 'children' => [ bless( { 'attr' => '2' }, 'NUM' ), bless( { 'attr' => 'b' }, 'VAR' ) ] }, 'SUBTRACT' ) ];
Terence Parr in his talk "Reuse of Grammars with Embedded Semantic Actions" (see http://www.cs.vu.nl/icpc2008/docs/Parr.pdf) explains the problem:
"Because many applications deal with the same language, the reuse of a common syntax specification with different semantics provides a number of advantages. While the advantages are obvious, the mechanism for grammar reuse is not so clear. To go beyond syntax checking, grammars must have some way to specify the translation or interpretation logic (the semantics). Unfortunately, the act of specifying the semantics can lock a grammar into one specific application since the grammar is often modified to suit (e.g., programmers often want to embed unrestricted semantic actions)."
The incoming sections deal with different solutions to the problem.
Default actions provide a way to write reusable grammars. Here is one solution:
pl@europa:~/LEyapp/examples/recycle$ cat -n Noactions.eyp 1 %left '+' 2 %left '*' 3 4 %defaultaction { 5 my $self = shift; 6 7 my $class = $self->YYPrefix; 8 $class .= $self->YYName; 9 10 $class->action(@_); 11 } 12 13 %% 14 exp: %name NUM 15 NUM 16 | %name PLUS 17 exp '+' exp 18 | %name TIMES 19 exp '*' exp 20 | '(' exp ')' 21 { $_[2] } 22 ; 23 24 %% 25 26 sub _Error { 27 my($token)=$_[0]->YYCurval; 28 my($what)= $token ? "input: '$token'" : "end of input"; 29 my @expected = $_[0]->YYExpect(); 30 31 local $" = ', '; 32 die "Syntax error near $what. Expected one of these tokens: @expected\n"; 33 } 34 35 36 my $x = ''; 37 38 sub _Lexer { 39 my($parser)=shift; 40 41 for ($x) { 42 s/^\s+//; 43 $_ eq '' and return('',undef); 44 45 s/^([0-9]+(?:\.[0-9]+)?)// and return('NUM',$1); 46 s/^([A-Za-z][A-Za-z0-9_]*)// and return('VAR',$1); 47 s/^(.)//s and return($1,$1); 48 } 49 } 50 51 sub Run { 52 my($self)=shift; 53 $x = shift; 54 my $debug = shift; 55 56 $self->YYParse( 57 yylex => \&_Lexer, 58 yyerror => \&_Error, 59 yydebug => $debug, 60 ); 61 }
This grammar is reused by the following program to implement a calculator: and a translator from infix to postfix:
pl@europa:~/LEyapp/examples/recycle$ cat -n calcu_and_post.pl 1 #!/usr/bin/perl 2 use warnings; 3 use Noactions; 4 5 sub Calc::NUM::action { 6 return $_[1]; 7 } 8 9 sub Calc::PLUS::action { 10 $_[1]+$_[3]; 11 } 12 13 sub Calc::TIMES::action { 14 $_[1]*$_[3]; 15 } 16 17 sub Post::NUM::action { 18 return $_[1]; 19 } 20 21 sub Post::PLUS::action { 22 "$_[1] $_[3] +"; 23 } 24 25 sub Post::TIMES::action { 26 "$_[1] $_[3] *"; 27 } 28 29 my $debug = shift || 0; 30 my $pparser = Noactions->new( yyprefix => 'Post::'); 31 print "Write an expression: "; 32 my $x = <STDIN>; 33 my $t = $pparser->Run($x, $debug); 34 35 print "$t\n"; 36 37 my $cparser = Noactions->new(yyprefix => 'Calc::'); 38 my $e = $cparser->Run($x, $debug); 39 40 print "$e\n";
An method to reuse a grammar is via inheritance. The client inherits the generated parser module and expands it with methods that inherit or overwrite the actions. Here is an example. Initially we have this Eyapp grammar:
pl@europa:~/LEyapp/examples/recycle$ cat -n NoacInh.eyp 1 %left '+' 2 %left '*' 3 4 %defaultaction { 5 my $self = shift; 6 7 my $action = $self->YYName; 8 9 $self->$action(@_); 10 } 11 12 %% 13 exp: %name NUM 14 NUM 15 | %name PLUS 16 exp '+' exp 17 | %name TIMES 18 exp '*' exp 19 | '(' exp ')' 20 { $_[2] } 21 ; 22 23 %% 24 25 sub _Error { 26 my($token)=$_[0]->YYCurval; 27 my($what)= $token ? "input: '$token'" : "end of input"; 28 my @expected = $_[0]->YYExpect(); 29 30 local $" = ', '; 31 die "Syntax error near $what. Expected one of these tokens: @expected\n"; 32 } 33 34 35 my $x = ''; 36 37 sub _Lexer { 38 my($parser)=shift; 39 40 for ($x) { 41 s/^\s+//; 42 $_ eq '' and return('',undef); 43 44 s/^([0-9]+(?:\.[0-9]+)?)// and return('NUM',$1); 45 s/^([A-Za-z][A-Za-z0-9_]*)// and return('VAR',$1); 46 s/^(.)//s and return($1,$1); 47 } 48 } 49 50 sub Run { 51 my($self)=shift; 52 $x = shift; 53 my $debug = shift; 54 55 $self->YYParse( 56 yylex => \&_Lexer, 57 yyerror => \&_Error, 58 yydebug => $debug, 59 ); 60 }
The following program defines two classes: CalcActions that implements the actions for the calculator and package PostActions that implements the actions for the infix to postfix translation. This way we have an example that reuses the former grammar twice:
CalcActions
PostActions
pl@europa:~/LEyapp/examples/recycle$ cat -n icalcu_and_ipost.pl 1 #!/usr/bin/perl -w 2 package CalcActions; 3 use strict; 4 use base qw{NoacInh}; 5 6 sub NUM { 7 return $_[1]; 8 } 9 10 sub PLUS { 11 $_[1]+$_[3]; 12 } 13 14 sub TIMES { 15 $_[1]*$_[3]; 16 } 17 18 package PostActions; 19 use strict; 20 use base qw{NoacInh}; 21 22 sub NUM { 23 return $_[1]; 24 } 25 26 sub PLUS { 27 "$_[1] $_[3] +"; 28 } 29 30 sub TIMES { 31 "$_[1] $_[3] *"; 32 } 33 34 package main; 35 use strict; 36 37 my $calcparser = CalcActions->new(); 38 print "Write an expression: "; 39 my $x = <STDIN>; 40 my $e = $calcparser->Run($x); 41 42 print "$e\n"; 43 44 my $postparser = PostActions->new(); 45 my $p = $postparser->Run($x); 46 47 print "$p\n";
The subroutine used as default action in NoacInh.eyp is so useful that is packed as the Parse::Eyapp::Driver method YYDelegateaction.
NoacInh.eyp
YYDelegateaction
See files examples/recycle/NoacYYDelegateaction.eyp and examples/recycle/icalcu_and_ipost_yydel.pl for an example of use of YYDelegateaction.
examples/recycle/NoacYYDelegateaction.eyp
examples/recycle/icalcu_and_ipost_yydel.pl
The methods YYSetaction and YYAction of the parser object provide a way to selectively substitute some actions of a given grammar. Let us consider once more a postfix to infix translator:
YYSetaction
YYAction
pl@europa:~/LEyapp/examples/recycle$ cat -n PostfixWithActions.eyp 1 # File PostfixWithActions.eyp 2 %right '=' 3 %left '-' '+' 4 %left '*' '/' 5 %left NEG 6 7 %% 8 line: $exp { print "$exp\n" } 9 ; 10 11 exp: $NUM 12 { $NUM } 13 | $VAR 14 { $VAR } 15 | %name ASSIGN 16 VAR.left '='exp.right 17 { "$_[3] &$_[1] ASSIGN"; } 18 | %name PLUS 19 exp.left '+'exp.right 20 { "$_[1] $_[3] PLUS"; } 21 | %name MINUS 22 exp.left '-'exp.right 23 { "$_[1] $_[3] MINUS"; } 24 | %name TIMES 25 exp.left '*'exp.right 26 { "$_[1] $_[3] TIMES"; } 27 | %name DIV 28 exp.left '/'exp.right 29 { "$_[1] $_[3] DIV"; } 30 | %name NEG '-' $exp %prec NEG 31 { "$exp NEG" } 32 | '(' $exp ')' 33 { $exp } 34 ; 35 36 %% 37 38 sub _Error { 39 my($token)=$_[0]->YYCurval; 40 my($what)= $token ? "input: '$token'" : "end of input"; 41 my @expected = $_[0]->YYExpect(); 42 43 local $" = ', '; 44 die "Syntax error near $what. Expected one of these tokens: @expected\n"; 45 } 46 47 my $x; 48 49 sub _Lexer { 50 my($parser)=shift; 51 52 for ($x) { 53 s/^\s+//; 54 $_ eq '' and return('',undef); 55 56 s/^([0-9]+(?:\.[0-9]+)?)// and return('NUM',$1); 57 s/^([A-Za-z][A-Za-z0-9_]*)// and return('VAR',$1); 58 s/^(.)//s and return($1,$1); 59 } 60 } 61 62 sub Run { 63 my($self)=shift; 64 $x = shift; 65 $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error, 66 #yydebug => 0xFF 67 ); 68 }
The program rewritepostfixwithactions.pl uses the former grammar to translate infix expressions to postfix expressions. It also implements a calculator reusing the grammar in PostfixWithActions.eyp. It does so using the YYSetaction method. The semantic actions for the productions named
rewritepostfixwithactions.pl
PostfixWithActions.eyp
PLUS
TIMES
DIV
NEG
are selectively substituted by the appropriate actions, while the other semantic actions remain unchanged:
pl@europa:~/LEyapp/examples/recycle$ cat -n rewritepostfixwithactions.pl 1 #!/usr/bin/perl 2 use warnings; 3 use PostfixWithActions; 4 5 my $debug = shift || 0; 6 my $pparser = PostfixWithActions->new(); 7 print "Write an expression: "; 8 my $x = <STDIN>; 9 10 # First, trasnlate to postfix ... 11 $pparser->Run($x, $debug); 12 13 # And then selectively substitute 14 # some semantic actions 15 # to obtain an infix calculator ... 16 my %s; # symbol table 17 $pparser->YYSetaction( 18 ASSIGN => sub { $s{$_[1]} = $_[3] }, 19 PLUS => sub { $_[1] + $_[3] }, 20 TIMES => sub { $_[1] * $_[3] }, 21 DIV => sub { $_[1] / $_[3] }, 22 NEG => sub { -$_[2] }, 23 ); 24 25 $pparser->Run($x, $debug);
When running this program the output is:
examples/recycle$ ./rewritepostfixwithactions.pl Write an expression: 2*3+4 2 3 TIMES 4 PLUS 10 examples/recycle$ rewritepostfixwithactions.pl Write an expression: a = 2*(b = 3+5) 2 3 5 PLUS &b ASSIGN TIMES &a ASSIGN 16
The project home is at http://code.google.com/p/parse-eyapp/. Use a subversion client to anonymously check out the latest project source code:
svn checkout http://parse-eyapp.googlecode.com/svn/trunk/ parse-eyapp-read-only
The tutorial Parsing Strings and Trees with Parse::Eyapp (An Introduction to Compiler Construction in seven pages) in http://nereida.deioc.ull.es/~pl/eyapsimple/
Parse::Eyapp, Parse::Eyapp::eyapplanguageref, Parse::Eyapp::debuggingtut, Parse::Eyapp::defaultactionsintro, Parse::Eyapp::translationschemestut, Parse::Eyapp::Driver, Parse::Eyapp::Node, Parse::Eyapp::YATW, Parse::Eyapp::Treeregexp, Parse::Eyapp::Scope, Parse::Eyapp::Base, Parse::Eyapp::datagenerationtut
The pdf file in http://nereida.deioc.ull.es/~pl/perlexamples/languageintro.pdf
The pdf file in http://nereida.deioc.ull.es/~pl/perlexamples/debuggingtut.pdf
The pdf file in http://nereida.deioc.ull.es/~pl/perlexamples/eyapplanguageref.pdf
The pdf file in http://nereida.deioc.ull.es/~pl/perlexamples/Treeregexp.pdf
The pdf file in http://nereida.deioc.ull.es/~pl/perlexamples/Node.pdf
The pdf file in http://nereida.deioc.ull.es/~pl/perlexamples/YATW.pdf
The pdf file in http://nereida.deioc.ull.es/~pl/perlexamples/Eyapp.pdf
The pdf file in http://nereida.deioc.ull.es/~pl/perlexamples/Base.pdf
The pdf file in http://nereida.deioc.ull.es/~pl/perlexamples/translationschemestut.pdf
The pdf file in http://nereida.deioc.ull.es/~pl/perlexamples/treematchingtut.pdf
perldoc eyapp,
perldoc treereg,
perldoc vgg,
The Syntax Highlight file for vim at http://www.vim.org/scripts/script.php?script_id=2453 and http://nereida.deioc.ull.es/~vim/
Analisis Lexico y Sintactico, (Notes for a course in compiler construction) by Casiano Rodriguez-Leon. Available at http://nereida.deioc.ull.es/~pl/perlexamples/ Is the more complete and reliable source for Parse::Eyapp. However is in Spanish.
Parse::Yapp,
Man pages of yacc(1) and bison(1), http://www.delorie.com/gnu/docs/bison/bison.html
Language::AttributeGrammar
Parse::RecDescent.
HOP::Parser
HOP::Lexer
ocamlyacc tutorial at http://plus.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-tutorial/ocamlyacc-tutorial.html
The classic Dragon's book Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman (Addison-Wesley 1986)
CS2121: The Implementation and Power of Programming Languages (See http://www.cs.man.ac.uk/~pjj, http://www.cs.man.ac.uk/~pjj/complang/g2lr.html and http://www.cs.man.ac.uk/~pjj/cs2121/ho/ho.html) by Pete Jinks
Hal Finkel http://www.halssoftware.com/
G. Williams http://kasei.us/
Thomas L. Shinnick http://search.cpan.org/~tshinnic/
Frank Leray
Casiano Rodriguez-Leon (casiano@ull.es)
This work has been supported by CEE (FEDER) and the Spanish Ministry of Educacion y Ciencia through Plan Nacional I+D+I number TIN2005-08818-C04-04 (ULL::OPLINK project http://www.oplink.ull.es/). Support from Gobierno de Canarias was through GC02210601 (Grupos Consolidados). The University of La Laguna has also supported my work in many ways and for many years.
A large percentage of code is verbatim taken from Parse::Yapp 1.05. The author of Parse::Yapp is Francois Desarmenien.
I wish to thank Francois Desarmenien for his Parse::Yapp module, to my students at La Laguna and to the Perl Community. Thanks to the people who have contributed to improve the module (see "CONTRIBUTORS" in Parse::Eyapp). Thanks to Larry Wall for giving us Perl. Special thanks to Juana.
Copyright (c) 2006-2008 Casiano Rodriguez-Leon (casiano@ull.es). All rights reserved.
Parse::Yapp copyright is of Francois Desarmenien, all rights reserved. 1998-2001
These modules are free software; you can redistribute it and/or modify it under the same terms as Perl itself. See perlartistic.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
1 POD Error
The following errors were encountered while parsing the POD:
Non-ASCII character seen before =encoding in 'válida\n";'. Assuming UTF-8
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.