语法 LL(1) 悬挂 else 和公共左前缀

Question

相信看过的人都对悬空else歧义不陌生。因此我将跳过解释。我在一本编译器书（龙书）上找到了一个没有歧义的语法，表示 IF 和 ELSE。在这里。

stmt->matched_stmt | open_stmt
matched_stmt->if exp then matched_stmt else matched_stmt | other
open_stmt->if exp then stmt | if exp then matched_stmt else open_stmt

问题是：

open_stmt->if exp then stmt | if exp then matched_stmt else open_stmt

为了使我在 LL(1) 语法上工作的语法，我需要消除左公共前缀，在这种情况下，左公共前缀是：

if exp then

当我尝试制造它时，它又变得模棱两可，这就是我尝试过的。

stmt->matched_stmt | open_stmt
matched_stmt->if exp then matched_stmt else matched_stmt | other
open_stmt->if exp thenO'
O'->stmt | matched_stmt else open_stmt

哪个是歧义的，谁能帮我让它不歧义并且没有共同的左前缀？非常感谢

Answer 1

我不相信可以编写一个 LL(1) 文法来处理其他悬垂问题，尽管编写一个这样做的递归下降解析器是微不足道的。

在递归下降解析器中，当您解析完表达式后的第一条语句后，如果您看到 else，您将继续生成。否则，您已完成对 if 语句的解析。换句话说，您只是贪婪地解析 else 子句。

但是该算法不能表示为 CFG，而且我一直认为不可能编写一个明确的 LL(1) CFG 来处理悬垂的 else，因为当您到达 S1 的开头时

if E then S1 ...

您仍然不知道它属于哪个作品。事实上，直到到达 S1 的末尾你才知道，无论 k 有多大，这肯定为时已晚，无法做出 LL(k) 决定。

但是，这个解释有很多人在挥手，而且我从来没有觉得它完全令人满意。所以我很高兴地拿起我破旧的龙之书（1986 年版）并阅读了第 192 页（第 4.4 节中的"LL(1) grammars"，"Top-down grammars"）语法 4.13（if-then-optional -else 语法) "has no LL(1) grammar at all".

以下段落以合理的建议结尾："if an LR parser generator… is available, one can get all of the benefits of predictive parsing and operator precedence automatically." 我的旁注（我猜是从 1986 年左右开始的）是 "So why did I just study this whole chapter????"；今天，我倾向于对 Dragon 书的作者更慷慨，但不会建议任何人实际使用一个解析器生成器，它至少不如LALR(1) 解析器生成器。

语法 LL(1) 悬挂 else 和公共左前缀

Grammar LL(1) Dangling else and common left prefix

regex

compiler-construction

grammar

ll