算符优先分析法原理

可视化演示

算符优先分析是一种自底向上的移进归约方法，通过定义算符间的优先关系构建优先矩阵。本文详解算符文法的定义条件、优... 切换模式查看不同维度。

算符文法定义

一本菜谱的第一页通常写着“本菜谱适用于中餐家庭小炒”。同样，算符优先分析法也不是对任何文法都适用，它只服务一类特殊文法——算符文法。想象大厨手里的菜谱有一条铁规矩：在任何一道工序里，两样生食材不能肩并肩直接下锅，中间必须隔着一层“调料工序”（非终结符）。只要这条规矩成立，大厨就能仅凭食材之间（终结符之间）的关系完成所有决策，不需要关心复杂的工序内部结构。

形式化地，文法 G 是一个四元组 $G=(V_T, V_N, S, P)$。$V_T$ 里的终结符是基础食材（如 +、*、i、(、)），$V_N$ 里的非终结符是工序名（如 E、T、F），P 是菜谱工序（产生式）的集合。算符文法要求：对 P 中任何产生式，右部都不会出现相邻两个终结符。例如 $E \rightarrow E+T$ 中，+ 的左边是 E、右边是 T，没有哪两个终结符直接贴在一起。这个条件看似苛刻，却恰好保证了分析过程“只看终结符”就能走通。

有了“不相邻”的规矩，大厨才能只靠看食材的先后手指挥全局，这是整套分析法坚实地基。它直接导致一个推论：非终结符在推导串中只扮演“缓冲垫”的角色，归约时不必深究它的名字——这让算法可以做得极其轻巧，但代价是分析能力受限。

优先关系判定

有了菜谱，大厨还需要知道每样食材谁先下锅，于是定义三种“下锅先后”关系：$a \lessdot b$ 表示 a 得等 b（b 先下锅，移进 b）；$a \gtrdot b$ 表示 a 先下锅（随后立即归约）；$a \equiv b$ 表示两样食材同时下锅、一同出锅。注意这是语法规格层面的“先手关系”，与数学上的大小比较无关。

三种关系从哪里来？都藏在产生式结构里。等于关系最容易判定：若产生式右部出现“终结符 a 紧跟终结符 b”（如 $U \rightarrow \cdots ab \cdots$），或“终结符 a 隔着非终结符 V 再碰终结符 b”（如 $U \rightarrow \cdots aVb \cdots$），则记 $a \equiv b$。例如 $F \rightarrow (E)$ 中 ( 与 ) 之间隔着一个非终结符 E，所以 ( 与 ) 是 $\equiv$ 关系。小于关系和大于关系则需要借助两个集合：FIRSTVT（首终结符集）和 LASTVT（尾终结符集），下一节展开。这里先给出小于关系的判定公式：

大厨在冰箱上贴出这批关系规则后，每当锅铲遇见“终结符 a + 工序 V”的组合，就知道 V 产出的一切首味都要给 a 让道。三种关系并非靠直觉规定，而是完全由产生式的骨架派生，这保证了分析器可以机械化地构造。

FIRSTVT计算

FIRSTVT 全称 First Terminal Set，即“首终结符集”。回到厨房：每种工序（非终结符）一开始运转，锅里最先飘出的香气是哪一味？FIRSTVT(U) 记录的就是从 U 出发能够“最先见到的终结符”清单。它是上一节 $\lessdot$ 关系的燃料——没有这份清单，小于关系就无处落笔。

定义：U 经过一步或多步推导，得到的符号串若以终结符 b 开头，或形如“非终结符 V 紧跟终结符 b”开头，则 b 进入 FIRSTVT(U)。计算时只有两条规则：直接规则——若有产生式 $U \rightarrow a\cdots$ 或 $U \rightarrow Va\cdots$，则 a 直接加入 FIRSTVT(U)；传递规则——若有产生式 $U \rightarrow V\cdots$，则 FIRSTVT(V) 全部并入 FIRSTVT(U)。两条规则不断迭代，直到所有集合不再变化为止，这个过程称为“迭代至不动点”。

