C 程序的 IF-ELSE 条件的 LL1 语法

Question

我必须生成涵盖 C 程序的 IF、IF-ELSE、IF - ELSE IF - ELSE 条件的 LL1 语法。我正在执行以下操作，但无法解决递归问题，所以我认为可能是我的语法错误或不满足 LL1 条件。

你能告诉我语法是否正确吗？

<MAIN> ::= int main () { <PROG> <AUX_PROG> }
<AUX_PROG> ::= <PROG> <AUX_PROG> | ε
<PROG> ::= <IF_STAT> | other | ε
<IF_STAT> ::= if ( other ) { <PROG> } <ELSE_STAT>
<ELSE_STAT> ::= else { <PROG> } | ε


follow(PROG) = { "}", if, other }
follow(AUX_PROG) = { "}" }
follow(IF_STAT) = follow(PROG) = { "}", if, other }
follow(ELSE_STAT) = follow(IF_STAT) = { "}", if, other }
follow(MAIN) = { $ }

first(MAIN) = { int }
first(AUX_PROG) = { if, other, ε }
first(PROG) = { if, other, ε }
first(IF_STAT) = { if }
first(ELSE_STAT) = { else, ε }

更新：我修改了语法，还包括了第一个和后面的内容。大括号是必需的，这样就没有悬空问题。

Answer 1

该语法有歧义，因为 <PROG> ::= ε 使 <AUX_PROG> ::= <PROG> <AUX_PROG> left-recursive。如果您消除 <PROG> 的空产生式，那么语法肯定是 LL(1).

但是仅仅成为 LL(1) 并不能证明语法正确地识别了所需的语法，更不用说它正确地将每个输入解析为所需的解析树了。所以这绝对取决于你如何定义“正确”。由于您的问题并没有真正指定您希望匹配的语法，也没有指定您希望对其进行分析的形式，因此很难对这些形式的正确性发表评论。

你完全正确地注意到 C 的 dangling-else 问题的核心是 C 不需要分隔 if 和 else 子句的主体。所以下面是合法的 C:

if (condition1) if (condition2) statement1; else statement2;

并且语言的规则导致 else statement2 绑定到 if (condition2)，而不是第一个 if。

这通常被称为歧义，但实际上很容易消除歧义。您会发现消歧技术随处可见，包括 Wikipedia's somewhat ravaged entry on dangling else 或大多数流行的编程语言教科书。但是，消歧技术不会产生 LL(1) 文法；您需要使用 bottom-up 解析器。（即使是运算符优先解析器也可以处理它，但 LALR(1) 解析器可能更常见。）

正如维基百科指出的那样，一个简单的解决方案是更改语法以消除 if (c1) if (c2) ... 的可能性。一种简单的方法是坚持以某种方式分隔 if 的目标，例如添加大括号（如果 body 不止一个语句，无论如何都需要） .没有必要对 else 子句的 body 提出相同的要求，但这可能会使语言用户感到困惑。但是，允许这样的链式 if...else 结构很方便：

if (c1) {
    body1
}
else if (c2) {
    body2
}
else if (c3) {
    body3
}
...

这不是模棱两可的，即使每个 else 的 body 没有分隔。在某些语言中，为了保留 else 子句必须是分隔块。但是简单地允许 else if 作为关于身体的一般规则的例外并不算太古怪。

因此，如果您正在设计一种语言，您有多种选择。如果您正在实施其他人的语言（例如课程讲师提供的语言），您需要确保了解他们的要求。

C 程序的 IF-ELSE 条件的 LL1 语法

LL1 grammar for IF-ELSE condition for a C program

c

compiler-construction

grammar

if-statement