问题标签 [glr]

我最近一直在开发一个带有 flex/bison bison 对的解析器。我无法让解析器以我想要的方式适应我的应用程序。这包括使解析器可重入和线程安全以及将其很好地适应应用程序框架的问题。

我最近转向 flex++/bison++，它为 C++ 编程提供了许多优势，并提供了一种非常清晰且易于管理的方式来使用 OOP 连接和扩展解析器。Bison++ 与原始野牛共享大部分接口。缺点是围绕特定用法的文档很差。一般来说，界面要直观得多，所以直到现在这还不是问题。

随着我的解析器的开发取得进展，我已经意识到在一些更复杂的解析器中使用 GLR 的潜力。

问题：是否可以专门在 bison++ 中使用 GLR，如何激活该选项？

我创建了一个语法，其精简版本如下所示：

我相信这种语言是明确的，应该是 LR 可解析的。（如果我错了，请告诉我！）

但是，当我尝试为此语法生成 LR(1) 解析器时，我会遇到移位/归约冲突，因为当解析器看到exp3前瞻?时，它不知道是移位还是归约：

有没有一种合理的方法可以使这种语言 LR(1) 可解析（没有冲突）？

还是 GLR（或者可能是 LR(2)？）对于这样的语言，我唯一现实的选择是什么？
（或者我认为语言一开始是明确的，我什至是错误的？）

作为参考，我生成的模棱两可的状态机如下（其中 ♦ 是 EOF）：

当 GLR 解析器以两种或多种方式将某些文本减少到相同的非终结符时，它会合并解析子树。Rekers 为此使用“符号节点”。

我这不是每个非终端都可能导致合并。提前知道哪些非终结符永远不会合并将大大简化解析树的构建。

例如，在 Elkhound 技术报告中，作者为 GLR 解析器实现了 C++ 语法。他是这样描述的：

该语法目前有 37 个移位/归约冲突、47 个归约/归约冲突和8 个模棱两可的非终结符。

如何区分给定 CFG 的模棱两可和明确的非终结符？我在哪里可以读到这个？

我有一个为DParser格式编写并使用 Python 绑定的大型语法。当我使用此语法解析代码时，我得到以下异常，但符号不同，具体取决于我传递给它的代码。但是模棱两可的符号总是相同的非终结符。我如何找出歧义是什么？

任何提示或想法将不胜感激。

我有一个为DParser 编写并使用 Python 绑定的大型语法。当我第一次运行解析器并且 DParser 生成它的内部表时，我收到了许多类似这样的警告：

不确定这些警告的来源是什么。我唯一能找到的是 DParser 源代码“write_tables.c”：

任何提示或想法将不胜感激。

在 1.5.4 节使用任意谓词控制解析：野牛手册指定您可以通过检查括号之间的谓词以这种格式的返回来使规则中的选项的解析失败：

问题是我的语法文件中出现上述格式的语法错误：

如手册中所述，我在第一个之前添加了%glr-parser标志%%。有什么我想念的吗？

更新：在发布之前尝试使用野牛 3.0 版进行此操作，但没有成功。正如文档所说，关于人们对这种“实验性功能”的体验的在线信息并不多。任何人都可以确认或否认它对他们有用吗？

更新#2：按照 rici 发布的解决方案后，生成的 .c 文件有问题。似乎为了帮助编译调试，bison 输出以下格式的#line 指令：

在任意谓词生成的情况下，规则的上述谓词选项最终在解析器文件的主开关块中，如下所示：

这当然不会编译，我猜想在 case 语句开始之前的行上输出，就像我在其他规则匹配选项中看到的那样。提交错误报告后，也许还有一些信息要添加到错误报告中？现在，我可以搜索并替换这些内容以继续前进。

我尝试了几种不同的解析器生成器（Bison、DParser 等），它们声称能够生成 GLR 解析器，即可以处理歧义语法的解析器。这是我正在谈论的类型的一个非常简单的模棱两可的语法：

我可以很好地生成解析器，但是当我提供应该有效的解析器输入时，我得到“未解决的歧义”错误或完全崩溃。当我将语法更改为明确的版本时，没有任何问题。

我对 GLR 解析器有什么不了解的地方？我认为重点在于，在出现歧义的情况下，会跟​​踪所有可能的解析，直到它们合并或到达死胡同。我所需要的只是一个解析器，它可以告诉我是否有任何有效的输入解析。

谢谢你的帮助。

编辑：

这令人沮丧。使用 %dprec 和 %merge 我已经能够让 Bison 处理模棱两可的规则和终端，但它仍然让我需要处理的那种非常简单但高度病态的伪英语语法窒息：

对于输入“a boy saw a girl”，Bison 无法解析并返回代码 1。另一方面，Tom 完美地处理了这个语法和这个输入语句，甚至通过将未知终端分配给所有可能的终端来自然地处理它们终端类型。但与 Bison 不同的是，Tom 对大型语法感到窒息。（“扼流圈”是指以各种不同的方式失败。如果失败模式有帮助，我可以报告这些。）

有人有其他想法吗？

我正在尝试从快乐中生成 GLR 解析器，但是一旦生成文件就会出错。

这是一个例子， ABC.y ，所以很清楚我在尝试什么：

这个例子适用于

但是，对 --glr 很满意，我无法构建结果。我想知道我是否做错了。准确地说，happy --glr 产生两个输出，ABC.hs。然而，ABCData.hs，

现在失败了。我得到的错误是找不到模块'System'，它是haskell-98的隐藏成员......我尝试添加包haskell98，并得到了模棱两可的前奏问题。我还尝试将语法编码为 BNFC 并使用他们的 -glr 选项，但我仍然遇到其他错误，例如对显然已弃用的 Data.FiniteMap 的依赖。有没有办法得到这个编译？

我有以下 Bison 语法片段：

|在我的语法中有重载的含义，所以我不能只从词法分析器中将它作为标记 BINARY_OP 返回。根据上下文，它可能是不同的标记。

如果我使用它作为我的输入：

我可以成功解析它（或被词法分析器识别为 BINARY_OP 令牌）。

但是，如果我的输入是这样的：

我得到一个模棱两可的语法错误。（|不被识别为左联想）

如何让binary_op在non_keyword_expr中保持左关联？%prec关于binary_op的第二条规则的声明似乎没有效果。

编辑：这是一个 GLR 解析器

假设我定义了一个快乐的语法

如果我编译这个

我通常对具有非平凡歧义的语法感兴趣；然而，这个例子展示了让我感到困惑的一点。

我得到了一个 Haskell 解析器。只有当令牌流是 abba 或 b 时，我才会成功

然而，我对失败更感兴趣。我想很快失败，而且我似乎需要比我想象的更多的代币。

例如，如果我提供令牌流 a,a,a ... 到第三个 a 失败。如果我喂 bbb，则需要第三个 b 才能失败。为什么要额外的前瞻？匹配 f 时，一旦我看到两个 'a'，语法中就没有什么可以匹配的了。