问题标签 [lalr]

以下（简化的）Bison 语法会产生减少减少冲突：

我看到了这个问题——只有一个前瞻标记，无法判断(an_id是 an'(' expr ')'还是 a fn。但是我该如何解决呢？

我已经看到一些声称优化的 PEG 解析器通常不能比优化的 LALR(1) 或 LL(k) 解析器快。（当然，解析的性能取决于特定的语法。）

我想知道 PEG 解析器是否有任何特定限制，无论是一般有效还是对于 PEG 语法的某些子集，这会使它们在性能方面不如 LALR(1) 或 LL(k)。

特别是，我对解析器生成器感兴趣，但假设在任何特定情况下都可以调整它们的输出以提高性能。我还假设解析器已经过优化，如果需要提高性能，可以稍微调整特定语法。

它是用 Lemon 编译的，它是一个 LALR(1) 解析器生成器：

错误信息是：

调试输出是：

我正在使用一些解析器和词法分析器生成工具（类似于 Lex 和 Bison，但用于 C#）来生成将字符串解析为抽象语法树的程序，以便以后进行评估。

我想做错误恢复（即在生成的抽象句子树中报告缺少标记等）。我有两种方法来构建生成的语法，我想知道哪种方法更好/更灵活/不会发生冲突（.y 和 .lex 文件是根据计算器的描述生成的）。

计算器描述允许用户指定终端/正则表达式及其对运算符和关联性的位置。所以像：

Terminal（通过添加's 和NonTerminal's的顺序指定优先级。"Add"是通过反射发现的方法的名称。基本上它告诉 NonTerminal 在抽象语法树中调用运算符的内容。）

方法1：（允许任何表达式的空规则）

a是一个终端。 @是空的。

方法2：（只允许空规则作为开始规则）

这是一个示例，显示使用每种方法的错误输入的最左推导。

输入： (a +

方法1：

方法2：

方法 2 更难编码（考虑减法/一元负运算符。你不能只看减法A -> A - B，先取出它A并报告错误，A -> - B因为这对一元运算符有效。）我今天早上为方法 2 编码只是发现我认为它有语法问题，并且方法 1 中的空规则使事情变得更简单，代码方面，但我主要担心的是，当程序员创建计算器描述时，哪种方法会产生最少的语法问题如上所述。

我有一个表示表达式的语法。为简单起见，假设它是：

, a, +,*和是我的字母表中的字母(。)

上述规则可以使用正确的运算顺序和关联性生成包含括号、乘法和加法的有效算术表达式。

我的目标是接受每个字符串，其中包含 0 个或更多字母。这是我的限制：

• 语法必须“接受”所有包含 0 个或多个字母的字符串。
• 可以通过算法引入新终端并将其插入到输入中。（我发现EOF，出于某种原因，在检测到超出其他有效表达式的额外标记时，显式提供终端会有所帮助。）
• 可能会引入新的生产规则。新规则将是错误标志（即，如果使用 1 解析字符串，那么尽管字符串被接受，但在语义上被认为是错误）。
• 可以修改产生规则以便插入新引入的终端。
• 语法应该是 LALR(1)，至少可以由 Lex/Yacc 类工具处理（如果我记得悬空的 else 问题需要非 LALR(1)，尽管与 Lex/Yacc 兼容）。

此外，我希望额外的规则对应于不同类型的错误（缺少二进制操作的参数、缺少括号 - 左或右 - 超出其他可接受的表达式的额外标记等）。我这么说是因为可能有一些简单的方法可以回答我的问题以“接受”所有输入，否则这些输入对错误报告无益。

我发现这些规则很有用，尽管我不知道它们是否违反了我的约束：

where$是显式EOF标记，@是空字符串。

如果我的问题不清楚：如何在我的约束范围内修改我的语法以实现接受所有输入的目标，最好是规则与错误类型的良好对应？我的规则是否符合我的目标？

我想制作一个使用 PLY 解析 Javascript 文件的 python 程序，我没有找到任何实现 ECMAScript 的解析器来源，使用 PLY 的 Javascript 规则。

我唯一发现的是一些 ANTLR 语法文件来解析 javascript 和 ecmascript： http ://www.antlr.org/grammar/1153976512034/ecmascriptA3.g http://www.antlr.org/grammar/1206736738015/JavaScript.g

ANTLR 语法文件是否可以调整为 PLY 规则，如果可以，如何以半自动方式完成，是否需要解析语法文件？是否有另一种解决方法（即比使用 ANTLR 语法文件）？

我目前正在为某种语言编写解析器。我已经获得了这种语言的语法，但是这种语法有一些左递归和非 LL(*) 构造，所以 ANTLR 表现不佳，即使有回溯。

因为删除这些左递归和非 LL(*) 构造比乍一看更难，所以我现在想尝试一个 LR(k) 或 LALR(k) 解析器生成器。k越高越好。

谁能推荐我一个满足这些要求的解析器​​生成器？

• 生成的解析器最好是具有一些高（甚至是任意）k 的 LR(k) 解析器，或者至少是具有一些高 k 的 LALR(k) 解析器。
• 生成的解析器是用 C 或 C++ 编写的，如果它是用 C 编写的，它可以链接到 C++-Code。
• 类似于 ANTLR 的功能集（尤其是 AST 重写）会很好。
• 性能不是最紧迫的问题，生成的解析器旨在用于具有大量内存和 cpu 能力的台式机。

谢谢和问候，
约斯特

PS：我问不是因为我不能自己google，而是因为没有时间自己测试一些生成器。因此，请仅在您对推荐的解析器生成器有经验的情况下回答。

我一直在使用 lex/yacc，现在我正在尝试切换到 ANTLR。主要问题是 ANTLR 是一个 LL(*) 解析器，而 yacc 是 LALR。我习惯于自下而上地思考，我并不完全知道 LL 语法的优势是什么。人们说现在 LL 语法更容易理解并且更受欢迎。但似乎 LR 解析器更强大，例如 LL 解析器无法处理左递归，尽管似乎有一些解决方法。

所以问题是 LL 语法相对于 LALR 的优势是什么？如果有人能给我一些例子，我将不胜感激。指向有用文章的链接也很棒。

提前感谢您的帮助！

（我看到这是一个很好的资源：LL 解析器比 LR 解析器有什么优势？，但如果有一些例子会更好。）

我知道可以在 scala 项目中使用例如野牛生成的 Java 文件，但是是否有任何本机的“Scala 语法”LALR(1) 生成器？

这更像是一个“原则上”的问题，而不是一个实际的问题。是 Yacc 减少产生式并从定义的词法分析器中读取新标记的顺序。也就是说，如果我有以下一组令牌：

Yacc 是否可以在其语义范围内LESS_THAN从词法分析器中读取标记，然后再将其简化INTEGER BEGIN INTEGER_VALUE为单个事物，给定一组产生式，例如：

如果这些规则是用语义动作定义的，这些规则会改变吗？