Parse::Eyapp::translatUsercContributed PParse::Eyapp::translationschemestut(3)NAMEParse::Eyapp::translationschemestut - Introduction to Translation
Schemes in Eyapp
INTRODUCTION
A translation scheme scheme is a context free grammar where the right
hand sides of the productions have been augmented with semantic actions
(i.e. with chunks of Perl code):
A -> alpha { action(@_) } beta
The analyzer generated by "Parse::Eyapp" executes "action()" after all
the semantic actions associated with "alpha" have been executed and
before the execution of any of the semantic actions associated with
"beta".
In a translation scheme the embedded actions modify the attributes
associated with the symbols of the grammar.
A -> alpha { action(@_) } beta
each symbol on the right hand side of a production rule has an
associated scalar attribute. In ordinary "eyapp" programs the
attributes of the symbol to the left of "action" are passed as
arguments to "action" (in the example, those of "alpha"). These
arguments are preceded by a reference to the syntax analyzer object.
There is no way inside an ordinary "eyapp" program for an intermediate
"action" to access the attributes of the symbols on its right, i.e.
those associated with the symbols of "beta". This restriction is lifted
if you use the %metatree directive.
Eyapp allows through the %metatree directive the creation of
Translation Schemes where the actions have access to almost any node of
the syntax tree.
When using the %metatree directive semantic actions aren't immediately
executed. Instead they are inserted as nodes of the syntax tree. The
main difference with ordinary nodes being that the attribute of such a
"CODE" node is a reference to the anonymous subroutine representing the
semantic action. The tree is later traversed in depth-first order
using the "$t->translation_scheme" method: each time a "CODE" node is
visited the action is executed.
The following example parses a tiny subset of a typical typed language
and decorates the syntax tree with a new attribute "t" holding the type
of each declared variable:
use strict; # File examples/trans_scheme_simple_decls4.pl
use Data::Dumper;
use Parse::Eyapp;
our %s; # symbol table
my $ts = q{
%token FLOAT INTEGER NAME
%{
our %s;
%}
%metatree
%%
Dl: D <* ';'>
;
D : $T { $L->{t} = $T->{t} } $L
;
T : FLOAT { $lhs->{t} = "FLOAT" }
| INTEGER { $lhs->{t} = "INTEGER" }
;
L : $NAME
{ $NAME->{t} = $lhs->{t}; $s{$NAME->{attr}} = $NAME }
| $NAME { $NAME->{t} = $lhs->{t}; $L->{t} = $lhs->{t} } ',' $L
{ $s{$NAME->{attr}} = $NAME }
;
%%
}; # end $ts
sub Error { die "Error sintA~Xctico\n"; }
{ # Closure of $input, %reserved_words and $validchars
my $input = "";
my %reserved_words = ();
my $validchars = "";
sub parametrize__scanner {
$input = shift;
%reserved_words = %{shift()};
$validchars = shift;
}
sub scanner {
$input =~ m{\G\s+}gc; # skip whites
if ($input =~ m{\G([a-z_A_Z]\w*)\b}gc) {
my $w = uc($1); # upper case the word
return ($w, $w) if exists $reserved_words{$w};
return ('NAME', $1); # not a reserved word
}
return ($1, $1) if ($input =~ m/\G([$validchars])/gc);
die "Not valid token: $1\n" if ($input =~ m/\G(\S)/gc);
return ('', undef); # end of file
}
} # end closure
Parse::Eyapp->new_grammar(input=>$ts,classname=>'main',outputfile=>'Types.pm');
my $parser = main->new(yylex => \&scanner, yyerror => \&Error);
parametrize__scanner(
"float x,y;\ninteger a,b\n",
{ INTEGER => 'INTEGER', FLOAT => 'FLOAT'},
",;"
);
my $t = $parser->YYParse() or die "Syntax Error analyzing input";
$t->translation_scheme;
$Data::Dumper::Indent = 1;
$Data::Dumper::Terse = 1;
$Data::Dumper::Deepcopy = 1;
$Data::Dumper::Deparse = 1;
print Dumper($t);
print Dumper(\%s);
Inside a Translation Scheme the lexical variable $lhs refers to the
attribute of the father.
EXECUTION STAGES OF A TRANSLATION SCHEME
The execution of a Translation Scheme can be divided in the following
stages:
1. During the first stage the grammar is analyzed and the parser is
built:
Parse::Eyapp->new_grammar(input=>$ts,classname=>'main',outputfile=>'Types.pm');
This stage is called Class Construction Time
2. A parser conforming to the generated grammar is built
my $parser = main->new(yylex => \&scanner, yyerror => \&Error);
This stage is called Parser Construction Time
3. The next phase is Tree construction time. The input is set and the
tree is built:
parametrize__scanner(
"float x,y;\ninteger a,b\n",
{ INTEGER => 'INTEGER', FLOAT => 'FLOAT'},
",;"
);
my $t = $parser->YYParse() or die "Syntax Error analyzing input";
4. The last stage is Execution Time. The tree is traversed in depth
first order and the "CODE" nodes are executed.
$t->translation_scheme;
This combination of bottom-up parsing with depth first traversing leads
to a semantic behavior similar to recursive top-down parsers but with
two advantages:
· The grammar can be left-recursive
· At the time of executing the action the syntax tree is already
built, therefore we can refer to nodes on the right side of the
action like in:
D : $T { $L->{t} = $T->{t} } $L
THE %begin DIRECTIVE
The "%begin { code }" directive can be used when building a
translation scheme, i.e. when under the control of the %metatree
directive. It indicates that such "{ code }" will be executed at tree
construction time. Therefore the code receives as arguments the
references to the nodes of the branch than is being built. Usually
begin code assist in the construction of the tree. Line 39 of the
following code shows an example. The action "{ $exp }" simplifies the
syntax tree bypassing the parenthesis node. The example also
illustrates the combined use of default actions and translation
schemes.
pl@nereida:~/LEyapp/examples$ cat -n trans_scheme_default_action.pl
1 #!/usr/bin/perl -w
2 use strict;
3 use Data::Dumper;
4 use Parse::Eyapp;
5 use IO::Interactive qw(is_interactive);
6
7 my $translationscheme = q{
8 %{
9 # head code is available at tree construction time
10 use Data::Dumper;
11 our %sym; # symbol table
12 %}
13
14 %defaultaction {
15 $lhs->{n} = eval " $left->{n} $_[2]->{attr} $right->{n} "
16 }
17
18 %metatree
19
20 %right '='
21 %left '-' '+'
22 %left '*' '/'
23
24 %%
25 line: %name EXP
26 exp <+ ';'> /* Expressions separated by semicolons */
27 { $lhs->{n} = $_[1]->Last_child->{n} }
28 ;
29
30 exp:
31 %name PLUS
32 exp.left '+' exp.right
33 | %name MINUS
34 exp.left '-' exp.right
35 | %name TIMES
36 exp.left '*' exp.right
37 | %name DIV
38 exp.left '/' exp.right
39 | %name NUM
40 $NUM
41 { $lhs->{n} = $NUM->{attr} }
42 | '(' $exp ')' %begin { $exp }
43 | %name VAR
44 $VAR
45 { $lhs->{n} = $sym{$VAR->{attr}}->{n} }
46 | %name ASSIGN
47 $VAR '=' $exp
48 { $lhs->{n} = $sym{$VAR->{attr}}->{n} = $exp->{n} }
49
50 ;
51
52 %%
53 # tail code is available at tree construction time
54 sub _Error {
55 die "Syntax error.\n";
56 }
57
58 sub _Lexer {
59 my($parser)=shift;
60
61 for ($parser->YYData->{INPUT}) {
62 s/^\s+//;
63 $_ or return('',undef);
64 s/^([0-9]+(?:\.[0-9]+)?)// and return('NUM',$1);
65 s/^([A-Za-z][A-Za-z0-9_]*)// and return('VAR',$1);
66 s/^(.)// and return($1,$1);
67 }
68 return('',undef);
69 }
70
71 sub Run {
72 my($self)=shift;
73 return $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error );
74 }
75 }; # end translation scheme
76
77 sub TERMINAL::info { $_[0]->attr }
78
79 my $p = Parse::Eyapp->new_grammar(
80 input=>$translationscheme,
81 classname=>'main',
82 firstline => 6,
83 outputfile => 'main.pm');
84 die $p->qtables() if $p->Warnings;
85 my $parser = main->new();
86 print "Write a sequence of arithmetic expressions: " if is_interactive();
87 $parser->YYData->{INPUT} = <>;
88 my $t = $parser->Run() or die "Syntax Error analyzing input";
89 $t->translation_scheme;
90
91 $Parse::Eyapp::Node::INDENT = 2;
92 my $treestring = $t->str;
93
94 $Data::Dumper::Indent = 1;
95 $Data::Dumper::Terse = 1;
96 $Data::Dumper::Deepcopy = 1;
97 our %sym;
98 my $symboltable = Dumper(\%sym);
99
100 print <<"EOR";
101 ***********Tree*************
102 $treestring
103 ******Symbol table**********
104 $symboltable
105 ************Result**********
106 $t->{n}
107
108 EOR
When executed with input "a=2*3;b=a*a" the program produces an output
similar to this:
pl@nereida:~/LEyapp/examples$ trans_scheme_default_action.pl
Write a sequence of arithmetic expressions: a=2*3;b=a*a
***********Tree*************
EXP(
_PLUS_LIST(
ASSIGN(
TERMINAL[a],
TERMINAL[=],
TIMES(
NUM(TERMINAL[2], CODE),
TERMINAL[*],
NUM(TERMINAL[3], CODE),
CODE
) # TIMES,
CODE
) # ASSIGN,
ASSIGN(
TERMINAL[b],
TERMINAL[=],
TIMES(
VAR(TERMINAL[a], CODE),
TERMINAL[*],
VAR(TERMINAL[a], CODE),
CODE
) # TIMES,
CODE
) # ASSIGN
) # _PLUS_LIST,
CODE
) # EXP
******Symbol table**********
{
'a' => {
'n' => 6
},
'b' => {
'n' => 36
}
}
************Result**********
36
SEE ALSO
· The project home is at http://code.google.com/p/parse-eyapp/
<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
<http://plus.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-
tutorial/ocamlyacc-tutorial.html>
REFERENCES
· 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
CONTRIBUTORS
· Hal Finkel <http://www.halssoftware.com/>
· G. Williams <http://kasei.us/>
· Thomas L. Shinnick <http://search.cpan.org/~tshinnic/>
· Frank Leray
AUTHOR
Casiano Rodriguez-Leon (casiano@ull.es)
ACKNOWLEDGMENTS
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.
LICENCE AND COPYRIGHT
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.
perl v5.16.22012-0Parse::Eyapp::translationschemestut(3)
