问题标签 [ll]

我正在尝试解析一种简单的语言。问题在于解析函数调用。我试图告诉它函数调用是一个表达式，后跟左括号、参数列表和右括号。我有这样的事情：

问题很明显：expr是左递归的。但是，我不知道该怎么做才能解决这个问题。我对右递归式语法（又名 PLY、Yacc 等）很有经验，但我仍在尝试找出左递归语法。

我知道：

如果一种语言可以由 LL(1) 语法生成，则称该语言为 LL(1)。可以证明 LL(1) 文法是

但我遇到了一个问题。

为什么语法

S-> aBDb

B -> 拉姆达

D-> dD | 拉姆达

为什么这个语法不是 LL(1) 也不是 SLR 也不是 LALR？谁能形容我？

如果我理解正确，解析会将一系列符号变成一棵树。我的问题是，是否可以使用一些标准程序（LR、LL、PEG、..？）来解析以下两个示例，或者是否有必要手动编写专门的解析器？

1. Python 源代码，即空格缩进的块

我想我在某处读到解析器跟踪前导空格的数量，并假装用大括号替换它们来分隔块。是因为标准解析技术不够强大还是出于性能原因而从根本上需要它？

2. PNG图像格式，块以标头和块大小开头，之后是块的内容

内容可能包含类似于某些标头的字节，因此有必要“知道”接下来的 x 个字节不会被“解析”，即应该跳过它们。比如说，如何用 PEG 来表达这一点？换句话说，“右括号”由内容的长度表示。

我有以下语法：

如何将其转换为 LL(1) 语法？

我试图消除左递归，所以我得到了

我还尝试先进行左分解，然后消除左递归，我得到了类似的结果：

但我仍然没有得到完美的答案。我觉得语法仍然不是 LL(1)。请帮忙。

这是我的语法：

这对测试用例很有用：

但是，我还需要让它能够识别：

语法规则如下：

应该匹配它并产生正确解析的语法。该规则在早期版本中有效，但在我修改语法以支持在表达式中包含括号时被删除。

我已经读过启用回溯应该能够在这些情况下提供帮助，但是文档似乎表明通常应该避免回溯。

如何在没有 LL 和/或左递归问题的情况下添加它？

是否有任何正式的算法或步骤来重写没有左递归并显示右优先级的语法。例如维基百科中描述的消除左递归的简单算法

例如，给定以下算法：

所需的输出应该是：

我了解 LL 递归下降解析器如何处理这种形式的规则：

有一个简单的循环，它根据前瞻令牌是否与第一组 B 中的终端匹配来检查是否继续循环。但是，我对基于表的 LL 解析器很好奇：这种形式的规则如何在那里工作？据我所知，处理这样的重复的唯一方法是通过右递归，但在不需要右关联解析树的情况下，这会破坏关联性。

我想知道，因为我目前正在尝试编写一个基于 LL(1) 表的解析器生成器，但我不确定如何在不更改预期解析树形状的情况下处理这样的情况。

我想验证我的 ANTLR 4 语法是 LL(1)。在旧版本的 ANTLR 中有一个选项可以做到这一点。ANTLR 4 中有类似的东西吗？

我浏览了文档，但没有找到任何东西。尽管似乎缺少选项页面，但我什至没有找到所有可能选项的列表。

我在下面有这个语法并试图弄清楚是否可以使用 LL 解析器进行解析？如果不是，请解释。

据我了解，两组的交集必须为空才能通过成对不相交测试。

但我不确定从哪里开始，并且一直在查看我的教科书和http://en.wikipedia.org/wiki/LL_parser#Parsing_procedure，但不能完全理解或找到任何可以遵循的示例。我只需要查看程序或步骤即可了解如何解决其他类似问题。任何帮助表示赞赏。

我在解决这个问题时遇到了问题。我必须重写以下语法以使其适用于 LL(1) 解析

S → 名词 | 名词和名词| M、名词和名词

M → M, 名词 | 名词

我注意到的第一个问题是语法在带有头 M 的生产中是递归的，我像这样修复它

M → 名词 NewPro

NewPro → , 名词 NewPro

但后来我注意到带有标题 S 的产生是模棱两可的，但我不知道如何解决它，我试图“分解”这个名词，但我实际上并不确定。

你能帮我吗？

谢谢您的回答。