Si2C

Appearance

语法分析 ​

概念 ​

语法分析（parsing）是对着文法，把记号流组织成一棵语法树，并回答一个问题：这串记号是不是一个合法的句子。

上一层交给它的是一串扁平记号；它交出去的是一棵树：

记号流： int x = 3 + 42 ;          （扁的，只有先后关系）
语法树： 一棵以 声明/表达式 为根的结构   （有嵌套、有层次）

语法错误就在这一步报：int x = ; 少了右值，词法层完全看不出来（= 和 ; 都是合法记号），是语法分析发现"= 后面接不上 ;"。

这里有个关键分界：语法分析只管"结构像不像"，不管"意思对不对"。a = b + 1; 里 b 没声明，结构完全合法，那是语义分析（下一章）的事。

原理 ​

一、上下文无关文法（CFG） ​

文法是一个四元组 G=(VT, VN, P, S)：

符号含义例（赋值表达式文法）
VT终结符集合（就是记号）id、num、+、*、(、)
VN非终结符集合E、T、F
P产生式集合E → E + T、F → ( E )……
S开始符号E

为什么用"上下文无关"：一条产生式左边永远只有一个非终结符，替换它时不看左右邻居。这让分析算法可以只看有限窗口就做决定——如果允许"上下文相关"，剪枝空间会爆炸。

二、推导、语法树、二义性 ​

  • 推导：从开始符号出发，反复用产生式替换非终结符，直到只剩终结符。每一步都替换最左边的非终结符叫最左推导；替换最右边的叫最右推导（也叫规范推导）。
  • 句型 vs 句子：推导中途得到的串（可能还含非终结符）叫句型；全是终结符了才叫句子。
  • 语法树（分析树）：把推导过程画成树，每个内部结点是一次替换，叶子是终结符。同一棵语法树可以对应多次推导，但最左推导与最右推导各自唯一。
  • 二义性：一个句子有两棵不同的语法树，文法就是二义的。经典的两个例子：
二义句子两种理解通行解法
1 + 2 * 3(1+2)*3 还是 1+(2*3)把优先级写进文法分层（E→T、T→F）
if (a) if (b) s1; else s2;else 配哪个 if规定 else 与最近的未匹配 if 配对

二义性不一定要"消除"：把优先级和结合性显式写进文法分层，比事后加规则更可靠。

三、自顶向下：LL(1) ​

从开始符号出发，"猜"着往下推。关键是每一步只看一个记号（1 个 lookahead）就能确定用哪条产生式。

判断能不能做到，靠两个集合：

  • FIRST(α)：从 α 出发能推导出的第一个终结符的集合；若 α 能推出空串 ε，则 ε ∈ FIRST(α)。
  • FOLLOW(A)：在所有句型里，紧跟在 A 后面的终结符集合（$ 表示串尾）。

于是产生式 A → α 的可选集 = FIRST(α)；若 α 能推 ε，还要并上 FOLLOW(A)。两个不同的产生式可选集相交 → 不是 LL(1)。

两大障碍：

  1. 左递归：E → E + T 会让递归下降的 E() 一进来就再调 E()，第一个记号还没消费就无限递归。改写为右递归：E → T E'、E' → + T E' ∣ ε。
  2. 回溯：如果一条产生式试错了要退回来重试，复杂度就退化。LL(1) 的意义正是永不回溯。

四、自底向上：LR ​

把记号一个一个移进栈里，等到栈顶形成一条产生式的右部（这个可归约串叫句柄）就归约它。核心是一张分析表，两项动作：

动作含义
s5移进，转到状态 5
r3用第 3 条产生式归约
acc接受
空白出错

按"看多远"和"表怎么造"，LR 家族分四档：

档次看多远表的大小能力
LR(0)不看 lookahead最小最弱，冲突多
SLR(1)归约时看 FOLLOW小够用
LALR(1)归约时看更精确的 lookahead中工业界主流（yacc/bison）
LR(1)全看最大最强，但表会膨胀十倍

两类冲突：移进-归约冲突（不知道该移进还是该归约）与归约-归约冲突（不知道用哪条产生式归约）。归约-归约冲突是文法层面真有二义，必须改文法；移进-归约冲突常常可以靠"算符优先级"裁决。

五、两条路线对比 ​

