Lec3: Parsing

Why CFG?#

• 并不是所有 token 串都构成合法程序。
• 我们需要：
  • 形式化地描述合法 token 串
  • 能区分 valid / invalid strings

Regular language 不够强#

• 正则语言是常用形式语言中较弱的一类。
• 但编程语言里存在大量 recursive structure，例如：

1
(), (()), ((()))
2
((1+2)+3)

• 这类结构不是 regular language，更自然的工具是 CFG。

CFG 定义#

一个 CFG 由以下部分组成：

产生式一般写作：

其中：

• $X \in N, \quad Y_i \in N \cup T \cup \{\varepsilon\}$

例子：匹配括号的 CFG#

1
S -> (S)
2
S -> ε

它描述的语言是：

1
{ ε, (), (() ), ((())), ... }

定义#

从开始符号 S 出发：

1. 初始串只包含开始符号 S
2. 每次把某个非终结符替换为某条产生式右侧
3. 重复直到串中只剩终结符

例如：

1
S -> (S) -> ((S)) -> (())

语言定义#

若文法 G 的开始符号是 S，则：

其中 $\Rightarrow^{*}$ 表示经过零步或多步推导。

Parse Tree 的作用#

• 不只是判断 $S \in L(G)$
• 更重要的是体现 phrase structure（短语结构）
• 也体现运算符的 association of operations

Left-most / Right-most Derivation#

• Left-most derivation：每一步都替换最左侧非终结符
• Right-most derivation：每一步都替换最右侧非终结符
• 对于 unambiguous CFG，它们虽然推导顺序不同，但会得到同一棵 parse tree。

定义#

如果一个文法能够对某个字符串生成 两棵不同的 parse tree，则它是 ambiguous grammar。

等价地说：

• 对某个字符串存在多个 left-most derivation
• 或存在多个 right-most derivation

经典例子#

1
E -> E * E
2
E -> E / E
3
E -> E + E
4
E -> E - E
5
E -> id
6
E -> num
7
E -> (E)

字符串：

1
id * id + id

可以解释为：

• (id * id) + id
• id * (id + id)

所以文法是歧义的。

为什么歧义有问题？#

• 编译器依赖 parse tree 来定义程序含义
• 例如：

1
2 * 3 + 4

不同 parse tree 会给出不同结果：

• (2*3)+4 = 10
• 2*(3+4) = 14

所以 ambiguous grammar 会让程序含义不明确。

目标#

我们通常希望：

• * / / 的优先级高于 + / -
• 运算符满足左结合（left associativity）

经典改写#

把歧义文法改写为：

1
E -> E + T
2
E -> E - T
3
E -> T
4
T -> T * F
5
T -> T / F
6
T -> F
7
F -> id
8
F -> num
9
F -> (E)

其中：

• E = expression
• T = term
• F = factor

为什么它能消歧义？#

• Precedence：高优先级运算符在更深层（T,F）推导
• Left associativity：使用左递归（如 E -> E + T）

Parser 的类型#

三类常见 parser：

• Top-Down 和 Bottom-Up 都是从左到右扫描输入。
• 最高效的方法通常只适用于某些 grammar 子类。

Top-Down Parsing#

• 从 parse tree 的根开始，自顶向下构造
• 可以看作寻找输入串的 left-most derivation

例如，对于字符输入 begin print num = num end 来说，可以画出语法分析树：

思想#

• 每个 non-terminal 对应一个递归函数
• 每条产生式对应函数中的一个分支

例如文法：

1
S -> if E then S else S
2
S -> begin S L
3
S -> print E
4
L -> end
5
L -> ; S L
6
E -> num = num

可以写出：

1
void S(void) {
2
    switch(tok) {
3
        case IF:    eat(IF); E(); eat(THEN); S(); eat(ELSE); S(); break;
4
        case BEGIN: eat(BEGIN); S(); L(); break;
5
        case PRINT: eat(PRINT); E(); break;
6
        default: error();
7
    }
8
}

