Неоднозначные грамматики (BNF NOTATION)

Question

Учитывая эту грамматику:

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

Как мне доказать, что это неоднозначно?

Answer 1

Если вы можете нарисовать два дерева разбора (или, что то же самое, написать два крайних левых вывода) для одного и того же предложения, грамматика будет неоднозначной. Для этого не существует общего алгоритма (двусмысленность - неразрешимая проблема), но для многих грамматик это не сложно.

Пример @rici дал достаточно.

If true then s1; s2

Одно дерево разбора

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

Я позволю тебе потренироваться с другим.