使用 CFG，让你爆切表达式解析题

zi2ven · 2025-06-10 14:40:04 · 算法·理论

表达式解析题是非常烦的题目，并且通常会让你在解析时做一些语义动作，例如短路等。这些题目如果硬切会让你怀疑人生+浪费数个小时的时间。那么接下来这里有一些快捷且易懂的表达式解析方法。

CFG

定义

CFG (Context-Free Grammar, 上下文无关文法) 是一种简单的文法，几乎所有的解析算法是从该文法的基础上诞生的。

CFG 有四个概念：

终结符 \Sigma
- 也就是字符或某个词法规则
- 类似 + * ( ) id等
非终结符 \mathrm{N}
- 某个语法规则
- E、T、F
起始符号 \mathrm{S}
- 从该符号开始解析
- E
产生式 \mathrm{P}
- “可替换”规则
- E → E + T T → F ...

如何产生

以下是一个四元组表示方式：

E → T E'
E'→ + T E' | ε
T → F T'
T'→ * F T' | ε
F → ( E ) | id

把起始符号 E 放在纸上。
找一条以 E 左侧开头的规则；例如 E → E + T，把左边的 E 换成右边整串。
继续在纸上找任意一个非终结符，再替换……

直到纸面上只剩终结符 id, +, (, ) … 为止。

E
⇒ E + T
⇒ T + T
⇒ F + T
⇒ id + T
⇒ id + T * F
⇒ id + F * F
⇒ id + id * id

过程中每一次替换叫一次推导，全程叫一棵推导树 / 语法树。

表达方式

除了四元组以外还有以下几种表达方式：

BNF / EBNF / ABNF
Antlr4
PEG

LL(k)

定义

两个 L 的含义

第 1 个 L：自左向右 (Left-to-right) 扫描输入串；
第 2 个 L：按 最左推导 (Leftmost derivation) 构造语法树。

$FIRST_k$ / $FOLLOW_k$： • $FIRST_k(\alpha) = \alpha$能推出的所有 **长 ≤ k** 的前缀终结符串集合； • $FOLLOW\_k(A)$ = 起始符号串 \$ 能推出的、其后紧跟 $A$ 时 **截取到 k** 的终结符串集合。当且仅当对每个非终结符 $A$ 的不同产生式 $FIRST_k(\alpha_i FOLLOW_k(A))\cap FIRST_k(\alpha_j FOLLOW_k(A))=\oslash

时，该文法才是 LL(k)。

解析

文法必须消除左递归并进行左因子化，使之 有可能 成为 LL(k)。

FIRST

F = { ε }
for symbol X in α:
    Fnew = ∅
    if X 终结符:
        for s in F:  Fnew += concat(s , {X})
    else (X 非终结符):
        for s in F, t in FIRST_k(X):  Fnew += concat(s , t)
    F = Fnew
return F

FOLLOW

初始化 FOLLOW_k(S) = {("$")} 迭代直到不再变化：

若产生式   A → α B β
  FOLLOW_k(B)  +=  FIRST_k( β  FOLLOW_k(A) )

预测表

对每条产生式  A → α
  lookset = FIRST_k( α FOLLOW_k(A) )
  对集合中的每个 w
      若 M[A,w] 已填且 ≠ α   → 冲突，非 LL(k)
      否则 M[A,w] = α

表驱动 LL(k) 解析

stack = [$ , S]          # $ 为输入结束符
pos   = 0
while (!stack.empty()):
    X = pop(stack)
    look = 下标 pos..pos+k-1 的终结符串(不足补 $)

    if X 终结符:
         若 X == look[0] → pos++            // 匹配并读入 1 符号
         否则出错
    else                 // X 为非终结符
         若 M[X,look] 未定义 → 出错
         否则把 α 右到左压栈
成功读取所有输入且栈清空 → 接受

Pratt Parser

定义

在《Crafting Interpreters》中，作者 Bob Nystrom 给 Lox 语言选用的解析技术叫做

Top-Down Operator Precedence (TDOP) ——通常也称 Pratt Parser

它既是递归下降又比经典 LL(1) 更灵活：

仍然自左向右扫描。
只看 1 个符号就够。
通过运算符优先级表解决表达式嵌套问题。

几乎不会遇到性能问题。

工作方式

expr(minPrec=LOWEST):
node = parsePrefix()           // 处理前缀/原子
while nextToken.prec ≥ minPrec // 根据优先级决定是否继续
    op      = advance()        // 消耗中缀运算符
    right   = expr(op.prec+1)  // 递归解析右操作数
    node    = new Binary(node, op, right)
return node

每个 token 类型登记两种函数

prefixFn —— 没有左操作数时怎么解析？
infixFn —— 有左操作数时怎么解析？优先级是多少？

expr() 用 循环而非递归链 处理左关联运算符，靠 while 条件把“小优先级”截断。

解析方式

处理文本流，将文本流解析为 Token 方便解析。
运行根表达式解析，每层匹配完对应的 Token 后返回相对应的表达式节点。