基础设施#

1
enum token {IF, THEN, ELSE, BEGIN, END, PRINT, SEMI, NUM, EQ};
2
extern enum token getToken(void);
3
enum token tok;
4

5
void advance() { tok = getToken(); }
6
void eat(enum token t) {
7
    if (tok == t) advance();
8
    else error();
9
}
10

11
void S(void) {
12
  switch(tok) {
13
    case IF: eat(IF); E(); eat(THEN); S(); eat(ELSE); S(); break;
14
    case BEGIN: eat(BEGIN); S(); L(); break;
15
    case PRINT: eat(PRINT); E(); break;
16
    default: error(); }}
17
void L(void) {
18
  switch(tok) {
19
    case END: eat(END); break;
20
    case SEMI: eat(SEMI); S(); L(); break;
21
    default: error(); }}
22
void E(void) { eat(NUM); eat(EQ); eat(NUM); }

优点#

• 简单
• 容易手写

缺点#

• 一般形式可能需要 backtracking
• 某些 grammar 会导致分支选择困难，开销高

定义#

• Predictive parsing 是 recursive descent 的一个特例
• 不需要 backtracking
• 通过查看前方 k 个 token 决定使用哪条产生式
• 能处理 LL(k) 文法

其中：

1
LL(k) = Left-to-right parse, Leftmost derivation, k-token lookahead

Nullable#

如果某个符号能推出 ε，则它是 nullable。

1
for each symbol X:
2
  Nullable(x) = False
3
repeat
4
  for each production X -> Y1 Y2 … Yk:
5
    if Nullable(Yi) = True for 1 <= i <= k:
6
      Nullable(X) = True
7
until Nullable did not change in this iteration

FIRST#

FIRST(γ) 表示：

从字符串 γ 推导出的串中，可能出现在最前面的终结符集合

若 $\gamma \Rightarrow^* t \beta$，则：

FOLLOW#

FOLLOW(X) 表示在某个句型中，紧接在 X 后面的终结符集合。也就是：

The algorithm to calculate First, Follow and Nullable Sets#

LL(1) Grammar#

若按上述方法构造出的 parsing table 没有重复表项，则文法是 LL(1)。

若某一格中出现多条产生式：

• predictive parsing 无法工作
• 文法不是 LL(1)

Non-Recursive Predictive Parser#

除了递归版本，也可以使用显式栈实现非递归预测分析：

• 栈顶为终结符：尝试 match
• 栈顶为非终结符：查表展开产生式
• 栈和输入都到 $ 时 accept

为什么要消左递归？#

例如：

1
E -> E + T
2
E -> T

会导致：

• FIRST(E+T) = FIRST(E)
• 与 E -> T 冲突
• predictive parsing table 中出现重复表项

因此：

Top-down parsing 不能处理 left-recursive grammar

经典消除方法#

把：

1
A -> Aα
2
A -> β

改写为：

1
A  -> β A'
2
A' -> α A'
3
A' -> ε

例如：

1
E -> E + T | T

改写为：

1
E  -> T E'
2
E' -> + T E'
3
E' -> ε

表达式文法改写后#

1
S -> E $
2
E -> T E'
3
E' -> + T E'
4
E' -> - T E'
5
E' -> ε
6
T -> F T'
7
T' -> * F T'
8
T' -> / F T'
9
T' -> ε
10
F -> id
11
F -> num
12
F -> (E)

为什么需要？#

若同一 non-terminal 的两条产生式有公共前缀：

1
S -> if E then S else S
2
S -> if E then S

在 LL(1) 中，当看到 if 时无法马上决定选哪条。

解决：提取公共前缀#

1
S -> if E then S X
2
X -> else S
3
X -> ε

一般形式#

1
A -> αβ
2
A -> αγ
3
A -> α

改写为：

