编译原理 什么是移进规约冲突

### 编译原理中的移进规约冲突

#### 移进规约冲突的解释与定义

在编译器设计中，特别是对于自底向上解析方法如LR(0)，SLR(1)，LALR(1)以及LR(k)[^3]而言，移进/规约（shift/reduce）冲突是指当分析器处于某个特定状态并面对下一个输入符号时无法决定应该执行移进操作还是应用某条产生式的规约动作的情况。

#### 冲突的原因

发生这种情况的主要原因是由于某些上下文无关文法可能允许存在多于一种方式去匹配给定的部分输入字符串。具体来说，在构建有限自动机用于指导解析过程中，如果一个项目集包含了形如`A -> α·aβ`的形式，并且该状态下也存在着可以由其他规则通过规约完成的状态，则可能会遇到这样的困境：

- 如果当前读取到的符号正好能够作为上述形式中的终结符`a`被接受；
- 同时这个位置又恰好位于另一个非终结符即将被替换为其右侧表达式的位置上[^1]。

这表明在同一时刻既有可能继续向下一层深入探索新的可能性（即移进），也可能已经找到了一条完整的路径准备回溯总结成果（即规约）。然而两者不可兼得，因此造成了决策上的矛盾。

为了更清晰地理解这一点，考虑如下简单的例子：假设有一个语法规则`E → E + T | T`用来描述算术表达式的结构。当我们尝试解析类似于`T + T * F`这样具有二义性的输入序列时，就很容易陷入两难境地——不知道是在看到加号之后立即进行一次减缩好呢？还是要先等待乘法运算结束后再回头处理前面部分？

// 示例代码片段展示了一个简化版的语法表驱动程序
switch (action[state][lookahead]) {
    case Shift(s'):
        stack.push(state);
        state = s';
        break;
    case Reduce(A → β):
        for each symbol in β do pop(stack); // 反向遍历产生式右边
        new_state = goto[top_of_stack, A];
        stack.push(new_state);
        break;
}