algorithm - 歧义语法（BNF 表示法）

Question

鉴于此语法：

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

我如何证明它是模棱两可的？

Answer 1

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.