=head1 NAME
Parse::Eyapp::languageintro - Introduction to the Eyapp language
=head1 The Eyapp Language
=head2 Eyapp Grammar
This section describes the syntax of the Eyapp language using its own notation.
The grammar extends L<yacc> and L<yapp> grammars.
Semicolons have been omitted to save space.
Between C-like comments you can find an (informal)
explanation of the language
associated with the token.
eyapp: head body tail ;
symbol: LITERAL /* A string literal like 'hello' */
| ident
ident: IDENT /* IDENT is [A-Za-z_][A-Za-z0-9_]* */
head: headsec '%%'
headsec: decl *
decl: '\n'
| SEMANTIC typedecl symlist '\n' /* SEMANTIC is %semantic\s+token */
| SYNTACTIC typedecl symlist '\n' /* SYNTACTIC is %syntactic\s+token */
| TOKEN typedecl symlist '\n' /* TOKEN is %token */
| ASSOC typedecl symlist '\n' /* ASSOC is %(left|right|nonassoc) */
| START ident '\n' /* START is %start */
| HEADCODE '\n' /* HEADCODE is %{ Perl code ... %} */
| UNION CODE '\n' /* UNION CODE see yacc/bison */
| DEFAULTACTION CODE '\n' /* DEFAULTACTION is %defaultaction */
| TREE treeclauses? '\n' /* TREE is %tree */
| METATREE '\n' /* METATREE is %metatree */
| TYPE typedecl identlist '\n' /* TYPE is %type */
| EXPECT NUMBER '\n' /* EXPECT is %expect */
/* NUMBER is \d+ */
typedecl: /* empty */
| '<' IDENT '>'
treeclauses: BYPASS ALIAS? | ALIAS BYPASS?
symlist: symbol +
identlist: ident +
body: rules * '%%'
rules: IDENT ':' rhss ';'
rhss: rule <+ '|'>
rule: optname rhs (prec epscode)?
rhs: rhseltwithid *
rhseltwithid :
rhselt '.' IDENT
| '$' rhselt
| rhselt
rhselt: symbol
| code
| '(' optname rhs ')'
| rhselt STAR /* STAR is (%name\s*([A-Za-z_]\w*)\s*)?\* */
| rhselt '<' STAR symbol '>'
| rhselt OPTION /* OPTION is (%name\s*([A-Za-z_]\w*)\s*)?\? */
| rhselt '<' PLUS symbol '>'
| rhselt PLUS /* PLUS is (%name\s*([A-Za-z_]\w*)\s*)?\+ */
optname: (NAME IDENT)? /* NAME is %name */
| NOBYPASS IDENT /* NOBYPASS is %no\s+bypass */
prec: PREC symbol /* PREC is %prec */
epscode: code ?
code:
CODE /* CODE is { Perl code ... } */
| BEGINCODE /* BEGINCODE is %begin { Perl code ... } */
tail: TAILCODE ? /* TAILCODE is { Perl code ... } */
The semantic of C<Eyapp> agrees with the semantic of C<yacc> and C<yapp>
for all the common constructions.
=head2 Comments
Comments are either Perl style, from C<#>
up to the end of line, or C style, enclosed between C</*> and C<*/>.
=head2 Syntactic Variables, Symbolic Tokens and String Literals
Two kind of symbols may appear inside a Parse::Eyapp program:
I<Non-terminal> symbols or I<syntactic variables>,
called also I<left-hand-side> symbols
and I<Terminal> symbols, called
also I<Tokens>.
Tokens are the symbols the lexical analyzer function returns to the parser.
There are two kinds: I<symbolic tokens> and I<string
literals>.
I<Syntactic variables> and I<symbolic tokens> identifiers must conform
to the regular expression C<[A-Za-z][A-Za-z0-9_]*>.
When building the syntax tree (i.e. when running under the C<%tree>
directive) I<symbolic tokens> will be considered I<semantic tokens> (see section
L</Syntactic and Semantic tokens>).
String literals are enclosed in single quotes and can contain almost
anything. They will be received by the parser as double-quoted strings.
Any special character as C<'"'>, C<'$'> and C<'@'> is escaped.
To have a single quote inside a literal, escape it with '\'.
When building the syntax tree (i.e. when running under the C<%tree>
directive) I<string literals> will be considered I<syntactic tokens> (see section
L</Syntactic and Semantic tokens>).
=head2 Parts of an C<eyapp> Program
An Eyapp program has three parts called head, body and tail:
eyapp: head body tail ;
Each part is separated from the former by the symbol C<%%>:
head: headsec '%%'
body: rulesec '%%'
=head2 The Head Section
The head section contains a list of declarations
headsec: decl *
There are different kinds of declarations.
This reference does not
fully describes all the declarations that are shared with L<yacc> and
L<yapp>.
=head3 Example of Head Section
In this and the next sections we will describe the basics
of the Eyapp language using the file C<examples/Calc.eyp>
that accompanies this distribution. This file implements a trivial
calculator. Here is the header section:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ sed -ne '1,11p' Calc.eyp | cat -n
1 # examples/Calc.eyp
2 %right '='
3 %left '-' '+'
4 %left '*' '/'
5 %left NEG
6 %right '^'
7 %{
8 my %s; # symbol table
9 %}
10
11 %%
=head3 Declarations and Precedence
Lines 2-5 declare several tokens. The usual way to declare
tokens is through the C<%token> directive. The declarations
C<%nonassoc>, C<%left> and C<%right>
not only declare the tokens but also associate a I<priority> with them.
Tokens declared in the same line have the same precedence.
Tokens declared with these directives in lines below have more
precedence than those declared above. Thus, in the example
above
we are saying that C<"+"> and C<"-"> have the same precedence
but higher precedence than =. The final effect of C<"-">
having greater precedence than = will be that an
expression like:
a = 4 - 5
will be interpreted as
a = (4 - 5)
and not as
(a = 4) - 5
The use of the C<%left> indicates that - in case of ambiguity
and a match between precedences - the parser must build the tree corresponding
to a left parenthesization. Thus, the expression
4 - 5 - 9
will be interpreted as
(4 - 5) - 9
=head3 Header Code
Perl code surrounded by C<%{> and C<%}>
can be inserted in the head section. Such code will be inserted in the module
generated by C<eyapp> near the beginning. Therefore, declarations like the
one of the calculator symbol table C<%s>
7 %{
8 my %s; # symbol table
9 %}
will be visible from almost any point in the file.
=head3 The Start Symbol of the Grammar
C<%start IDENT> declares C<IDENT> as the start symbol of
the grammar. When C<%start> is not
used, the first rule in the body section will be used.
=head3 Expect
The C<%expect #NUMBER> directive works as in L<bison>
and suppress warnings when the number of Shift/Reduce
conflicts is exactly C<#NUMBER>. See section
L</Solving Ambiguities and Conflicts> to know more
about Shift/Reduce conflicts.
=head3 Type and Union
C oriented declarations like C<%type> and C<%union> are
parsed but ignored.
=head3 The C<%strict> Directive
By default, identifiers appearing in the rule section
will be classified as terminal if they don't appear
in the left hand side of any production rules.
The directive C<%strict> forces the declaration of all tokens.
The following C<eyapp> program issues a warning:
pl@nereida:~/LEyapp/examples$ cat -n bugyapp2.eyp
1 %strict
2 %%
3 expr: NUM;
4 %%
pl@nereida:~/LEyapp/examples$ eyapp bugyapp2.eyp
Warning! Non declared token NUM at line 3 of bugyapp2.eyp
To keep silent the compiler declare all tokens using
one of the token declaration directives (C<%token>, C<%left>, etc.)
pl@nereida:~/LEyapp/examples$ cat -n bugyapp3.eyp
1 %strict
2 %token NUM
3 %%
4 expr: NUM;
5 %%
pl@nereida:~/LEyapp/examples$ eyapp bugyapp3.eyp
pl@nereida:~/LEyapp/examples$
It is a good practice to use C<%strict> at the beginning of your grammar.
=head3 Default Action Directive
In C<Parse::Eyapp> you can modify the default action using the C<%defaultaction { Perl code }>
directive. See section
L<Default actions>.
=head3 Tree Construction Directives
C<Parse::Eyapp> facilitates the construction of concrete syntax trees and
abstract syntax trees (abbreviated AST from now on) through the C<%tree>
C<%metatree> directives. See section
L<Abstract Syntax Trees : %tree and %name>
and L<Parse::Eyapp::translationschemestut>.
=head3 Syntactic and Semantic Tokens
The new token declaration directives C<%syntactic token> and
C<%semantic token> can change the way C<eyapp> builds the abstract syntax tree.
See section L<Syntactic and Semantic tokens>.
=head2 The Body
The body section contains the rules describing the grammar:
body: rules * '%%'
rules: IDENT ':' rhss ';'
rhss: (optname rhs (prec epscode)?) <+ '|'>
=head3 Rules
A rule is made of a left-hand-side symbol (the I<syntactic variable>),
followed by a C<':'> and one
or more I<right-hand-sides> (or I<productions>)
separated by C<'|'> and terminated by a C<';'>
like in:
exp:
exp '+' exp
| exp '-' exp
| NUM
;
A I<production> (I<right hand side>) may be empty:
input:
/* empty */
| input line
;
The former two productions can be abbreviated as
input:
line *
;
The operators C<*>, C<+> and C<?> are presented in section
L</Lists and Optionals>.
A I<syntactic variable cannot appear more than once as
a rule name> (This differs from L<yacc>).
=head3 Semantic Values and Semantic Actions
In C<Parse::Eyapp>
a production rule
A -> X_1 X_2 ... X_n
can be followed by a
I<semantic action>:
A -> X_1 X_2 ... X_n { Perl Code }
Such
semantic action is nothing but Perl code that will be treated
as an anonymous subroutine. The semantic action associated
with production rule C<A -E<gt> X_1 X_2 ... X_n> is executed
after any actions associated with the subtrees of C<X_1>,
C<X_2>, ..., C<X_n>.
C<Eyapp> parsers build the syntax tree using a left-right
bottom-up traverse of the syntax tree. Each times
the Parser visits the node associated with the
production C<A -E<gt> X_1 X_2 ... X_n>
the associated semantic action is called.
Asociated with each symbol
of a Parse::Eyapp grammar there is a scalar I<Semantic Value>
or I<Attribute>. The semantic values of terminals are provided
by the lexical analyzer. In the calculator example
(see file C<examples/Calc.yp> in the distribution),
the semantic value associated with an expression
is its numeric value. Thus in the rule:
exp '+' exp { $_[1] + $_[3] }
C<$_[1]> refers to the attribute of the first C<exp>, C<$_[2]>
is the attribute associated with C<'+'>, which is the second component of the
pair provided by the lexical analyzer and C<$_[3]> refers to the attribute of
the second C<exp>.
When the semantic action/anonymous subroutine is called,
the arguments are as follows:
=over
=item *
C<$_[1]> to C<$_[n]> are the attributes of
the symbols C<X_1>, C<X_2>, ..., C<X_n>.
Just as C<$1> to C<$n> in L<yacc>,
=item *
C<$_[0]> is the parser object itself.
Having C<$_[0]> beeing the parser object itself allows you to call
parser methods. Most L<yacc> macros have been converted into
parser methods. See section 'Methods Available in the Generated Class'
in L<Parse::Eyapp>.
=back
The returned value will be the attribute associated
with the left hand side of the production.
Names can be given to the attributes using the dot notation
(see file C<examples/CalcSimple.eyp>):
exp.left '+' exp.right { $left + $right }
See section L<Names for attributes> for more details about the I<dot> and I<dollar>
notations.
If no action is specified and no C<%defaultaction> is specified
the default action
{ $_[1] }
will be executed instead. See section L</Default actions> to know more.
=head3 Actions in Mid-Rule
Actions can be inserted in the middle of a production like in:
block: '{'.bracket { $ids->begin_scope(); } declaration*.decs statement*.sts '}' { ... }
A middle production action is managed by inserting a new rule in the grammar and associating
the semantic action with it:
Temp: /* empty */ { $ids->begin_scope(); }
Middle production actions can refer to the attributes on its left. They count
as one of the components of the production. Thus the program:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ sed -ne '1,4p' intermediateaction2.yp
%%
S: 'a' { $_[1]x4 }.mid 'a' { print "$_[2], $mid, $_[3]\n"; }
;
%%
The auxiliar syntactic variables are named C<@#position-#order> where C<#position>
is the position of the action in the rhs and C<order> is an ordinal number. See
the C<.output> file for the former example:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ eyapp -v intermediateaction2.yp
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ sed -ne '1,5p' intermediateaction2.output
Rules:
------
0: $start -> S $end
1: S -> 'a' @1-1 'a'
2: @1-1 -> /* empty */
when given input C<aa> the execution will produce as output C<aaaa, aaaa, a>.
=head3 Example of Body Section
Following with the calculator example, the body is:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ sed -ne '12,48p' Calc.eyp | cat -n
1 start:
2 input { \%s }
3 ;
4
5 input: line *
6 ;
7
8 line:
9 '\n' { undef }
10 | exp '\n' { print "$_[1]\n" if defined($_[1]); $_[1] }
11 | error '\n'
12 {
13 $_[0]->YYErrok;
14 undef
15 }
16 ;
17
18 exp:
19 NUM
20 | $VAR { $s{$VAR} }
21 | $VAR '=' $exp { $s{$VAR} = $exp }
22 | exp.left '+' exp.right { $left + $right }
23 | exp.left '-' exp.right { $left - $right }
24 | exp.left '*' exp.right { $left * $right }
25 | exp.left '/' exp.right
26 {
27 $_[3] and return($_[1] / $_[3]);
28 $_[0]->YYData->{ERRMSG} = "Illegal division by zero.\n";
29 $_[0]->YYError; # Pretend that a syntactic error ocurred: _Error will be called
30 undef
31 }
32 | '-' $exp %prec NEG { -$exp }
33 | exp.left '^' exp.right { $left ** $right }
34 | '(' $exp ')' { $exp }
35 ;
36
37 %%
This example does not uses any of the Eyapp extensions (with the exception of the
I<star list> at line 5) and the dot and dollar notations.
Please, see the L<Parse::Yapp> pages and elsewhere documentation
on L<yacc> and L<bison> for more information.
=head3 Solving Ambiguities and Conflicts
When Eyapp analizes a grammar like:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ cat -n ambiguities.eyp
1 %%
2 exp:
3 NUM
4 | exp '-' exp
5 ;
6 %%
it will produce a warning announcing the existence of
I<shift-reduce> conflicts:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ eyapp ambiguities.eyp
1 shift/reduce conflict (see .output file)
State 5: reduce by rule 2: exp -> exp '-' exp (default action)
State 5: shifts:
to state 3 with '-'
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ ls -ltr | tail -1
-rw-rw---- 1 pl users 1082 2007-02-06 08:26 ambiguities.output
when C<eyapp> finds warnings automatically produces a C<.output> file
describing the conflict.
What the warning is saying is that an expression like C<exp '-' exp> (rule 2) followed by a
minus C<'-'> can be worked in more than one way. If we
have an input like C<NUM - NUM - NUM> the activity of a LALR(1) parser
(the family of parsers to which Eyapp belongs)
consists of a sequence of I<shift and reduce actions>. A I<shift action>
has as consequence the reading of the next token. A I<reduce action>
is finding a production rule that matches and substituting
the rhs of the production by the lhs. For input C<NUM - NUM - NUM>
the activity will be as follows (the dot is used to indicate where the next
input token is):
.NUM - NUM - NUM # shift
NUM.- NUM - NUM # reduce exp: NUM
exp.- NUM - NUM # shift
exp -.NUM - NUM # shift
exp - NUM.- NUM # reduce exp: NUM
exp - exp.- NUM # shift/reduce conflict
up this point two different decisions can be taken: the next description can be
exp.- NUM # reduce by exp: exp '-' exp (rule 2)
or:
exp - exp -.NUM # shift '-' (to state 3)
that is why it is called a I<shift-reduce conflict>.
That is also the reason for the precedence declarations in the
head section. Another kind of conflicts are I<reduce-reduce conflicts>.
They arise when more that rhs can be applied for a reduction
action.
Eyapp solves the conflicts applying the following rules:
=over
=item * In a shift/reduce conflict, the default is the shift.
=item * In a reduce/reduce conflict, the default is to reduce by the
earlier grammar production (in the input sequence).
=item * The precedences and associativities are associated with tokens in
the declarations section. This is made by a sequence of lines beginning
with one of the directives: C<%left>, C<%right>, or C<%nonassoc>,
followed by a list of
tokens. All the tokens on the same line
have the same precedence and associativity;
the lines are listed in order of increasing precedence.
=item * A precedence and associativity is associated with each grammar
production; it is the precedence and associativity of the I<last token>
or I<literal> in the right hand side of the production.
=item * The C<%prec> directive can be used when
a rhs is involved in a conflict and has no tokens
inside or it has but the precedence of the last token leads
to an incorrect interpretation. A rhs can be followed by
an optional C<%prec token> directive
giving the production the precedence of the C<token>
exp: '-' exp %prec NEG { -$_[1] }
=item * If there is a shift/reduce conflict, and both the grammar production
and the input character have precedence and associativity associated
with them, then the conflict is solved in favor of the action (shift or
reduce) associated with the higher precedence. If the precedences are the
same, then the associativity is used; left associative implies reduce,
right associative implies shift, and nonassociating implies error.
=back
To solve a shift-reduce conflict between a production C<A --E<gt> SOMETHING>
and a token C<'a'> you can follow this procedure:
=over
=item 1. Edit the C<.output> file
=item 2. Search for the state where the conflict between the production and the token
is. In our example it looks like:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ sed -ne '56,65p' ambiguities.output
State 5:
exp -> exp . '-' exp (Rule 2)
exp -> exp '-' exp . (Rule 2)
'-' shift, and go to state 3
'-' [reduce using rule 2 (exp)]
$default reduce using rule 2 (exp)
=item 3. Inside the state there has to be a production of the type C<A --E<gt> SOMETHING.>
(with the dot at the end)
indicating that a reduction must take place. There has to be also another production
of the form C<A --E<gt> prefix . suffix>, where suffix can I<start> with the involved
token C<'a'>.
=item 4. Decide what action shift or reduce matches the kind of trees you want.
In this example we want C<NUM - NUM - NUM> to produce a tree like
C<MINUS(MINUS(NUM, NUM), NUM)> and not C<MINUS(NUM, MINUS(NUM, NUM))>. We want the
conflict in C<exp - exp.- NUM> to be solved in favor of the reduction
by C<exp: exp '-' exp>.
This is achieved by declaring C<%left '-'>.
=back
=head3 Error Recovery
The token name C<error> is reserved for error handling. This name can
be used in grammar productions; it suggests places where errors are
expected, and recovery can take place:
line:
'\n' { undef }
| exp '\n' { print "$_[1]\n" if defined($_[1]); $_[1] }
| error '\n'
{
$_[0]->YYErrok;
undef
}
The parser pops its stack until
it enters a state where the token C<error> is legal. It then shifts
the token C<error> and proceeds to discard tokens until finding
one that is acceptable. In the example
all the tokens until finding a C<'\n'> will be skipped.
If no special error productions have been specified,
the processing will halt.
In order to prevent a cascade of error messages, the parser, after
detecting an error, remains in error state until three tokens have been
successfully read and shifted. If an error is detected when the parser
is already in error state, no message is given, and the input token is
quietly deleted. The method C<YYErrok> used in the example
communicates to the parser
that a satisfactory recovery has been reached
and that it can safely emit new error
messages.
You cannot have a literal I<'error'> in your grammar as it would
confuse the driver with the I<error> token. Use a symbolic token instead.
=head2 The Tail
The tail section contains Perl code. Usually the lexical analyzer and the
Error management subroutines go there. A better practice however is to isolate
both subroutines in a module and use them in the grammar. An example of this is in
files C<examples/CalcUsingTail.eyp> and C<examples/Tail.pm>.
=head3 The Lexical Analyzer
The Lexical Analyzer
is called each time the parser needs a new token.
It is called with only one argument (the parser object)
and returns a pair
containing the next token and its associated attribute.
The fact that is a method of the parser object means that
the parser
methods are accesible inside the lexical analyzer.
Specially interesting is the C<$_[0]-E<gt>YYData>
method which provides access to the user data area.
I<When the lexical analyzer reaches the end of input, it must return the
pair> C<('', undef)>
See below how to write a lexical analyzer (file C<examples/Calc.eyp>):
1 sub make_lexer {
2 my $input = shift;
3
4 return sub {
5 my $parser = shift;
6
7 for ($$input) {
8 m{\G[ \t]*}gc;
9 m{\G([0-9]+(?:\.[0-9]+)?)}gc and return ('NUM',$1);
10 m{\G([A-Za-z][A-Za-z0-9_]*)}gc and return ('VAR',$1);
11 m{\G\n}gc and do { $lineno++; return ("\n", "\n") };
12 m{\G(.)}gc and return ($1,$1);
13
14 return('',undef);
15 }
16 }
17 }
The subroutine C<make_lexer> creates the lexical analyzer as
a closure. The lexer returned by C<make_lexer> is used by the
C<YYParse> method:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ sed -ne '90,97p' Calc.eyp | cat -n
1 sub Run {
2 my($self)=shift;
3 my $input = shift or die "No input given\n";
4
5 return $self->YYParse( yylex => make_lexer($input), yyerror => \&_Error,
6 #yydebug =>0x1F
7 );
8 }
=head3 The Error Report Subroutine
The Error Report subroutine is also a parser method,
and consequently receives as parameter the parser object.
See the error report subroutine
for the example in C<examples/Calc.eyp>:
1 %%
2
3 my $lineno = 1;
4
5 sub _Error {
6 my $parser = shift;
7
8 exists $parser->YYData->{ERRMSG}
9 and do {
10 print $parser->YYData->{ERRMSG};
11 delete $parser->YYData->{ERRMSG};
12 return;
13 };
14 my($token)=$parser->YYCurval;
15 my($what)= $token ? "input: '$token'" : "end of input";
16 my @expected = $parser->YYExpect();
17 local $" = ', ';
18 print << "ERRMSG";
19
20 Syntax error near $what (lin num $lineno).
21 Expected one of these terminals: @expected
22 ERRMSG
23 }
See the L<Parse::Yapp> pages and elsewhere documentation
on L<yacc> and L<bison> for more information.
=head2 Using an Eyapp Program
The following is an example of a program that uses the calculator explained
in the two previous sections:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ cat -n usecalc.pl
1 #!/usr/bin/perl -w
2 use strict;
3 use Calc;
4
5 my $parser = Calc->new();
6 my $input = <<'EOI';
7 a = 2*3
8 d = 5/(a-6)
9 b = (a+1)/7
10 c=a*3+4)-5
11 a = a+1
12 EOI
13 my $t = $parser->Run(\$input);
14 print "========= Symbol Table ==============\n";
15 print "$_ = $t->{$_}\n" for sort keys %$t;
The output for this program is (the input for each output
appear as a Perl comment on the right):
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ eyapp Calc.eyp
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ usecalc.pl
6 # a = 2*3
Illegal division by zero. # d = 5/(a-6)
1 # b = (a+1)/7
Syntax error near input: ')' (lin num 4). # c=a*3+4)-5
Expected one of these terminals: -, /, ^, *, +,
7 # a = a+1
========= Symbol Table ==============
a = 7
b = 1
c = 22
=head2 Lists and Optionals
The elements of a rhs can be one of these:
rhselt:
symbol
| code
| '(' optname rhs ')'
| rhselt STAR /* STAR is (%name\s*([A-Za-z_]\w*)\s*)?\* */
| rhselt '<' STAR symbol '>'
| rhselt OPTION /* OPTION is (%name\s*([A-Za-z_]\w*)\s*)?\? */
| rhselt '<' PLUS symbol '>'
| rhselt PLUS /* PLUS is (%name\s*([A-Za-z_]\w*)\s*)?\+ */
The C<STAR>, C<OPTION> and C<PLUS> operators provide a simple mechanism
to express lists:
=over
=item *
In Eyapp the C<+> operator indicates one or more repetitions of the element
to the left of C<+>, thus a rule like:
decls: decl +
is the same as:
decls: decls decl
| decl
An additional symbol may be included to indicate lists of elements
separated by such symbol. Thus
rhss: rule <+ '|'>
is equivalent to:
rhss: rhss '|' rule
| rule
=item *
The operators C<*> and C<?> have their usual meaning: 0 or more for
C<*> and optionality for C<?>. Is legal to parenthesize
a C<rhs> expression as in:
optname: (NAME IDENT)?
=back
=head2 The Semantic of Lists Operators
=head3 The C<+> operator
The grammar:
pl@nereida:~/LEyapp/examples$ head -12 List3.yp | cat -n
1 # List3.yp
2 %semantic token 'c'
3 %{
4 use Data::Dumper;
5 %}
6 %%
7 S: 'c'+ 'd'+
8 {
9 print Dumper($_[1]);
10 print Dumper($_[2]);
11 }
12 ;
Is equivalent to:
pl@nereida:~/LEyapp/examples$ eyapp -v List3.yp | head -9 List3.output
Rules:
------
0: $start -> S $end
1: PLUS-1 -> PLUS-1 'c'
2: PLUS-1 -> 'c'
3: PLUS-2 -> PLUS-2 'd'
4: PLUS-2 -> 'd'
5: S -> PLUS-1 PLUS-2
By default, the semantic action associated with a C<+> returns the lists of attributes
to which the C<+> applies:
pl@nereida:~/LEyapp/examples$ use_list3.pl
ccdd
$VAR1 = [ 'c', 'c' ];
$VAR1 = [ 'd', 'd' ];
The semantic associated with a C<+> changes
when one of the tree creation directives is active (for instance C<%tree> or C<%metatree>)
or it has been explicitly requested with a call to the C<YYBuildingTree> method:
$self->YYBuildingTree(1);
Other ways to change the associated semantic are to use the
C<yybuildingtree> option of C<YYParse>:
$self->YYParse( yylex => \&_Lexer, yyerror => \&_Error,
yybuildingtree => 1,
# yydebug => 0x1F
);
In such case the associated semantic action creates a node labelled
_PLUS_LIST_#number
whose children are the attributes associated with the items in the
plus list. The C<#number> in C<_PLUS_LIST_#number> is the ordinal
of the production rule as it appears in the C<.output> file.
As it happens when using the C<%tree> directive syntactic tokens
are skipped.
When executing the example above but under the C<%tree> directive
the ouput changes:
pl@nereida:~/LEyapp/examples$ head -3 List3.yp; eyapp List3.yp
# List3.yp
%semantic token 'c'
%tree
pl@nereida:~/LEyapp/examples$ use_list3.pl
ccdd
$VAR1 = bless( {
'children' => [
bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' ),
bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' )
]
}, '_PLUS_LIST_1' );
$VAR1 = bless( { 'children' => [] }, '_PLUS_LIST_2' );
The node associated with the list of C<d>s is empty since
terminal C<d> wasn't declared semantic.
=head3 When Nodes Dissappear from Lists
When under the influence of the C<%tree> directive
the action associated with a list operator
is to I<flat> the children in a single list.
In the former example, the C<d> nodes dont show up
since C<'d'> is a syntactic token. However, it may happen that changing the status
of C<'d'> to semantic will not suffice.
When inserting the children, the tree (C<%tree>) node construction
method (C<YYBuildAST>) omits any attribute that is not a reference.
Therefore, when inserting explicit actions, it is necessary to guarantee that
the returned value is a reference or a semantic token
to assure the presence of the value in the lists of children of the node.
Certainly you can use this property to prune parts of the tree.
Consider the following example:
pl@nereida:~/LEyapp/examples$ head -19 ListWithRefs1.eyp | cat -n
1 # ListWithRefs.eyp
2 %semantic token 'c' 'd'
3 %{
4 use Data::Dumper;
5 %}
6 %%
7 S: 'c'+ D+
8 {
9 print Dumper($_[1]);
10 print $_[1]->str."\n";
11 print Dumper($_[2]);
12 print $_[2]->str."\n";
13 }
14 ;
15
16 D: 'd'
17 ;
18
19 %%
To activate the I<tree semantic> for lists we use the C<yybuildingtree>
option of C<YYParse>:
pl@nereida:~/LEyapp/examples$ tail -7 ListWithRefs1.eyp | cat -n
1 sub Run {
2 my($self)=shift;
3 $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error,
4 yybuildingtree => 1,
5 #, yydebug => 0x1F
6 );
7 }
The execution gives an ouput like this:
pl@nereida:~/LEyapp/examples$ eyapp ListWithRefs1.eyp; use_listwithrefs1.pl
ccdd
$VAR1 = bless( {
'children' => [
bless( {
'children' => [],
'attr' => 'c',
'token' => 'c'
}, 'TERMINAL' ),
bless( {
'children' => [],
'attr' => 'c',
'token' => 'c'
}, 'TERMINAL' )
]
}, '_PLUS_LIST_1' );
_PLUS_LIST_1(TERMINAL,TERMINAL)
$VAR1 = bless( {
'children' => []
}, '_PLUS_LIST_2' );
_PLUS_LIST_2
Though C<'d'> was declared semantic the default action
assoaciated with the production C<D: 'd'> in line 16
returns C<$_[1]> (that is, the scalar C<'d'>). Since it is not
a reference it won't be inserted in the list of children of
C<_PLUS_LIST>.
=head3 Recovering the Missing Nodes
The solution is to be sure that the attribute is a reference:
pl@nereida:~/LEyapp/examples$ head -22 ListWithRefs.eyp | cat -n
1 # ListWithRefs.eyp
2 %semantic token 'c'
3 %{
4 use Data::Dumper;
5 %}
6 %%
7 S: 'c'+ D+
8 {
9 print Dumper($_[1]);
10 print $_[1]->str."\n";
11 print Dumper($_[2]);
12 print $_[2]->str."\n";
13 }
14 ;
15
16 D: 'd'
17 {
18 bless { attr => $_[1], children =>[]}, 'DES';
19 }
20 ;
21
22 %%
Now the attribute associated with C<D> is a reference
and appears in the list of children of C<_PLUS_LIST>:
pl@nereida:~/LEyapp/examples$ eyapp ListWithRefs.eyp; use_listwithrefs.pl
ccdd
$VAR1 = bless( {
'children' => [
bless( {
'children' => [],
'attr' => 'c',
'token' => 'c'
}, 'TERMINAL' ),
bless( {
'children' => [],
'attr' => 'c',
'token' => 'c'
}, 'TERMINAL' )
]
}, '_PLUS_LIST_1' );
_PLUS_LIST_1(TERMINAL,TERMINAL)
$VAR1 = bless( {
'children' => [
bless( {
'children' => [],
'attr' => 'd'
}, 'DES' ),
bless( {
'children' => [],
'attr' => 'd'
}, 'DES' )
]
}, '_PLUS_LIST_2' );
_PLUS_LIST_2(DES,DES)
=head3 Building a Tree with C<Parse::Eyapp::Node-E<gt>new>
The former solution consisting on writing I<by hand> the code to
build the node may suffice when dealing with a single node.
Writing by hand the code to build a node is a cumbersome task.
Even worst: though the node built in the former example
looks like a C<Parse::Eyapp> node actually isn't. C<Parse::Eyapp>
nodes always inherit from C<Parse::Eyapp::Node> and
consequently have access to the methods in such package.
Thefollowing execution using the debugger illustrates the point:
pl@nereida:~/LEyapp/examples$ perl -wd use_listwithrefs.pl
Loading DB routines from perl5db.pl version 1.28
Editor support available.
Enter h or `h h' for help, or `man perldebug' for more help.
main::(use_listwithrefs.pl:4): $parser = new ListWithRefs();
DB<1> f ListWithRefs.eyp
1 2 #line 3 "ListWithRefs.eyp"
3
4: use Data::Dumper;
5
6 #line 7 "ListWithRefs.eyp"
7 #line 8 "ListWithRefs.eyp"
8
9: print Dumper($_[1]);
10: print $_[1]->str."\n";
through the command C<f ListWithRefs.eyp> we inform the debugger
that subsequent commands will refer to such file. Next
we execute the program up to the semantic action
associated with the production rule C<S: 'c'+ D+> (line 9)
DB<2> c 9 # Continue up to line 9 of ListWithRefs.eyp
ccdd
ListWithRefs::CODE(0x84ebe5c)(ListWithRefs.eyp:9):
9: print Dumper($_[1]);
Now we are in condition to look at the contents
of the arguments:
DB<3> x $_[2]->str
0 '_PLUS_LIST_2(DES,DES)'
DB<4> x $_[2]->child(0)
0 DES=HASH(0x85c4568)
'attr' => 'd'
'children' => ARRAY(0x85c458c)
empty array
the C<str> method works with the object C<$_[2]> since
C<_PLUS_LIST_2> nodes inherit from C<Parse::Eyapp::Node>.
However, when we try with the C<DES> node we get an
error:
DB<6> x $_[2]->child(0)->str
Can't locate object method "str" via package "DES" at \
(eval 11)[/usr/share/perl/5.8/perl5db.pl:628] line 2, <STDIN> line 1.
DB<7>
More robust than the former solution of building the node I<by hand>
is to use the constructor C<Parse::Eyapp::Node-E<gt>new>:
The method C<Parse::Eyapp::Node-E<gt>new>
is uset to build forests of syntactic trees.
It receives a list of terms describing the trees and - optionally -
a reference to a subroutine used to set up the attributes
of the just created nodes. After the creation
of the trees the sub is called by C<Parse::Eyapp::Node-E<gt>new>
with arguments the list of references to the nodes (in the order
in which they appear in the terms, from left to right).
C<Parse::Eyapp::Node-E<gt>new> returns a list of references
to the jsut created nodes. In a scalar context returns a reference to the first of such trees.
See an example:
pl@nereida:~/LEyapp/examples$ perl -MParse::Eyapp -MData::Dumper -wde 0
main::(-e:1): 0
DB<1> @t = Parse::Eyapp::Node->new('A(C,D) E(F)', sub { my $i = 0; $_->{n} = $i++ for @_ })
DB<2> $Data::Dumper::Indent = 0
DB<3> print Dumper($_)."\n" for @t
$VAR1 = bless( {'n' => 0,'children' => [bless( {'n' => 1,'children' => []}, 'C' ),
bless( {'n' => 2,'children' => []}, 'D' )
]
}, 'A' );
$VAR1 = bless( {'n' => 1,'children' => []}, 'C' );
$VAR1 = bless( {'n' => 2,'children' => []}, 'D' );
$VAR1 = bless( {'n' => 3,'children' => [bless( {'n' => 4,'children' => []}, 'F' )]}, 'E' );
$VAR1 = bless( {'n' => 4,'children' => []}, 'F' );
See the following example in which the nodes associated with C<'d'> are
explictly constructed:
pl@nereida:~/LEyapp/examples$ head -28 ListWithRefs2.eyp| cat -n
1 # ListWithRefs2.eyp
2 %semantic token 'c'
3 %{
4 use Data::Dumper;
5 %}
6 %%
7 S: 'c'+ D+
8 {
9 print Dumper($_[1]);
10 print $_[1]->str."\n";
11 print Dumper($_[2]);
12 print $_[2]->str."\n";
13 }
14 ;
15
16 D: 'd'.d
17 {
18 Parse::Eyapp::Node->new(
19 'DES(TERMINAL)',
20 sub {
21 my ($DES, $TERMINAL) = @_;
22 $TERMINAL->{attr} = $d;
23 }
24 );
25 }
26 ;
27
28 %%
To know more about C<Parse::Eyapp::Node-E<gt>new>
see the L<Parse::Eyapp::Node> section about C<new>
When the former eyapp program is executed produces the following
output:
pl@nereida:~/LEyapp/examples$ eyapp ListWithRefs2.eyp; use_listwithrefs2.pl
ccdd
$VAR1 = bless( {
'children' => [
bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' ),
bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' )
]
}, '_PLUS_LIST_1' );
_PLUS_LIST_1(TERMINAL,TERMINAL)
$VAR1 = bless( {
'children' => [
bless( {
'children' => [
bless( { 'children' => [], 'attr' => 'd' }, 'TERMINAL' )
]
}, 'DES' ),
bless( {
'children' => [
bless( { 'children' => [], 'attr' => 'd' }, 'TERMINAL' )
]
}, 'DES' )
]
}, '_PLUS_LIST_2' );
_PLUS_LIST_2(DES(TERMINAL),DES(TERMINAL))
=head3 The C<*> operator
Any list operator operates on the factor to its left.
A list in the right hand side of a production rule
counts as a single symbol.
Both operators C<*> and C<+> can be used
with the format
C<X E<lt>* SeparatorE<gt>>.
In such case they describe lists of C<X>s separated by
C<separator>. See an example:
pl@nereida:~/LEyapp/examples$ head -25 CsBetweenCommansAndD.eyp | cat -n
1 # CsBetweenCommansAndD.eyp
2
3 %semantic token 'c' 'd'
4
5 %{
6 sub TERMINAL::info {
7 $_[0]->attr;
8 }
9 %}
10 %tree
11 %%
12 S:
13 ('c' <* ','> 'd')*
14 {
15 print "\nNode\n";
16 print $_[1]->str."\n";
17 print "\nChild 0\n";
18 print $_[1]->child(0)->str."\n";
19 print "\nChild 1\n";
20 print $_[1]->child(1)->str."\n";
21 $_[1]
22 }
23 ;
24
25 %%
The rule
S: ('c' <* ','> 'd')*
has only two items in its right hand side: the (separated by commas) list
of C<c>s and the list of C<d>s. The production rule is equivalent to:
pl@nereida:~/LEyapp/examples$ eyapp -v CsBetweenCommansAndD.eyp
pl@nereida:~/LEyapp/examples$ head -11 CsBetweenCommansAndD.output | cat -n
1 Rules:
2 ------
3 0: $start -> S $end
4 1: STAR-1 -> STAR-1 ',' 'c'
5 2: STAR-1 -> 'c'
6 3: STAR-2 -> STAR-1
7 4: STAR-2 -> /* empty */
8 5: PAREN-3 -> STAR-2 'd'
9 6: STAR-4 -> STAR-4 PAREN-3
10 7: STAR-4 -> /* empty */
11 8: S -> STAR-4
The semantic action associated with C<*> is to return
a reference to a list with the attributes of the
matching items.
When working -as in the example -
under a tree creation directive it returns
a node belonging to a class named C<_STAR_LIST_#number>
whose children are the items in the list.
The C<#number> is the ordinal number of the production rule
as it appears in the C<.output> file. The attributes must be
references or associated with semantic tokens to be included
in the list. Notice -in the execution of the former
example that follows -
how the node for C<PAREN-3> has been
eliminated from the tree. Parenthesis nodes are - generally -
obivated:
pl@nereida:~/LEyapp/examples$ use_csbetweencommansandd.pl
c,c,cd
Node
_STAR_LIST_4(_STAR_LIST_1(TERMINAL[c],TERMINAL[c],TERMINAL[c]),TERMINAL[d])
Child 0
_STAR_LIST_1(TERMINAL[c],TERMINAL[c],TERMINAL[c])
Child 1
TERMINAL[d]
Notice that the comma (since it is a syntactic token) has
also been supressed.
=head3 Giving Names to Lists
To set the name of the node associated with a list operator the
C<%name> directive must precede the operator as in
the following example:
pl@nereida:~/LEyapp/examples$ sed -ne '1,27p' CsBetweenCommansAndDWithNames.eyp | cat -n
1 # CsBetweenCommansAndDWithNames.eyp
2
3 %semantic token 'c' 'd'
4
5 %{
6 sub TERMINAL::info {
7 $_[0]->attr;
8 }
9 %}
10 %tree
11 %%
12 Start: S
13 ;
14 S:
15 ('c' <%name Cs * ','> 'd') %name Cs_and_d *
16 {
17 print "\nNode\n";
18 print $_[1]->str."\n";
19 print "\nChild 0\n";
20 print $_[1]->child(0)->str."\n";
21 print "\nChild 1\n";
22 print $_[1]->child(1)->str."\n";
23 $_[1]
24 }
25 ;
26
27 %%
The execution shows the renamed nodes:
pl@nereida:~/LEyapp/examples$ use_csbetweencommansanddwithnames.pl
c,c,c,cd
Node
Cs_and_d(Cs(TERMINAL[c],TERMINAL[c],TERMINAL[c],TERMINAL[c]),TERMINAL[d])
Child 0
Cs(TERMINAL[c],TERMINAL[c],TERMINAL[c],TERMINAL[c])
Child 1
TERMINAL[d]
=head3 Optionals
The C<X?> operator stands for the presence or omission
of C<X>.
The grammar:
pl@nereida:~/LEyapp/examples$ head -11 List5.yp | cat -n
1 %semantic token 'c'
2 %tree
3 %%
4 S: 'c' 'c'?
5 {
6 print $_[2]->str."\n";
7 print $_[2]->child(0)->attr."\n" if $_[2]->children;
8 }
9 ;
10
11 %%
is equivalent to:
pl@nereida:~/LEyapp/examples$ eyapp -v List5
pl@nereida:~/LEyapp/examples$ head -7 List5.output
Rules:
------
0: $start -> S $end
1: OPTIONAL-1 -> 'c'
2: OPTIONAL-1 -> /* empty */
3: S -> 'c' OPTIONAL-1
When C<yybuildingtree> is false the associated attribute
is a list that will be empty if CX> does not show up.
Under the C<%tree> directive the action creates an c<_OPTIONAL>
node:
pl@nereida:~/LEyapp/examples$ use_list5.pl
cc
_OPTIONAL_1(TERMINAL)
c
pl@nereida:~/LEyapp/examples$ use_list5.pl
c
_OPTIONAL_1
=head3 Parenthesis
Any substring on the right hand side of a production rule can be grouped
using a parenthesis. The introduction of a parenthesis implies the introduction
of an additional syntactic variable whose only production
is the sequence of symbols between the parenthesis. Thus the grammar:
pl@nereida:~/LEyapp/examples$ head -6 Parenthesis.eyp | cat -n
1 %%
2 S:
3 ('a' S ) 'b' { shift; [ @_ ] }
4 | 'c'
5 ;
6 %%
is equivalent to:
pl@nereida:~/LEyapp/examples$ eyapp -v Parenthesis.eyp; head -6 Parenthesis.output
Rules:
------
0: $start -> S $end
1: PAREN-1 -> 'a' S
2: S -> PAREN-1 'b'
3: S -> 'c'
By default the semantic rule associated with a parenthesis
returns an anonymous list with the attributes of the symbols
between the parenthesis:
pl@nereida:~/LEyapp/examples$ cat -n use_parenthesis.pl
1 #!/usr/bin/perl -w
2 use Parenthesis;
3 use Data::Dumper;
4
5 $Data::Dumper::Indent = 1;
6 $parser = Parenthesis->new();
7 print Dumper($parser->Run);
pl@nereida:~/LEyapp/examples$ use_parenthesis.pl
acb
$VAR1 = [
[ 'a', 'c' ], 'b'
];
pl@nereida:~/LEyapp/examples$ use_parenthesis.pl
aacbb
$VAR1 = [
[
'a',
[ [ 'a', 'c' ], 'b' ]
],
'b'
];
when working under a tree directive or when the attribute
C<buildingtree> is set via theC<YYBuildingtree> method
the semantic action returns a node with children the attributes
of the symbols between parenthesis. As usual attributes
which aren't references will be skipped from the list of children.
See an example:
pl@nereida:~/LEyapp/examples$ head -23 List2.yp | cat -n
1 %{
2 use Data::Dumper;
3 %}
4 %semantic token 'a' 'b' 'c'
5 %tree
6 %%
7 S:
8 (%name AS 'a' S )'b'
9 {
10 print "S -> ('a' S )'b'\n";
11 print "Attribute of the first symbol:\n".Dumper($_[1]);
12 print "Attribute of the second symbol: $_[2]\n";
13 $_[0]->YYBuildAST(@_[1..$#_]);
14 }
15 | 'c'
16 {
17 print "S -> 'c'\n";
18 my $r = Parse::Eyapp::Node->new(qw(C(TERMINAL)), sub { $_[1]->attr('c') }) ;
19 print Dumper($r);
20 $r;
21 }
22 ;
23 %%
The example shows (line 8)
how to rename a C<_PAREN> node. The C<%name CLASSNAME> goes
after the opening parenthesis.
The call to C<YYBuildAST> at line 13
with argumetns the attributes of the symbols on the right hand side
returns the node describing the current production rule.
Notice that line 13 can be rewritten as:
goto &Parse::Eyapp::Driver::YYBuildAST;
At line 18 the node for the rule is explictly created
using C<Parse::Eyapp::Node->new>. The handler passed as second argument
is responsible for setting the value of the atribute C<attr>
of the just created C<TERMINAL> node.
Let us see an execution:
pl@nereida:~/LEyapp/examples$ use_list2.pl
aacbb
S -> 'c'
$VAR1 = bless( {
'children' => [
bless( {
'children' => [],
'attr' => 'c'
}, 'TERMINAL' )
]
}, 'C' );
the first reduction occurs by the non recursive rule. The execution
shows the tree built by the call to
C<Parse::Eyapp::Node->new>
at line 18.
The execution continues with the reduction or antiderivation by the rule
C<S -E<gt> ('a' S )'b'>. The action at lines 9-14
dumps the attribute associated with C<('a' S)>
- or, in other words, the attribute associated with the variable
C<PAREN-1>. It also dumps the attribute of C<'b'>:
S -> ('a' S )'b'
Attribute of the first symbol:
$VAR1 = bless( {
'children' => [
bless( { 'children' => [], 'attr' => 'a', 'token' => 'a' }, 'TERMINAL' ),
bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'c' }, 'TERMINAL' )
]
}, 'C' )
]
}, 'AS' );
Attribute of the second symbol: b
The last reduction shown is by the rule:
C<S -E<gt> ('a' S )'b'>:
S -> ('a' S )'b'
Attribute of the first symbol:
$VAR1 = bless( {
'children' => [
bless( { 'children' => [], 'attr' => 'a', 'token' => 'a' }, 'TERMINAL' ),
bless( {
'children' => [
bless( {
'children' => [
bless( { 'children' => [], 'attr' => 'a', 'token' => 'a' }, 'TERMINAL' ),
bless( {
'children' => [
bless( { 'children' => [], 'attr' => 'c' }, 'TERMINAL' )
]
}, 'C' )
]
}, 'AS' ),
bless( { 'children' => [], 'attr' => 'b', 'token' => 'b' }, 'TERMINAL' )
]
}, 'S_2' )
]
}, 'AS' );
Attribute of the second symbol: b
=head3 Actions Inside Parenthesis
Though is a practice to avoid, since it clutters
the code, it is certainly permitted to introduce
actions between the parenthesis, as in the example below:
pl@nereida:~/LEyapp/examples$ head -16 ListAndAction.eyp | cat -n
1 # ListAndAction.eyp
2 %{
3 my $num = 0;
4 %}
5
6 %%
7 S: 'c'
8 {
9 print "S -> c\n"
10 }
11 | ('a' {$num++; print "Seen <$num> 'a's\n"; $_[1] }) S 'b'
12 {
13 print "S -> (a ) S b\n"
14 }
15 ;
16 %%
This is the output when executing this program with input C<aaacbbb>:
pl@nereida:~/LEyapp/examples$ use_listandaction.pl
aaacbbb
Seen <1> 'a's
Seen <2> 'a's
Seen <3> 'a's
S -> c
S -> (a ) S b
S -> (a ) S b
S -> (a ) S b
=head2 Names for attributes
Attributes can be referenced by meaningful names instead
of the classic error-prone positional approach using the I<dot notation>:
rhs: rhseltwithid *
rhseltwithid :
rhselt '.' IDENT
| '$' rhselt
| rhselt
for example:
exp : exp.left '-' exp.right { $left - $right }
By qualifying the first appearance of the syntactic variable C<exp>
with the notation C<exp.left> we can later refer inside the actions
to the associated attribute using the lexical variable
C<$left>.
The I<dolar notation> C<$A> can be used as an abbreviation
of C<A.A>.
=head2 Default actions
When no action is specified both C<yapp> and C<eyapp>
implicitly insert the semantic action C<{ $_[1] }>.
In C<Parse::Eyapp> you can modify such behavior using the C<%defaultaction { Perl code }>
directive. The C<{ Perl code }> clause that follows the C<%defaultaction>
directive is
executed when reducing by any production for which no explicit
action was specified.
=head3 Translator from Infix to Postfix
See an example that translates an infix expression
like C<a=b*-3> into a postfix expression like C<a b 3 NEG * = >:
# File Postfix.eyp (See the examples/ directory)
%right '='
%left '-' '+'
%left '*' '/'
%left NEG
%defaultaction { return "$left $right $op"; }
%%
line: $exp { print "$exp\n" }
;
exp: $NUM { $NUM }
| $VAR { $VAR }
| VAR.left '='.op exp.right
| exp.left '+'.op exp.right
| exp.left '-'.op exp.right
| exp.left '*'.op exp.right
| exp.left '/'.op exp.right
| '-' $exp %prec NEG { "$exp NEG" }
| '(' $exp ')' { $exp }
;
%%
# Support subroutines as in the Synopsis example
...
The file containing the C<Eyapp> program must be compiled with C<eyapp>:
nereida:~/src/perl/YappWithDefaultAction/examples> eyapp Postfix.eyp
Next, you have to write a client program:
nereida:~/src/perl/YappWithDefaultAction/examples> 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:
nereida:~/src/perl/YappWithDefaultAction/examples> usepostfix.pl
Write an expression: -(2*a-b*-3)
2 a * b 3 NEG * - NEG
=head3 Default Actions, C<%name> and C<YYName>
In C<eyapp> each production rule has a name.
The name of a rule can be explicitly given by the programmer
using the C<%name> directive. For example, in the piece of code
that follows the name C<ASSIGN> is given to the rule C<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 C<Lhs_#>
as it appears in the C<.output> file.
Avoid giving names matching such pattern to production rules.
The patterns
C</${lhs}_\d+$/> where C<${lhs}> is the name of the syntactic variable
are reserved for internal use by C<eyapp>.
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 C<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 C<children> which is a reference
to the list of children of the node.
The call to C<grep>
11 bless { children => [ grep {ref($_)} @_] }, $name;
excludes children that aren't references. Notice that the lexical analyzer
only returns references for the C<NUM> and C<VAR> terminals:
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 C<a=(2+3)*b> the parser produces
the following tree:
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('SUBSTRACT'); # 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 C<SUBSTRACT> nodes:
pl@nereida:~/LEyapp/examples$ useyynamedynamic.pl
2-b
$VAR1 = [
bless( {
'children' => [
bless( {
'attr' => '2'
}, 'NUM' ),
bless( {
'attr' => 'b'
}, 'VAR' )
]
}, 'SUBSTRACT' )
];
=head2 Abstract Syntax Trees : C<%tree> and C<%name>
C<Parse::Eyapp> facilitates the construction of concrete syntax trees and
abstract syntax trees (abbreviated AST from now on) through the C<%tree>
directive.
Nodes in the AST are blessed in the production
C<name>.
By default the name of a production is the concatenation
of the left hand side and the production number. The production number
is the ordinal number of the production as they appear in the associated
C<.output> file (see option C<-v> of L<eyapp>). For example,
given the grammar:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ sed -ne '9,28p' treewithoutnames.pl
my $grammar = q{
%right '=' # Lowest precedence
%left '-' '+' # + and - have more precedence than = Disambiguate a-b-c as (a-b)-c
%left '*' '/' # * and / have more precedence than + Disambiguate a/b/c as (a/b)/c
%left NEG # Disambiguate -a-b as (-a)-b and not as -(a-b)
%tree # Let us build an abstract syntax tree ...
%%
line: exp <+ ';'> { $_[1] } /* list of expressions separated by ';' */
;
exp:
NUM | VAR | VAR '=' exp
| exp '+' exp | exp '-' exp | exp '*' exp
| exp '/' exp
| '-' exp %prec NEG
| '(' exp ')' { $_[2] }
;
The tree produced by the parser when feed with input C<a=2*b>
is:
_PLUS_LIST(exp_6(TERMINAL[a],exp_9(exp_4(TERMINAL[2]),exp_5(TERMINAL[b]))))
If we want to see the correspondence between names and rules we can generate and
check the corresponding file C<.output>:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ sed -ne '28,42p' treewithoutnames.output
Rules:
------
0: $start -> line $end
1: PLUS-1 -> PLUS-1 ';' exp
2: PLUS-1 -> exp
3: line -> PLUS-1
4: exp -> NUM
5: exp -> VAR
6: exp -> VAR '=' exp
7: exp -> exp '+' exp
8: exp -> exp '-' exp
9: exp -> exp '*' exp
10: exp -> exp '/' exp
11: exp -> '-' exp
12: exp -> '(' exp ')'
We can see now that the node C<exp_9> corresponds to the production C<exp -E<gt> exp '*' exp>.
Observe also that the Eyapp production:
line: exp <+ ';'>
actually produces the productions:
1: PLUS-1 -> PLUS-1 ';' exp
2: PLUS-1 -> exp
and that the name of the class associated with the non empty list is C<_PLUS_LIST>.
A production rule can be
I<named> using the C<%name IDENTIFIER> directive.
For each production rule a
namespace/package is created. I<The> C<IDENTIFIER>
I<is the name of the associated package>.
Therefore, by modifying the former grammar with
additional C<%name> directives:
pl@nereida:~/src/perl/YappWithDefaultAction/examples$ sed -ne '8,26p' treewithnames.pl
my $grammar = q{
%right '=' # Lowest precedence
%left '-' '+' # + and - have more precedence than = Disambiguate a-b-c as (a-b)-c
%left '*' '/' # * and / have more precedence than + Disambiguate a/b/c as (a/b)/c
%left NEG # Disambiguate -a-b as (-a)-b and not as -(a-b)
%tree # Let us build an abstract syntax tree ...
%%
line: exp <%name EXPS + ';'> { $_[1] } /* list of expressions separated by ';' */
;
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] }
;
we are explictly naming the productions. Thus, all the node instances
corresponding to the
production C<exp: VAR '=' exp> will belong to the class C<ASSIGN>. Now
the tree for C<a=2*b> becomes:
EXPS(ASSIGN(TERMINAL[a],TIMES(NUM(TERMINAL[2]),VAR(TERMINAL[b]))))
Observe how the list has been named C<EXPS>. The C<%name> directive prefixes the
list operator (C<[+*?]>).
=head3 About the Encapsulation of Nodes
There is no encapsulation of nodes. The user/client
knows that they are hashes that can be decorated with new keys/attributes.
All nodes in the AST created by C<%tree> are C<Parse::Eyapp::Node> nodes.
The only reserved field is C<children> which is a reference to the
array of children. You can always create a C<Node> class
I<by hand> by inheriting from C<Parse::Eyapp::Node>. See
section 'Compiling with eyapp and treereg' in L<Parse::Eyapp> for an example.
=head3 TERMINAL Nodes
Nodes named C<TERMINAL> are built from the
tokens provided by the lexical analyzer.
C<Parse::Eyapp> follows the same protocol
than L<Parse::Yapp> for communication between the parser and the lexical analyzer:
A couple C<($token, $attribute)> is returned by the lexical analyzer.
These values are stored under the keys C<token> and C<attr>.
C<TERMINAL> nodes as all C<Parse::Eyapp::Node> nodes
also have the attribute C<children> but is - almost always - empty.
=head3 Explicit Actions Inside C<%tree>
Explicit actions can be specified by the programmer like in this line
from the L<Parse::Eyapp> C<SYNOPSIS> example:
| '(' exp ')' { $_[2] } /* Let us simplify a bit the tree */
Explicit actions receive as arguments the references to the children nodes already
built. The programmer can influence the shape of the tree by inserting
these explicit actions. In this example the programmer has decided to simplify the
syntax tree: the nodes associated with the parenthesis are
discarded and the reference to the subtree containing the proper
expression is returned. Such manoeuvre is called I<bypassing>.
See section L<The bypass clause and the %no bypass directive>
to know more about I<automatic bypassing>
=head3 Explicitly Building Nodes With C<YYBuildAST>
Sometimes the best time to decorate a node with some
attributes is just after being built.
In such cases the programmer can take I<manual control>
building the node with C<YYBuildAST> to
inmediately proceed to decorate it.
The following example illustrates the situation:
Variable:
%name VARARRAY
$ID ('[' binary ']') <%name INDEXSPEC +>
{
my $self = shift;
my $node = $self->YYBuildAST(@_);
$node->{line} = $ID->[1];
return $node;
}
This production rule defines the expression to access an array element
as an identifier followed by
a non empty list of binary expressions C< Variable: ID ('[' binary ']')+>.
Furthermore, the node corresponding
to the list of indices has been named C<INDEXSPEC>.
When no explicit action is
inserted a binary node will be built having as first child the node
corresponding to the identifier C<$ID> and as second child the reference
to the list of binary expressions. The children corresponding to
C<'['> and C<']'> are discarded since they are -by default- I<syntactic tokens>
(see section L<Syntactic and Semantic tokens>).
However, the programmer wants to decorate
the node being built with a C<line> attribute holding the line number in the source
code where the identifier being used appears. The call to the C<Parse::Eyapp::Driver>
method C<YYBuildAST> does the job of building the node. After
that the node can be decorated and returned.
Actually, the C<%tree> directive is semantically equivalent to:
%default action { goto &Parse::Eyapp::Driver::YYBuildAST }
=head3 Returning non References Under C<%tree>
When a I<explicit user action returns s.t. that is not a reference
no node will be inserted>. This fact can be used to supress nodes
in the AST being built. See the following example (file C<examples/returnnonode.yp>):
nereida:~/src/perl/YappWithDefaultAction/examples> sed -ne '1,11p' returnnonode.yp | cat -n
1 %tree
2 %semantic token 'a' 'b'
3 %%
4 S: /* empty */
5 | S A
6 | S B
7 ;
8 A : 'a'
9 ;
10 B : 'b' { }
11 ;
since the action at line 10 returns C<undef>
the C<B : 'b'> subtree will not be inserted in the AST:
nereida:~/src/perl/YappWithDefaultAction/examples> usereturnnonode.pl
ababa
S_2(S_3(S_2(S_3(S_2(S_1,A_4(TERMINAL[a]))),A_4(TERMINAL[a]))),A_4(TERMINAL[a]))
Observe the absence of C<B>s and C<'b'>s.
=head3 Intermediate actions and C<%tree>
Intermediate actions can be used to change the shape of the AST (prune it,
decorate it, etc.) but the value returned by them is ignored. The grammar
below has two intermediate actions. They modify the attributes of the
node to its left and return a reference C<$f> to such node (lines 5 and 6):
nereida:~/src/perl/YappWithDefaultAction/examples> \
sed -ne '1,10p' intermediateactiontree.yp | cat -n
1 %semantic token 'a' 'b'
2 %tree bypass
3 %%
4 S: /* empty */
5 | S A.f { $f->{attr} = "A"; $f; } A
6 | S B.f { $f->{attr} = "B"; $f; } B
7 ;
8 A : %name A 'a'
9 ;
10 B : %name B 'b'
See the client program running:
nereida:~/src/perl/YappWithDefaultAction/examples> cat -n useintermediateactiontree.pl
1 #!/usr/bin/perl -w
2 use strict;
3 use Parse::Eyapp;
4 use intermediateactiontree;
5
6 { no warnings;
7 *A::info = *B::info = sub { $_[0]{attr} };
8 }
9
10 my $parser = intermediateactiontree->new();
11 my $t = $parser->Run;
12 print $t->str,"\n";
nereida:~/src/perl/YappWithDefaultAction/examples> useintermediateactiontree.pl
aabbaa
S_2(S_4(S_2(S_1,A[A],A[a]),B[B],B[b]),A[A],A[a])
The
attributes
of left C<A>s
have been effectively changed by the intermediate actions
from C<'a'> to C<'A'>.
However no further children have been inserted.
=head3 Syntactic and Semantic tokens
C<Parse::Eyapp> diferences between C<syntactic tokens>
and C<semantic tokens>. By default all tokens
declared using string notation (i.e. between quotes
like C<'+'>, C<'='>)
are considered I<syntactic tokens>. Tokens declared by an identifier
(like C<NUM> or C<VAR>) are by default considered
I<semantic tokens>. B<Syntactic tokens do not yield to nodes in the
syntactic tree>. Thus, the first print in the former L<Parse::Eyapp> C</SYNOPSIS> example:
$parser->YYData->{INPUT} = "2*-3+b*0;--2\n";
my $t = $parser->Run;
local $Parse::Eyapp::Node::INDENT=2;
print "Syntax Tree:",$t->str;
gives as result the following output:
nereida:~/src/perl/YappWithDefaultAction/examples> synopsis.pl
Syntax Tree:
EXPRESION_LIST(
PLUS(
TIMES(
NUM(
TERMINAL[2]
),
UMINUS(
NUM(
TERMINAL[3]
)
) # UMINUS
) # TIMES,
TIMES(
VAR(
TERMINAL[b]
),
NUM(
TERMINAL[0]
)
) # TIMES
) # PLUS,
UMINUS(
UMINUS(
NUM(
TERMINAL[2]
)
) # UMINUS
) # UMINUS
) # EXPRESION_LIST
C<TERMINAL> nodes corresponding to tokens that were defined by strings like
C<'='>, C<'-'>, C<'+'>, C<'/'>, C<'*'>, C<'('> and C<')'> do not
appear in the tree. C<TERMINAL> nodes corresponding to tokens that were defined
using an identifer, like C<NUM> or C<VAR> are, by default, I<semantic tokens>
and appear in the AST.
=head3 Changing the Status of a Token
The new token declaration directives C<%syntactic token> and
C<%semantic token> can change the status of a token.
For example (file C<15treewithsyntactictoken.pl> in the C<examples/> directory),
given the grammar:
%syntactic token b
%semantic token 'a' 'c'
%tree
%%
S: %name ABC
A B C
| %name BC
B C
;
A: %name A
'a'
;
B: %name B
b
;
C: %name C
'c'
;
%%
the tree build for input C<abc> will be
C<ABC(A(TERMINAL[a]),B,C(TERMINAL[c]))>.
=head3 Saving the Information of Syntactic Tokens in their Father
The reason for the adjective C<%syntactic> applied to a token is to
state that the token influences the shape of the syntax tree
but carries no other information. When the syntax tree is built
the node corresponding to the token is discarded.
Sometimes the difference between syntactic and semantic
tokens is blurred. For example the line number associated
with an instance of the syntactic token C<'+'> can be used later
-say during type checking- to emit a more accurate error
diagnostic. But if the node was discarded the information
about that line number is no longer available.
When building the syntax tree C<Parse::Eyapp> (namely
the method C<Parse::Eyapp::YYBuildAST>) checks
if the method C<TERMINAL::save_attributes> exists and if so
it will be called when dealing with a I<syntactic token>.
The method receives as argument - additionally
to the reference to the attribute of the token as it
is returned by the lexical analyzer - a reference
to the node associated with the left hand side of the
production. Here is an example (file C<examples/Types.eyp>)
of use:
sub TERMINAL::save_attributes {
# $_[0] is a syntactic terminal
# $_[1] is the father.
push @{$_[1]->{lines}}, $_[0]->[1]; # save the line number
}
=head3 The C<bypass> clause and the C<%no bypass> directive
The shape of the tree can be also modified using some C<%tree> clauses
as C<%tree bypass> which will produce an automatic I<bypass> of any
node with only one child at tree-construction-time.
A I<bypass operation> consists in I<returning the only child
of the node being visited to the father of the node and re-typing (re-blessing)
the node in the name of the production> (if a name was provided).
A node may have only one child at tree-construction-time for one of
two reasons.
=over
=item *
The first occurs when the right hand side of the production
was already unary like in:
exp:
%name NUM NUM
Here - if the C<bypass> clause is used -
the C<NUM> node will be bypassed and the child C<TERMINAL> built
from the information provided by the lexical analyzer will be renamed/reblessed
as C<NUM>.
=item *
Another reason for a node to be I<bypassed> is the fact that though the right
hand side of the production may have more than one symbol,
only one of them is not a syntactic token
like in:
exp: '(' exp ')'
=back
A consequence of the global scope application of C<%tree bypass>
is that undesired bypasses may occur like in
exp : %name UMINUS
'-' $exp %prec NEG
though the right hand side has two symbols, token C<'-'> is
a syntactic token and therefore only C<exp> is left. The I<bypass>
operation will be applied when building this node.
This I<bypass> can be avoided applying the C<no bypass ID> directive to the corresponding
production:
exp : %no bypass UMINUS
'-' $exp %prec NEG
The following example (file C<examples/bypass.pl>)
is the equivalent of the L<Parse::Eyapp> C</SYNOPSIS> example
but using the C<bypass> clause instead:
use Parse::Eyapp;
use Parse::Eyapp::Treeregexp;
sub TERMINAL::info { $_[0]{attr} }
{ no warnings; *VAR::info = *NUM::info = \&TERMINAL::info; }
my $grammar = q{
%right '=' # Lowest precedence
%left '-' '+'
%left '*' '/'
%left NEG # Disambiguate -a-b as (-a)-b and not as -(a-b)
%tree bypass # Let us build an abstract syntax tree ...
%%
line: exp <%name EXPRESION_LIST + ';'> { $_[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
| %no bypass UMINUS
'-' $exp %prec NEG
| '(' exp ')'
;
%%
# sub _Error, _Lexer and Run like in the synopsis example
# ...
}; # end grammar
our (@all, $uminus);
Parse::Eyapp->new_grammar( # Create the parser package/class
input=>$grammar,
classname=>'Calc', # The name of the package containing the parser
firstline=>7 # String $grammar starts at line 7 (for error diagnostics)
);
my $parser = Calc->new(); # Create a parser
$parser->YYData->{INPUT} = "a=2*-3+b*0\n"; # Set the input
my $t = $parser->Run; # Parse it!
print "\n************\n".$t->str."\n************\n";
# Let us transform the tree. Define the tree-regular expressions ..
my $p = Parse::Eyapp::Treeregexp->new( STRING => q{
{ # Example of support code
my %Op = (PLUS=>'+', MINUS => '-', TIMES=>'*', DIV => '/');
}
constantfold: /TIMES|PLUS|DIV|MINUS/:bin(NUM, NUM)
=> {
my $op = $Op{ref($_[0])};
$NUM[0]->{attr} = eval "$NUM[0]->{attr} $op $NUM[1]->{attr}";
$_[0] = $NUM[0];
}
zero_times_whatever: TIMES(NUM, .) and { $NUM->{attr} == 0 } => { $_[0] = $NUM }
whatever_times_zero: TIMES(., NUM) and { $NUM->{attr} == 0 } => { $_[0] = $NUM }
uminus: UMINUS(NUM) => { $NUM->{attr} = -$NUM->{attr}; $_[0] = $NUM }
},
OUTPUTFILE=> 'main.pm'
);
$p->generate(); # Create the tranformations
$t->s(@all); # constant folding and mult. by zero
print $t->str,"\n";
when running this example with input C<"a=2*-3+b*0\n">
we obtain the following output:
nereida:~/src/perl/YappWithDefaultAction/examples> bypass.pl
************
EXPRESION_LIST(ASSIGN(TERMINAL[a],PLUS(TIMES(NUM[2],UMINUS(NUM[3])),TIMES(VAR[b],NUM[0]))))
************
EXPRESION_LIST(ASSIGN(TERMINAL[a],NUM[-6]))
As you can see the trees are more compact when using the C<bypass> directive.
=head3 The C<alias> clause of the C<%tree> directive
Access to children in L<Parse::Eyapp> is made through the C<child> and C<children>
methods.
There are occasions however where access by name to the children may be preferable.
The use of the C<alias> clause with the C<%tree> directive creates accessors
to the children with names specified by the programmer. The I<dot and dolar notations>
are used for this. When dealing with a production like:
A:
%name A_Node
Node B.bum N.pum $Chip
methods C<bum>, C<pum> and C<Chip> will be created for the class C<A_Node>.
Those methods wil provide access to the respective child (first, second and third in
the example). The methods are build at compile-time and therefore later
transformations of the AST modifying the order of the children may
invalidate the use of these getter-setters.
As an example, the CPAN module L<Language::AttributeGrammar> provides
AST decorators from an attribute grammar specification of the AST.
To work L<Language::AttributeGrammar> requires named access to the children
of the AST nodes. Follows an example (file C<examples/CalcwithAttributeGrammar.pl>)
of a small calculator:
pl@nereida:~/LEyapp/examples$ cat -n CalcwithAttributeGrammar.pl
1 #!/usr/bin/perl -w
2 use strict;
3 use Parse::Eyapp;
4 use Data::Dumper;
5 use Language::AttributeGrammar;
6
7 my $grammar = q{
8 %{
9 # use Data::Dumper;
10 %}
11 %right '='
12 %left '-' '+'
13 %left '*' '/'
14 %left NEG
15 %tree bypass alias
16
17 %%
18 line: $exp { $_[1] }
19 ;
20
21 exp:
22 %name NUM
23 $NUM
24 | %name VAR
25 $VAR
26 | %name ASSIGN
27 $VAR '=' $exp
28 | %name PLUS
29 exp.left '+' exp.right
30 | %name MINUS
31 exp.left '-' exp.right
32 | %name TIMES
33 exp.left '*' exp.right
34 | %name DIV
35 exp.left '/' exp.right
36 | %no bypass UMINUS
37 '-' $exp %prec NEG
38 | '(' $exp ')' { $_[2] } /* Let us simplify a bit the tree */
39 ;
40
41 %%
42
43 sub _Error {
44 exists $_[0]->YYData->{ERRMSG}
45 and do {
46 print $_[0]->YYData->{ERRMSG};
47 delete $_[0]->YYData->{ERRMSG};
48 return;
49 };
50 print "Syntax error.\n";
51 }
52
53 sub _Lexer {
54 my($parser)=shift;
55
56 $parser->YYData->{INPUT}
57 or $parser->YYData->{INPUT} = <STDIN>
58 or return('',undef);
59
60 $parser->YYData->{INPUT}=~s/^\s+//;
61
62 for ($parser->YYData->{INPUT}) {
63 s/^([0-9]+(?:\.[0-9]+)?)//
64 and return('NUM',$1);
65 s/^([A-Za-z][A-Za-z0-9_]*)//
66 and return('VAR',$1);
67 s/^(.)//s
68 and return($1,$1);
69 }
70 }
71
72 sub Run {
73 my($self)=shift;
74 $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error,
75 #yydebug =>0xFF
76 );
77 }
78 }; # end grammar
79
80
81 $Data::Dumper::Indent = 1;
82 Parse::Eyapp->new_grammar(
83 input=>$grammar,
84 classname=>'Rule6',
85 firstline =>7,
86 outputfile => 'Calc.pm',
87 );
88 my $parser = Rule6->new();
89 $parser->YYData->{INPUT} = "a = -(2*3+5-1)\n";
90 my $t = $parser->Run;
91 print "\n***** Before ******\n";
92 print Dumper($t);
93
94 my $attgram = new Language::AttributeGrammar <<'EOG';
95
96 # Compute the expression
97 NUM: $/.val = { $<attr> }
98 TIMES: $/.val = { $<left>.val * $<right>.val }
99 PLUS: $/.val = { $<left>.val + $<right>.val }
100 MINUS: $/.val = { $<left>.val - $<right>.val }
101 UMINUS: $/.val = { -$<exp>.val }
102 ASSIGN: $/.val = { $<exp>.val }
103 EOG
104
105 my $res = $attgram->apply($t, 'val');
106
107 $Data::Dumper::Indent = 1;
108 print "\n***** After ******\n";
109 print Dumper($t);
110 print Dumper($res);
=head1 SEE ALSO
=over
=item *
L<Parse::Eyapp>,
L<Parse::Eyapp::eyapplanguageref>,
L<Parse::Eyapp::debugingtut>,
L<Parse::Eyapp::defaultactionsintro>,
L<Parse::Eyapp::translationschemestut>,
L<Parse::Eyapp::Driver>,
L<Parse::Eyapp::Node>,
L<Parse::Eyapp::YATW>,
L<Parse::Eyapp::Treeregexp>,
L<Parse::Eyapp::Scope>,
L<Parse::Eyapp::Base>,
=item * The pdf file in L<http://nereida.deioc.ull.es/~pl/perlexamples/languageintro.pdf>
=item * The pdf file in L<http://nereida.deioc.ull.es/~pl/perlexamples/debuggingtut.pdf>
=item * The pdf file in L<http://nereida.deioc.ull.es/~pl/perlexamples/eyapplanguageref.pdf>
=item * The pdf file in L<http://nereida.deioc.ull.es/~pl/perlexamples/Treeregexp.pdf>
=item * The pdf file in L<http://nereida.deioc.ull.es/~pl/perlexamples/Node.pdf>
=item * The pdf file in L<http://nereida.deioc.ull.es/~pl/perlexamples/YATW.pdf>
=item * The pdf file in L<http://nereida.deioc.ull.es/~pl/perlexamples/Eyapp.pdf>
=item * The pdf file in L<http://nereida.deioc.ull.es/~pl/perlexamples/Base.pdf>
=item * The pdf file in L<http://nereida.deioc.ull.es/~pl/perlexamples/translationschemestut.pdf>
=item * The pdf file in L<http://nereida.deioc.ull.es/~pl/perlexamples/MatchingTrees.pdf>
=item * The tutorial I<Parsing Strings and Trees with> C<Parse::Eyapp>
(An Introduction to Compiler Construction in seven pages) in
L<http://nereida.deioc.ull.es/~pl/eyapsimple/>
=item *
perldoc L<eyapp>,
=item *
perldoc L<treereg>,
=item *
perldoc L<vgg>,
=item * The Syntax Highlight file for vim at L<http://www.vim.org/scripts/script.php?script_id=2453>
and L<http://nereida.deioc.ull.es/~vim/>
=item * I<Analisis Lexico y Sintactico>, (Notes for a course in compiler
construction) by Casiano Rodriguez-Leon.
Available at L<http://nereida.deioc.ull.es/~pl/perlexamples/>
Is the more complete and reliable source for Parse::Eyapp. However is in Spanish.
=item *
L<Parse::Yapp>,
=item *
Man pages of yacc(1),
=item *
Man pages of bison(1),
=item *
L<Language::AttributeGrammar>
=item *
L<Parse::RecDescent>.
=item *
L<HOP::Parser>
=item *
L<HOP::Lexer>
=item * ocamlyacc tutorial at
L<http://plus.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-tutorial/ocamlyacc-tutorial.html>
=back
=head1 REFERENCES
=over
=item *
The classic Dragon's book I<Compilers: Principles, Techniques, and Tools>
by Alfred V. Aho, Ravi Sethi and
Jeffrey D. Ullman (Addison-Wesley 1986)
=item *
I<CS2121: The Implementation and Power of Programming Languages>
(See L<http://www.cs.man.ac.uk/~pjj>, L<http://www.cs.man.ac.uk/~pjj/complang/g2lr.html>
and L<http://www.cs.man.ac.uk/~pjj/cs2121/ho/ho.html>) by
Pete Jinks
=back
=head1 AUTHOR
William N. Braswell, Jr. <wbraswell_cpan@NOSPAM.nym.hush.com>
(Remove "NOSPAM".)
=head1 ACKNOWLEDGMENTS
This work has been supported by CEE (FEDER) and the Spanish Ministry of
I<Educacion y Ciencia> through I<Plan Nacional I+D+I> number TIN2005-08818-C04-04
(ULL::OPLINK project L<http://www.oplink.ull.es/>).
Support from Gobierno de Canarias was through GC02210601
(I<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 L<Parse::Yapp> 1.05.
The author of L<Parse::Yapp> is Francois Desarmenien.
I wish to thank Francois Desarmenien for his L<Parse::Yapp> module,
to my students at La Laguna and to the Perl Community. Special thanks to
my family and Larry Wall.
=head1 LICENSE AND COPYRIGHT
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.
These modules are free software; you can redistribute it and/or
modify it under the same terms as Perl itself. See L<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.