问题标签 [ambiguous-grammar]

考虑这个 BNF 语法：

这个语法没有歧义，因为一个语句只能绘制一个解析树。但是，这显然不遵循运算符优先级规则。运算符 *,+,() 具有相同的优先级。这个语法是明确的，还是只是不模棱两可？如果它是明确的，那么语法可以在不遵循运算符关联性和优先级规则的情况下是明确的，这是真的吗？

语法如下。

我理解它的方式，这个语法的派生就像SS'S'S'S'... (0 or more S')，每个SorS'都会生成aor b。

有人可以提供一个例子来说明这个语法是模棱两可的吗？（解决方案说是。）

我正在学习语法中的歧义，我需要一些帮助才能更好地理解。这是一个语法：

使用解析树或最左边的推导，我怎样才能证明这个语法是模棱两可的？

我正在尝试为一种简单的语言编写解析器：

当我运行它时，我收到以下错误：

我知道发生这种情况是因为，如果我们想象解析器是在没有错误的情况下构建的，然后写入parser.parse('foo')，两者arithmetic_expr和boolean_expr都是“正确的”派生。此外，如您所见，我使用的是 LALR，它是一种严格确定性的算法，无法处理歧义。

所以我的问题是，我怎样才能使这个语法明确？我似乎找不到解决方案。

最近我写了一个（高度优化的）LALR(1) 解析器（它可以处理模棱两可的语法），并为它提供了一个非常模棱两可的语法。之后，我为相同的语法编写了一个递归下降解析器，但消除了所有的歧义。我读过很多次 LALR(1) 解析器非常高效，而递归下降解析器非常低效，所以我自然希望 LALR 解析器运行得更快，即使它有一个模棱两可的语法。当我比较两次运行的结果时，我惊呆了——递归下降解析器比 LALR 解析器快得多！为什么 LALR 解析器比递归下降解析器慢？是因为 LALR 解析器的语法不明确吗？

我是 Lex 和 Yacc 的新手。我尝试学习语法规则和语义动作。我试图编写一个解析器，它基本上可以执行赋值、函数声明、函数调用和打印语句。问题是，在我给出输入后，我得到的输出是语法错误。所以我认为我的语法会导致这种情况，但我不确定。这是我的文件：

扫描仪.flx：

解析器.y：

当我尝试在 MacOS 终端中运行我的文件时，我照常使用这些命令：

- 没问题 -

- 没问题 -

- 警告 -

这是 parser.tab.c 中的第 1330 行附近：

这是我的输入：

输入1：

输出1：

输入2：

输出2：

输入3：

输出3：

我正在使用 Bison 和 Flex 为类 C 语言开发编译器。目前，编译器能够识别具有声明、赋值和打印语句以及算术和逻辑表达式的语言（仅使用 int 变量）。它生成一个 3AC（以及一些管理内存的指令）。这是我的野牛代码：

如您所见，逻辑表达式的语法有点复杂，但编译器会做它应该做的。该行为类似于 C，因此整数值可用于 AND/OR/NOT。

我对语法的想法是这样的：

但是通过这种方式，我得到了两个冲突，1 个 shift/reduce 和 1 个 reduce/reduce。有没有办法简化语法？

我想知道以下上下文无关语法是否模棱两可。

S -> 0S | 一个 | 0
A -> 1A | 1

我相当确信它是明确的，但我被告知它是模糊的。有人可以帮我吗？

谢谢你。

我有这个问题：

显示语法。S->aS|aSbS|Ɛ 有歧义，找到明确的语法。

我尝试从互联网上学习有关歧义语法的任何内容，但大多数人都尝试使用相同的旧示例，我觉得他们没有正确传达将歧义语法转换为明确语法的方法。我知道没有一种明确的方法可以解决这个问题。我尝试了各种尝试方法，这就是我得到的：

首先证明给定的语法不明确：尝试从上述语法中获取 aab

你会发现至少有两种方法可以解决它。

所以我想了想，想出了一个使用hit and trial的解决方案。

S -> aT|ε T -> aTbT | ε

我没有正确性的证据，也没有太多可靠的想法来支持我提出这个问题，但我至少无法使用这种新语法为 aab 制作两个不同的解析树。

这个答案是否正确。如果有人告诉我这实际上是如何完成的以及它背后的基本原理，而不是像我一样进行尝试和尝试，我将不胜感激。

尽管我对编译/解析的知识有限，但我还是敢于​​为 OData $filter 表达式构建一个小型递归下降解析器。解析器只需要检查表达式的正确性并在 SQL 中输出相应的条件。由于输入和输出具有几乎相同的标记和结构，这相当简单，我的实现完成了我想要的 90%。

但现在我被括号困住了，它们出现在逻辑和算术表达式的单独规则中。ABNF 中的完整 OData 语法在这里，所涉及的规则的浓缩版本是这样的：

这个语法如何匹配一个简单的表达式，比如(1 eq 2)？据我所知，所有这些都被里面(的规则所消耗，即它们也必须在之后关闭才能不会导致错误并且永远不会被击中。我想我阅读这种语法的经验/直觉不足以理解它。ABNF 中的一条评论说：“注意 boolCommonExpr 也是一个 commonExpr”。也许这就是谜团的一部分？parenExprcommonExprcommonExprboolParenExpr

显然，(单独的开头不会告诉我它将在哪里关闭：在当前commonExpr表达式之后或更远之后boolCommonExpr。我的词法分析器前面有一个所有标记的列表（URL 是非常短的输入）。我想用它来找出(我有什么类型。好主意？

我宁愿限制输入或进行一些小技巧，也不愿切换到通常更强大的解析器模型。对于像这样的简单表达式翻译，我也想避免使用编译器工具。

编辑 1：rici 回答后的扩展 - 语法重写是否正确？

实际上，我从Wikipedia 上给出的递归下降解析器示例开始。然后我想更好地适应 OData 标准给出的官方语法更“符合”。但是根据 rici 的建议（以及“内部服务器错误”的评论）来重写语法，我倾向于回到 Wikipedia 上提供的更易于理解的结构。

适应 OData $filter 的布尔表达式，这可能看起来像这样：

以上对于布尔表达式是否有意义，它是否与上面的原始结构大致等效并且对于递归下降解析器是可消化的？

@rici：感谢您对类型检查的详细评论。新语法应该解决您对算术表达式优先级的担忧。

对于所有三个终端（上面语法中的大写字母），我的词法分析器提供了一个类型（字符串、数字、日期时间或布尔值）。非终结符返回它们产生的类型。有了这个，我在当前的实现中很好地进行了类型检查，包括体面的错误消息。希望这也适用于新语法。

编辑 2：返回原始 OData 语法

“逻辑”和“算术”之间的区别(并非微不足道。为了解决这个问题，甚至 N.Wirth 也使用了一种狡猾的解决方法来保持 Pascal 的语法简单。因此，在 Pascal 中，and 表达式周围必须有()一个额外的一对。既不直观也不符合 OData :-(。关于“() 困难”的最佳读物是在Let's Build a Compiler (Part VI)中。其他语言似乎在语法上花费了很大的篇幅来解决问题。正如我没有语法结构的经验我停止自己做。andor

我最终实现了原始的 OData 语法。在我运行解析器之前，我会向后检查所有标记以找出哪些(属于逻辑/算术表达式。URL 的潜在长度不是问题。