编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法

Presentation on theme: "编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法"— Presentation transcript:

1 编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法 第六章 自底向上优先分析方法 第七章 LR分析方法 第八章 语法制导翻译和中间代码生成 第九章 符号表 第一○章 代码优化 第一一章 代码生成

2 第六章我们学过自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法与第6章介绍的运算符优先函数一样，LR方法也是通过求句柄逐步归约进行语法分析。在运算符优先函数中，句柄是通过运算符的优先关系而求得，LR方法中句柄是通过求可归前缀而求得。

3 LR分析概述 LR（k）分析是根据当前分析栈中的符号串和向右顺序查看输入串的k(k≥0)个符号就可以唯一确定分析的动作是移进还是归约以及用哪个产生式归约。 从左到右扫描(L)自底向上进行规约(R) (是规范规约）

4 LR分析的优缺点 1)适合文法类足够大,适用于大多数上下文无关文法 2)分析效率高 3)报错及时 4)手工实现工作量大 5)可以自动生成
美国Bell实验室推出的编译程序自动构造工具——YACC：能接受一个用BNF描述的满足LALR（1）上下文无关文法并对其自动构造出LALR（1）分析器。

5 第七章 LR分析法 一、LR分析概述（基本构造原理与方法） 二、LR(0)分析 三、SLR(1)分析 四、LR(1)分析
五、LALR (1)分析

6 ＬＲ分析器模型 总控程序 output Input# S1 Xm … X1 S0 # 栈 ACTION GOTO LR分析表 产生式表 状态
文法符号 ACTION GOTO LR分析表 产生式表

7 2、LR分析方法的逻辑结构 逻辑上说，一个LR分析器由3个部分组成：
(2) 分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。 (3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号所决定。

8 总控程序根据不同的分析表来决定其下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。LR方法是根据具体文法的分析表对输入串进行分析处理。

9 分析表的组成： a1 a2 (1) 分析动作表Action 符号 状态 … at S0 S1 Sn action[S0 , a1]
action[S0 , at] S1 action[S1 , a1] action[S1 , a2] action[S1 , at] Sn action[Sn , a1] action[Sn , a2] action[Sn , at]

10 表中action[Si,aj]为二维数组，指出当前栈顶为状态Si，输入符号为aj是所执行的动作。其动作有四种可能，分别为移进(S)、归约(r)、接受(acc)、出错(error)。
(2) 状态转换表goto

11 表中goto[Si,xj]指出栈顶状态为Si，文法符号为xj时应转到的下一状态。
… xt S0 goto[S0 , x1] goto[S0 , x2] goto[S0 , xt] S1 goto[S1 ,x1] goto[S1 , x2] goto[S1 , xt] Sn goto[Sn , x1] goto[Sn , x2] goto[Sn , xt] 表中goto[Si,xj]指出栈顶状态为Si，文法符号为xj时应转到的下一状态。

12 分析表种类的不同决定使用不同的LR分析方法
a) SLR分析表(简单LR分析表) 构造简单,最易实现,大多数上下文无关文法都 可以构造出SLR分析表,所以具有较高的实用 价值。使用SLR分析表进行语法分析的分析器 叫SLR分析器 b) LR分析表(规范LR分析表) 适用文法类最大,大多数上下文无关文法都能 构造出LR分析表,但其分析表体积太大.暂时实 用价值不大. 12 12

13 YACC c) LALR分析表(超前LR分析表) 这种表适用的文法类及其实现上难易在上面 两种之间,在实用上很吸引人.
使用LALR分析表进行语法分析的分析器叫LALR分析器。 例：YACC 文法规则文件 YACC源文件 YACC 某语言的 LALR分析器 13 13

14 几点说明 1.三种分析表对应三类文法 2.一个SLR文法必定是LALR文法和LR文法 14 14

15 3、LR分析过程： LR分析步骤： (a) 将初始状态S0和句子的左界符#分别进分析栈。
(b) 根据栈顶状态和当前输入符号查动作表，进 行如下的工作。 ※ 移进：当前输入符号进符号栈，根据状态转换表新的状态进状态栈，继续扫描，从而下一输入符号变成当前输入符号。 ※ 归约： (1)按某个产生式进行归约，若产生式的右端长度为n，则符号栈顶和状态顶n个元素同时相应退栈。(2)归约后的文法符号进符号栈，(3)查

16 状态转换表，新的状态进状态栈。 (c) 接受：分析成功，终止分析。 (d) 出错：报告出错信息。 (2) 具体分析过程： 举例说明具体分析过程： 设文法为G[L] （假定已存在LR分析表） (1) L E,L (2) L E (3) E a (4) E b

17 LR分析算法 置ip指向输入串w的第一个符号 令S为栈顶状态 a是ip指向的符号 重复 begin if ACTION[S,a]=Sj
then begin PUSH j,a(进栈) ip 前进(指向下一输入符号) end else if ACTION[S,a]=rj (第j条产生式为A)

