问题标签 [lalr]

我的 Bison 语法有问题。我有一对很好的移位/减少，还有六个减少/减少。问题是我不明白减少/减少冲突是如何发生的，因为解析器应该知道先从令牌中选择哪个。

这是我的语法。Bison 对 and 之间的歧义提出质疑，function_argument_definition以及primary_expressionand 之间function_argument_definition的歧义function_argument。但是，我很确定它在遇到任何此类事情时应该已经知道该选择哪个。我该如何解决这些歧义？

我正在阅读这个野牛介绍。

我有两个问题，如果有人能帮助我理解，那就太好了：

1. 术语是什么context free grammar意思？

2. 从上面的链接：Bison 可以处理并非所有上下文无关语言，只有那些是 LALR(1) 的语言。简而言之，这意味着必须能够仅用一个前瞻标记来说明如何解析输入字符串的任何部分。“可以告诉如何只用一个前瞻标记来解析输入字符串的任何部分”是什么意思

我想创建一个 LALR 语法来解析嵌套列表，但我总是遇到移位/减少冲突。

我有 list1，它是 type1 项目和 list2 的列表：

我有一个 list2 ，它是 type2 项目的列表：

此语法产生移位/减少错误。我怎样才能避免它？

这是具体的Bigloo来源：

终端是：comment、new-line、text-chunk 和 white-space。非终结符是：输入、节点列表、节点和文本。

Bigloo 抱怨文本到文本块的缩减规则：

但我不认为这是一个 Bigloo 问题。它看起来像一个语法问题。

我有非常简单的语法：

我想扩展它以支持 unar 操作（恕我直言，这是正确的语法，但它可能是错误的，因为我在语法、解析器、词法分析器等方面是真正的 n00b）：

当我尝试更新解析表时，真正的问题出现了：

所以问题是我应该如何编辑这个表来提供一元操作支持（基于描述的语法）？

PS无论如何，我将非常感谢使用LR（k）（或LALR）解析器解析Java（或任何其他OO语言）中的ariphmetic表达式的任何帮助^_^

PS2。解析器生成器不适合这种情况。

如果我正在编写自己的自定义解析器，我怎么知道我是否正在编写递归上升解析器？我绝对对 LALR 解析的 O(n) 复杂性感兴趣（而且我已经有一个 LALR 语法）并且不想以后发现我已经编写了一个 LL 解析器。

编辑：我只见过自动表驱动解析器和几个生成的简单示例递归解析器——它们看起来都不像我手工构建的任何东西。因此，很难将处理规则的“明显”代码与实际算法联系起来。

如果您将代码用于一个相对简单的规则，例如

我已经翻译成

没有什么左或右的。这显然是有用且重要的信息，但我没有看到。这里唯一明显的事实是它是递归的。

编辑：对不起，不好的例子。像这样的东西怎么样：

我想可视化一个语法文件（实际上是咖啡脚本的Jison语法）。所以输入文件是一个 Bison/Yacc 风格的语法文件。预期的输出可能是 Graphviz 点文件或类似文件。

我不一定要寻找完整的 IDE，例如GOLD。但是能够处理 LALR 输入很重要，这就是为什么优秀的ANLTRWorks没有考虑在内的原因。

我还检查了Wikipedia 上的解析器比较，但它仅包括 IDE 支持，但不包括可视化。

这是我真正想要可视化的咖啡脚本语法文件。

在 LALR(1) 解析器中，语法中的规则被转换为一个解析表，该表有效地表示“如果到目前为止你有这个输入，并且前瞻标记是 X，那么转移到状态 Y，或者通过规则 R 减少” .

我已经成功地用解释语言（ruby）构建了一个 LALR(1) 解析器，而不是使用生成器，而是在运行时计算解析表并使用该解析表评估输入。这工作得非常好，表生成非常简单（这让我有些惊讶），支持自我引用规则和左/右关联。

然而，我难以理解的一件事是 yacc/bison 在概念上如何处理空规则定义。我的解析器无法处理它们，因为在生成表时，它会递归地查看每个规则中的每个符号，并且“空”不是来自词法分析器的东西，也不会被规则减少。那么，LALR(1) 解析器如何处理空规则呢？他们是否特别对待它，或者它是一个有效算法应该使用的“自然”概念，甚至不需要对这样一个概念有特别的认识？

假设一个规则可以匹配任意数量的成对括号，中间没有任何内容：

如下输入将匹配此规则：

这意味着在前瞻标记中读取 '(' 并看到 ')' 时，解析器会选择：

1. 移动“）”（不可能）
2. 根据其他规则减少输入（不可能）
3. 还有什么...

不太适合“移位”或“减少”的核心算法。解析器实际上需要什么都不移动到堆栈上，将“无”归expr约为 ，然后移动下一个标记')'，给'(' expr ')'，当然归约为expr，依此类推。

让我困惑的是“什么都不做”。解析表是如何传达这样一个概念的？还要考虑到应该可以调用一些语义动作来返回一个值来$$减少空值，所以一个相当简单的视图只是从解析表中跳过它并说'('在堆栈和')'前瞻中应该简单地转换为一个转变，不会真正产生序列'(' expr ')'，而只会产生序列'(' ')'。

我想知道 C# 和 Java 语法是否是 LALR(x)？如果是，x 的值是多少？

编辑：

接受了真实答案后，我觉得这样改Q比较好：

是否有任何 LALR(x) 解析器可以解析当前版本的 Java（版本 7）或 C#（版本 4）？如果是，x 的值是多少？

这不是我的作业，我正在尝试理解 LALR(1) 语法。所以我发现了这个

我写了 LR 项目，但我不明白为什么这是 LR(1) 语法而不是 LALR(1)？

谁能帮我？谢谢

根据Recursive Descent vs. LALR 中的这篇文章，任何 LALR(k) 都可以通过“因式分解”转换为 LALR(1)。我不拥有帖子中提到的龙之书，在线某处是否有一些解释或示例，或者有人可以在这里提供如何进行分解的解释或示例？