1
A  -> α A'
2
A' -> β | γ | ε

本质：

• 延迟决策
• 直到读到更多输入后再选分支

两种策略#

• 直接报错并退出
• 报错后尽量恢复，继续分析

常见恢复思路#

1
skip until a token in FOLLOW(X)

1
int Tprime_follow[] = {PLUS, RPAREN, EOF};

基本思想#

• 自底向上构造 parse tree
• 从 leaves 一直归约到 root

Shift-Reduce Parsing#

Bottom-Up parsing 的一般风格是 shift-reduce parsing。

• shift：读入下一个 token，压栈
• reduce：若栈顶匹配某个产生式右部，则用其左部替换

Reduce vs Derive#

• Derive：把 LHS 展开成 RHS
• Reduce：把 RHS 归约回 LHS

Bottom-up parsing 本质上是在 逆转 right-most derivation。

LR(k)#

• L = left-to-right scan
• R = construct the reverse of a rightmost derivation
• k = lookahead token 数

优点#

• 比 LL(k) 更强
• 可以把决策推迟到看到完整 RHS 之后再做

Parser 维护的信息#

• 当前输入位置
• 一个状态栈（或状态+符号栈）

四类动作#

LR(0) Item#

1
A -> α . β

表示：

• α 已经处理过
• 接下来期望看到 β

Closure(I)#

若在集合 I 中有：

1
A -> α . X β

且 X 是非终结符，则对每条产生式：

1
X -> γ

加入：

1
X -> . γ

重复直到不再变化。

Goto(I, X)#

若 I 中有：

1
A -> α . X β

则把点右移：

1
A -> α X . β

收集后再做 closure。

LR(0) DFA#

• 状态 = item 集合
• 边 = Goto
• 然后由 DFA 构造 action/goto 表

LR(0) 表项填写#

• 若有终结符边：填 shift
• 若有非终结符边：填 goto
• 若状态中含有 A -> α .：对所有终结符填 reduce
• 若状态中含有 S' -> S . $：在 $ 列填 accept

LR(0) 的问题#

• 有时会出现 shift/reduce conflict 或 reduce/reduce conflict
• 说明文法不是 LR(0)

思想#

LR(0) 的 reduce 太激进：

• 只要看到 A -> α .，就对所有终结符都 reduce

SLR 改进为：

只在 FOLLOW(A) 中的 token 上放置 reduce 动作

规则#

若状态 I 中含有：

1
A -> α .

则仅对：

1
t ∈ FOLLOW(A)

填写：

1
reduce A -> α

优点#

• 比 LR(0) 更精确
• 能解决一部分 LR(0) 冲突

仍然可能出问题#

• SLR 仍可能保留一些冲突
• 因为 FOLLOW 集是全局信息，不够精细

核心思想#

在 item 中加入 lookahead。

LR(1) Item#

1
(A -> α . β, x)

含义：

• 当前处于 A -> αβ 的某个分析状态
• 完成这个产生式后，合法的后继 lookahead 是 x

Closure（LR(1)）#

若有：

1
(A -> α . X β, z)

则对每个产生式：

1
X -> γ

以及每个：

1
w ∈ FIRST(β z)

加入：

1
(X -> . γ, w)

Reduce（LR(1)）#

若状态中有：

1
(A -> α ., z)

则只在 lookahead z 上 reduce。

优势#

• 比 SLR 更准确
• 能解决更多冲突

代价#

• 状态数通常更多
• 表可能非常大

动机#

LR(1) 表太大。

做法#

把 LR(1) 项目核相同、只有 lookahead 不同 的状态合并。

特点#

• 表比 LR(1) 小很多
• 比 SLR 强
• 现代 parser generator 常用
• Yacc 基于 LALR 思想构造 parser

关系#

1
LR(0) ⊂ SLR ⊂ LALR(1) ⊂ LR(1)

通常：

• 所有 SLR grammar 都是 LALR(1)
• 但反过来不成立

