问题标签 [ambiguous-grammar]

我正在寻找专门用于处理歧义的算法或数据结构。

在我当前特别感兴趣的领域中，我正在研究自然语言的模棱两可的解析，但我认为在计算中一定有许多领域中模棱两可起了作用。

我可以找到很多关于试图避免歧义的信息，但在如何接受歧义和分析歧义数据方面却很少。

假设解析器生成这些替代标记流或解释：

• A B1 C
• A B2 C
• A B3 B4 C

可以看出，流的某些部分在解释（A... B）之间共享，而其他部分分支为替代解释，并且经常与主流相遇。

当然，可能还有更多的解释，替代方案的嵌套，以及没有主流的解释。

这显然是某种带有节点的图。我不知道它是否有固定的名称。

是否有我可以研究的现有算法或数据结构旨在处理这种模棱两可的图？

假设我有一个很好的模棱两可的 Marpa 语法和一个很好的模棱两可的输入字符串。

我可以用 Marpa 解析字符串并最终得到一个解析森林。我什至可以遍历森林中的每个解析树。

但是我怎样才能“沿着”解析森林进行迭代呢？

描述我的意思：

解析森林是一种图，它可以具有备选方案分离的节点，以及备选方案重新组合成“主流”的节点。

假设这些是一个解析森林的替代解析树：

• A B1 C
• A B2 C
• A B3 B4 C

有一个主流A......C但是一个模棱两可的B部分。

当然，在现实世界的解析中，分支可能有许多级别的分支，并且可能存在不重新加入单个主流的流。但总的来说，两种或多种解释会有很多共同的部分。

可以使用哪些方法沿着明确和不明确的节点链进行迭代？

事实上我可以输出整个图表吗？

我正在为基本方言编写一个 antlr 语法文件。其中大部分要么正在工作，要么我很清楚接下来需要做什么。但是，我完全不确定应该如何处理用于相等测试和赋值的 '=' 字符。

例如，这是一个有效的语句

这将评估 x 是否等于 5，如果 y 等于 3，则对这些结果执行逻辑 AND 并将结果分配给 t。

我的语法会解析这个；虽然不正确，但我认为一旦歧义得到解决，它就会自行解决。

如何区分“=”字符的两种用法？
1）我是否应该从表达式中删除分配规则并在代码生成期间在我的访问者和/或侦听器实现中处理这些情况（分配与相等测试）

2）有没有更好的方法来定义语法，使其已经被整理出来

有人可以简单地指出我如何最好地实现这种语言“功能”的正确方向吗？

此外，我一直在阅读 ANTLR4 的权威指南以及语言实现模式，以寻找解决方案。它可能在那里，但我还没有找到它。

下面是完整的解析器语法。ASSIGN 令牌当前设置为“=”。EQUAL 设置为 '=='。

这是词法分析器语法。

问题

通过给出字符串 abaca 的两个解析树，证明上下文无关文法“S->SbS|ScS|a”是不明确的。

我不明白字符串是如何模棱两可的？我正在读一本关于编译器和自学的书，所以我在书中做这个问题，我被难住了。

可能的解决方案

谁能确认我的解决方案是否正确，如果不是，请指导我。

我正在为 COOL（面向对象的课堂语言）编写解析器/词法分析器。您可以在以下链接中查看语法：（手册的最后一页）

http://theory.stanford.edu/~aiken/software/cool/cool-manual.pdf

我正在使用 ANTLR 编写此程序，并使用以下输入，我希望得到以下输出：

输入 ：

输出 ：

但我得到的输出是：

这是我的解析器/词法分析器代码：

这是ANTLR中COOL语法的代码版本。主代码中注释的部分已消除歧义（意味着消除了歧义！），并在第二部分（数学规则）中消除了左递归。

谁能指出这哪里出错了，为什么我没有得到想要的输出？

提前致谢！

我需要在谓词的帮助下创建一个语法。对于给定的情况，以下语法失败。

对于给定的输入，它失败了

它应该在结果部分中将“create”作为“name”键的值。

任何帮助都会很棒。

给定一个 CFG： S--> aS | Sa | b 我找不到任何可以由两个不同的 pars 树组成的字符串。

中间状态已经离开递归但没有消除是否有任何字符串显示 CFG 歧义？任何人都可以帮助PLZ。

给定语法规则（BNF，|表示或）：

， 和

• +左结合（a+a+a手段(a+a)+a），
• 连接左关联（aaa均值(aa)a，非a(aa)），
• 和+懒洋洋地吃操作数（aa+aa手段a(a+a)a）。

问题： 这个语法有歧义吗？即是否可以以两种不同的方式解析字符串？

例子：

允许：a, a+a, a+"a", "a+a"+"a+a"(读作(a+a)+(a+a)), ""a"+"a""+"a"(读作((a)+(a))+(a)), a+a+a, a+"a"+a.

禁止："a+a", +"a", a++a, "a", a+"a, ""a+a"+a".

应用程序：我讨厌在 LaTeX 中转义{，}所以我想制作一种 LaTeX 方言，其中只需要转义一个字符，因此例如用一个字符{和而不是.}"""1+2"/3"^"a+b"{\frac{1+2}{3}}^{a+b}

我不知道这是否是问这个问题的正确网站。但我们正在研究语法的歧义。包括最左推导和最右推导。我的练习题是这样的：

有没有办法让它模棱两可？以及使语法模棱两可的任何提示？

我正在尝试将我们创建的假设语言的语法简化为 LL(1)。我使用引入新的非终结符的一般规则，删除了语法中的大部分左分解问题。

例如，

被转化为

在对所有必需的语句应用这些规则之后，我期望得到一个明确的语法。

但是下面的陈述不知何故仍然模棱两可。

下面是语法的相关说明（只显示了需要的）

我对其进行了更多研究，发现歧义在“楼层”和“统计”之间。FIRST('stats') 和 FIRST('floors')，即第一个终端字符的集合都包含“id”和“}”。

我可以看到为什么这会是一个问题，以及左分解如何解决这个问题。但是我怎样才能通过左分解来消除这种歧义呢？

注意：这里，'id' 表示标识符。

'#' 表示 epsilon。