BNF歧义

Question

"Compiler construction" 书中给出了 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的前面的声明，这只能通过上下文相关的语法来实现。

BNF歧义

BNF ambiguities

compiler-construction

bnf