两种解决办法#

Why?#

• 手写 parser 复杂
• LL/LR 文法都可以自动构造 parsing table

因此可以使用 parser generator。

基本概念#

• Yacc = Yet Another Compiler-Compiler
• 输入：.y 规格文件
• 输出：C 语言 parser 代码（常见为 tab.c）

基本结构#

1
definitions
2
%%
3
rules
4
%%
5
auxiliary routines

Example#

可用 Yacc 写表达式计算器：

1
%token NUMBER
2
%%
3
command: exp { printf("%d\n", $1); };
4
exp: exp '+' term { $$ = $1 + $3; }
5
   | exp '-' term { $$ = $1 - $3; }
6
   | term { $$ = $1; }
7
;
8
term: term '*' factor { $$ = $1 * $3; }
9
    | factor { $$ = $1; }
10
;
11
factor: NUMBER { $$ = $1; }
12
      | '(' exp ')' { $$ = $2; }
13
;

yyparse()#

• Yacc 生成的 parser 主函数
• 成功返回 0，失败返回 1

yylex()#

• 由 lexer 提供
• 返回 token 类型
• 返回 0 表示输入结束

yyerror()#

• 用来输出错误信息

yylval#

• 存储 token 的语义值
• 例如数字 token 对应的整数值

$$, $1, $2, …#

• $i：产生式右部第 i 个符号的值
• $$：产生式左部的值

例如：

1
exp: exp '+' term { $$ = $1 + $3; }

表示：

• $$ = 当前 exp 的值
• $1 = 左边 exp 的值
• $3 = term 的值

声明方式#

1
%nonassoc EQ NEQ
2
%left PLUS MINUS
3
%left TIMES DIV
4
%right EXP

表示：

• PLUS / MINUS：同优先级，左结合
• TIMES / DIV：更高优先级，左结合
• EXP：右结合
• EQ / NEQ：不结合

冲突解决规则#

• shift 的优先级来自当前 token
• reduce 的优先级来自该规则 RHS 最后一个 token

若发生冲突：

1. 规则优先级高 → reduce
2. token 优先级高 → shift
3. 优先级相同：
   • %left → reduce
   • %right → shift
   • %nonassoc → error

%prec#

可给规则强行指定优先级，例如一元负号：

1
%left PLUS MINUS
2
%left TIMES
3
%left UMINUS
4

5
exp: MINUS exp %prec UMINUS

目标#

开发者通常希望编译器报告 尽可能多的错误，而不是遇到第一个错误就停止。

两类技术#

Yacc 的局部恢复#

Yacc 提供特殊终结符：

1
error

例如：

1
exp  -> ( error )
2
exps -> error ; exp

作用：

• 当 parser 遇到错误时，回退栈
• 直到找到可以 shift error 的状态
• 跳过输入，直到同步 token（如 ) 或 ;）
• 然后继续分析

这些同步 token 叫做：

1
synchronizing tokens

Global Error Repair#

• 试图通过插入 / 删除 / 替换 token 使输入变为合法
• 更强，但也更复杂、代价更高
• 例如 Burke-Fisher error repair

1. CFG#

• CFG 比 regular language 更适合表达递归结构
• parser 的核心任务是构造 parse tree

2. Top-Down Parsing#

• 对应 left-most derivation
• recursive descent 简单但可能 backtracking
• predictive parsing 要求 LL(k)

3. FIRST / FOLLOW / Nullable#

• 是构造 predictive parser 的基础
• 用于判断在某个 lookahead 下该选哪条产生式

4. Bottom-Up / LR#

• 对应 right-most derivation 的逆过程
• shift-reduce 是核心思想
• LR(0) < SLR < LR(1)
• LALR(1) 是工业界常用方案

5. Yacc#

• 自动生成 parser
• 支持语义动作、类型值、优先级声明、错误恢复
• 常与 Lex/Flex 配合使用