BNF歧义

Question

“编译构造”一书给出了Algol 60最初定义的一个例子。它们含有模棱两可之处。

至少找到两种不同的结构

IF a THEN b ELSE c=d

有一部分的定义

unconditional Statement = basicStatement | forStatement | compoundStatement | ... .
ifStatement = "IF" BooleanExpression "THEN" unconditionalStatement.
conditionalStatement = ifStatement | ifStatement "ELSE" statement.

statement = unconditionalStatement | conditionalStatement. 

因此，既然：

A "else" B, and A => "if" a "then" b

我们得到：

if a then b else B

看起来，B是c=d

含糊不清在哪里？如何找到两种不同的结构？

Answer 1

IF a THEN b ELSE c=d不是一种声明。它是某种形式的表达式；它是什么类型取决于b的类型。(这个语句将是IF a THEN b ELSE c:=d.回忆，在Algol中，:=是赋值，=是相等比较，==是语法错误。)

如果b是布尔表达式，那么它是一个布尔条件表达式，其替代方法是b和c=d；在本例中，c和d必须具有算术类型，因为语法不允许将布尔值与=进行比较。

但是，如果b是算术的，那么它是比较IF a THEN b ELSE c和d (同样，c和d必须有算术类型)。

至少，这是我对语法的解读。它不完全是模棱两可的，但BNF不足以解析解析，因为该语言不是上下文无关的。选择正确的解析需要b的先前声明，这只能通过上下文敏感的语法来实现。