18 LR分析算法 end.重复 then begin end else if ACTION[s,a]=acc else error
pop || 项 令当前栈顶状态为S’ push GOTO[S’,A]和A(进栈) end else if ACTION[s,a]=acc then return (成功） else error end.重复

19 ri表示按第i个产生式进行归约 空白表示分析动作出错。 为了介绍LR分析过程，在这里直接给出该文法的分析表，之后再介绍如何生成该表。
Si表示把当前输入符号移进栈，且转第i个状态，即第i个状态进状态栈。 i表示转第i个状态，即第i个状态进状态栈。 状态 ACTION GOTO a b , # L E S0 S3 S4 1 2 S1 acc S2 S5 r2 r3 r4 6 S6 r1 ri表示按第i个产生式进行归约 空白表示分析动作出错。

20 根据上述分析表，即可对输入串进行分析。如输入串为#a,b,a#具体分析过程如下：
状态栈 符号栈 产生式 输入符号 说明 S0 # a,b,a# S0和#进栈 S0S3 #a ,b,a# a和S3进栈 S0S2 #E Ea a和S3退栈 E和S2进栈 S0S2S5 #E, b,a# , 和S5进栈 S0S2S5S4 #E,b , a# b和S4进栈 S0S2S5S2 #E,E Eb b和S4退栈

21 状态栈 符号栈 产生式 输入符号 说明 S0S2S5S2S5 #E,E, a# , 和S5进栈 S0S2S5S2S5S3 #E,E,a # a和S3进栈 S0S2S5S2S5S2 #E,E,E Ea a和S3退栈 E和S2进栈 S0S2S5S2S5S6 #E,E,L LE E和S2退栈 L和S6进栈 S0S2S5S6 #E,L LE,L E,L和S2S5S6退 S0S1 #L L和S1进栈 acc

22 自底向上分析法的关键问题是在分析过程中如何确定句柄。LR方法中的句柄是通过求可归前缀而求得。

23 活前缀与可归前缀 例：文法G[S]为： S aAcBe A b A Ab B d 为产生式加序号变为： S aAcBe[1]
对于输入串abbcde句子的最右推导（规范推导）如下： SaAcBe[1] aAcd[4]e[1] aAb[3]cd[4]e[1] ab[2]b[3]cd[4]e[1]

24 对它的逆过程最左归约(规范归约)为： ab[2]b[3]cd[4]e[1] aAb[3]cd[4]e[1] aAcd[4]e[1] aAcBe[1] S 为产生式加序号变为： S aAcBe[1] A b[2] A Ab[3] B d[4] 用哪个产生式继续归约仅取决于当前句型的前部。 我们把每次采取归约动作前的符号串部分称为可归前缀。 LR分析的关键就是识别何时到达可归前缀。

25 ，a，aA，aAc，aAcB，aAcBe
在规范句型中形成可归前缀之前包括可归前缀的所有前缀称为活前缀。活前缀为一个或若干规范句型的前缀。在规范归约过程中的任何时刻只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀，则表明输入串的已被分析过的部分是某规范句型的一个正确部分。 例如：有下面规范句型的前缀： ，a，ab ，a，aA，aAb ，a，aA，aAc，aAcd ，a，aA，aAc，aAcB，aAcBe 左部均为活前缀，其中，红色部分为可归前缀

26 活前缀的定义及在LR分析中的应用 G=(Vn,Vt,P,S),若有S’  αAω  αβω, A  β （ β是句柄 ）
* G=(Vn,Vt,P,S),若有S’  αAω  αβω, A  β （ β是句柄 ） γ是αβ的前缀,则称是文法G的活前缀 αβ是含句柄的活前缀，并且句柄是αβ的后端，则称αβ是可归前缀或可规范前缀。 在LR分析过程中，实际上是把αβ的前缀（即文法G的活前缀）列出放在符号栈中，一旦在栈中出现αβ（形成可归前缀），即句柄已经形成，则用产生式A  β进行归约。 R

27 P126 识别活前缀的有限自动机 对任何一个上下文无关文法，只要能构造出它的识别可归前缀的有限自动机，就可以构造其相应的分析表（状态转换表和动作表）。

28 S0S1...... Sm #S0x1S1x2...... xmSm # x1x2..... xm ☆ 状态栈:
☆ 状态栈: 栈顶状态概括了从分析开始到该状态的 全部分析历史. ☆ 符号栈: X1X Xm 为从开始状态(S0)到当前状态(Sm)所识别的规范句型的活前缀.

29 ☆ 分析表 a. 状态转移表 (GOTO表) GOTO表 E T F S0 S1 S2 : Sn 是一个矩阵： 行---分析器的状态
☆ 分析表 是一个矩阵： 行---分析器的状态 列----文法符号 a. 状态转移表 (GOTO表) GOTO表 符号 E T F 状态 S0 S1 S2 : Sn

30 Si ------ 新的栈顶状态(状态转移) Si需要满足条件是:
符号 E T F S0 S1 S2 : Sn GOTO表 #S0x1S1x xi-1Si-1 xiSi GOTO[Si-1, xi]=Si Si-1 ---当前状态(栈顶状态) xi 新的栈顶符号 Si 新的栈顶状态(状态转移) Si需要满足条件是: 若X1X2…. Xi-1是由S0到Si-1所识别的规范句型的活前缀,则X1X2…. Xi是由S0到Si所识别的规范句型的活前缀

31 状态转移函数GOTO是定义了一个以文法符号集为字母表的有穷自动机，该自动机识别文法所有规范句型的活前缀及可归前缀。
通过对有穷自动机的了解,我们可以看出: 状态转移函数GOTO是定义了一个以文法符号集为字母表的有穷自动机，该自动机识别文法所有规范句型的活前缀及可归前缀。 M=(S, V, GOTO, S0, Z) S0 S1 Si-1 S2 Si X1 X2 Xi-1 Xi

32 ACTION[Si,a]=动作分析 a∈Vt
b. 分析动作表(ACTION表) 识别为活前缀的，则移进；识别为可归前缀的，则归约 Sn 状态s 输入符号a i + * ( ) # S0 S1 S2 : ACTION表 ACTION[Si,a]=动作分析 a∈Vt

33 分析动作： 1)移进(shift) ACTION[Si,a]=S 动作：将a推进栈，并设置新的栈顶状态Sj
Sj=GOTO[Si,a]，将指针指向下一个输入符号 2)规约(reduce) ACTION[Si,a]=rd d：文法规则编号 (d) A→β 动作：将符号串β(假定长度为n)连同状态从栈内弹出把A推进栈，并设置新的栈顶状态Sj , Sj=GOTO[Si-n,A] 3)接受(accept) ACTION[Si,#]=accept 4)出错(error) ACTION[Si,a]=error

34 ☆ 控制程序:(Driver Routine)
1) 根据栈顶状态和现行输入符号，查分析动作表(ACTION表)，执行有分析表所规定的操作； 2) 并根据GOTO表设置新的栈顶状态(即实现状态转移)

