曖昧語法（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 

我會讓你的工作的另一個。