我得出以下语法：
S -> a | aT
T -> b | bR
R -> cb | cbR
我知道为了使语法成为 LL(1)，它必须是明确的和右递归的。问题是我不完全理解左递归和右递归语法的概念。我不知道以下语法是否正确递归。我真的很感激对左递归和右递归语法的概念的简单解释，如果我的语法是 LL(1)。
非常感谢。
问问题
4257 次
2 回答
5
该文法不是 LL(1)。在 LL(1) 解析器中，应该始终可以根据当前的非终结符和输入的下一个标记来确定下一个使用哪个产生式。
让我们看一下这个制作，例如：
S → a | 在
现在，假设我告诉你当前的非终结符是 S，而下一个输入符号是 a。你能确定使用哪个产品吗？不幸的是，没有更多的上下文，你不能这样做：也许你应该使用 S → a，也许你应该使用 S → aT。使用类似的推理，您可以看到所有其他产品都有类似的问题。
这与左递归或右递归没有任何关系，而是一个事实，即 LL(1) 语法中同一个非终结符的两个产生式不能有一个非空的公共前缀。事实上，检查一个文法是否不是LL(1) 的简单启发式方法是看你是否能找到两个这样的产生式规则。
希望这可以帮助！
于 2013-10-20T06:32:07.263 回答
4
该文法只有一个递归规则：最后一个 R 是左边的符号，也出现在右边。它是右递归的，因为在语法规则中，R 是最右边的符号。该规则引用 R，并且该引用是最右边的。
语言是 LL(1) 。我们如何知道这一点是因为我们可以很容易地构造一个不使用回溯并且最多使用一个前瞻标记的递归下降解析器。
但是这样的解析器将基于稍微修改过的语法版本。
例如，两个产生式：S -> a和S -> a T可以合并成一个可以由 EBNF 表示的产生式S -> a [ T ]。（S派生a，后跟可选T）。该规则可以由用于识别的单个解析函数处理S。
该函数匹配a然后查找可选的T，这将由下一个输入符号指示b。
我们可以为此编写一个 LL(1) 语法，如下所示：
S -> a T_opt
T_opt -> b R_opt
T_opt -> <empty>
... et cetera
的可选性T被显式处理，通过使T（我们将其重命名为T_opt）能够派生空字符串，然后将 压缩为单个规则S，因此我们没有两个都以 开头的短语a。
所以总而言之，语言是 LL(1)，但给定的语法不是。由于语言是 LL(1)，因此可以找到另一种语法是 LL(1)，并且该语法与给定的语法相距不远。
于 2013-10-20T06:08:11.243 回答