LR(1)与LALR(1)状态机构造算法的时间复杂度分析

一、LR(1)状态机构造算法的时间复杂度 #

先给出《龙书》中的LR(1)状态机构造算法：

initialize C to Closure([S` -> .S, $])
repeat
    for each state in C
        for each grammar symbol X
            if Goto(state, X) is not empty and is not in C
                add Goto(state, X) to C
until no new states are added

关键变量定义 #

设：

• 终结符数量为 n
• 非终结符数量为 m，文法符号总数（终结符+非终结符）为 t = n + m
• 产生式规则数量为 k

分步骤复杂度分析 #

1. Closure操作：已知最坏时间复杂度为 O(n*k)，每个新状态生成时都需要执行一次Closure。
2. 外层循环（repeat-until）：
   • LR(1)的状态总数 S_LR 最坏情况下为 **O(k*2^{n)**——因为每个LR(1)项目是「产生式+展望符」的组合，展望符是终结符的子集，最多有2}n种可能，每个产生式的不同位置对应不同的项目，因此总状态数是产生式数量与展望符组合数的乘积级。
   • 每次循环会遍历当前所有状态，每个状态需要遍历t个文法符号计算Goto；判断状态是否已存在的操作（in C）假设为O(1)（如用哈希表实现），生成新状态时需执行Closure。

综上，LR(1)构造算法的最坏时间复杂度为：
$$T_{LR} = O(S_{LR} \times t \times nk) = O(n^2k2(n+m)2^n)$$

平均情况下，由于实际文法的展望符组合不会达到理论上限，复杂度会远低于最坏情况。

二、LALR(1)与LR(1)的运行时间区分 #

LALR(1)的构造仅修改了算法中in C的判定逻辑：判断新生成的状态是否与已有状态核心相同（核心指去掉展望符后的LR(0)项目集），而非完全相同的LR(1)项目集。

核心差异的数学量化 #

1. 状态总数差异：
   • LALR(1)的状态总数 S_{LALR} 等于LR(0)的状态数，最坏情况下为 O(k)——因为LR(0)状态仅关注产生式的位置，不涉及展望符，状态数与产生式数量同量级，远小于LR(1)的$O(k*2^n)$。
2. 运行时间公式：
   假设in C操作的复杂度不变（均为O(1)），Goto操作（不含Closure）的时间为常数级$O(1)$，则：
   • LR(1)总运行时间：$T_{LR} = Θ(nk^2(n+m)2n)$
   • LALR(1)总运行时间：$T_{LALR} = Θ(nk^2(n+m))$

二者的核心差距在于终结符数量n的指数项：LR(1)的时间复杂度随n呈指数增长，而LALR(1)是多项式级增长，这是因为LALR(1)合并了相同核心的状态，避免了LR(1)中因展望符组合导致的状态爆炸。

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