第四章_语法分析(4)

I3
R I6 S L= R S L=R RL I9 id L *R L I3 S L =R = L id I2 R L L * * L * R I5 R L L R L I7 L id R id L * R L *R I8 S' S *
编译原理 20
LR(1)项目[A· a]对可行前缀有效，如果 , 存在着推导 S *rm Aw rm w，其中： 1. = ，且 2. a是w的第一个符号，或者w为且a是$。
编译原理
21
例4.37
考虑文法： S BB B aB | b
rm rm rm
这个文法生成的语言是什么？ a*ba*b
编译原理
14
一个可行前缀可能有多个有效项目。 可能存在动作冲突 一个可行前缀的有效项目集就是从这个DFA的初态出 发，沿着标记为的路径到达的那个项目集（状态） 。
编译原理
15
例4.35
串E + T *是可行前缀，读完它后，DFA处于状态I7 I7: TT *· F · E ), F · F, ( id
据假设，存在一个规范推导S *Aw 1B2w 设2w * xw， 则对任何B 有规范推导 S *Aw 1 B 2w 1 Bxw 1 xw 所以 B . 对可行前缀 1 也是有效的。
编译原理 13
一个项目可能对好几个可行前缀都是有效的。 E ·E+T对 和(这两个可行前缀都有效 E E E+T (，1都为空) E E (E) (E+T) ( =“(”，1为空) DFA读入 和(后到达不同的状态，那么项目E ·E+T就出现在不同的项目集中
编译原理 5
S
I1
I4 S R
SLR(1)文法的描述能力有限
I0 S' S S L=R SR L *R L id RL
L
S L =R I2 R L
第一个项目使得 action[2, = ] 为shift 第二个项目使得 action[2, = ]为reduce，因 为 = Follow(R)。 S L=R *R=R 但是，不存在以R=…开始 的右句型，只有* R = …开始的右句型。
编译原理
23
算法4.38 LR(1)项目集的构造
输入：拓广文法G。 输出： LR(1)项目集规范族，是对G 的一个或多个 可行前缀有效的项目集。 方法：如图4-40所示。
编译原理
24
Fig4.40 Sets of LR(1) items construction for G
function closure(I) begin repeat for each [A B, a] in I each production B of G and each terminal b in FIRST(a) such that [B. , b]is not in I do add [B , b] to I until no more items can be added to I return I end
SS.,$ I1 SC.C,$ C.cC,$ C.d,$ I2 c C
SCC.,$ I5 c
C d CcC.,$ I9
Cc.C,$ C.cC,$ C.d,$ I6 Cd.,$ I7
d c c
d
Cc.C, c/d C C.cC, c/d C.d, c/d I3 d Cd.,c/d 编译原理 I4
编译原理 25
function goto(I, X) begin let J be the set of items [A X, a] such that [A X, a] is in I return closure(J) end
编译原理
26
procedure items(G ) begin C := {closure({[S · $]})}; S, repeat for each set of items I in C and each grammar symbol X such that goto(I, X) is not empty and not in C do add goto(I, X) to C until no more sets of items can be added to C end
S BB BaB Bab aBab aaBab aaaBab
rm rm rm
从最右推导S *rm aaBab rm aaaBab看出： [Ba · a]对可行前缀 = aaa是有效的； B, 从最右推导S *rm BaB rm BaaB看出： [Ba · $]对可行前缀 = Baa是有效的。 B,
2
例4.34 每个SLR(1)文法都不是二义的，但是， 有许多非二义的文法不是SLR(1)。
例如，下面的产生式文法
S L=R SR L *R L id RL
编译原理
3
拓广文法G的LR(0)项目集规范族为：
I0: S' · S S · L=R S · R L · *R L · id R · L S'S · SL · =R RL ·
编译原理
8
识别G的所有可行前缀的NFA
1. 2. NFA的状态是一个LR(0)项目。 从每个形如B · 的状态出发画一条标记为X X 的弧到状态BX · ， 3. 从每个形如B · 的状态出发画一条标记为的 A 弧到所有形如A · 的状态。 这个NFA通过子集构造法得到的DFA和前面构造 的LR(0)自动机是相同的。
编译原理
6
4.6.5 可行前缀（viable prefix）
对于一个文法G，构造一个LR（0）自动机，它能 识别所有可能出现在分析栈中的文法符号串，栈中 的文法符号串一定是某个右句型的前缀。
S x
rm *
不是右句型的所有前缀都会出现在栈中。
E F * id ( E ) * id
编译原理
I3 :
I4:
SR ·
L* · R R · L L · *R L · id Lid ·
I6:
SL= · R R · L L · *R L · id
L*R ·
I7:
I1: I2:
I5:
I8 :
I9:
RL ·
SL=R ·
4
I0
S' S S L=R SR L *R L id RL id R L id
S.S start S.SS+ S.SS* S.a I0
S
SS . SS. S+ SS. S* S.SS+ S.SS* S.a I1
a
S
+ SSS +. I4 * SSS *. I5
a
Sa . I2
a
编译原理 12
有效项目
如果存在一个规范推导S *Aw 12w， 则 项A1 ·2 对可行前缀1 是有效的。 若项目A1 ·B2 对可行前缀1 是有效的，且 B 是产生式，则项目 B · 对可行前缀1 也是有效的。
第四章 语法分析(4)
4.7 LR(1)、LALR
1
4.6.4 构造SLR分析表
算法 4.32 构造SLR分析表 输入：一个拓广文法G 输出：G 的SLR分析表的函数action和goto 方法： 1. 构造G 的LR(0)项目集规范族C = {I0, I2, …, In}。 2. 对于状态Ii的分析动作如下： (a) 若A . aB Ii且 goto (Ii ,a)= Ij action[i, a] = “shift j” (b) 若A . Ii, 对于所有a FOLLOW(A) action[i, a] = “reduce A” , A S (c) 若SS. Ii, action[i, $]= “accept” 3. 若goto(Ii, A) = Ij, AVN , 则 goto[i,A] = j 4. 分析表其余位置为error 编译原理
例 I2有两个项目SL · =R和RL · 当下一个输入为‘=’时用RL · 归约，但是文 法没有以R=…开始的右句型，只有以*R=…开 始的右句型，可见，仅仅知道可行前缀L不应当 进行归约。 扩充项目的定义！
编译原理
19
LR(1)项目
重新定义项目，让它带上搜索符(向前看符号)， 成为如下形式 LR(1)项目: 由LR(0)项目和一个lookahead符号 组成 [ A., a ] 对于项目[ A· a ]，搜索符a表示只有当下一 , 个输入符号是a时，才能进行归约。 这样的a的集合一定是FOLLOW(A)的一个子 集，可能是真子集。
编译原理 22
构造有效的LR(1)项目集
考虑对可行前缀有效的项目[A · , a]，必 B 定存在最右推导S *rm Aax rm Bax，其中 = 。 假设ax能推出by，那么， [B · , b]对有效， b是从 能推出的第一个终结符，或当 可空时， b就是a。bFIRST(a)。
编译原理
9
例：p153 描述文法的可行前缀
S S S SS+| SS* | a
文法的项目有：
1. S · S 2. S S· 3. S · SS+ 4. S S· S+ 5. S SS · + 6. S SS+ ·
7. S · SS* 8. S S· S* 9. S SS· * 10. S SS*·
编译原理
17
图4.36 识别可行前缀的 DFA
I0
E
I1
+
I6
T
I2 I3 (
*
I7
T F ( id F (
I9 to I3 to I4 to I5 I10
*
to I7
F
(
id E T F ) + to I2 to I3
编译原理
to I4 to I5 I11
to I6
I4
I8
id id I5
18
4.7 构造规范的LR分析表
编译原理 27
例4.39
构造文法 S S SCC CcC|d 的LR(1)和SLR分析表。
计算[S.S,$]的闭包 I0：S.S, $ S.CC, $ C.cC, c/d C.d, c/d c/d FIRST(C$)
编译原理
28
S.S,$ S S.CC,$ C.cC,c/d C.d,c/d I0 C
rm rm *
编译原理
7
可以出现在移进归约分析器栈中的右句型的前缀称 为可行前缀。 定义：一个可行前缀是一个右句型的前缀，并且不 含右句柄之后的任何符号。 可行前缀后加上终结符可以得到右句型。 只有输入串中已分析过的那部分能归约成可行前缀， 就没有语法错误。 事实上，LR（0）自动机是一个识别可行前缀的DFA。
11 S · a 12. S a·
编译原理
10
识别可行前缀的NFA

start
3
S
S
4

S
5
+
6
1
2
7 11

S


8
S
9
*
10
a
12编译原理
11
识别可行前缀的DFA
S SSS . + SSS . * SS. S+ SS. S* S.SS+ S.SS* S.a I3
E
E E E+T E+T * F E+T * id E+T * F * id
E E E+T E+T * F E+T * (E )
E E+T E+T * F E+T* id
编译原理
16
有效项目集和项目集规范族
文法G的某个可行前缀的所有有效项目组成的集合， 称为可行前缀的LR(0)有效项目Fra Baidu bibliotek。 文法G的所有有效项目集组成的集合，称为G的LR(0) 项目集规范族。
CcC.,c/d I8
29
算法4.40 规范LR(1)语法分析表的构造
输入：拓广文法G。 输出：文法G的规范LR语法分析表函数action和goto。 方法： 1. 构造G 的LR(1)项目集规范族C={I0, I1, …, In}。 2. 从Ii构造分析器的状态i，状态i的action函数确定如下： 若[A · , b]在Ii中，且goto(Ii, a) = Ij，则置action[i, a a]为“shift j”； 若[A · a]在Ii中，且A S，则置action[i, a]为 , “reduce j”，j是产生式A 的序号； 若[SS·$]在Ii中，则置action[i, $]为“accept”。 ,