LR分析系统中R的含义疑问：对最右推导逆过程的困惑

嗨，我太懂你现在的困惑了——L（左到右不回溯读输入）很好理解，但这个R（逆向最右推导）总觉得像隔着一层雾，对吧？咱们拿你给的算术文法E → E + E | E * E | (E) | id一步步掰明白。

先搞清楚：什么是最右推导？ #

最右推导的核心就是每次推导都优先替换当前字符串里最靠右的非终结符。举个例子，要推导句子id + id * id，最右推导的步骤是这样的：

1. E → E + E          // 从开始符号E出发，选第一个产生式，此时最右的非终结符是第二个E
2. E + E → E + E * E  // 把最右的E替换成E*E，现在最右的非终结符是第三个E
3. E + E * E → E + E * id  // 把最右的E替换成id（终结符，没法再推导了）
4. E + E * id → E + id * id  // 现在最右的非终结符是第二个E，替换成id
5. E + id * id → id + id * id  // 最后把最左的E替换成id，得到目标句子

你看，最右推导里，每一步都是先把最右边的“可变”部分（非终结符）换成终结符或者其他串，所以句子里最靠右的终结符是最早“固定”下来的。

那LR里的“逆向最右推导”是什么意思？ #

LR分析器不是从E开始“往下推”出句子，而是反过来：从输入句子出发，一步步“往上归约”回开始符号E，这个归约过程刚好是最右推导的逆过程。

还是拿id + id * id举例，逆向最右推导（也就是LR的归约过程）是这样的：

1. id + id * id → E + id * id  // 把最左边的id归约成E（对应最右推导的第5步逆过程）
2. E + id * id → E + E * id    // 把中间的id归约成E（对应最右推导的第4步逆过程）
3. E + E * id → E + E * E      // 把最右边的id归约成E（对应最右推导的第3步逆过程）
4. E + E * E → E + E           // 把`E * E`归约成E（对应最右推导的第2步逆过程）
5. E + E → E                   // 把`E + E`归约成E（对应最右推导的第1步逆过程）

这里的关键是句柄——每一步要归约的那个串，就是最右推导中最后被替换的那个部分。LR分析器左到右读输入时，会跟踪当前的状态，判断什么时候已经读到了句柄的右端，然后就可以把这个句柄归约成对应的非终结符，一步步往回走。

为什么LR要选逆向最右推导？ #

这其实是适配“左到右扫描”的最优选择：

• 最右推导的句柄，其右端刚好是我们左到右读输入时的当前位置——当我们读到某个字符时，句柄的完整范围已经确定了，不用回溯就能判断要不要归约。
• 如果换成逆向最左推导，那句柄可能在输入的左边，还没读到后面的字符就需要归约，这对左到右扫描的分析器来说非常不友好。

总结一下 #

• L：分析器从左到右读输入，读了就不回头，这个你已经理解到位了。
• R：分析的过程是逆向的最右推导——从输入句子出发，通过不断识别并归约句柄，一步步还原到文法的开始符号，每一步都对应最右推导步骤的反向操作。

内容的提问来源于stack exchange，提问作者mustafa salim