项LL(1)（自顶向下）LR(1)（自底向上）
建树顺序先根后叶先叶后根
能处理的文法不含左递归、可选集不冲突范围大得多
左递归必须先消除天然支持
动作位置可在产生式中间插入语义动作只在归约时做动作
典型工具手写递归下降（GCC/Clang 前端就是）yacc / bison
错误恢复好（知道"期望什么"）稍难

示例 ​

文法与它的树 ​

用一套消除了左递归的表达式文法：

E  -> T E'
E' -> + T E' | eps
T  -> F T'
T' -> * F T' | eps
F  -> ( E ) | num

3 + 4 * 5 的语法树（分析树，含全部非终结符）：

E
├─ T
│  └─ F  ->  3
└─ E'
   ├─ +
   ├─ T
   │  ├─ F  ->  4
   │  └─ T'
   │     ├─ *
   │     ├─ F  ->  5
   │     └─ T'  ->  eps
   └─ E'  ->  eps

同一句话的抽象语法树（AST，丢掉所有非终结符，只留运算符与操作数）：

      (+)
     /   \
    3    (*)
        /   \
       4     5

编译器内部用的是后者：非终结符只是分析时的脚手架，进不了后续阶段。

例 1：递归下降求值（C） ​

#include <stdio.h>
#include <ctype.h>

/* E -> T E' ; E' -> + T E' | eps ; T -> F T' ; T' -> * F T' | eps ; F -> ( E ) | num */
static const char *s;

static int E(void);

static int F(void) {                       /* F -> ( E ) | num */
    if (*s == '(') {
        s++;                               /* 吃 '(' */
        int v = E();
        s++;                               /* 吃 ')' */
        return v;
    }
    int v = 0;
    while (isdigit((unsigned char)*s)) v = v * 10 + (*s++ - '0');
    return v;
}

static int T(void) {                       /* T -> F T' ；循环即 T' -> * F T' | eps */
    int v = F();
    while (*s == '*') { s++; v = v * F(); }
    return v;
}

static int E(void) {                       /* E -> T E' ；循环即 E' -> + T E' | eps */
    int v = T();
    while (*s == '+') { s++; v = v + T(); }
    return v;
}

