2

Given this grammar:

<Program>     ::= <Stmt> | <Program>; <Stmt>  
<Conditional> ::= If <Bool> then <Program>  
<Bool>        ::= true | false  
<Stmt>        ::= <Conditional> | s1 | s2

How do I prove that it is ambiguous?

icktoofay
  • 126,289
  • 21
  • 250
  • 231
Jade
  • 335
  • 1
  • 2
  • 12
  • 1
    You could provide two different derivations of the same sentence. – Matt Fenwick Nov 26 '13 at 18:06
  • By finding two possible parses for some sentence. Try this one: `If true then s1; s2` – rici Nov 26 '13 at 18:07
  • This question has already been asked and answered: http://stackoverflow.com/questions/4788148/what-is-the-easiest-way-of-telling-whether-a-bnf-grammar-is-ambiguous-or-not?rq=1 – Matt Fenwick Nov 26 '13 at 19:15

1 Answers1

2

If you can draw two parse trees (or equivalently, write two leftmost derivations) for the same sentence, the grammar is ambiguous. No general algorithm exists to do this (ambiguity is an undecidable problem), but for many grammars it's not hard.

The example @rici gave is sufficient. 

If true then s1; s2

One parse tree is 

    <Program>
    /     |  \
<Program> ; <Stmt>
    |         |
 <Stmt>       s2
   /|\__________
  / |     \     \
If <Bool> then <Program>
    |              |
    true         <Stmt>
                   |
                   s1

I will let you work out the other one.

Gene
  • 46,253
  • 4
  • 58
  • 96