以经典文法 $E \rightarrow E+T \mid T$、$T \rightarrow T*F \mid F$、$F \rightarrow (E) \mid i$ 为例，算得 $FIRSTVT(F)=\{(, i\}$，$FIRSTVT(T)=\{*, (, i\}$，$FIRSTVT(E)=\{+, *, (, i\}$。有了首味清单，大厨查“一开工第一口是什么”只需一瞥，$\lessdot$ 关系的所有原材料都已备齐。

LASTVT计算

与 FIRSTVT 相对，LASTVT 是“串尾终结符集”，记录工序完成装盘前留在锅底的最后一位味道。它与 FIRSTVT 完全对称：一个管开头，一个管结尾，两者拼起来才覆盖 $\lessdot$ 与 $\gtrdot$ 的全部判定需求。

LASTVT 的定义与计算规则完全镜像 FIRSTVT：U 推导出的串若以终结符 a 结尾，或形如“终结符 a 后跟非终结符 V”结尾，则 a 属于 LASTVT(U)。直接规则——若有产生式 $U \rightarrow \cdots a$ 或 $U \rightarrow \cdots aV$，则 a 直接加入 LASTVT(U)；传递规则——若有产生式 $U \rightarrow \cdots V$，则 LASTVT(V) 全部并入 LASTVT(U)。同样迭代至不动点。

对同样文法计算得到 $LASTVT(F)=\{), i\}$，$LASTVT(T)=\{*, ), i\}$，$LASTVT(E)=\{+, *, ), i\}$。你会发现尾味清单几乎就是首味清单的“镜像投影”——把 ( 换成 )，把开头的 + 保留到结尾。这份对称性正是算符优先分析优雅之处：记住一套算法，两套集合都能算。

优先矩阵构造

食材的关系规则攒了一堆，大厨把它们整理成一张“食材搭配速查表”——优先矩阵。矩阵的行和列都是终结符（外加结束符 #），交叉格子里填三者之一：$\lessdot$、$\equiv$、$\gtrdot$，没有关系的格子留空。查询时，行是栈顶终结符，列是当前输入终结符，一眼就能决定动作。

构造算法分三步走。第一步，求所有非终结符的 FIRSTVT 与 LASTVT。第二步，逐条扫描产生式右部：出现相邻终结符对或“a V b“模式则填 $\equiv$；出现”终结符 a 后跟非终结符 V“模式，对 FIRSTVT(V) 的每个 b 填 $a \lessdot b$；出现”非终结符 V 后跟终结符 b”模式，对 LASTVT(V) 的每个 a 填 $a \gtrdot b$。第三步，补结束符 #：# 对文法开始符号 S 的首终结符集合全填 $\lessdot$，S 的尾终结符集合对 # 全填 $\gtrdot$，# 对 # 填 $\equiv$。若同一格子被填上两个不同关系，该文法就不是算符优先文法——这是冲突检测，一票否决。

以经典表达式文法生成的 6×6 优先矩阵如下（# 为结束符）：

| 关系 | + | * | i | ( | ) | # |

| --- | --- | --- | --- | --- | --- | --- |

| + | ⋗ | ⋖ | ⋖ | ⋖ | ⋗ | ⋗ |

| * | ⋗ | ⋗ | ⋖ | ⋖ | ⋗ | ⋗ |

| i | ⋗ | ⋗ | — | — | ⋗ | ⋗ |

| ( | ⋖ | ⋖ | ⋖ | ⋖ | ≡ | — |

| ) | ⋗ | ⋗ | — | — | ⋗ | ⋗ |

| # | ⋖ | ⋖ | ⋖ | ⋖ | — | ≡ |

这张表就是大厨贴在灶台旁的“终极速查表”：炒到任何一步，只需看栈顶调味料与案板下一位食材的交叉格，动作一目了然。构造过程完全机械化，因此优先矩阵适合用程序自动生成——这正是我们稍后会在 Python 演示中做的事。

移进归约算法

有了速查表，大厨开始正式掌勺。分析器维护一个栈（锅）与输入缓冲区（案板），栈底和输入末尾都放哨兵 #。每一轮动作只看两样东西：栈中最近的终结符（栈顶终结符）与当前输入符号，查表后四选一：$\lessdot$ 或 $\equiv$ 则移进（把输入符号铲入锅中），$\gtrdot$ 则归约（把锅中最左素短语盛出装盘，压入非终结符），# 对 # 则接受，查不到关系则报语法错误。

