BNF歧义
BNF ambiguities
"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
歧义在哪里?
如何找到两个不同的结构?
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
的前面的声明,这只能通过上下文相关的语法来实现。
"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
歧义在哪里? 如何找到两个不同的结构?
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
的前面的声明,这只能通过上下文相关的语法来实现。