algorithm - 歧义文法(BNF表示法)

This question already has answers here:

What is the easiest way of telling whether a BNF grammar is ambiguous or not?
（2个答案）
根据这个语法：

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

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

最佳答案

如果您可以为同一个句子绘制两个解析树（或者等价地，编写两个最左边的派生），那么语法是不明确的没有通用算法来执行（模糊性是一个不可判定的问题），但是对于许多语法来说，这并不难。
@rici给出的例子就足够了。

If true then s1; s2

一个解析树是

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

我会让你解决另一个问题。

关于algorithm - 歧义文法(BNF表示法)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20224227/