时间戳

首页 > 解决方案 > 无法为递归下降解析器获得 LL(1) 形式的语法

parsing - 无法为递归下降解析器获得 LL(1) 形式的语法

问题描述

我有语法：

S -> bU | ad | d
U -> Ufab | VSc | bS
V -> fad | f | Ua

要构建递归下降解析器，我需要 LL(1) 形式。我得到的最好的是：

S -> bU | ad | d
U -> fY | bSX
Y -> adScX | ScX
X -> fabX | aScX | ε

删除了左递归并做了一些左分解，但我被卡住了。尝试了几个小时，但我无法得到它......

例如，有效的字符串是：

显然我的语法形式对某些人来说是模棱两可的，所以我不能制作递归下降解析器......

从答案：

S -> bU | ad | d
U -> fYZ | bSZ
X -> fab | aSc
Y -> adA | bUc | dc
Z -> ε | XZ
A -> Sc | c

仍然不是 LL(1)。Z 的 First 和 follow 不相交。

标签： parsingcompiler-constructioncontext-free-grammarrecursive-descentambiguous-grammar

解决方案

通常，要制作语法 LL(1)，您需要反复左因子并删除左递归，直到您设法摆脱所有非 LL 事物。您首先执行的操作取决于语法，但在这种情况下，您需要从左分解开始

左因子规则

U -> Ufab | VSc | bS

你需要先用 V 代替

U -> Ufab | fadSc | fSc | UaSc | bS

然后你把它留给了

U -> UX | fY | bS
X -> fab | aSc
Y -> adSc | Sc

现在 U 很简单，您可以直接消除左递归：

U -> fYZ | bSZ
Z -> ε | XZ

给你

S -> bU | ad | d
U -> fYZ | bSZ
X -> fab | aSc
Y -> adSc | Sc
Z -> ε | XZ

现在你仍然有 Y 的左分解问题，所以你需要替换 S：

Y -> adSc | bUc | adc | dc

你留下的因素

Y -> adA | bUc | dc
A -> Sc | c

给出一个几乎 LL(1) 的语法：

S -> bU | ad | d
U -> fYZ | bSZ
X -> fab | aSc
Y -> adA | bUc | dc
Z -> ε | XZ
A -> Sc | c

但是现在事情被卡住了，因为 Z 的 epsilon 规则意味着我们需要 FIRST(X) 和 FOLLOW(Z) 是不相交的（以便在两个 Z 规则之间做出决定）。这通常表示非 LL 语言，因为有一些尾随上下文可能与多个规则相关联（通过S -> bU -> bbSZ -> bbbUZ -> bbbbSZZ扩展链 - 尾随 Z 可以被识别，但可能是空的）。通常，您仍然可以使用简单的递归下降解析器（或 LL 样式的状态表）通过简单地解决 Z 歧义/冲突以支持非 epsilon 规则来识别这种语言。

推荐阅读