Finding ambiguous statements, given the context free grammar

2
votes

I have a homework assignment, in which i'm supposed to detect ambiguities in a statement, given the grammar in which the statement is defined.

Example:

Grammar: S -> S + S | S * S | id
Statement: id * id + id

The above statement is ambiguous because two parse trees are possible.

I have the following ambiguities in mind as of now:

1) Operator precedence (example above)
2) If-else dangling case
3) Infinite loop (example above is left recursive)
4) Associativity

Could you tell me any more which would be doable?

I have to design this parser using lex and bison (yacc), and submit it in 2 days, so any pointers would be helpful on the ambiguities in the grammar and in the statement.

2
bisonlexcontext-free-grammarambiguous
You might consider asking such questions at the new Computer Science Stack Exchange site: cs.stackexchange.com - Patrick87
@Patrick87: Thanks for the tip! - Khushman Patel
@Patrick87 IMHO, its more suitable for CSTheory :) - Pale Blue Dot

2 Answers

1
votes

Well, if you have lex and bison at your command you could simply feed the grammar into bison and it will tell you if it is ambiguous or not.

Otherwise, you'll have to construct the entire LALR1 parser generator algorithm in order to determine if there are conflicts which makes the grammar ambiguous. Those conflicts are detected pretty late in the parser construction stages (my parser generator finds them in the table generation step). Perhaps you can take some pointers from how my code does it, it is found at https://github.com/Dervall/Piglet

The classical case of shift/reduce and reduce/reduce in a bottom up parser occurs when you try to fill in a part of the action table which has already been filled with an entry that has the same precedence as the token that you try to put in it.

If you are talking about LL parsers, the infinite loop isn't really a case of an ambiguous grammar - the grammar can be refactored into being non ambiguous.

And the statement itself won't in any way affect wheter the grammar is ambiguous. It was ambiguous regardless of what input it was given.

1
votes

In general you can't -- grammar ambiguity is undecidable.

That said, there are a number of grammar patterns that you can recognize that are obviously ambiguous.

  • Any (non-useless) non-terminal that is both left- and right- recursive is ambiguous (covers all the cases you note above except dangling else).
  • Any (non-useless) non-terminal with two right-recursive rules one of which is a prefix of the other is ambiguous (covers dangling-else).