int main(void) {
    const char *tests[3] = {"3+4*5", "(3+4)*5", "2*3+4*5"};
    for (int i = 0; i < 3; i++) {
        s = tests[i];
        printf("%-8s = %d\n", tests[i], E());
    }
    return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

3+4*5    = 23
(3+4)*5  = 35
2*3+4*5  = 26

注意 E() 与 T() 里的 while 循环：它就是 E' → + T E' ∣ ε 的"右递归变迭代"。递归下降把尾递归写成循环，是标准手法——不然为了一条 ε 产生式就要多一层函数调用。

例 2：FIRST、FOLLOW 与预测分析表（Python 对照） ​

def pad(s, w):
    """按显示宽度补空格：中文算 2 列"""
    return s + " " * max(0, w - sum(2 if ord(c) > 0x2000 else 1 for c in s))

# 文法（已消除左递归）：
#   E  -> T E'
#   E' -> + T E' | eps
#   T  -> F T'
#   T' -> * F T' | eps
#   F  -> ( E ) | id
FIRST = {"E": {"(", "id"}, "E'": {"+", "eps"},
         "T": {"(", "id"}, "T'": {"*", "eps"},
         "F": {"(", "id"}}
FOLLOW = {"E": {")", "$"}, "E'": {")", "$"},
          "T": {"+", ")", "$"}, "T'": {"+", ")", "$"},
          "F": {"*", "+", ")", "$"}}

print("=== FIRST 集 ===")
for k in ["E", "E'", "T", "T'", "F"]:
    print("  " + pad("FIRST(%s)" % k, 14) + "= {" + ", ".join(sorted(FIRST[k])) + "}")
print()
print("=== FOLLOW 集 ===")
for k in ["E", "E'", "T", "T'", "F"]:
    print("  " + pad("FOLLOW(%s)" % k, 14) + "= {" + ", ".join(sorted(FOLLOW[k])) + "}")

# 预测分析表：行 = 非终结符，列 = 终结符
COLS = ["(", "id", "+", "*", ")", "$"]
TABLE = {
    "E":  {"(": "T E'",           "id": "T E'"},
    "E'": {"+": "+ T E'",         ")": "eps", "*": None, "$": "eps"},
    "T":  {"(": "F T'",           "id": "F T'"},
    "T'": {"+": "eps", "*": "* F T'", ")": "eps", "$": "eps"},
    "F":  {"(": "( E )",          "id": "id"},
}
print()
print("=== LL(1) 预测分析表 ===")
print("  " + pad("非终结符", 12) + "".join(pad(c, 10) for c in COLS))
for nt in ["E", "E'", "T", "T'", "F"]:
    cells = []
    for c in COLS:
        cells.append(TABLE[nt].get(c) or "-")
    print("  " + pad(nt, 12) + "".join(pad(x, 10) for x in cells))

# ---- 最左推导 ----
print()
print("=== 3 + 4 * 5 的最左推导 ===")
DERIV = [
    "E", "T E'", "F T' E'", "3 T' E'", "3 E'", "3 + T E'",
    "3 + F T' E'", "3 + 4 T' E'", "3 + 4 * F T' E'",
    "3 + 4 * 5 T' E'", "3 + 4 * 5 E'", "3 + 4 * 5",
]
for n in range(len(DERIV) - 1):
    print("  " + pad(DERIV[n], 22) + "=> " + DERIV[n + 1])
print("  -> 共 %d 步推导" % (len(DERIV) - 1))


# ---- 递归下降求值 ----
def tokenize(s):
    toks, i = [], 0
    while i < len(s):
        c = s[i]
        if c.isspace():
            i += 1
            continue
        if c.isdigit():
            j = i
            while j < len(s) and s[j].isdigit():
                j += 1
            toks.append(("num", s[i:j]))
            i = j
        else:
            toks.append((c, c))
            i += 1
    toks.append(("$", "$"))
    return toks


class Parser:
    def __init__(self, toks):
        self.t, self.i = toks, 0

    def peek(self):
        return self.t[self.i][0]

    def eat(self, kind):
        if self.peek() != kind:
            raise SyntaxError("期望 %s，实得 %s" % (kind, self.peek()))
        v = self.t[self.i][1]
        self.i += 1
        return v

    def E(self):                      # E -> T E'
        v = self.T()
        while self.peek() == "+":     # E' -> + T E' | eps
            self.eat("+")
            v = v + self.T()
        return v

    def T(self):                      # T -> F T'
        v = self.F()
        while self.peek() == "*":     # T' -> * F T' | eps
            self.eat("*")
            v = v * self.F()
        return v

    def F(self):                      # F -> ( E ) | id
        if self.peek() == "(":
            self.eat("(")
            v = self.E()
            self.eat(")")
            return v
        return int(self.eat("num"))


print()
print("=== 递归下降求值 ===")
for src in ["3+4*5", "(3+4)*5", "2*3+4*5"]:
    print("  " + pad(src, 12) + "= " + str(Parser(tokenize(src)).E()))
print("  对照 Python 的结果：" + pad("3+4*5", 12) + "= " + str(3 + 4 * 5)
      + "，" + pad("(3+4)*5", 10) + "= " + str((3 + 4) * 5))

# ---- 左递归不消除会怎样 ----
print()
print("=== 左递归 E -> E + T 的递归下降会无限递归 ===")
print("  E() 一进来就调 E()，第一个 token 还没消费 -> 栈溢出")
print("  消除办法：E -> T E'，把左递归改写成右递归（循环/尾递归）")
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

=== FIRST 集 ===
  FIRST(E)      = {(, id}
  FIRST(E')     = {+, eps}
  FIRST(T)      = {(, id}
  FIRST(T')     = {*, eps}
  FIRST(F)      = {(, id}

=== FOLLOW 集 ===
  FOLLOW(E)     = {$, )}
  FOLLOW(E')    = {$, )}
  FOLLOW(T)     = {$, ), +}
  FOLLOW(T')    = {$, ), +}
  FOLLOW(F)     = {$, ), *, +}

=== LL(1) 预测分析表 ===
  非终结符    (         id        +         *         )         $         
  E           T E'      T E'      -         -         -         -         
  E'          -         -         + T E'    -         eps       eps       
  T           F T'      F T'      -         -         -         -         
  T'          -         -         eps       * F T'    eps       eps       
  F           ( E )     id        -         -         -         -         

=== 3 + 4 * 5 的最左推导 ===
  E                     => T E'
  T E'                  => F T' E'
  F T' E'               => 3 T' E'
  3 T' E'               => 3 E'
  3 E'                  => 3 + T E'
  3 + T E'              => 3 + F T' E'
  3 + F T' E'           => 3 + 4 T' E'
  3 + 4 T' E'           => 3 + 4 * F T' E'
  3 + 4 * F T' E'       => 3 + 4 * 5 T' E'
  3 + 4 * 5 T' E'       => 3 + 4 * 5 E'
  3 + 4 * 5 E'          => 3 + 4 * 5
  -> 共 11 步推导

=== 递归下降求值 ===
  3+4*5       = 23
  (3+4)*5     = 35
  2*3+4*5     = 26
  对照 Python 的结果：3+4*5       = 23，(3+4)*5   = 35

=== 左递归 E -> E + T 的递归下降会无限递归 ===
  E() 一进来就调 E()，第一个 token 还没消费 -> 栈溢出
  消除办法：E -> T E'，把左递归改写成右递归（循环/尾递归）

三条结论：

  1. 预测分析表里每一格最多只有一条产生式，这就是 LL(1) 的判据。若有哪一格出现两条，就得改文法。
  2. E' 那一行的 eps 落在 ) 和 $ 两列，因为 FOLLOW(E') = {), $}——ε 产生式填在 FOLLOW 集上，这一条最容易记反。
  3. 11 步最左推导对应那棵 9 个结点以上的语法树；每一步替换的都是当前串里最左边的非终结符。C 与 Python 两段程序算出同一组值（23 / 35 / 26），互相印证。

考点 ​

考点

1. 必背定义

  • 文法是四元组，产生式左边只能是一个非终结符——这就是"上下文无关"。
  • 最左推导每一步替换最左非终结符；最右推导又叫规范推导。
  • 句柄：一次归约对应的、最靠右的直接短语。LR 分析就是"找句柄、归约句柄"。
  • 二义性：同一句子存在两棵不同的语法树。注意——"有多种推导"不等于二义，只有"多种语法树"才是。

2. 两个集合

集合定义用在哪
FIRST(α)α 能推出的第一个终结符决定该不该选这条产生式
FOLLOW(A)紧跟 A 之后的终结符ε 产生式填表的列

FOLLOW 三条规则：① 开始符号的 FOLLOW 含 $；② 若 A → αBβ，则 FIRST(β) 去掉 ε 加入 FOLLOW(B)；③ 若 A → αB 或 A → αBβ 且 β 能推 ε，则 FOLLOW(A) 加入 FOLLOW(B)。

3. 高频陷阱

  • 左递归必须先消除，且要同时消直接左递归和间接左递归。E → E + T 是直接左递归；A → Bx、B → Ay 是间接左递归。
  • 左递归消除改变语法树形状但不改变语言：E → E+T 与 E → TE' 生成的是同一个语言。
  • LR 分析里"移进优先"是默认的冲突裁决，但算符优先级高的场景要优先归约——不要背"一律移进"。
  • 归约-归约冲突不能靠 lookahead 救，那说明文法有真正的二义，得改文法。
  • missing ';' 的报错位置常常偏一行：语法分析器要看见下一个记号才能判断上一条语句没结束。
  • a = b + 1; 里 b 未声明，语法分析不报错——结构合法，报错的是语义分析。

4. 一句话分界

错误归属阶段例子
词法错词法分析出现 @、字符串没闭合
语法错语法分析少分号、括号不配对
语义错语义分析类型不符、变量未声明、重复定义

小结 ​

  • 语法分析把扁平的记号流变成有层次的语法树，判据是上下文无关文法。
  • 自顶向下（LL）好写、好报错，但要先消除左递归；自底向上（LR）能力更强，是工具生成的主流。
  • 表驱动的两套方法都归结为两个集合（FIRST / FOLLOW）和一张表。
  • 这一层只判结构，不判意义——"结构对不对"和"意思对不对"必须分开报。

回到主线：上一章（词法分析）把字符流变成了记号流，本篇把记号流变成了树。树一成形，"结构的合法性"就检查完了；接下来要在这棵树上做两件新事——查类型与生成中间代码，这就是下一章。

下一篇：语义分析与中间代码

我的笔记

当前浏览器不允许本地存储，笔记无法保存。

评论（0）

当前浏览器不允许本地存储，评论无法保存。

还没有评论，来说两句。

内容以 CC BY-NC-SA 4.0 共享

Si2C · 由硅到 C