неоднозначных грамматик (BNF ОБОЗНАЧЕНИЯ)

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 

Я дам вам работать другой.