7 May 1998 16:49:30 -0400

Related articles |
---|

Need help with grammars! dan.hovang@usa.net (1998-04-15) |

Re: Need help with grammars! jrw@pobox.com (John Williams) (1998-04-21) |

Re: Need help with grammars! torbenm@diku.dk (Torben Mogensen) (1998-05-07) |

From: | Torben Mogensen <torbenm@diku.dk> |

Newsgroups: | comp.compilers |

Date: | 7 May 1998 16:49:30 -0400 |

Organization: | Compilers Central |

References: | 98-04-064 |

Keywords: | parse, Java |

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)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.