第4章 语法分析
S c A S c a
2015-5-27
c
a
b
d
d
A
c d a S A c
信息学院 孙丽云
b
d
A b
a
b
d
3
回溯分析法
4章 语法分析 4.2第 自上而下分析法
例：已知符号串S=cad 文法G[Z]: Z→cAd A→ab|a 求解 SL(G[Z]) 1.开始:令Z为根结点
分析过程 是设法建立一棵语法树, 使语法树的末端结点与 给定符号串相匹配. Z Z ·
2015-5-27 信息学院 孙丽云
注意：有ε产生式 时求First集，别漏 元素！！
注意：除了求非终结 符的First集外，还可 求符号串的First集。 例：求First(BaB)
17
第4章 语法分析
■ Follow集合 定义：FOLLOW(A)={a| S=> * …Aa…，a∈T}A∈N, S开始符号 特殊地：若S => *...A ，则 $∈FOLLOW(A)
1.若X,则FIRST(X)={X} 2.若XN,且有产生式Xa…，则把a加入到FIRST(X)中 ;若X也是一条产生式,则把也加到FIRST(X)中. 3.若XY…是一个产生式且YN,则把FIRST(Y)中的所 有非元素都加到FIRST(X)中;若X Y1Y2…YK 是一个 产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何j,1≤j ≤i-1, FIRST(Yj)都含有 (即Y1..Y(i-1) =>* ),则把 FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是, 若所有的FIRST(Yj , j=1,2,…,K)均含有,则把加到 FRIST(X)中.
第4章 语法分析
■ 求Follow集合举例说明
求下列各种情况下的Follow(A) (1)A为开始符号时 (2) BAa (3) BaA （Follow(B)={x,y}） (4) CaAB（Follow(C)={x,y},First(B)={b}） (5) CaAB（Follow(C)={x,y},First(B)={b, }）
算法：
1.对于文法的开始符号S,置$于FOLLOW(S) 中; 2.若Ａ α B β是一个产生式,则把FIRST(β)－{}加至 FOLLOW(B)中; 3.若Ａ αB是一个产生式,或Ａ αBβ是一个产生式而 FIRST(β) ，则把FOLLOW（A）加至FOLLOW（B） 中。
2015-5-27 信息学院 孙丽云 18
例：将文法G： E→ Ea | t 消除左递归。
解： E → t E’ E’ → aE’ | ε
2015-5-27 信息学院 孙丽云 6
第4章 语法分析
(1) 左递归改成右递归——普通的直接左递归的消除 A → Aα1| Aα2| … | Aαn|β1|β2|…|βm A →β1 A’ | β2 A’ | … | βm A’ A’ → α1 A’ | α2 A’ | … | αn A’ | ε ● Example 将文法G： exp → exp + term | exp - term | term 消除 左递归。 解： exp → term exp’
2015-5-27
信息学院 孙丽云
19
● 举例1
第4章 语法分析
1)求文法G的 FOLLOW集合(the simple expression grammar) (1) expr → expr addop term (2) expr → term (3) addop → + (4) addop → (5) term → term mulop factor (6) term → factor (7) mulop →* (8) factor →(expr) (9) factor →number 解：First(expr)={(,number} First(term)={(,number} First(factor)={(,number} First(addop)={+,-} First(mulop)={*}
定义：FIRST(α) = {a | α => * aβ， a T , α,β (TN)* } 若α => * ε，则规定ε FIRST(α) 该集合称为α的头符号集合
2015-5-27
信息学院 孙丽云
10
■ First集合算法 P67
第4章 语法分析
令X为一个文法符号或，则集合First(X)由终结符组成， 此外还可能有，定义如下：
2015-5-27 信息学院 孙丽云 15
■ 练习
第4章 语法分析
3)求文法G的 FIRST集合(Grammar for statement sequences) stmt-sequence →stmt stmt-seq’ stmt-seq’ → ; stmt-sequence|ε stmt→s (1) stmt-sequence →stmt stmt-seq’ 解： (2) stmt-seq’ →; stmt-sequence (3) stmt-seq’ →ε (4) stmt→s First(stmt-sequence)={s} First(stmt-seq’)={;, ε} First(stmt)={s}
■ LL(1)文法
LL(1)中的第一个L表示从左到右扫描输入串，第二个 L表明分析过程中使用最左推导，1表示分析时每一步 只需向前看一个符号即可决定所选用的规则，而且这 种选择是准确无误的。P63
2015-5-27 信息学院 孙丽云 9
第4章 语法分析
First集合和Follow集合
■ First集合
2.用Z的右部,符号串去匹配输入串
完成一步推导ZcAd 检查 c-c匹配 A是非终结符,将匹配任务交给A
2015-5-27 信息学院 孙丽云
c A d
4
S=cad 第4章 语法分析 3. 选用A的右部符号串匹配输入串 A有两个右部,选第一个 完成进一步推导Aab 检查,a-a匹配,b-d不匹配(失败) 但是还不能冒然宣布SL(G[Z]) 4. 回溯 即砍掉A的子树 改选A的第二右部 Aa 检查 a-a匹配 d-d匹配
2015-5-27 信息学院 孙丽云 11
■ 求First集合举例说明
求下列各种情况下的First(A) (1)A∈T (2)A∈N 例：①AaB|ε ②ABa Bbd|c ③ABa Bbd|c|ε ④ABCa Bbd|c|ε Cxy| ε ⑤ABCD Bbd|c|ε Cxy| ε Dm| ε
exp’ → + term exp’ | - term exp’ |ε
练习：对文法G: E → T*f | T/f | f T → f | T*f | T/f 消除左递归
2015-5-27 信息学院 孙丽云 7
第4章 语法分析
（2）采用扩充BNF表示法改写含直接左递归的规则
使用花括号{a}表示符号串a的出现可0次或多次，即表示a*。
■ 练习
第4章 语法分析
1)求文法G的 FIRST集合(Simple integer expression grammar) expr → expr addop term∣term addop → +|term → term mulop factor ∣ factor mulop →* factor →(expr) ∣ number
信息学院 孙丽云
同例1，仅符号不一 样而已
First(expr)={(,number} First(term)={(,number} First(factor)={(,number} First(addop)={+,-} First(mulop)={*}
14
2015-5-27
■ 练习
第4章 语法分析
2)求文法G的 FIRST集合(Left factored grammar of if-statement) statement → if-stmt | other if-stmt → if (exp) statement else-part else-part → else statement | ε exp → 0 | 1 解： (1) statement → if-stmt (2) statement → other (3) if-stmt → if (exp) statement else-part (4) else-part → else statement (5) else-part →ε First(statement)={if,other} (6) exp → 0 First(if-stmt)={if} (7) exp → 1 First(else-part)={else,ε} First(exp)={0,1}
G[Z]: Z→cAd A→ab|a
Z ·
c A d a b
分析工作要部 分地或全部地 退回去重做叫 回溯
Z · c A d
a
建立语法树,末端结点为cad与输入cad相匹配, 建立了推导序列 EcAdcad ∴cadL(G(E))
2015-5-27
回溯分析法分析效率低，代价高，实际不常用。
信息学院 孙丽云 5
语法分析程序的输入是单词符号序列；输出是语 法树。
2015-5-27 信息学院 孙丽云 1
第4章 语法分析
语法分析方法
自顶向下分析方法 从根结点出发构造 语法树 回溯分析方法（不确定的分析法） 递归下降法 预测分析方法 (确定的分析法) LR(0) parsing SLR(1) parsing LR(1) parsing LALR(1) parsing LL(1)分析法
L:由左向右的处理输入 L:为输入串构造最左推导
自底向上分析方法 从叶结点出发构造 语法树
L:由左向右的处理输入 R:为输入串构造最右推导