Re: JavaCUP and actions

Chris Dodd <cdodd@acm.org>
28 Apr 2005 14:30:01 -0400

          From comp.compilers

Related articles
JavaCUP and actions stofte@gmail.com (Svend Tofte) (2005-04-26)
Re: JavaCUP and actions cdodd@acm.org (Chris Dodd) (2005-04-28)
Re: JavaCUP and actions cfc@shell01.TheWorld.com (Chris F Clark) (2005-04-28)
| List of all articles for this month |

From: Chris Dodd <cdodd@acm.org>
Newsgroups: comp.compilers
Date: 28 Apr 2005 14:30:01 -0400
Organization: Compilers Central
References: 05-04-069
Keywords: parse, LALR

[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


Post a followup to this message

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