Re: Need help with grammars!

Torben Mogensen <>
7 May 1998 16:49:30 -0400

          From comp.compilers

Related articles
Need help with grammars! (1998-04-15)
Re: Need help with grammars! (John Williams) (1998-04-21)
Re: Need help with grammars! (Torben Mogensen) (1998-05-07)
| List of all articles for this month |

From: Torben Mogensen <>
Newsgroups: comp.compilers
Date: 7 May 1998 16:49:30 -0400
Organization: Compilers Central
References: 98-04-064
Keywords: parse, Java writes:

>This is propably real basic stuff. I'm using java_cup and have the

>lvalue ::= id | id [ exp ] | lvalue . lvalue
>exp ::= id ( functargs )
>exp ::= id [ arrayinit ]
>exp ::= lvalue
>exp ::= lvalue := exp
>exp ::= exp + exp

>There are semantic actions attached to each production which I omitted. I get
>ambiguity warnings when running java_cup since it dont know if it should
>shift id (exp ::= id (.. | exp ::= id [ ..) or reduce (lvalue ::= id).

The obvious problem is the (lvalue ::= lvalue . lvalue) production,
which makes the grammar ambigous. This can, however be solved by
declaring '.' to be left associative.

As the grammar is written above, you should not get a shift/reduce
error after an id. The only other possible conflict is between
arrayinit and exp: If these have a non-empty intersection, you'll get
a reduce/reduce conflict at the symbol ']'.

However, I have a feeling that the grammar you have is not exactly as
you wrote it above. I have had a problem with the symptoms you
describe with a (very similar) grammar for the Tiger language in
Andrew Appels book. In this, the grammar is

                lvalue -> id | lvalue [ exp ] | lvalue . id
                exp -> lvalue | lvalue := exp | id [ exp ] of exp | ...

Note that this grammar allows multi-dimensional array lookups like
"x[2][3]", which Dan's grammar does not.

While this grammar is unambigous (at least for the fragment given), it
generates a shift/reduce conflict in the set of items which contains
(among other things) the following items:

                lvalue -> id
                exp -> id [ exp ] of exp

The conflict happens because '[' is in follow(lvalue). Since it is the
production (lvalue -> lvalue [ exp ]) which causes '[' to be in
follow(lvalue), the solution is to rewrite the productions for lvalue
such that we avoid this production (and any that adds '[' to
follow(lvalue)). We can do this by eliminating the left-recursion in
the productions for lvalue:

                lvalue -> id lvalue'
                lvalue' -> \epsilon | [ exp ] lvalue' | . id lvalue'

Now the only symbols in follow(lvalue) are ':=' and the symbols in
follow(exp), which (in Tiger) does not include '['. Hence, the
conflict is gone.

                Torben Mogensen (

Post a followup to this message

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