如何解析这个简单的语法？模棱两可吗？
How to parse this simple grammar? Is it ambiguous?
我正在深入研究解析，遇到了一个我不太明白的问题。我编了下面的语法：
S = R | aSc
R = b | RbR
其中 S 是起始符号。可以证明 abbbc 是基于此语法的有效句子，希望这是正确的，但我可能完全误解了某些东西。如果我尝试使用递归下降来实现它，我在尝试使用左派生 eg
解析 abbbc 时似乎遇到了问题
S => aSc
aSc => aRc
在这一点上，我认为递归下降会在第二个产生式中选择第一个选项，因为下一个标记是 b 导致：
aRc => abc
我们已经完成了，因为没有更多的非终端，这当然不是 abbbc。证明 abbbc 有效的唯一方法是选择第二个选项，但我假设它总是选择 b。我不认为语法有歧义，除非我错过了什么。那我做错了什么？
更新： 我在 https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/ 遇到了这个不错的推导应用程序。我曾经做过完整性检查，以确保 abbbc 是一个有效的句子，而且确实如此。
仔细想想这个问题，是不是说我不能用LL(1)来解析这个文法，而实际上需要LL(2)？通过两次前瞻，我可以在第二个产品中正确地选择第二个选项，因为我现在也知道有更多的标记要读取，因此选择 b 会过早地终止推导。
首先，很高兴您发现我们的 CFG 工具很有用！我的几个助教不久前就做到了，我们已经从中取得了很多成就。
你的语法确实有歧义。这源于您的 R 非终结符：
R → b | RbR
一般来说，如果您的递归产生式规则中包含同一个非终结符的两个副本，则会导致歧义，因为对于如何应用规则两次会有多个选项。例如，在这种情况下，您可以通过先将 R 扩展为 RbR 来导出 bbbbb，然后
- 将左边的 R 扩展为 RbR 并将每个 R 转换为 b，或者
- 将右 R 扩展为 RbR 并将每个 R 转换为 b。
因为这个文法是有歧义的，所以对于 k 的任何选择都不会是 LL(k)，因为所有 LL(k) 文法都必须是无歧义的。这意味着加强解析器的能力在这里无济于事。您需要重写语法才能避免歧义。
您在此处描述的非终结符 R 生成其中包含奇数个 b 的字符串，因此我们可以尝试重新设计 R 以更直接地实现这一点。最初的尝试可能是这样的：
R → b | bbR
不幸的是，这不是 LL(1)，因为在看到单个 b 之后，您不清楚您是应该应用第一个生产规则还是第二个。然而，它是 LL(2).
如果你想要 LL(1) 语法，你可以这样做：
R → bX
X → bbX | ε
这是通过放置一个 b，然后放置任意多对可选的 b 来实现的。
我正在深入研究解析，遇到了一个我不太明白的问题。我编了下面的语法：
S = R | aSc
R = b | RbR
其中 S 是起始符号。可以证明 abbbc 是基于此语法的有效句子，希望这是正确的，但我可能完全误解了某些东西。如果我尝试使用递归下降来实现它，我在尝试使用左派生 eg
解析 abbbc 时似乎遇到了问题S => aSc
aSc => aRc
在这一点上，我认为递归下降会在第二个产生式中选择第一个选项，因为下一个标记是 b 导致：
aRc => abc
我们已经完成了，因为没有更多的非终端，这当然不是 abbbc。证明 abbbc 有效的唯一方法是选择第二个选项，但我假设它总是选择 b。我不认为语法有歧义，除非我错过了什么。那我做错了什么？
更新： 我在 https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/ 遇到了这个不错的推导应用程序。我曾经做过完整性检查，以确保 abbbc 是一个有效的句子，而且确实如此。
仔细想想这个问题，是不是说我不能用LL(1)来解析这个文法，而实际上需要LL(2)？通过两次前瞻，我可以在第二个产品中正确地选择第二个选项，因为我现在也知道有更多的标记要读取，因此选择 b 会过早地终止推导。
首先，很高兴您发现我们的 CFG 工具很有用！我的几个助教不久前就做到了，我们已经从中取得了很多成就。
你的语法确实有歧义。这源于您的 R 非终结符：
R → b | RbR
一般来说，如果您的递归产生式规则中包含同一个非终结符的两个副本，则会导致歧义，因为对于如何应用规则两次会有多个选项。例如，在这种情况下，您可以通过先将 R 扩展为 RbR 来导出 bbbbb，然后
- 将左边的 R 扩展为 RbR 并将每个 R 转换为 b，或者
- 将右 R 扩展为 RbR 并将每个 R 转换为 b。
因为这个文法是有歧义的，所以对于 k 的任何选择都不会是 LL(k)，因为所有 LL(k) 文法都必须是无歧义的。这意味着加强解析器的能力在这里无济于事。您需要重写语法才能避免歧义。
您在此处描述的非终结符 R 生成其中包含奇数个 b 的字符串，因此我们可以尝试重新设计 R 以更直接地实现这一点。最初的尝试可能是这样的：
R → b | bbR
不幸的是，这不是 LL(1)，因为在看到单个 b 之后，您不清楚您是应该应用第一个生产规则还是第二个。然而，它是 LL(2).
如果你想要 LL(1) 语法，你可以这样做：
R → bX
X → bbX | ε
这是通过放置一个 b，然后放置任意多对可选的 b 来实现的。