问题标签 [shift-reduce]

我正在尝试了解 shift-reduce 解析。假设我们有以下语法，使用强制操作顺序的递归规则，受ANSI C Yacc 语法的启发：

我们想使用 shift-reduce 解析来解析 1+2。首先，将 1 作为数字移动。我的问题是，它是否会被简化为 P，然后是 M，然后是 A，最后是 S？它怎么知道在哪里停下来？

假设它确实一直减少到 S，然后移动“+”。我们现在有一个堆栈，其中包含：

如果我们移动'2'，减少可能是：

现在，在最后一行的任一侧，S 可以是 P、M、A 或 NUMBER，并且它仍然有效，因为任何组合都是文本的正确表示。解析器如何“知道”它

这样它就可以将整个表达式简化为A，然后S？换句话说，它如何知道在移动下一个令牌之前停止减少？这是 LR 解析器生成的关键难点吗？

编辑：对问题的补充如下。

现在假设我们解析1+2*3. 一些移位/减少操作如下：

这是正确的（当然，它还没有完全解析）？此外，1 符号前瞻是否也告诉我们不要减少A+M到A，因为这样做会导致读取后不可避免的语法错误*3？

我正在用 Bison 用 C 语言编写一个解析器，虽然它似乎在我迄今为止尝试过的所有情况下都能正常工作，但我的二元运算符（以及我的一元 NOT 运算符作为出色地）。

当我通过 bison --verbose 运行我的 .y 文件时，我看到：

我没有看到任何实际解析二进制运算符的问题，但似乎我应该无论如何都应该解决移位/减少问题。我不知道冲突在哪里—— set_existence 产生似乎完全不相关。我最好的猜测（在黑暗中拍摄）是它可能与 EQ 用作二元运算符（相等比较）以及赋值（例如，“foo = bar = baz;”将设置根据 bar 和 baz 是否相等，将 foo 设置为 true/false）。如果我将相等比较更改为 == ("foo = bar==baz;")，我的解析器会按预期运行，但仍然存在相同的移位/减少冲突。

编辑：我确实指定了关联性：

我一直在尝试解决看似简单的移位/减少冲突，但无济于事。当然，如果我忽略冲突，解析器工作正常，但如果我重新组织我的规则，我会感觉更安全。在这里，我将一个相对复杂的语法简化为单个冲突：

使用 yacc 中的详细选项，我得到了描述具有上述冲突的状态的输出文件：

感谢您提供任何帮助。

给定一个简单的语法，比如

移动前三个标记，然后查看第四个标记以查看要减少的规则，以及简单地执行三个标记的前瞻以查看要减少的规则有什么区别？

这是我的代码：

我的输入字符串是：+selector1.selector2||-selector4->selector4

此输入的解析树预计为：

我的 yacc 生成的程序给出如下输出：

似乎程序停止执行 shift&& reduce 一次无法从 yylex() 获取更多符号，但我希望它减少堆栈中剩余的符号，L||-P->C因此，我可以在我的代码中生成整个解析树。

我的预期输出是：

我正在尝试将 Stanford Shift Reduce Parser 与提供的西班牙模型一起使用。然而，我注意到，与词法分析器不同，尽管发送了足够的标志 -outputFormat typedDependencies，但我无法获得 TypedDependencies，这可以在 lexparser.bat/sh 中看到。

以防万一，这是我用来传递标志和创建解析器的 Java 代码。

谢谢

LL(1) 解析器需要一个前瞻符号才能决定使用哪个产生式。这就是为什么我一直认为使用术语“前瞻”的原因，当解析器查看下一个输入标记而不“消耗”它时（即它仍然可以通过下一个操作从输入中读取）。然而，LR(0) 解析器让我怀疑这是正确的：

我见过的每个 LR(0) 解析器示例也使用下一个输入标记来决定是移位还是减少。在减少的情况下，不消耗输入令牌。

我使用免费软件工具“ParsingEmu”生成 LR 表并在下面对“aab”一词执行 LR 评估。如您所见，列标题包含标记。从评估中，您可以看到解析器通过查看下一个输入标记来决定使用哪一列。但是当解析器在步骤 4 - 6 中减少时，输入不会改变（尽管解析器在执行到下一个状态的转换时需要知道下一个输入标记“$”）。

语法：

桌子：

评估：

由于我的困惑，现在我做了以下假设：

1. 我对“前瞻”定义的假设（前瞻 = 未使用输入令牌）是错误的。对于 LL 解析器或 LR 解析器，前瞻只是意味着两种不同的东西。如果是这样，那么如何定义“前瞻”呢？

2. LR 解析器（从理论的角度来看，当您使用下推自动机时）具有额外的内部状态，它们通过将输入标记放在堆栈上来消耗输入标记，因此只需查看即可做出移位减少决策在堆栈上。

3. 上面显示的评估是 LR(1)。如果为真，LR(0) 评估会是什么样子？

现在什么是正确的，1、2 或 3 还是完全不同的？

我正在尝试使用 nlp 分析情绪。我使用的 stanford-nlp 版本是 3.4.1。我有一些垃圾数据要处理，使用默认 PCFG 文件处理似乎需要大约 45 秒。

这是示例：

根据这里的建议，我再次尝试使用 shift-reduce 解析器。

我必须下载 shift-reduce 模型并将其放入类路径中。模型类正在加载，但它抛出了一个空指针异常。有什么想法和建议吗？

我正在为我们的编译器设计主题做一个移位减少算法。这是代码。

当我评论这printf("Stack = %s\nQueue = %s\n", stack, str);条线时，它运作良好。但是当我取消注释它时，它会返回 code 3221225477。

顺便提一句。这是出队函数：

和 addChar 函数：

最后替换功能。

PS。prod数组：

我正在尝试解析正数和负数小数。

包含前两个规则会产生移位/减少冲突，但我不知道如何编写语法以使冲突永远不会发生。我正在使用柠檬解析器。

编辑：来自 .out 文件的冲突

编辑 2：导致问题的最小语法