问题标签 [glr]

我正在使用 Bison 2.7 编写 GLR 解析器并打开 %error-verbose 选项。当我运行解析器时，它给了我“语法不明确”的错误。有没有办法让 Bison 给我更多关于语法在哪里/如何模棱两可的细节？

当我尝试编译生成的文件时，我尝试了多个示例语法并得到相同的错误。

例如，我完全按照这个问题的解决方案 - GLR_Lib.hs：找不到模块“系统”

语法文件在哪里

但是当我编译时，我得到：

[1 of 2] 编译 ABCData ( ABCData.hs, ABCData.o )

[2 of 2] 编译 ABC ( ABC.hs, ANC.o )

GLR_Lib.hs:164:2：输入“case”时解析错误</p>

我尝试过的每种语法都发生了这个确切的错误。我不知道我可以对那些成功运行示例的人做些什么不同的事情。

像这样的EBNF

我应该将其转换为

或者

这两个 BNF 对 GLR 解析器的含义相同吗？

------------------------ 附加内容 ------------------------ ------

如果词法是

GLR 解析器应该得到两棵树

和

但是第一个转换的 BNF 只能得到第一棵树，因为当它遇到时"else"，reduce/shift 没有冲突，冲突在遇到 X。

第二个 BNF 在遇到时会发生 reduce/shift 冲突"else"，因此解析器将拆分为两个线程在不同的条件下进行解析。

我对吗？是否有任何 ACTION、GOTO TABLE 生成器可以像对待第二个 BNF 一样对待第一个 BNF？

是否有完整的系列测试来测试 GLR 解析器是否正确编写？

我正在编写一个 GLR 解析器，所以我想为我的代码找到一些测试。由于可能缺少一些条件，我自己无法找到完整的测试套装。

我已经编写了一些测试来测试解析器。但我不知道它是否会在其他条件下失败。所以我需要“一个完整的测试”，可能是很多人在测试中添加测试用例。这可以保证解析器可以处理任何情况。GLR 解析器可以处理任何上下文无关文法，因此需要测试很多条件。

我是野牛的新手，不幸的是需要为一种语言编写解析器，该语言可能具有变量名中的运算符。例如，根据上下文，表达式

可以解释为：

1. "FOO"分配给变量的值减去变量的"BAR"值"BAZ"，或
2. "FOO"被赋予变量值的变量"BAR-BAZ"

幸运的是，该语言需要提前声明变量，因此我可以通过我实现的函数确定给定字符串是否为有效变量：

如果给定的字符串是有效的变量名，则返回 true，否则返回 false。

我如何告诉野牛首先尝试上面的第二种情况，并且只有当（通过使用isVariable()）该路径失败时，才返回并按照上面的第一种情况进行尝试？我读过你可以让野牛尝试多个解析路径并在遇到 a 时剔除无效的路径YYERROR，所以我尝试了一组类似于以下的规则：

但是当给定"BAR-BAZ"解析器时，它会尝试将其作为单个变量，并且当它遇到时完全停止，YYERROR而不是像我期望的那样探索"BAR" - "BAZ"路径。我究竟做错了什么？

编辑：我开始认为我的弹性规则STRING可能是罪魁祸首：

在这种情况下，如果 '-' 出现在字母数字字符的中间，则整个批次被视为 1 STRING，解析器不可能进行细分（因此只探索了一条路径）。我想我可以STRING在解析器操作中手动解析，但似乎应该有更好的方法。也许 flex 可以返回备用令牌流（一个用于"BAR-BAZ"案例，另一个用于"BAR"-"BAZ"案例），这些令牌流被转移到不同的解析器堆栈进行探索？这样的事情可能吗？

目前我正在尝试为 VHDL 构建一个解析器，它存在 C++ 解析器必须面对的一些问题。VHDL 的上下文无关文法生成解析森林而不是单个解析树，因为它在函数调用和数组订阅方面存在歧义

只有当解析器携带一个分层的、类型感知的符号表时，这个赋值才能被明确地解析，它可以用来在运行中解决歧义。

我不想这样做，因为对于上述语句，解析森林不会呈指数增长，而是线性增长，具体取决于函数调用和数组订阅的数量。

（当然，除了有人会用类似这样的语句来折磨解析器）

由于野牛强制用户只创建一个解析树，我使用 %merge 属性递归地收集所有子树，并将这些子树添加到单例 AST 中所谓的 AMBIG 节点下。

结果看起来像这样。

为了产生上述内容，我解析了令牌流“I=I(N);”。我在 parse.y 文件中使用的语法的实质内容收集在下面。它试图类似于 VHDL 的模棱两可的部分：

整个源代码可以在这个 github 存储库中阅读。

现在，让我们开始讨论实际的问题。正如您在上面生成的解析树中所见，节点 FCALL1 和 ARRIDX1 引用同一个节点 EXPR1，而 EXPR1 又引用 N1 两次。

无论如何，这不应该发生，我不知道为什么。相反，应该有路径

你知道为什么野牛会重用上述节点吗？

我还在官方 gnu 邮件列表上为 bison 写了一个错误报告，但没有回复这一点。不幸的是，由于对新的 stackoverflow 用户的限制，我无法提供此错误报告的链接...

我目前正在使用野牛创建一个解析器，它大量使用变体功能，因为我的语法不是 LALR(1) 我想使用 GLR 选项。当我尝试这样做时，我收到以下错误：

我究竟做错了什么？

我正在使用 GNU bison 开发解析器，但我遇到了一个有趣的问题。我的实际问题有点不同，一般来说不太有趣，所以我会用不同的方式陈述它，这样答案通常会更有用。

