语法LL（1）悬于其他和常见的左前缀

Question

我相信读它的每个人都熟悉其他模糊不清的问题。所以我会跳过解释。 我在一本编译器书（dragon book）上找到了代表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->如果EXP然后stmt是|如果EXP然后matched_stmt其他open_stmt

为了使我的工作语法上的LL（1）语法，我需要消除左共同的前缀，而在这种情况下，离开共同的前缀是：

如果EXP然后

当我尝试它的工厂然后重新变得模糊，这是我的尝试。

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 

这是不明确的，任何人都可以帮助我使它不ambigous和没有共同的左前缀？非常感谢你

Answer 1

我不认为有可能写一个LL（1）语法，它将处理其他的悬挂，尽管编写一个递归下降解析器是很简单的。

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

但该算法不能表示为CFG，我一直认为这是不可能写出一个明确的LL（1）CFG负责处理别人的晃来晃去，因为当你在

达到S1的开始

if E then S1 ... 

您仍然不知道哪些产品是其中的一部分。事实上，直到S1结束时才知道，无论做出多大的k，无论做出LL（k）决定都为时过晚。

但是，这种解释有很多手摇，我从来没有发现它完全令人满意。所以我很高兴拿起我的龙书（1986年版）的副本，并在第192页（第4.4节“自上而下语法”中的“LL（1）语法）”中读到，语法4.13（if-然后 - 可选 - 其他语法）“根本没有LL（1）语法”。

以下段落以合理的建议结束：“如果LR解析器生成器可用，则可以自动获得预测解析和运算符优先级的所有好处。”我的边际说明（从大约1986年开始）我读到“那么，为什么我只研究这整章？”;今天，我倾向于对Dragon书籍的作者更加慷慨，但并不意味着任何人实际上都使用了一个解析器生成器，它至少不像LALR（1）解析器生成器那样强大。