Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there a set way to determine ambiguity in a grammar?

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>
like image 420
Mint Dreyer Avatar asked Mar 02 '13 15:03

Mint Dreyer


1 Answers

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.

like image 117
DPenner1 Avatar answered Dec 02 '22 05:12

DPenner1