Shift-reduce parser如何高效确定待应用的语法规则？

首先明确一个最容易被教材误导的点：所有生产环境可用的shift-reduce解析器，从来不会在运行时遍历所有文法规则、匹配栈顶内容来选规则。你看到的教材示例直接给出正确归约规则，是因为省略了解析前最核心的预计算步骤——构造LR分析表。
所有规则选择的判断逻辑，都会在解析开始前的预处理阶段全部算好，固化成两张只读查找表，运行时只需要根据栈顶状态和当前输入符号查表，就能直接拿到要执行的动作，单步判断是O(1)时间，整体解析效率和输入长度线性相关，根本不需要临时做规则匹配。

预处理阶段：构造LR分析表 #

构造分析表的核心是LR项的概念：LR项就是加了圆点标记的文法规则，圆点用来表示当前已经匹配到规则右部的哪个位置。以你给出的文法为例：

规则1：S -> S + S
规则2：S -> id

对应的所有LR项包括：

• S -> . S + S：还没匹配任何内容，接下来需要匹配非终结符S
• S -> S . + S：已经匹配完一个S，接下来需要匹配终结符+
• S -> S + . S：已经匹配完S+，接下来需要匹配非终结符S
• S -> S + S .：已经匹配完规则1的整个右部，可以执行归约
• S -> . id：还没匹配任何内容，接下来需要匹配终结符id
• S -> id .：已经匹配完规则2的整个右部，可以执行归约

通过计算项集的闭包、项集之间的跳转关系，就能得到所有解析状态，最终生成两张全局固定的查找表：

• 动作表（Action Table）：行索引是解析状态编号，列索引是所有终结符（包括结束标记$），表项存储三类动作：
  • 移进（Shift n）：将当前输入符号压栈，跳转至状态n
  • 归约（Reduce r）：用编号为r的文法规则执行归约
  • 接受（Accept）：输入解析完成，语法合法
• 转移表（Goto Table）：行索引是解析状态编号，列索引是所有非终结符，表项存储归约后需要跳转的状态编号

运行时规则选择逻辑（对应你的示例） #

运行时解析栈存储的不是单纯的文法符号，而是<状态, 符号>二元组，每一步的动作完全由查表结果决定，不需要做任何规则遍历或匹配。
我们对应你列出的解析栈场景，逐步骤说明判定逻辑（为方便理解，状态做简单编号）：

1. 初始栈为[<0, $>]，当前输入第一个符号是id：查Action表得到Shift 2，将<2, id>压栈，对应栈状态$ id
2. 栈顶状态为2，当前输入符号是+：查Action表得到Reduce 2（用规则2S->id归约）。弹出1个栈元素（规则2右部长度为1），回到栈顶状态0，查Goto表Goto[0][S] = 1，将<1, S>压栈，对应栈状态$ S
3. 栈顶状态为1，当前输入符号是+：查Action表得到Shift 3，将<3, +>压栈，对应栈状态$ S +
4. 栈顶状态为3，当前输入符号是id：查Action表得到Shift 2，将<2, id>压栈，对应栈状态$ S + id
5. 栈顶状态为2，当前输入符号是$：查Action表得到Reduce 2（用规则2S->id归约）。弹出1个栈元素，回到栈顶状态3，查Goto表Goto[3][S] = 4，将<4, S>压栈，对应栈状态$ S + S
6. 栈顶状态为4，当前输入符号是$：查Action表得到Reduce 1（用规则1S->S+S归约）。弹出3个栈元素（规则1右部长度为3），回到栈顶状态0，查Goto表Goto[0][S] = 1，将<1, S>压栈，对应栈状态$ S
7. 栈顶状态为1，当前输入符号是$：查Action表得到Accept，解析结束

核心伪代码实现 #

// 预处理阶段生成的全局只读表，解析前构造完成，运行时不修改
const Action: Map<(state: Int, terminal: String), Action>
// Action的三类取值：
// {type: "shift", nextState: Int}
// {type: "reduce", ruleId: Int}
// {type: "accept"}
const Goto: Map<(state: Int, nonTerminal: String), Int>
// 规则表，存储每条文法规则的左部符号、右部长度
const Rules: Array<{left: String, rightLen: Int}>

function parse(input: Array<String>): Bool {
    // 初始化栈，压入初始状态0和栈底标记$
    const stack: Array<{state: Int, symbol: String}> = [{state: 0, symbol: "$"}]
    let inputCursor = 0
    input.push("$") // 输入末尾补结束标记

    while (True) {
        const currentState = stack[stack.length - 1].state
        const currentToken = input[inputCursor]
        const action = Action.get(currentState, currentToken)

        if (action.type == "shift") {
            // 移进：压入当前符号和新状态，输入指针后移
            stack.push({state: action.nextState, symbol: currentToken})
            inputCursor += 1
        } else if (action.type == "reduce") {
            // 归约：弹出对应长度的栈元素，压入归约后的非终结符
            const targetRule = Rules[action.ruleId]
            // 不需要校验栈内容，LR表已经保证栈顶一定匹配规则右部
            stack.splice(stack.length - targetRule.rightLen, targetRule.rightLen)
            const prevState = stack[stack.length - 1].state
            const nextState = Goto.get(prevState, targetRule.left)
            stack.push({state: nextState, symbol: targetRule.left})
        } else if (action.type == "accept") {
            // 解析成功
            return True
        } else {
            // 触发语法错误
            throw Error(`Syntax error at position ${inputCursor}`)
        }
    }
}

补充说明 #

• 你给出的S -> S + S属于二义性文法，构造分析表时会出现移进/归约冲突，工程上只需要给符号定义优先级和结合性（比如定义+为左结合，优先级高于id），冲突时直接选择优先级更高的动作即可，不需要修改文法。
• 归约时不需要额外校验栈中符号是否匹配规则右部，LR分析表的构造过程已经保证了合法输入下栈内容一定符合规则要求，运行时直接弹出对应长度的元素即可，没有额外匹配开销。
• 部分教材提到的回溯式shift-reduce实现会在运行时遍历规则尝试匹配，效率极低且存在回溯开销，仅存在于理论示例中，没有实际生产使用价值。

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