Re: JavaCUP and actions

[posted and mailed]


"Svend Tofte" <stofte@gmail.com> wrote in news:05-04-069@comp.compilers:
> Given an ordinary expression grammar, for example:
>
> E ::= E PLUS:p T | T ;
> T ::= T TIMES:t F | F ;
> F ::= LPAREN:l E RPAREN:r | NUMBER:n ;
>
> JavaCUP eats it up fine. However, if I proceed to add actions to the
> first production, such as:
>
> E ::= {: System.out.print("<E>"); :}
> E
> PLUS:p
> {: System.out.print(p); :}
> T
> {: System.out.print("</E>"); :}
>
> Then I get some six shift/reduce errors. Which on one hand seems fine
> (how can it know, so early in the parse, that this production is it).


As the moderator notes, the problem is that embedded actions introduce
extra rules, and those extra rules introduce conflicts. What's
particularly annoying here is that there generally don't need to be
conflicts -- the conflicts tend to come from identical embedded
actions. So if the parser would recognize the actions are identical,
and use the same extra symbol for them, it would be ok. Fortunately,
you can get around this by adding your own fake symbols.


For example, from your example you probably have:


        E ::= {: System.out.print("<E>"); :}
E
PLUS:p
{: System.out.print(p); :}
T
{: System.out.print("</E>"); :}
| {: System.out.print("<E>"); :}
T
{: System.out.print("</E>"); :}
;


Which gives you a reduce/reduce conflict on the two extra symbols
introduced for the "{: System.out.print("<E>"); :}" rules. If you
instead do it yourself with a single rule:


        E ::= _begin_E_
E
PLUS:p
{: System.out.print(p); :}
T
{: System.out.print("</E>"); :}
| _begin_E_
T
{: System.out.print("</E>"); :}
;
        _begin_E_ ::= {: System.out.print("<E>"); :} ;


the conflict goes away...


Alternatively, you can use a parser generator such as btyacc which
automatically combines such identical actions.


Chris Dodd
cdodd@acm.org

Return to the comp.compilers page.
Search the comp.compilers archives again.