parsing - LR Parser reduce/reduce（YACC等）

Question

假设我有以下上下文无关语法，按特定顺序（对于 YACC）：

• z → x
• z → zx

如果我有以下输入：

(z (zx

解析器会减少：

1. “x”到“z”
2. 'z x' 到 'z'

我在想它的 2 号，但不太清楚为什么。非常感谢

编辑：更改输入以进行澄清

Answer 1

你的语法是左结合的，因为它是左递归的。左关联意味着当输入从左到右扫描时贪婪地完成生产。您总是有一个通过扫描另一个并减少z来延长到更长的时间。zx

关于您的问题，您无法输入z z x，因为输入由终端符号组成。大概x是一个终结符号（否则语法不完整）。z显然是非终结符。

你可以考虑一个部分的句子形式z z x。然而，这种语法不能生成这样的形式。

从 开始z，您的下一步是生成x（并因此完成）或生成z x. 之后的下一个可能步骤是以z两种方式之一替换 ： generate x x（并完成）或 generate z x x。

如您所见，z z x这些规则无法访问字符串。