我需要根据表达式的类型来区分表达式，例如算术表达式和字符串表达式。他们的顶级非终结符有一些共同的祖先，比如

现在我需要能够在两种表达式中都有变量

（在 stringexpression 情况下只允许使用 string 类型的变量，在算术表达式情况下只允许使用 int 或 float 类型的变量）但这显然会导致 R/R 冲突，这是语言中固有的 -这是不可能解决的，因为语言是模棱两可的。

当然我可以淡化语言，这样只有一般的“表达式”对象在解析堆栈上传递，但是我必须在动作中做很多手动类型检查，我想这样做避免。此外，在我的真实用例中，通过语法到变量规则的路径是如此不同，以至于我不得不将语言淡化，以至于我会丢失很多语法规则（即丢失很多结构信息），并且需要将解析引擎手写到某些操作中。

我读过关于 GLR 解析的文章，听起来它可以解决我的问题。我正在考虑使用此功能：具有上述语法以及YYERROR相应变量具有错误类型的路径。

但野牛手册说

1. 在确定性 GLR 操作期间，YYERROR 的效果与其在确定性解析器中的效果相同。
2. 延迟动作的效果是类似的，但是错误的精确点是不确定的；相反，解析器恢复到确定性操作，选择一个未指定的堆栈以继续出现语法错误。
3. 在非确定性解析期间的语义谓词（请参阅语义谓词）中，YYERROR 默默地修剪调用测试的解析。

我不确定我是否理解正确 - 我是这样理解的：

1. 不适用于此处，因为 GLR 解析不是确定性的
2. 是我在上面的代码中的方式，但不应该这样做，因为 YYERROR 杀死的路径是完全随机的（如果我错了，请纠正我）
3. 不会解决我的问题，因为语义谓词（不是语义动作！）必须在规则的开头（如果我错了，请纠正我），此时来自 TOK_IDENTIFIER 令牌的 yylval 不可访问（纠正我如果我错了），所以我无法查看符号表来查找变量的类型。

有没有人遇到过这种情况？我对手册的理解有误吗？你会如何处理这个问题？对我来说，这个问题似乎很自然，我会假设人们经常遇到它，以至于野牛会有一个内置的解决方案......

我正在研究 GNU bison 中的 GLR 解析器，但遇到以下问题：

我试图解析的语言允许布尔表达式，包括关系（<、>、<=、...）和布尔组合（和、或、非）。现在的问题是该语言还允许在关系的右侧有多个算术表达式......并且它们使用用于布尔组合的相同 AND 标记组合！这是一个非常愚蠢的语言设计，但我无法改变它。

所以你可以拥有a > b and c应该等同于的(a > b) and (a > c)，你也可以拥有a > b and c > d应该等同于的(a > b) and (c > d)

这导致的 S/R 冲突在此示例中已经很明显：在a > b使用前瞻读取之后，and您可以将 减少a > b为布尔表达式并等待另一个布尔表达式，或者您可以转移and并等待另一个算术表达式。

我的语法目前看起来像这样：

对于任何k ，该语言显然不是LR(k) ，因为使用任何常量k -lookahead都无法解决 S/R 冲突，因为两者之间的算术表达式可以有任意多个标记。因此，我打开了 GLR 解析。

但是，当我尝试a > b and c对此进行解析时，我可以在调试输出中看到解析器的行为如下：

• 它读取并在a前瞻>中将aarithmeticexpression
• 它读取b并向前看and它减少b到一个arithmeticexpression然后已经减少到一个maxtree
• 它减少a > b到一个relation
• 它读取并将其简化c为arithmeticexpression

然后什么也没有发生！and c显然被丢弃了 - 调试输出不显示这些令牌的任何操作。甚至没有错误消息。我的 AST 中不存在相应的 if 语句（我仍然得到一个 AST，因为我有错误恢复）。

我认为，在阅读完之后b，应该有 2 个堆栈。但是b不应该减少。或者至少它应该给我一些错误信息（“语言是模棱两可的”会好的，我以前看过这条信息 - 我不明白为什么它不适用于这里）。任何人都可以理解这一点吗？

看了一会儿语法，你可以看出这里的主要问题是在下一个算术表达式之后是否出现

• 另一个关系标记（那么你应该减少）
• 另一个布尔组合（那么你应该转移）
• 布尔/算术表达式语法（如 THEN）之外的标记，它将终止表达式，您还应该转换

你能想出一种不同的语法以更好/更确定的方式捕捉情况吗？你会如何处理这个问题？我目前正在考虑使语法更从右到左，比如

我认为这会使野牛更喜欢变速，并且只会首先减少右侧。也许通过使用不同的非终结符，它可以允许算术表达式后面的准“前瞻”......

旁注：GnuCOBOL 通过收集所有标记、将它们推送到中间堆栈并从那里手动构建表达式来处理这个问题。这让我灰心丧气，但我坚持希望他们这样做是因为野牛在开始时不支持 GLR 解析......

编辑：一个可重复的小例子

这个奇怪地确实在 input 上打印了错误消息“语法错误” a>b&c。

我对著名的巴科斯-瑙尔形式的 C 语法感兴趣并研究了一段时间，令我困惑的是，有些语法在我看来是错误的，但根据 BNF 被认为是正确的。

例如，int test {}这是什么？我认为这是 C 中的错误语法，但事实是 BNF 认为这是一个函数定义：

我用野牛试过这个，它认为输入int test {}是正确的形式，但我在 C 编译器上试过，它不会编译。

所以有问题：

1. int test {}语法是否正确？
2. 如果它是正确的语法，那是什么意思，为什么编译器不能识别它？
3. 如果它是一个错误的语法，我能说 BNF 不严谨吗？这是否意味着现代 C 编译器不坚持这个 BNF？