6

We are learning about ambiguity in class, and the following grammar was given as an example of an ambiguous grammar. I just am not seeing how it is ambiguous. Is there a set pattern or method people use to determine ambiguity or is it just like a logic puzzle where you have to work through combinations to find an ambiguous sentence in the grammar? The examples I've read online mostly given the ambiguous sentence already, but how do you find that sentence in the first place? I'd appreciate any help, thank you.

< stmt_list> ==> < stmt>

               | < stmt> ; < stmt_list>

< var> ==> A | B | C

< stmt> ==> < var> + < var>

               | < var> - < var>

               | < var>
Anderson Green
  • 30,230
  • 67
  • 195
  • 328
Mint Dreyer
  • 61
  • 4
  • I made mistake in my answer thats why I remove you present grammar is not ambiguous. – Grijesh Chauhan Mar 02 '13 at 16:04
  • @GrijeshChauhan I see. Thank you. This is very confusing because our professor told us this was ambiguous. – Mint Dreyer Mar 02 '13 at 16:06
  • But your grammar is not correct for the purpose of math expression too :( view this example for correct http://stackoverflow.com/questions/14554752/how-can-i-add-parentheses-as-the-highest-level-of-precedence-in-a-simple-grammar/14569166#14569166 – Grijesh Chauhan Mar 02 '13 at 16:07
  • This must have been asked upteem times, but @DPenner's very concise answer makes this Q&A a keepr. – Apalala Mar 03 '13 at 14:55

1 Answers1

2

In general, determining whether a grammar is ambiguous or not is undecidable. So yes, finding an ambiguous sentence in a grammar reduces to a very difficult logic puzzle. Solving specific cases and finding heuristics is an active area of research though. Here is a fairly good tool at finding ambiguity: http://www.brics.dk/grammar/. The webpage includes a link to a paper explaining how it works, though honestly, that goes over my head.

DPenner1
  • 10,037
  • 5
  • 31
  • 46