Re: Need help with grammars!

dan.hovang@usa.net writes:


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


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


>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 (torbenm@diku.dk)
--

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