这里关键的“出锅”对象叫最左素短语。素短语是句型中一个至少含一个终结符、且自身不再包含更小素短语的短语。它在栈中呈现固定形态：以终结符 $a_i$ 开头，以终结符 $a_j$ 结尾，中间夹着若干非终结符与终结符，且满足“左界 $\lessdot$、内部 $\equiv$、右界 $\gtrdot$”：

以 $i+i*i$ 为例：初始栈 #、输入 i+i*i#，查表 # ⋖ i 移进；栈 #i、输入首 +，查表 i ⋗ +，归约 i→N；随后 # ⋖ + 移进……如此反复，直到 # 与 # 相遇时接受。整个过程中大厨从来不问“这锅菜叫什么名”，只认关系符号，这就是算符优先分析的风格：轻快、机械、无需记忆状态。

优先函数优化

矩阵虽然直观，但查表意味着保存一张 $n \times n$ 的二维表格。大厨的灶台有限，能不能更省？优先函数是一种压缩技巧：给每个终结符 a 派发两个整数 $f(a)$、$g(a)$，用数值比较代替矩阵查询。若 a 所在行和 b 所在列的交叉关系是 $\lessdot$，则要求 $f(a) < g(b)$；$\equiv$ 则 $f(a) = g(b)$；$\gtrdot$ 则 $f(a) > g(b)$。查询时只需 O(1) 次整数比较，空间从 $n^2$ 降到 $2n$。

构造方法是迭代打分：先把所有 f、g 设为 1，然后反复扫描矩阵——若 $a \lessdot b$ 但当前 $f(a) \ge g(b)$，就把 $g(b)$ 抬到 $f(a)+1$；若 $a \gtrdot b$ 但 $f(a) \le g(b)$，就把 $f(a)$ 抬到 $g(b)+1$；直到所有条件满足。若迭代步数超过 $2n$ 仍未收敛，说明原矩阵不存在等价优先函数。

优先函数不仅节省空间，还能借助整数比较提升解析器速度，是早期编译器中的经典优化。但代价也存在：数值比较会把矩阵中“无关系”的空格也强行赋予大小，从而掩盖某些本应报错的组合——因此工业实现中保留冲突检测机制尤为重要。

错误处理工具

大厨也有失手的时候：某一步查表发现交叉格是空的，没有任何优先关系——这意味着锅里的食材搭配根本不在菜谱上，即输入串存在语法错误。算符优先分析的错误处理就像“尝一口发现问题”。常见策略有三种：跳过输入符号直到找到能与栈顶恢复关系的符号；弹出栈顶符号放弃部分已处理内容；两者结合，先弹栈再跳符号，尽量让分析器回到可继续的轨道。由于算符优先分析不携带状态信息，错误恢复做不到精确定位，但足以满足多数编译场景的“报错并继续”需求。

在工业实践中，Yacc/Bison 这类解析器生成器虽然采用 LALR 分析，却借鉴了同一思想：用户用 %left '+'、%left '*'、%prec UMINUS 等声明终结符优先级，生成器据此化解移进/归约冲突。这与算符优先分析中“用终结符关系决定动作”的哲学一脉相承，区别在于 Yacc 的优先级声明是人为附加的语义信息，而算符优先分析中的关系完全从文法自动导出。