35 （2） LR分析过程 例：文法G[E] (1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F
(5)F::=(E) (6)F::=i 该文法是SLR文法,故可以构造出SLR分析表(ACTION表和GOTO表)

36 i + * ( ) # E T F ACTION表 GOTO表 0(S0) 3 1(S1) 2(S2) 3(S3) 4(S4) 5(S5)
文法符号 状态 i + * ( ) # E T F 0(S0) S5 S4 1 2 3 1(S1) S6 ACCEPT 2(S2) R2 S7 3(S3) R4 4(S4) 8 5(S5) R6 6(S6) 9 7(S7) 10 8(S8) S11 9(S9) R1 10(S10) R3 11(S11) R5 文法G[E] ：(1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F (5)F::=(E) (6)F::=i

37 Si：移入，i为状态 Ri：规约，i为产生式编号
ACTION 表 GOTO 表 输入符号 状态 文法G[E] (1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F (5)F::=(E) (6)F::=i Si：移入，i为状态 Ri：规约，i为产生式编号

38 分析过程 ： i*i+i 步骤 状态栈 符号 输入串 动作 1 ＃0 ＃ i*i+i# 初始化 2 ＃0i5 ＃i *i+i# S
步骤 状态栈 符号 输入串 动作 1 ＃0 ＃ i*i+i# 初始化 2 ＃0i5 ＃i *i+i# S 3 ＃0F3 ＃F *i+i# R6 4 ＃0T2 ＃T *i+i# R4 5 ＃0T2*7 ＃T* i+i# S 6 ＃0T2*7i5 ＃T*i +i# S 7 ＃0T2*7F10 ＃T*F +i# R6

39 8 ＃0T2 #T +i# R3 9 ＃0E1 #E +i# R2 10 ＃0E1+6 #E i# S 11 ＃0E1+6i5 #E+i # S 12 ＃0E1+6F3 #E+F # R6 13 ＃0E1+6T9 #E+T # R4 14 ＃0E1 #E # R1 #E Accept

40 (1) 每次规约总是规约当前句型的句柄，是规范规约，可以看到语法树(算符优先是规约最左素短语)
由分析过程可以看到: E T + * F i 8 7 5 6 4 3 2 1 (1) 每次规约总是规约当前句型的句柄，是规范规约，可以看到语法树(算符优先是规约最左素短语) (2) 分析的每一步栈内符号串均是规范句型的活前缀，与输入串的剩余部分构成规范句型.

41 LR方法概述（回顾）

42 LR分析法如何分析句子？ 移进归约（从左到右扫描(L)自底向上进行规约(R) ） 移进归约的关键问题是什么？ 判断符号栈顶的符号串是否构成句柄。 LR分析法如何识别句柄？ LR分析法在分析过程中并不是直接分析符号栈中的符号是否形成句柄，而是通过识别可归前缀来识别句柄。 具体地，LR分析法的分析过程可以看作识别活前缀和可归前缀的过程，只要符号栈中的符号串构成活前缀，就表示已分析过的部分是正确的，继续移进；直到符号栈中的符号串构成可归前缀，则表示当前栈顶符号串已形成句柄，则进行归约。

43 如何识别活前缀和可归前缀？ 通过有限自动机来识别。 如何构造识别活前缀和可归前缀的有限自动机？ 根据文法规则 状态集合：列出所有活前缀的识别状态 符号表：所有的终结符和非终结符 状态转换函数： f(Ki ，a)= Kj 某一个活前缀的识别状态，在输入符号表中的一个符号之后，转向另一个活前缀的识别状态。 终态集：所有可归前缀的识别状态

44 LR(0)分析 构造LR分析器的关键是构造其分析表 构造LR分析表的方法是: （1）根据文法构造识别规范句型活前缀的有穷自动机DFA
（2）由DFA构造LR分析表

45 1. 构造DFA (1) DFA是一个五元式 M=(S, V, GOTO, S0, Z) S：有穷状态集
在此具体情况下，S=LR(0)项目集规范族LR(0)。 项目集规范族：其元素是由项目所构成的集合. V：文法字汇表 Vn∪Vt S0：初始状态 GOTO:状态转移函数 GOTO[Si,X]=Sj Si ,Sj∈S Si ,Sj为项目集合 X∈Vn∪Vt 表示当前状态Si面临文法符号为X时，应将状态转移到 Sj Z：终态集合

46 ∴构造DFA方法： 1） 确定S集合，即LR（0）项目集规范族，同时确定S0 2） 确定状态转移函数GOTO

47 LR(0)分析 确定状态集合 每一个状态对应文法中某一个产生式规则的某一个项目 每一个产生式规则的每一个项目代表一个活前缀的识别状态。
产生式规则的项目？

48 活前缀与句柄的关系： G[S]: 若S => αAω =>αβω r是αβ的前缀，则 * R 称r是G的一个活前缀 R

49 活前缀,与句柄 ,与 LR(0)项目 为刻划这种分析过程中的文法G的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶）的情况，分别用标有圆点的产生式来指示位置。 A→β．刻划产生式A→β的 右部β已出现在栈顶 A→β1．β2 刻划A→β1β2的右部子串β1已出现在栈顶，期待从输入串中看到β2推出的符号 A→．β 刻划没有句柄的任何符号在栈顶，此时期望A→β的右部所推出的符号串 对于A→ε的LR(0)项目只有A→．

50 项目:文法G的每个产生式(规则)的右部添加一个圆点就构成一个项目。
项目的直观意义:指明在分析过程中的某一时刻已经规约的部分和等待规约部分。 例:产生式:A→XYZ 项 目: A→.XYZ A→X.YZ A→XY.Z A→XYZ. 产生式:A→ε 项 目: A→. 其中， ε、 X、XY、 XYZ为活前缀，XYZ是可归前缀。

51 例如：产生式SaAcBe对应有6个项目。
[0] S·aAcBe [1] Sa·AcBe [2] SaA·cBe [3] SaAc·Be [4] SaAcB·e [5] SaAcBe ·

52 项目类型： 项目类型有归约项目、移进项目、待约项目和接受项目。  归约项目：后继符号为空的项目称为归约项目。 如：A   · 此时已把分析结束， 已在栈顶，从而可按相应的产生式进行归约。  移进项目：后继符号为终结符的项目称为移进项目。如A   ·X，XVn 此时把X移进，即X进符号栈。  待约项目：后继符号为非终结符的项目，称为待约项目。

53 此时期待着从余留的输入符号中进行归约而得到X。
 接受项目：当归约项目为S’  S · 时则表明已分析成功，即输入串为该文法的句子，相应状态为接受状态。 构造识别活前缀的NFA P131 NFA的确定化——将NFA的一些状态组成集合构成DFA的状态 状态集合的闭包

54 LR(0)项目集规范族的构造 状态内容是项目集组成的，它分为基本(BASIC)部分和闭包(CLOSURE)部分。 ※求BASIC和CLOSURE的方法如下： 设Si是Sk关于符号X的后继状态，则有 BASIC(Si)的计算： BASIC(Si)={AX·|A·XSk} CLOSURE(Si)的计算：  BASIC(Si)  CLOSURE(Si)

55 若A  ·YCLOSURE(Si), 且Y  Vn则 Y  · r CLOSURE(Si),r为符号串
例如：文法G[S]： S  A A  aAb A  c 设开始状态为S0，则S0的状态内容为： BASIC(S0)={S  · A} CLOSURE(S0)={S  · A , A  · aAb,A  · c}

56 A.项目集闭包closure的定义和计算:
令I是文法G’的任一项目集合，定义closure(I)为项目集合I的闭包，可用一个过程来定义并计算closure(I)。 Procedure closure(I); begin 将属于I的项目加入closure(I); repeat for closure(I)中的每个项目A→α.Bβ(B∈Vn) do 将B→.r(r∈V* )加入closure(I) until closure(I)不再增大 end 例:G’[E’] 令I={E’→.E} closure(I)={E’→.E, E→.E+T, E→.T, T→.T*F, T→.F, F→.(E), F→.i }

57 B 状态转移函数GOTO的定义: GOTO(I,X)=closure(J) I：项目集合 X：文法符号，X∈V J：项目集合
J={任何形如A→αX.β的项目| A→α.Xβ∈I} closure(J):项目集J的闭包仍是项目集合 所以,GOTO(I,X)=closure(J)的直观意义是: 它规定了识别文法规范句型活前缀的DFA从状态I(项目集)出发,经过X弧所应该到达的状态(项目集合)

58 LR(0)项目集规范族的构造算法: P133步骤（1）、（2）、（3） G'→LR(0) Procedure ITEMSETS(G');
begin LR(0):={closure({E'→.E})}; repeat for LR(0)中的每个项目集I和G'的每个符号X do if GOTO(I , X)非空,且不属于LR(0) then 把GOTO(I , X)放入LR(0)中 until LR(0)不再增大 end

59 (0) E’→E (4) T→F E→E+T (5) F→(E) E→T (6) F→i T→T*F 例.求G'[E']的LR(0) V={E, T, F, I, +, *, (, )} G'[E']共有20个项目 LR(0)={I0,I1,I2,…I11} 有12个项目组成: I0: E'→.E E→.E+T E→.T T→.T*F T→.F F→.(E) F→.i I1: E'→E. E→E.+T Closure({B’→.B})=I0 GOTO(I0,E)=closure({E’→E. E→E.+T}) =I1

60 I2: E→T. GOTO(I0,T)=closure({E→T. T→T.*F})= I2 T→T.*F
I3: T→F GOTO(I0,F)=closure({T→F.})= I3 I4: F→(.E) GOTO(I0,()=closure({F→(.E)})= I4 E→.E+T E→ .T T→.T*F T→.F F→.(E) F→.i I5: F→i GOTO(I0,i)=closure({F→i.})= I5 GOTO(I0,*)=φ GOTO(I0,+)=φ GOTO(I0,))=φ I0: E'→.E E→.E+T E→.T T→.T*F T→.F F→.(E) F→.i

61 I6: E→E+.T GOTO(I1,+)=closure({E→E+.T})= I6 T→.T*F GOTO(I1,其他符号)为空
I2: E→T. T→T.*F I6: E→E+.T GOTO(I1,+)=closure({E→E+.T})= I6 T→.T*F GOTO(I1,其他符号)为空 T→.F F→.(E) F→.i I7: T→T*.F GOTO(I2,*)=closure({T→T*.F})= I7 F→.(E) GOTO(I2,其他符号)为空 F→.i GOTO(I3,其他符号)为空

62 I8: F→(E.) GOTO(I4,E)=closure({F→(E.),E→E.+T})= I8
I4: F→(.E) E→.E+T E→ .T T→.T*F T→.F F→.(E) F→.i I8: F→(E.) GOTO(I4,E)=closure({F→(E.),E→E.+T})= I8 E→E.+T GOTO(I4,T)= I2 ∈LR(0) GOTO(I4,F)= I3 ∈LR(0) GOTO(I4,()= I4 ∈LR(0) GOTO(I4,i)= I5 ∈LR(0) GOTO(I4,+)=φ GOTO(I4,*)=φ GOTO(I4,))=φ GOTO(I5,其他符号)=φ I9: E→E+T. GOTO(I6,T)=closure({E→E+T.,T→T.*F})= I9 E→T.*F GOTO(I6,F)= I3 GOTO(I6,()= I4 GOTO(I6,i)= I5

63 I10:T→T*F. GOTO(I7,T)=closure({T→T*F .})= I10
GOTO(I7,()= I4 GOTO(I7,i)= I5 I11:F→(E). GOTO(I8,))=closure({F→(E) .})= I11 求完所有Ii的后继 GOTO(I8,+)= I6 GOTO(I9,*)= I7 GOTO(I10,所有符号)=φ, GOTO(I11,所有符号)=φ

64 构造DFA M=(S, V, GOTO, S0, Z) S ={I0, I1, I2, …, I11}=LR(0)
V ={+, *, i, (, ), E, T, F} GOTO(Im , X)= Im S0=I0 Z=S-{I0}={I1, I2, …, I11}

65 + + I1 i I6 I9 E i I5 + i i * start F I0 F I3 ( I8 I11 ( F ( I4 ) E T I7 I10 T ( F I2 *

66 除I0以外,其余状态都是活前缀的识别状态,从I0到每一状态的每条路径都识别和接受一个规范句型的活前缀。

67 项目集的相容性： 〖定义〗 满足下列两个条件的项目集称为相容的项目集。 P134 ※ 无移进项目和归约项目并存。 ※ 无多个归约项目并存。 例如：若有项目集｛A ·，B ·｝此时栈顶为，根据项目集无法确定是移进还是归约。项目集是不相容的。 对一个文法的LR(0)项目集规范族不存在移进归约或归约归约冲突时，称该文法为LR(0)文法。

68 LR(0)分析表的构造 LR（0）分析表由两部分组成： 动作表表示当前状态下面临输入符号应做的动作是移进、归约、接受或出错； 状态转换表表示在当前状态下面临文法符号时应转向的下一个状态。

69 (2) LR(0)分析表的构造 构造原则： 设有文法G[S]，则LR(0)分析表的构造规则为：
 对于A ·XSi，GOTO(Si,X)=Sj 若X Vt，则置action[Si,X]=Sj 若X Vn，则置goto[Si,X]=j  对于A · Si，若A 是文法的第j个产生式，则对所有的xVt，均置action[Si,x]=rj  若S  · Si，则置action[Si,#]=acc  其他均置出错。

70 LR(0)分析表的构造 假定C={I0, I1,……，In}，令每个项目集Ik的下标k 为分析器的一个状态，因此，G` 的LR(0)分析表含有状态0，1，……，n。令那个含有项目S`→．S的Ik的下标k为初态。ACTION和GOTO可按如下方法构造： 若项目A→α．aβ属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTION[k, a]为“把状态j和符号a移进栈”，简记为“sj”; 若项目A→α．属于Ik, 那么，对任何终结符a, 置ACTION[k, a]为“用产生式A→α进行规约”，简记为“rj”;其中，假定A→α为文法G`的第j个产生式； 若GO (Ik, A)= Ij, A为非终结符，则置GOTO(k, A)=j; 若项目S`→S．属于Ik, 则置ACTION[k, #]为“接受”，简记为“acc”; 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”

71 例子：文法G为： (0) S’ E (1) E aA (2) E bB (3) A cA (4) A d (5) B cB (6) B d 该文法的状态描述序列见下表：

72 状态 项目集 后继符号 后继状态 S0 {S’  ·E E ·aA E ·bB E a b S1 S2 S3 S1 {S’ E · } #S’ E S12 S2 {Ea ·A A  · cA A · d} A c d S6 S4 S10 S3 {Eb·B B · cB B · d} B S7 S5 S11

73 状态 项目集 后继符号 后继状态 S4 {A c · A A · cA A · d} A c d S8 S10 S5 {Bc · B B · cB B · d} B S9 S11 S6 {EaA · } #EaA S12 S7 {EbB · } #EbB {A cA · } #A cA

74 根据状态描述序列和分析表的构造规则得到的LR(0)分析表如下：
项目集 后继符号 后继状态 S9 {BcB · } #BcB S12 S10 {Ad · } #Ad S11 {Bd · } #Bd { } 根据状态描述序列和分析表的构造规则得到的LR(0)分析表如下：

75 状 态 ACTION GOTO a b c d # E A B S0 S2 S3 1 S1 acc S4 S10 6 S5 S11 7 8 9 S6 r1 S7 r2 S8 r3 S9 r5 r4 r6

76 对于输入串#bccd#的分析过程如下： 状态栈 符号栈 产生式 输入符 action goto 说明 S0 # bccd# S3
b和S3进栈 S0S3 #b ccd# S5 c和S5进栈 S0S3S5 #bc cd# S0S3S5S5 #bcc d# S11 d和S11进栈 S0S3S5S5S11 #bccd B  d r6 9 d和S11退栈 B和S9进栈 S0S3S5S5S9 #bccB B  cB r5 … S0S3S5S9 #bcB 7 S0S3S7 #bB E  bB r2 1 S0S1 #E acc 接受

77 三、SLR(1)分析表的构造 1、问题的提出：
只有当一个文法G是LR(0)文法，即G的每一个状态项目集相容（P134）时，才能构造出LR(0)分析表； 由于大多数适用的程序设计语言的文法不能满足LR(0) 文法的条件，因此本节将介绍对于LR(0)规范族中冲突的项目集（状态）用向前查看一个符号的办法进得处理，以解决冲突。 因为只对有冲突的状态才向前查看一个符号，以确定做那种动作，因而称这种分析方法为简单的LR(1)分析法，用SLR(1)表示。

78 状态 项目集 后继符号 后继状态 S0 S’  · S S  · rD S r S1 S2 S’  S · #S’  S S7
文法G为： (0) S’  S S  rD D D,i D i 状态描述序列见下表： 状态 项目集 后继符号 后继状态 S0 S’  · S S  · rD S r S1 S2 S’  S · #S’  S S7

79 S2 S  r · D D  · D,i D  · i D i S3 S4 S  rD · D D · ,i #S  rD , S7 S5 Di · #Di D D, · i S6 D D,i · #D D,i { }

80 分析每个状态包含的项目集，不难发现在状态S3中含项目：
S  rD · 为归约项目 D  D · ,ｉ　 为移进项目 也就是按SrD · 项目的动作认为用SrD产生式进行归约的句柄已形成，不管当前的输入符号是什么，都应把rD归约成S。但是按DD · ,i 项目当面临输入符为’,’号时，应将‘,’号移入符号栈，状态转向S5。显然该文法不是LR(0)文法，S3项目集不相容。也可在构造它的LR(0)分析表时发现这个问题，如下表所示。

81 状 态 ACTION GOTO r , i # S D S0 S2 1 S1 acc S4 3 S3 r1 r1, S5 r3 S5 S6 r2

82 如何解决这种移进-归约冲突？ LR（0）在归约时不向前看输入符号； 在LR（0）基础上，如果出现不相容的项目（存在移进-归约冲突或归约-归约冲突）则LR（k）方法通过向前看k个输入符号来解决冲突（利用上下文信息来消除当前的歧义） SLR（1）： （1）只在项目出现冲突时S，（2）才向前看1个输入符号LR（1）；

83 SLR(1)分析表的构造方法思想 在出现移进-归约冲突或归约-归约冲突时，通过观察归约成的非终结符的后跟符号集合，来区分移进-归约动作或不同的归约动作。 上例冲突的解决 归约还是移进？ 如果归约，那么要构成一个合法的句子，该非终结符后都可以跟哪些终结符？ 而输入符号串中的当前符号是什么？ 是否匹配？ 匹配：则归约；不匹配：则不归约。

84 后跟符号集合的定义： Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。
设G=（VT，VN，P，S）是上下文无关文法，A∈VN，S是开始符号， Follow(A)={a | S uAβ且a∈VT，a ∈First(β)，u∈VT*，β∈V+}。针对非终结符 若S  uAβ，且β  ε，则#∈Follow(A) （#表示输入串的结束符，或句子括号） * * * 可写成为： Follow(A)＝｛a|S…Aa…， a∈VT｝ 若S…A，则#∈Follow(A)。 * * Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。

85 2、SLR(1)分析表的构造方法思想 在构造SLR(1)分析表时，根据不同的向前看符号，将Si中的各项目所对应的动作加以区分，从而即可使冲突动作得到解决。

86 假定一个LR(0)规范族中含有如下的项目集（状态）Si 
Si={ X→ · bβ, A →  · , B→δ· } 也就是在该项目集中含有移进-归约冲突和归约-归约冲突。其中,β,  ,δ为文法符号串，b为终结符。方法如下： 对于归约项目A  · ，B  δ · 分别求Follow(A)和Follow(B )， Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。 如果满足如下条件：

87 FOLLOW(A)∩FOLLOW(B)＝φ FOLLOW(A)∩{b}＝φ FOLLOW(B)∩{b}＝φ
那么，当在状态Si时面临某输入符号为a时，则构造分析表时用以下方法即可解决冲突动作。 (1) 若a=b，则移进。 (2) 若a∈Follow(A),则用产生式A →  进行归约。   (3) 若a∈Follow(B),则用产生式B →δ进行归约。 (4) 此外，报错。

88 如果对于一个文法的LR（0）项目集规范族所含有的动作冲突都能用以上方法来解决，则称该文法为SLR（1）文法。

89 3、SLR(1)分析表的构造 例如文法： (0) S’ →E (1) E→E+T (2) E→T (3) T→T*F (4) T→F
      (5) F→(E)       (6) F→i

90 状态描述序列如下： 状态 项目集 后继符号 后继状态 S0 { S’→ · E E→ · E+T E→ · T Ｔ→ ·Ｔ*F Ｔ→ · F F→ ·（E） F→ ·ｉ } E T F ( i S1 S2 S3 S4 S5 { S’→E · E→E · +T } #S’→E + S12 S6

91 状态 项目集 后继符号 后继状态 S2 {E→Ｔ· Ｔ→Ｔ· *F } #E→T · * S12 S7 S3 {Ｔ→F · } #T→F S4 {F→（· E） E→· E+T E→ · T Ｔ→·Ｔ*F Ｔ→· F F→·（E） F→·ｉ } E T F ( i S8 S5

92 状态 项目集 后继符号 后继状态 S5 {F→ｉ· } #F→ｉ S12 S6 {E→E＋·T T→ · T*F Ｔ→ · F F→·（E） F→·ｉ} T F ( i S9 S3 S4 S7 {T→T* · F F→ ·（E） F→ ·ｉ } S10

93 由上图可见，S1、S2和S9的项目集均不相容，其有移进项目和归约项目并存，构造LR(0)分析表如下：
状态 项目集 后继符号 后继状态 S8 {F→( E · ) E→E · +T } ) + S11 S6 S9 {E→E+T · T→T · *F } #E→E+T * S12 S7 S10 {T→T*F · } #T→T*F {F→( E ) · } #F→(E) { } 由上图可见，S1、S2和S9的项目集均不相容，其有移进项目和归约项目并存，构造LR(0)分析表如下：

94 状 态 ACTION GOTO i + * ( ) # E T F S0 S5 S4 1 2 3 S1 S6 acc S2 r2 r2 S7 S3 r4 8 r6 9 S7 10 S8 S11 S9 r1 r1 S7 S10 r3 r5

95 从上表也可见在S１, S２, S９中存在移进-归约冲突 。这个表达式不是LR(0)文法，也就不能构造LR(0)分析表，现在分别考查这三个项目（状态）中的冲突是否能用SLR(1)方法解决。
对于S1：{S’→E · , E→E ·＋T } 由于Follow(S’)={＃}，而S’→· E是唯一的接受项目，所以当且仅当遇到句子的结束符“＃”号时才被接受。又因{＃}∩{＋}=，因此S1中的冲突可解决。 对于S2 : S2={ E T · , TT · *F } 计算Follow(E) = { #, +, ) }

96 所以Follow(E)∩{*}= 因此面临输入符为‘+’，‘)’或‘＃’号时，则用产生式E→T进行归约。 当面临输入符为‘*’号时，则移进, 其它情况则报错。 对于S9 : S9={ E E+T · , TT · *F } 计算Follow(E) = { #, +, ) } , 所以Follow(E)∩{*}= 因此面临输入符为‘+’，‘)’或‘＃’号时，则用产生式E→E+T进行归约。 当面临输入符为‘*’号时，则移进。 其它情况则报错。

97 由以上考查，该文法在S１，S２，S９三个项目集(状态)中存在的移进-归约冲突都可以用SLR(１)方法解决，因此该文法是SLR(１)文法。我们可构造其相应的SLR(１)分析表。
SLR(1)分析表的构造与LR(0)分析表的构造类似，仅在含有冲突的项目集中分别进行处理。 进一步分析我们可以发现如下事实：例如在状态S3中，只有一个归约项目T→F ·　，按照SLR(1)方法，在该项目中没有冲突，所以保持原来LR(0)的处理方法，不论当前面临的输入符号是什么都将用产生式T→F进行归约。

98 但是很显然T的后跟符没有‘（’符号，如果当前面临输入符是‘（’，也进行归约显然是错误的。因此我们对所有归约项目都采取SLR(1)的思想，即对所有非终结符都求出其Follow集合，这样凡是归约项目仅对面临输入符号包含在该归约项目左部非终结符的Follow集合中，才采取用该产生式归约的动作。 对于这样构造的SLR(1)分析表我们称它为改进的SLR(1)分析表。 改进的SLR(1)分析表的构造方法如下：

99 对于A · X，GO[ Si , X ]Sj ，若X  Vi ，则置actoin[Si , X]=Sj
若X Vn ，则置goto[Si , X]=j (2) 对于归约项目A   · Si , 若A为文法的第j个产生式，则对任何输入符号a，若aFollow(A)，则置action[Si , a]=rj (3) 若S · Si，则置action[Si , #]=acc (4) 其它情况均置出错。 改进的SLR(1)分析表如下：

100 状 态 ACTION GOTO i + * ( ) # E T F S0 S5 S4 1 2 3 S1 S6 acc S2 r2 S7 S3 r4 8 r6 9 10 S8 S11 S9 r1 S10 r3 r5

101 四、LR(1)分析表的构造 1、问题的提出 在SLR(1)方法中，对于某状态Si，其项目集若不相容时，可根据SLR(1)分析表的构造规则来解决冲突分析动作，但如果不相容的项目集中的向前看集合及其有关集合相交时，就不可能通过SLR(1)分析表构造规则来构造SLR(1)分析表。这时就用LR(1)分析。

102 SLR 例：文法G: （0）S`→S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e

103 查看I5 ，I7中的冲突，体会LR(1)如何解决
文法G‘： (0) S’  S (1) S  aAd (2) S  bAc (3) S  aec (4) S  bed (5) A  e I0: S’ ® • S S  • aAd S  • bAc S  • aec S  • bed I1: S’ ® S • I4: S  aA • d I2: S  a •Ad S  a • ec A  • e I5: S  ae • c A  e • I8: S  aAd • I3: S  b • Ac S  b • ed A  • e I6: S  bA • c I9: S  ae c • I7: S  be • d A  e • 查看I5 ，I7中的冲突，体会LR(1)如何解决 I10: S  bAc • I11: S  bed •

104 I5: S →ae．c 并不是Follow（A）的每个元素在含A的所有句型中都会在A的后面出现 A →e．
S`==>S==>aAd==>aed S`==>S==>aec 活前缀ae遇到c应移进；遇到d应归约 I7: S →be．d S`==>S==>bAc==>bec S`==>S==>bed 活前缀be遇到d应移进；遇到c应归约 并不是Follow（A）的每个元素在含A的所有句型中都会在A的后面出现 R R R R R R R R R R

105 LR（1）方法 在每个项目中增加向前搜索符 若项目集[A→•B]属于I时，则[B→•]也属于I
把FIRST()作为用产生式归约的搜索符（称为向前搜索符），作为用产生式B→归约时查看的符号集合（用以代替SLR(1)分析中的FOLLOW集），并把此搜索符号的集合也放在相应项目的后面，这种处理方法即为LR(1)方法

106 LR(1)项目集族的构造：针对初始项目S’→•S,#求闭包后再用转换函数逐步求出整个文法的LR(1)项目集族。
1）构造LR（1）项目集的闭包函数 a)I的项目都在CLOSURE(I)中 b)若A→ • B，a属于CLOSURE(I)， B→ 是文法的产生式，V*，bFIRST(a),则B→• ,b也属于CLOSURE(I) c)重复b)直到CLOSURE(I)不再扩大 2)转换函数的构造 GOTO（I，X）= CLOSURE（J） 其中：I为LR(1)的项目集，X为一文法符号 J={任何形如A→X • ,a的项目| A→ • X ,a属于I}

107 一个文法符号串的first集合计算方法：
如果文法符号串V*, =X1X2…Xn, 1、当X1ε，则first()=first(X1) 2、当对任何j（1≤j≤i-1，2 ≤i ≤n），εfirst(Xj) 则first()=(first(X1)-{ε}) ∪(first(X2)-{ε}) ∪…∪(first(Xi-1)-{ε}) ∪first(Xi) 3、当first(Xj)都含有ε时(1 ≤ j ≤ n)，则first()=first(X1) ∪first(X2) ∪…∪first(Xj) ∪{ε} *

108 查看I5 ，I7中的冲突，体会LR(1)如何解决
文法G‘： (0) S’  S (1) S  aAd (2) S  bAc (3) S  aec (4) S  bed (5) A  e I0: S’ ® • S, # S  • aAd, # S  • bAc, # S  • aec, # S  • bed, # I1: S’ ® S •, # I4: S  aA • d, # I2: S  a •Ad, # S  a • ec, # A  • e, d I5: S  ae • c, # A  e •, d I8: S  aAd •, # I3: S  b • Ac, # S  b • ed, # A  • e, c I6: S  bA • c, # I9: S  ae c •, # I7: S  be • d, # A  e •, c 查看I5 ，I7中的冲突，体会LR(1)如何解决 I10: S  bAc •, # I11: S  bed •, #

109 LR(1)分析表的构造 LR(1)分析表的构造与LR(0)分析表的构造在形式上基本相同，不同之处在于：归约项目的归约动作取决于该归约项目的向前搜索符号集。 1) 若项目[A→ • a,b]属于Ik，且转换函数GO(Ik,a)= Ij ，当a为终结符时，则置ACTION[k,a]为Sj 2) 若项目[A→ • ,a]属于Ik ，则对a为任何终结符或‘#’，置ACTION[k,a] = rj ，j为产生式在文法G‘中的编号 3) 若GO(Ik,A)= Ij ，则置GOTO[k,A]=j，其中A为非终结符，j为某一状态号 4) 若项目[S‘→S • ,#]属于Ik ，则置ACTION[k,#] = acc 5) 其它填上“报错标志” 例：P146 表7.10

110 LALR(1)分析 文法G‘： (0) S’  S (1) B  aB (2) S  BB (3) B  b

111 LR(1)项目集和转换函数 文法G‘： (0) S’  S (1) B  aB (2) S  BB (3) B  b I0:
B  • aB, a/b B  • b, a/b I1: S’ ® S •, # S I5: S  B B •, # B I2: S  B • B, # B  • a B, # B  • b, # B a I6: S  a • B, # B  • aB, # B  • b, # a b I4: B  b •, a/b b a b B b a I7: B  b •, # I9: B  a B •, # I3: B  a • B, a/b B  • aB, a/b B  • b, a/b B LR(1)项目集和转换函数 I8: B  a B •, a/b

112 分析可发现I3和I6 ， I4和I7 ， I8和I9分别为同心集
如果两个LR(1)项目集去掉搜索符之后是相同的， 则称这两个项目集具有相同的心。 分析可发现I3和I6 ， I4和I7 ， I8和I9分别为同心集 I3: B  a • B, a/b B  • aB, a/b B  • b, a/b I6: S  a • B, # B  • aB, # B  • b, # I3,6: S  a • B, a/b/# B  • aB, a/b/# B  • b, a/b/# 合并为 I4: B  b •, a/b I7: B  b •, # 合并为 I4,7: B  b •, a/b/# I8: B  a B •, a/b I9: B  a B •, # I8,9: B  a B •, a/b/# 合并为

113 LALR(1)分析 对LR(1)项目集规范族合并同心集，若合并同心集后不产生新的冲突，则为LALR(1)项目集。

114 合并同心集的几点说明 同心集合并后心仍相同，只是超前搜索符集合为各同心集超前搜索符的和集 合并同心集后转换函数自动合并
LR(1)文法合并同心集后也只可能出现归约-归约冲突，而没有移进-归约冲突 合并同心集后可能会推迟发现错误的时间，但错误出现的位置仍是准确的

115 合并同心集后

116 G’[S’]: (0) S’S (1) S  L=R (2) S  R (3) L  *R (4) L  i (5) R  L 判断该文法是否是LR(0)、SLR(1)、LR(1)、LALR(1)文法。

117 构造LR（0）项目集规范族 If 所有的项目集都是相容的，则为LR（0）文法； Else if 冲突项目可以通过考察非终结符的后跟符号集来解决，则为SLR（1）文法； Else 构造LR（1）项目集规范族 If 任何项目集中都不存在动作冲突，则为LR（1）文法； 对LR（1）项目集规范族进行同心集的合并，如合并之后仍不存在冲突，则为LALR（1）文法。

118 几种文法的比较 LR(0) SLR(1): 生成的LR(0)项目集如有冲突，则根据非终结符的FOLLOW集决定
LR(1)、LR(k): 项由 核心与向前搜索符组成，搜索符长度为1或k LALR(1): 对LR(1)项目集规范族合并同心集 由弱到强：LR（0）、SLR（1）、LALR（1）、LR（1） LR（1）中的向前搜索符号集合是与该项目相关的非终结符号的Follow集的子集； LALR项目的搜索符一般是与该项目相关的非终结符号的Follow集的子集，这正是LALR分析法比SLR分析法强的原因。

119 作业 P 、3、9