3. Select集(可选集)
定义:文法G[S],有规则Aβ ,则该规则的可选集为: First(β ), 当β ≠ε Select(Aβ )= Follow(A), 当β =ε 例: 对于G[E] select(EE+T)=First(E+T)={(,i} select(ET)=First(T)={(,i} select(TT*F)=First(T*F)={(,i} select(TF)=First(F)={(,i} select(F(E))=First((E))={(} select(Fi)=First(i)={i}
2
LL(1)分析表
x1
(1) LL(1)分析过程 x2 当前句型的右端部分x1x2…xm# (xi∈V) 待分析串的右端部分y1y2…yn# (yi∈VT) … 分几种情况: xm 1)当x1∈VN，由y1选择相应规则替换x1 2)当x1∈VT,若x1=y1≠#,则说明x1与y1匹配,分 别删去x1,y1, 继续分析. 若x1 ≠ y1,则说明不匹配，进行出错处理 3)若x1=y1=#,说明全部匹配,分析成功. LL(1)分析程序见P77--78
5.4.2
a1 a2
LL(1)分析方法的逻辑结构
a3 … ai … am #
输入串
x1
分析表 控制程序 分析器
x2 …. xn
分析栈
#
输入串a1a2a3…am#,以定界符”#”作为结尾
分析表:M[A,a] (A为栈中元素,a为输入字符)
5.4.3
1. LL(1)文法
LL(1)分析方法
对于文法G[S],其每个非终结符的不同规则具 有不相交的select集. 即对于Ux1|x2|…|xn,有 select(Uxi)∩select(Uxj)=Φ, (i≠j)
例:文法G[S]:SAB Aab Bcd|cBd 判断abccdd是否是句子。 (1)自顶向下构造语法树 S A B a b c B d c d
(2)推导 S AB AcBd Accdd abccdd
5.2
不确定的自顶向下分析思想
例: G[S]: SxAy Aab|a S x A y x (1)
First(dB)={d}
First(Bq)={b,d}
例: G[E]:
EE+T|T TT*F|F F(E)|I First(F)={(,i} First((E))={(} First(i)={i}
则: First(E+T)={(,i} First(T)={(,i} First(T*F)={(,i}
注：有些不是LL(1)文法的文法，经过修改 （如左提左因子，消除递归等）可化为 LL(1)文法，但并不是所有的非LL(1)文法 都能改造为LL(1)文法。
例 对于文法G [Z]:
ZAU |BR AaAU|b BaBR|b Uc Rd
First(AU) ∩First(BR)={a,b} ≠Φ 所以，不是一个LL(1)文法
第5章 语法分析 ----自顶向下分析方法
学习目标
自上而下语法分析的基本思想 自上而下语法分析面临的问题及解决方 消除左递归的方法 FIRST（x）的求法、FOLLOW（U）的求法 递归子程序的构造方法 LL（1）文法 LL（1）分析表的构造方法
语法分析是编译过程的核心部分。 -----在词法分析识别出单词符号串的基础上， 分析并判定程序的语法结构是否符合语法规则。
例: G[S]: SaBc|bB BbB|d|ε Select(Bε)=Follow(B)={#,c}
5.2.2
自顶向下分析过程中存在的问题 及解决办法
1. 左递归问题 例:G[S]: SSa|b S
b S
分析baa
S
a S
S
a
S
S a
S
S a
S
S a
b
S a
S a
b
S
a…Biblioteka 分析时可能出现:例 5－6 ① 消除左递归 ② 求select 集 ③ 构造分析表 ④ 分析符号串 例 文法G [S] S abB A SC|BAA|ε B AbA C B|c
VN={S,A,B,C} VT={a,b,c}
判断此文法是不是LL(1)文法: Select (SabB)={a} Select (ASC)={a} ∩≠Φ Select (ABAA)={a,b} Select (Aε)={a,b,#} Select (CB)={a,b} ∩=Φ Select (Cc)={c} Selcet (BAbA)={a,b} ∴不是LL(1)文法。构造出的分析表含有多重定义。
AaBc
a
BbB b BbB b Bd
d c
(2)
LL(1)分析表构造
LL(1)分析表反映分析栈中元素与输入串中元 素的匹配关系.记M[A,a]
几个约定: C:继续读入下一字符 R:重读当前字符
RE(β):用β 的逆串替换栈顶符号.
构造LL(1)分析表的算法如下:
(1)对于ADβ (D∈VN)且 select(ADβ )={b1,b2…bn} 则M[A,bi]=RE(Dβ )/R 表示:用Dβ 的逆替换A,重读当前字符. (2)对于Aaβ (a∈VT) 则M[A,a]= RE(β )/C 表示:用β 的逆替换A,继续读入下一字符. (3)对于Aε 且select(Aε )={b1,b2…bn} 则M[A,bi]=RE(ε )/R=ε /R
构造LL(1)分析表:
a A b B/C ε/C succ c d ε/C e B/C #
cB/C
B
c #
分析abbedc的过程 分析栈 余留输入串 动作
#A
#cB #cB #cB #cB #c #
abbedc#
bbedc# bedc# edc# dc# c# #
cB/C
B/C B/C B/C ε/C ε/C succ
自顶向下
语法分析
如 LL(k), 递归下降分法等 如LR(K), 算符优先分析法等
自底向上
目

录
5.1 自顶向下分析技术 5.2 不确定的自顶向下分析技术 5.3 确定的自顶向下分析技术 5.4 LL(K)分析方法 5.5 递归下降分析方法
5.1
分析思想:
自顶向下分析技术
从文法的开始符号出发,向下推导, 看能否推出 待分析的符号串,如果能推出,说明该符号串是符合 语言语法的句子,否则不是句子。
(1) 回溯
(2) 死循环, 在没有对当前输入符号匹配就进入处 理S的过程，无法确定什么时候才用Sb替换, 造成死循环. 解决方法:
文法的实用限制(算法6)
消除左递归
扩充的BNF表示法
2.
回溯问题 在分析中，假定被代换的最左非终结符A存在n 条规则,Ax1|x2|…|xn，难以确定采用哪个规则，若 从x1到xn逐个来试,则效率太低。
(2) 首符号相同
First(xi)∩First(xj)≠Φ
即对于 Aα x1|α x2 ...|α xn 改为 Aα (x1|x2 ...|xn) 进一步Aα B Bx1|x2 ...|xn
(i≠j)
解决方法:”左提左因子”修改文法
例: Uα x1|α x2 |x3|…|xn
且First(xi)∩First(xj)=Φ , (i,j≥3,i≠j)
(1)首符号不同
First(xi)∩First(xj)=Φ (i≠j) 若a∈First(xk),则选用Axk来推导 例: G[S]: AaB|bA BbaA|c {First(aB)={a}} ∩ {First(bA)={b}} = Φ {First(baA)={b}} ∩ {First(c)={c}} = Φ 分析符号串bbabaac A bA bbA bbaB bbabaA bbabaB bbabaac
First(xi) ≠α , (i=3,4,…n) 采用 U α V|x3|…|xn Vx1|x2
例: G[S]: Sif B then S1 else S2|if B then S1 改为: Sif B then S1 T T else S2 | ε
5.3
确定的自顶向下分析思想
文法是非左递归的
2.
Follow集(向前看集)
定义:文法G[S],非终结符号U的向前看集 Follow(U)={a|S * …Ua…,a∈VTU{#}} 特别,当a=ε时,视U后面的符号为”#” ∵E * E, E * E+T, E * (E) ∴Follow(E)={#,+,)} Follow(T)={#,+,*,)} Follow(F)={#,+,*,)}
推导过程是一个不断试探的过程,出现回溯现象， 所以又称带回溯的自顶向下分析方法(效率低，代价高) 原因:推导过程中有多个侯选式可供选择.
5.2.1
三种终结符集
1.First集 (首符号集) 定义: 文法G[S]:字汇表V,则符号串β 的首符号集 First(β )={a|β * ay,a∈VT,y∈V*} 特别,若β =ε ,则First(β )=Φ 例：G[S]： SAp SBq Aa|cA Bb|dB First(Ap)={a,c}
例:G[A]: AaBc BbB|eB|d 分析abbdc# 设计文法的分析表: a AaBc b c d e
A
B
BbB
Bd
BeB
分析过程:
分析栈 输入符号
产生式
匹配删除
#A #cBa #cB #cBb #cB #cBb #cB #cd #c #
abbdc# abbdc# bbdc# bbdc# bdc# bdc# dc# dc# c# #
分析xay是否句子 S S x A y A y a a b (3) (2)