与 LR 分析对比：LR 分析器归约的是句柄（含状态与展望信息），能力更强；算符优先分析器归约的是最左素短语，不看状态，只认终结符关系。前者像一位经验丰富、记得每道菜火候细节的大厨；后者像一位只凭食材搭配速查表就能出菜的快厨——快而稳，但只会做表上的菜。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-"""算符优先分析: 计算 FIRSTVT / LASTVT 并构造优先关系矩阵""" raw = {    'E': [['E', '+', 'T'], ['T']],    'T': [['T', '*', 'F'], ['F']],    'F': [['(', 'E', ')'], ['i']],} terminals = {'#'}nonterminals = set()productions = [] for lhs, rhs_list in raw.items():    nonterminals.add(lhs)    for rhs in rhs_list:        productions.append((lhs, rhs))        for s in rhs:            if s.isupper():                nonterminals.add(s)            else:                terminals.add(s)  def firstvt():    first = {nt: set() for nt in nonterminals}    changed = True    while changed:        changed = False        for lhs, rhs in productions:            first_sym = rhs[0]            if first_sym in terminals:                if first_sym not in first[lhs]:                    first[lhs].add(first_sym)                    changed = True            else:                for t in first[first_sym]:                    if t not in first[lhs]:                        first[lhs].add(t)                        changed = True                if len(rhs) > 1 and rhs[1] in terminals:                    if rhs[1] not in first[lhs]:                        first[lhs].add(rhs[1])                        changed = True    return first  def lastvt():    last = {nt: set() for nt in nonterminals}    changed = True    while changed:        changed = False        for lhs, rhs in productions:            last_sym = rhs[-1]            if last_sym in terminals:                if last_sym not in last[lhs]:                    last[lhs].add(last_sym)                    changed = True            else:                for t in last[last_sym]:                    if t not in last[lhs]:                        last[lhs].add(t)                        changed = True                if len(rhs) > 1 and rhs[-2] in terminals:                    if rhs[-2] not in last[lhs]:                        last[lhs].add(rhs[-2])                        changed = True    return last  def build_relations(first, last):    eq, lt, gt = set(), set(), set()    for lhs, rhs in productions:        for i, s in enumerate(rhs):            if s in terminals:                if i + 1 < len(rhs) and rhs[i + 1] in terminals:                    eq.add((s, rhs[i + 1]))                if (i + 2 < len(rhs) and                        rhs[i + 1] in nonterminals and                        rhs[i + 2] in terminals):                    eq.add((s, rhs[i + 2]))            else:                if i > 0 and rhs[i - 1] in terminals:                    for b in first[s]:                        lt.add((rhs[i - 1], b))                if i + 1 < len(rhs) and rhs[i + 1] in terminals:                    for a in last[s]:                        gt.add((a, rhs[i + 1]))    return eq, lt, gt  def main():    first = firstvt()    last = lastvt()    for nt in sorted(nonterminals):        print('FIRSTVT(%s) = %s' % (nt, sorted(first[nt])))        print('LASTVT(%s)  = %s' % (nt, sorted(last[nt])))     eq, lt, gt = build_relations(first, last)    for b in first['E']:        lt.add(('#', b))    for a in last['E']:        gt.add((a, '#'))    eq.add(('#', '#'))     rel = {}    for a, b in eq:        rel[(a, b)] = '='    for a, b in lt:        rel[(a, b)] = '<'    for a, b in gt:        rel[(a, b)] = '>'     ts = ['#'] + sorted(terminals - {'#'})    print('优先关系矩阵 (< 表示先移进, > 表示可归约, = 表示同煎):')    print('     ' + ''.join('%3s' % c for c in ts))    for a in ts:        line = ['%3s' % a]        for b in ts:            line.append('%3s' % rel.get((a, b), '.'))        print(''.join(line))     conflicts = [p for p in rel if sum(p in s for s in (eq, lt, gt)) > 1]    print('冲突数量:', len(conflicts))  if __name__ == '__main__':    main()

1. raw = {...}用嵌套字典表示文法，每个非终结符映射到一个产生式列表。
2. productions.append((lhs, rhs))把每条产生式展平成二元组，方便后续逐条扫描。
3. first = {nt: set() for nt in nonterminals}为每个非终结符初始化一个空集合，后续迭代填充。
4. while changed:只要本轮有新增元素就继续迭代，直到集合稳定（不动点）。
5. if first_sym in terminals:右部首符号是终结符时，直接按直接规则加入集合。
6. for t in first[first_sym]:右部首符号是非终结符时，把它已有的 FIRSTVT 全部继承过来（传递规则）。
7. if len(rhs) > 1 and rhs[1] in terminals:处理 U → V a ... 形式，第二个符号是终结符也直接加入。
8. last_sym = rhs[-1]LASTVT 与 FIRSTVT 完全对称，从右部末尾开始处理。
9. lt.add((rhs[i - 1], b))发现“终结符 a 后跟非终结符 V”时，批量填入 a 与 FIRSTVT(V) 的小于关系。
10. conflicts = [p for p in rel if sum(p in s for s in (eq, lt, gt)) > 1]检查是否有同一对关系被重复标记，用于冲突检测。

常见误区

面试题