问题标签 [glr]

我正在编写一个GLR 解析器生成器，并希望在互联网上和死树品种（不熟悉极客语言的人的书籍）上获得与该算法相关的资源的一些建议。

我知道 Bison 可以生成 GLR 解析器，并且鉴于它在 GPL 下，我可以检查它的代码，但是最好对算法进行完整描述。

那么，有人知道我可以利用的任何好的资源吗？谢谢。

好的，所以我想做一个 GLR 解析器生成器。我知道存在比我可能制作的更好的程序，但我这样做是为了娱乐/学习，所以这并不重要。

我一直在阅读有关 GLR 解析的内容，并且我认为我现在对它有了相当高的理解。但现在是开始做生意的时候了。

图结构堆栈 (GSS) 是 GLR 解析器中使用的关键数据结构。从概念上讲，我知道 GSS 是如何工作的，但到目前为止，我所看到的资料都没有解释如何实现 GSS。我什至没有要支持的权威操作列表。有人可以为我指出一些很好的 GSS 示例代码/教程吗？谷歌到目前为止没有帮助。我希望这个问题不要太含糊。

我已经实现了组合 GLR 解析器。其中有：

• char(·)使用指定字符或字符范围的解析器。
• many(·)从零到无限次重复指定解析器的组合器。

示例："char('a').many()"将匹配带有任意数量"a"-s 的字符串。

但是many(·)组合器是贪婪的，因此，例如char('{') >> char('{') >> char('a'..'z').many() >> char('}') >> char('}')（">>"解析器的顺序链接在哪里）将成功地消耗整个"{{foo}}some{{bar}}"字符串。

我想实现many(·)在前面的例子中使用的惰性版本，它只会消耗"{{foo}}"。我怎样才能做到这一点？

编辑：

可能是我把你们都弄糊涂了。在我的程序中，解析器是一个函数（或 C++ 中的“函子”），它接受“步骤”并返回“步骤”的森林。“步骤”可能是 OK 类型（表示解析器已成功使用部分输入）和 FAIL 类型（表示解析器遇到错误）。有更多类型的步骤，但它们是辅助的。

所以当我解析输入时，我：

• 编写简单的预定义 Parser 函数以获得表示所需语法的复杂 Parser 函数。

• 从输入形成初始步骤。

• 将初始 Step 赋予复杂的 Parser 函数。

• 使用 Steps 过滤 TreeNodes，只留下 OK 的（或者如果输入有错误，则使用最少的 FAIL-s）。

• 从剩下的 Steps 中收集信息。

前言

我已经编写了具有错误恢复功能的 GLR 解析器。当它遇到错误时，它会分成以下替代方案：

1. 将预期的元素插入输入中（可能是用户刚刚错过了它）并照常进行。
2. 用预期的元素替换错误的元素（可能是用户刚刚输入错误）并照常进行。
3. 跳过错误元素，如果下一个元素也是错误的，则转到#2。

但是，如果输入有很多错误（例如，用户错误地将 JPEG 文件提供给解析器），则替代方案的数量会呈指数增长。

例子

这样的解析器对应如下文法：

适用于以下文本：

在中等现代的台式计算机上因“内存不足”而失败。

问题

如果输入错误，如何减少备选方案的数量？

如何在野牛/yacc GLR 解析器中获取“预期令牌”？

你好，

在我正在做的项目中，有一些模棱两可的语法。所以我正在尝试使用 %glr-parser 来解决移位/减少冲突。

当我使用非 GLR 解析器时，我可以在检测到语法错误时使用 yystate（全局变量）来获取“预期的令牌”。但是切换到 GLR 解析器后，我发现它不再是全局变量了。

所以我的问题是，当出现语法错误时，是否可以在 GLR 解析器中获取“预期令牌”？

我正在使用 Bison 生成解析器。我有一个班次/减少冲突，我真的需要 Bison 使用 GLR 而不是 LALR 来处理它。但是我已经通过了%glr-parser指令并且源文件仍然声明它是一个 LALR 解析器。我什至发现了一个“glr.cc”骨架，它表明它是一个 GLR C++ 解析器，并且使用它%skeleton "glr.cc"并没有改变输出。Bison 不会为所有目标语言提供所有算法吗？

如何强制通过 GLR 方法解决 shift\reduce 冲突？
假设我希望解析器自己解决右移位运算符和模板参数的两个右尖括号之间的冲突。我让词法分析器将 2 个连续的“>”符号作为单独的标记传递，而不将它们合并为一个“>>”标记。然后我把这些规则放到语法中：

我希望这是一个转变\减少冲突。如果我有具有左关联性的“>”的令牌声明，这不会是冲突。所以我必须删除令牌优先级\关联性声明，但这会导致许多其他冲突，我不想通过为每个冲突规则指定上下文优先级来手动解决这些冲突。那么，有没有办法在声明令牌的同时强制 shift\reduce 冲突？

我正在尝试为C/AL 编程语言创建某种lint工具。所以基本上我需要对源代码进行语法和词法分析。我计划从头开始编写解析器，但后来发现有很多工具可以帮助自动生成这些解析器。

我需要性能，因为在一段中检查 20 兆字节的代码是正常情况，我需要该工具可以通过自定义规则进行扩展。所以我决定使用 JavaScript。

到目前为止，我已经找到了两个可以使用Jison和PEG.js的生成器。

它们中的哪一个给了我更多的解析性能？也许不是比较库，而是算法？

哪一个更适合我的需求（解析通用编程语言）？

更新： 我发现了类似的问答：

• Packrat 解析与 LALR 解析
• 解析器的性能：PEG vs LALR(1) 或 LL(k)

我写一个 GLR 是为了好玩（同样，因为自从我上次尝试以来我理解了一些事情）。解析器现在正在工作，我正在实施消歧规则。我正在以一种似乎有效的方式处理优先级。现在我对关联性有点不知所措。

假设我有这样的语法：

其中规则 1) 和 2) 具有相同的优先级和左结合性。

如果没有关联性处理，字符串 '1-1+0' 将生成两个解析树：

其中数字表示用于减少的规则。正确的解析树是第一个，因此我只想保留这个。

我想知道如何通过算法有效地检测关联性侵犯。

我尝试的一种方法是查看在第一棵树的顶部节点处，规则 2 是规则 1 子列表中规则 3 的左侧，而在第二棵树中，规则 1 是规则 4 的右侧，因此由于规则2 和 1 是左关联的我只保留第一棵树。

然而，在更复杂的例子中，这并没有让我走得太远。此解决方案的一个限制是我只能根据与另一棵树的比较来丢弃树。

您认为我可以使用这种方法的改进版本找到解决方案吗？标准的做法是什么？

根据维基百科 GLR 的描述，它们“处理非确定性和模棱两可的语法”。 我可以想象一个模棱两可的语法，就像悬空的 else 问题一样，但是什么是不模棱两可的非确定性 CF 语法？