第五章 语法分析-自下而上分析 5.1 自下而上分析的基本问题 Figure5.5LR演示自下而上分析 i+(i+i)*i

Presentation on theme: "第五章 语法分析-自下而上分析 5.1 自下而上分析的基本问题 Figure5.5LR演示自下而上分析 i+(i+i)*i"— Presentation transcript:

1 第五章 语法分析-自下而上分析 5.1 自下而上分析的基本问题 Figure5.5LR演示自下而上分析 i+(i+i)*i
原理:自左向右扫描，自下而上分析 从输入符号串入手，通过反复查找当前句型的可归约串，并使用文法的产生式把它归约成相应的非终结符来一步步地进行分析的。 最终把输入串归约成文法的开始符号，表明分析成功。 任何自下而上分析方法的关键就是要找出当前句型的可归约串，然后根据产生式判别将它归约成什么样的非终结符。

2 规范归约基本概念 G为文法，S为开始符号，假定αβδ是G的一个句型，如果 则称β是句型 αβδ相对于非终结符A的短语。
如果A=> β，则称β是句型 αβδ相对于非终结符A的直接短语。 最左直接短语称为句柄。 表达式文法的例子 i+i*i,找出所有短语，直接短语和句柄 从句子到开始符号的归约序列，如果每一步都是把句柄替换为 相应产生式的左部符号而得到的，则称为规范归约。规范归约 是最右推导（规范推导）的逆过程。

3 例：考虑文法G(E)：E→E +T |T T→T*F | F F→i| (E) 并假定输入串为（i+i)*i，考察自下而上的分析过程。

4 分析过程图表： 步骤 分析栈 输入串 动作 # (i+i)*i# 移进 #( i+i)*i# 移进 #(i +i)*i# 归约 #(F +i)*i# 归约 #(T +i)*i# 归约 #(E +i)*i# 移进 #(E+ i)*i# 移进 #(E+i )*i# 归约 #(E+F )*i# 归约 步骤 分析栈 输入串 动作 #(E+T )*i# 归约 #(E )*i# 移进 #(E) *i# 归约 #F *i# 归约 #T *i# 移进 #T* i# 移进 #T*i # 归约 #T*F # 归约 #T # 归约 #E # 接受 栈上的候选式不一定是句柄。例如，在第14步对栈顶为T，它是E的一候选式，但它不是句柄，不能归约成E。判定候选式是极为简单的事情，但判定句柄就不那么容易。而不同的自底向上方法给出不同的判定方法。 自下而上方法包括四个动作： 移进：把输入流的头符读到分析栈中。 归约：把分析栈顶的句柄归约为一非终极符。 接受：分析成功。 报错：处理错误。

5 例：考虑文法G(E)：E→E +T |T T→T*F | F F→i| (E) 是否是算符文法？
5.2 算符优先分析 首先规定文法符号之间的优先关系和结合性质，然后再利用这种关系，通过比较两个相邻的符号之间的优先顺序来确定可归约串。 算符文法：任何产生式的右部都不含两个相继的非终结符 例：考虑文法G(E)：E→E +T |T T→T*F | F F→i| (E) 是否是算符文法？

6 优先关系： b… 终结符ab的三种优先关系： 当且仅当存在形如下面的产生式U→ … ab…或U→ … aQb…
当且仅当存在形如下面的产生式U→…aW…的生产式， 且有 W b… 当且仅当存在形如U→…V b…的产生式 且有 V …a 或V … aQ a b

7 例：考虑文法G(E)：E→E +T |T T→T*F | F F→i| (E) 是否是算符优先文法？
如果一个算符文法的任何终结符对至多只满足三种关系之一，称为算符优先文法。 例：考虑文法G(E)：E→E +T |T T→T*F | F F→i| (E) 是否是算符优先文法？ 验证终结符对之间的优先关系(p90优先表)

8 如何从文法构造优先关系表？ 检查文法产生式的每个候选，可找出所有满足 的终结符对。 如何找出满足 和 终结符对？
检查文法产生式的每个候选，可找出所有满足 的终结符对。 如何找出满足 和 终结符对？ 对每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P) FIRSTVT(P)= LASTVT(P) = 检查每个产生式候选，若形为...aP...,则对任何b∈FIRSTVT(P)， 我们有a b。 若形为...Pb...,则对任何a∈LASTVT(P)， 我们有a b。 对表达式文法的非终结符构造FIRSTVT和LASTVT并建立优先关系表

9 算符优先分析算法 素短语：这样的一个短语，它至少含一个终结符，不含比自身更小的素短语。 最左素短语：句型最左边的素短语。
定理：算符优先文法的句型#N1a1N2a2...NnanNn+1#的最左素短语是满足如下条件的最左子串Njaj...NiaiNi+1 aj-1 aj aj+1 ... ai ai+1

10 优先函数 利用两个函数f和g，对每个终结符θ，映射为两个数f(θ)和g(θ)，使得： 若θ1 θ2则f(θ1)< g(θ2)
有的关系表不存在优先函数！ 对于存在优先函数的关系表，如何构造优先函数？ 请自学p94~95优先函数的构造方法。

11 5.3 LR 分析法 1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技术。
在分析的每一步，只须根据分析栈中当前已移进和归约出的 全部文法符号，并至多再向前查看K个输入符号，就能确定 相当于某一产生式右部符号的句柄是否已在分析栈的顶部形 成。从而也就可以确定所应采取的分析动作（是移进输入符号 还是按某产生式进行归约）。 例：#X1X2…Xi… Xn Xn+1Xn+2…Xn+kXn+k+1…# 栈顶 当前扫描到Xn+1,向前查看k个符号，来确定是把 Xn+1移进栈，还是把Xi…Xn作为句柄进行归约。 1） 要归约时，则根据某产生式U→XiXi+1…Xn进行归约： #X1X2…Xi-1UXn+1Xn+2…Xn+k…#

12 2） 要移进时，即把Xn+1进栈，并读下一符号： #X1X2…Xi…XnXn+1 Xn+2…Xn+k…#
在栈中 当前扫描符 栈顶 LR(0) 表示在每一步分析时都不用向前输入符号 LR(1) 表示在每一步分析时都向前看一个输入符号来决定当 前的动作。 SLR(1) 表示简单的LR(1)，即只在动作不唯一的地方向前看一 个符号，在动作唯一时则不向前看输入符号。

13 5.3.1 LR分析概论 # … ai a1 总 控 程 序 ACTION 表 GOTO 一 .LR分析器的逻辑结构及工作过程
输入串 # … ai a1 Sp→ X1 S1 S0 ┋ Xm Sm 总 控 程 序 输出 ACTION 表 GOTO 其中S栈为状态栈 X栈为符号栈 栈

14 所有LR分析器的总控程序大同小异,只有分析表各不相同。
三种不同的分析表 规范LR分析表构造法。用此法构造的分析表功能最强而且也适合于很多文法，但实现代价比较高。 简单LR(即SLR)分析表构造法。这是一种比较容易实现的方法。但SLR分析表的功能太弱，而且对某些文法可能根本就构造不出相应的SLR分析表。 向前LR（即LALR）分析表构造法。这种方法构造的分析表功能介于规范LR分析表SLR分析表之间。这种表适用于绝大多数程序语言的文法。而且也可以设法有效的实现。

15 二、LR 分析器的分析过程如下： 1.首先将初始状态 S0及句子的左界限#分别压入状态栈和符号栈中。 2.设在分析中的某一步，分析栈及余留的输入串为如下格局： ↓ S0S1… Sm ai ai+1…an #X1… Xm ↑ ↑ 则用栈顶状态Sm和当前扫描符 ai组成符号对（ Sm, ai)去查 分析动作表，根据ACTION[Sm, ai]的指示完成相应的分析动作。 表中每一表元素所规定的动作仅能是下列四种动作之一： （1） ACTION[Sm, ai]= Sm+1 （移进） 表明句柄尚未在栈顶形成，此时正期待移进输入符号以便形成 句柄。故将当前的输入符号和表元素Sm+1分别压入栈中，有 S0S1 S2 … Sm Sm ai+1 ai+2 …an # # X1 X2 … Xm ai ↑ ↑ ↓

16 （2） ACTION[Sm, ai]= Rj (归约）
表明此时应按文法的第j个产生式A→ Xm-k+1Xm-k+2 …Xm 进行归约。即栈顶符号串Xm-k+1Xm-k+2 …Xm已成为当前句型的句 柄。所谓按第j个产生式归约，就是将分析栈中从顶向下的k个符 号退栈，然后将文法符号A压入符号栈中。此时分析的格局为： ↓ S0S1… Sm-k ai ai+1…an # # X1… Xm-k A ↑ ↑ 然后以（ Sm-k,A)去查状态转移表，设GOTO[Sm-k,A]= Sl ,则将此新状态压入状态栈中，则有如下格局： ↓ S0S1… Sm-k Sl ai ai+1…an # # X1… Xm-k A ↑ ↑

17 （3） ACTION[Sm, ai]=acc （接受）
表明当前的输入串已被成功地分析完毕，应停止分析器的工作。 （4） ACTION[Sm, ai]=ERROR（空白）。 表明当前的输入串中含有错误，也应终止当前的分析工作。转出错处理。 3. 重复上述第2步的工作，直到分析栈顶出现“接受状态”或“出错状态”为止。对接受状态，分析栈的格局为： ↓ S0 Sα # # Z ↑ ↑ 其中Z为文法开始符号 Sα为使ACTION[Sα ，#]=acc的 唯一状态（接受状态）

18 5.3.2 LR(0) 分析表的构造 为了给出构造LR(0)分析表的算法，给出一些术语： 1、规范句型的活前缀
前缀：一个符号串的前缀是指该串的任意首部（包括）。 例如 abc的前缀有： ,a,ab,abc abcd的前缀有：,a,ab,abc,abcd 由此可知，对于符号串 而言，其前缀的数量为+1。 例：有文法G[S]:S→aAcBe[1] A→b[2] 这里在每条产生式后加上了产生 A→Ab[3] 式的序号[i]当进行推导时把序号 B→d[4] 带上，以便说明问题。 对输入串abbcde进行推导如下（最右推导）： S  aAcBe[1]  aAcd[4]e[1]  aAb[3]cd[4]e[1]  ab[2]b[3]cd[4]e[1] 由此可知，abbcde是该文法的句子。

19 S→aAcBe[1] A→b[2] A→Ab[3] B→d[4] 最左归约为： ab[2]b[3]cd[4]e[1] 用[2]式归约  aAb[3]cd[4]e[1] [3]  aAcd[4]e[1] [4]  aAcBe[1] [1] 其中表示归约符  S 归约时，归约前和归约后的被归约部分与剩余部分合起来仅构成文法的规范句型，而用哪个产生式归约仅取决于当前句型的前面部分；X1X2…Xn[p] 其中Xi为文法的符号，[p]为第p个产生式序号。 如上例中每次归约前句型的前面部分为： ab[2] aAb[3] aAcd[4] aAcBe[1] 我们把规范句型的这种前端部分的串称为活前缀。实际上，它们恰好是符号栈栈顶形成句柄时符号栈中的内容。

20 活前缀：是指规范句型的一个前缀，这种前缀不含句柄之
后的任何符号。 这是因为一旦句型的句柄在符号栈顶形成，将会立即被归约 之故。所以我们将把规范句型具有上述性质（即不含句柄之后的 任何符号）的前缀称之为活前缀。 对各规范句型有前缀： ab[2]b[3]cd[4]e[1] ,a,ab aAb[3]cd[4]e[1] ,a,aA,aAb aAcd[4]e[1] ,a,aA,aAc,aAcd aAcBe[1] ,a,aA,aAc,aAcB,aAcBe

21 在规范归约过程中的任何时候只要已分析过的部分即在符号栈中的符号串为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。
活前缀定义： 由此可形式地定义活前缀如下： 定义 ：若S * A 是 文法G中的一个规范推导， 如果符号串是的前缀，则称是G的一个活前缀。 其中 S为 文法开始符号。 R

22 2、LR（0）项目 活前缀与句柄间的关系： （1）活前缀中已含有句柄的全部符号（句柄的最后符号就是 活前缀的最后符号）。 （2）活前缀中只含有句柄的前部分符号（句柄的最左子串 为活前缀的最右子串）。 （3）活前缀中全然不包含句柄的任何符号。 第一种情况表明：此时某一产生式A→β的右部β已出现在符号 栈顶，因此此时相应的分析动作应当是用此产生式进行归约。 第二种情况表明：形如A→12的产生式的 右部子串已在符号栈栈顶，如1，正期待着从余留的输入串中看到能由β推出的 符号串，即期待2 进栈以便能进行归约。故此时分析动作是“移进”当前输入符号。 第三种情况则意味着：期望从余留输入串中能看到由某产生式 A→的右部，即所代表的符号串(即句柄) 。所以此时分析的动作也是读输入符进符号栈。

23 在产生式的右部相应位置上加一个圆点“.”，来指示识别位置，标明在“.”前的部分已被识别。
如上述三种情况，可分别标注为：A→β.； A→1 .2 ; A→. 。 右部某位置上标有圆点的产生式称为LR(0)项目(item)。 不同的LR(0)项目，反映了分析过程中符号栈顶的不同情况。 例如：产生式S→aAcBe对应有六个项目。 [0] S→.aAcBe [1] S→a.AcBe [2] S→aA.cBe [3] S→aAc.Be [4] S→aAcB.e [5] S→aAcBe.

24 每个项目的含义与圆点的位置有关。 圆点左边的子串表示在分析过程的某一时刻用该产生式归约时句柄中已识别过的部分，圆点右边的子串表示待识别的部分。 文法的全部LR(0)项目将是构造识别它的所有活前缀的有穷自动机的基础。

25 3、LR(0)项目的分类： G'：(0)S'→S (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 例：考虑文法G[S]=({S,A,B}, {a,b,c,d},P,S),构造其分析表： 其中P: (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 求该文法的项目集规范族C： 在上述文法中引入一个新的开始符号S',且将S' →S作为第0个产生式添加到文法G中，得到G的拓广文法G'。显然L(G')=L(G)，则对于文法G'，其LR(0)项目为： 1) S' →.S ) S' → S ) S→.A ) S→A . 5) S→.B ) S→B ) A→.aAb ) A→a .Ab 9) A→aA .b 10) A→aAb ) A→.c ) A→c . 13) B→.aBd 14) B→a .Bd ) B→aB .d ) B→aBd . 17)B→.d ) B→d .

26 LR(0)项目分类 A→. 因为它表明右部符号串已出现在栈顶，此时相应的分析动作应当是按此产生式进行归约，此种项目称为归约项目。 S‘ → S. 称为接受项目。 对于拓广文法而言，接受项目是唯一的。 A→. Xβ 的项目（其中 可以是 ），当X为终结符时，相应的分析动作应将当前的输入符号移入栈中，故我们将此种项目称为移进项目。 当X为非终结符时，期待着从余留的输入符中进行归约后而得到X，此类项目称为待约项目。

27 把终结符和非终结符都可看成一个有限自动机的输入符号，每把一个符号进栈相当于已识别过该符号，而状态进行转换（到下一状态），当识别到可归前缀时相当于栈顶已形成了句柄，则认为到达了识别句柄的终态。
4、构造识别活前缀的DFA DFA中的中每一个状态由若干个LR(0)项目所组成的集合（称为项目集）来表示。

28 举例：构造识别前缀的DFA 用I0表示这个DFA的初态， 将项目S‘→.S列入项目集I0。 将项目S→.A和S→.B加入I0中。 将A→.aAb和A→.c和B→.aBb, B→.d加入I0中。 项目集I0将由如下项目组成： I0 : S'→.S, S→.A, S→.B, A→.aAb, A→.c, B→.aBd, B→.d S'→.S称为项目集I0的基本项目，从基本项目出发构造项目集I0的过程，可用closure({S'→.S})表示。

29 1）I中的每一个项目都属于closure(I);
Closure(I)=I∪{A→.A→∈G∧K→  .A∈closure(I)∧∈V*∧∈V*} 构造closure(I)的算法： 1）I中的每一个项目都属于closure(I); 2）若形如K→.A的项目属于I，且A→是文法的一个产生式，任何形如A→.的项目也应加到closure(I)中 3）重复上述过程，直至不再有新的项目加入到closure(I)中为止。 如何确定从I0可能转移到的下一状态？ 若I0中有项目K→ .A，从输入串识别出A后，进入下一状态。设此状态为Ii ，显然Ii中必含有形如K→A .的项目，称为K→ .A的后继项目。 后继项目组成集合J，则J中的每个项目都是项目集Ii的基本项目，有： Ii =closure(J)

30 定义状态转移函数：GO(I,A)=closure(J)
其中，I是当前状态，A为文法符号，J是I中所有形如K→.A 的项目之后继项目K→A.所组成的集合，而closure(J)就是项目 集I（即状态I)关于符号A的后继项目集（即后继状态）。 GO(I,A)=closure({所有形如[K→A .]的项目[K→ .A]∈I}) 对于上例，有： I1 =GO(I0,S)=closure({S'→S.}) I1 : S'→S.; I2 =GO(I0,A)=closure({S→A.}) I2 :S→A.; I3 =GO(I0,B)=closure({S→B.}) I3 : S→B.; I4 =GO(I0,a)=closure({A→a.Ab,B→a.Bd})

31 I4 : A→a.Ab B→a.Bd A→.aAb B→.aBd A→.c B→.d I5=GO(I0,c)=closure({A→c.}) I5 : A→c. I6=GO(I0,d)=closure({B→d.}) I6 :B→d. I1, I2,I3,I5,I6均无后继项目集，仅I4有后继项目集： I7 =GO(I4,A)=closure({A→aA.b})={A→aA.b} I9 =GO(I4,B)=closure({B→aB.d})={B→aB.d} 此外，还有： GO(I4,a)=closure({A→a.Ab, B→a.Bd})= I4 GO(I4,c)=closure({A→c.})= I5 GO(I4,d)=closure({B→d.})= I6 这些项目集均不产生新的项目集。另外还有:

32 I8 =GO(I7,b)=closure({A→aAb.})={A→aAb.}
I10 =GO(I9,b)=closure({B→aBd.})={B→aBd.} I8 ， I10也后继项目集。 G[S‘]的全部项目集即为I0～ I10 。 将这些项目集的全体称为文法G[S']的LR(0)项目集规范族，并记为C=(I0, I1,…, I10) 识别文法G[S']的全部活前缀的DFA为 M=(C,V,GO, I0,Z) 其中C—M的状态集，即文法G[S']的LR(0)项目集规范族I0～ I10 V— M的字母表，即V={S',S,A,B,a,b,c,d}； GO—M的状态转换函数，即上面定义的状态转移函数GO； I0—M的唯一初态； Z—M的终态集， ZC为规范族中所有含有归约项目的 那些项目集。

33 DFA: S I0 : S'→.S I1 :S'→S. I2 :S→A. I8 :A → aAb. I3 :S→B. b A
A→.c B→.aBd B→.d I1 :S'→S. I2 :S→A. I3 :S→B. I4 :A→a.Ab B→a.Bd I8 :A → aAb. I7 :A → aA.b I9 :B → aB.d I10 :B → aBd. I5 :A→c. I6 :B→d. A B d b c a S

34 4、LR(0)分析表的构造 要求每一个项目集中的的诸项目不出现下列的情况： （1）移进项目和归约项目并存，即存在移进—归约冲突； （2）多个归约项目并存，即存在归约—归约冲突。 如果一个文法G满足上述条件，也就是它的每个LR(0)项目集中都不含有冲突的项目，则称G为LR(0)文法。 只有当一个文法是LR(0)文法时，才能对它构造不含冲突动作的LR(0)分析表。

35 构造LR(0)分析表的算法为： (1)对于每一项目集Ii中形如A→.X的项目，且有GO(Ii,X)=Ij, 若X为一终结符号 a 时，则置ACTION[i,a]=Sj; 若X为一非终结符号时，则置GOTO[i,X]=j (2)若Ii中有归约项目A→. ,设A→为文法第j个产生式，则对文法的任何终结符和“#”（均记为a）置ACTION[i,a]=Rj

36 (3)若接受项目S'→S .属于Ii ,则置ACTION[i,#]=acc。
(4)在分析表中,凡不能按上述规则填入信息的元素,均置为“出错”。 如上例可构造分析表为： ACTION GOTO a b c d # S A B S S5 S Acc R1 R1 R1 R1 R1 R2 R2 R2 R2 R2 S S5 S R4 R4 R4 R4 R4 R6 R6 R6 R6 R6 S8 R3 R3 R3 R3 R3 S10 10 R5 R R5 R5 R5

37 5、LR(0)分析器的工作过程 根据输入串当前符号a和分析栈栈顶状态i查找分析表应采取的动作： 1）若ACTION[i,a]=Sj, a∈VT,则把a移进符号栈，j移进状态栈。 2）若ACTION[i,a]=Rj，a∈VT或#，则用第j个产生式归约。并将两个栈的指针减去K(其中K为第j 个产生式右部的串长度），并把产生式的左部符号A压入符号栈，同时用符号对（ Si-k,A)去查GOTO表（其中Si-k为状态栈当前栈顶元素，若GOTO[Si-k,A]=j,则j压入状态栈，使得两个栈内的元素一样多。 3）若ACTION[i,a]=Acc,（此时a应为“#”号），则表明分析成功，结束分析。 4）若ACTION[i,a]=空白，转出错处理。

38 SLR分析表的构造 大多数程序设计语言的文法不是LR(0)文法。 对LR(0)规范族中有冲突的项目集（状态）用向前查 看一个（输入）符号的办法进行处理，以解决冲突。即为SLR(1)。 假定有一个LR(0)规范族中含有如下项目集(状态)I: I={X→.b,A→., B→.}其中,,,为符号串，b∈VT, I中含有移进—归约和归约—归约冲突。 只要FOLLOW(A)和FOLLOW(B)互不相交，且都不包含b,即： FOLLOW(A)∩FOLLOW(B)=φ FOLLOW(A)∩{b}=φ FOLLOW(B)∩{b}=φ

39 当状态I面临某输入符号a时，则动作为： 1）若a = b,则移进。 2）若a ∈ FOLLOW(A),则用产生式A→归约。 3）若a ∈ FOLLOW(B),则用产生式B→归约。 一般地，对于LR(0)规范族的一个项目集I可能含有多个移进项目和多个归约项目，我们可假设项目集I中有m个移进项目： A1→1. b11, A2→ 2. b22, …, Am→ m. bmm;同时含 有n个归约项目：B1→1. , B2→ 2. ,…, Bn→ n. ,只要集合 {b1, b2,…bm}和FOLLOW(B1),FOLLOW(B2),…,FOLLOW(Bn) 两两交集都为空，则我们仍可用上述归则来解决冲突： 1）若a∈{b1, b2,…,bm},则移进。 2）若a∈FOLLOW(Bi),i=1,…,n,则用Bi→ i进行归约。 3）此外，则报错。

40 SLR分析表的构造方法 (1)对于每一项目集Ii中形如A.X的项目，且有GO(Ii,X)=Ij, 若X为一终结符号a时，则置ACTION[I,a]=S; 若X为一非终结符号时，则仅置GOTO[i,X]=j； (2')若归约项目A→.属于Ii,设A→为文法第j个行产生式，则 对任何属于FOLLOW(A)的输入符号a,置ACTION[i,a]=Rj； (3)若接受项目S' → S.属于Ii ,则置ACTION[i,#]=acc。 (4) 在分析表,凡不能按上述规则填入信息的元素,均置为“出错”。

41 例： 表达式文法G[E],构造其LR(0)项目规范簇和SLR(1)分析表。 G[E]: E→E+TT T→T*FF F→(E)  i
解：1、拓广文法为G'[S'] : (0) S'→E E→E+T E→T T→T*F T→F F→(E) F→i

42 2、再求识别G'的全部活前缀的DFA： I0: S'→.E E→.E+T GO(I0,E)=I1 E→.T T→.T*F GO(I0,T)=I2 T→.F GO(I0,F)=I3 F→.(E) GO(I0,( )=I4 I1: S'→E. E→E.+T GO(I1,+)=I6 I2: E→T. T→T.*F GO(I2,*)=I7 I3: T→F.

43 I4: F→(.E) E→.E+T GO(I4,E)=I8 E→.T T→.T*F GO(I4,F)=I2 T→.F GO(I4,F)=I3 F→.(E) GO(I4,( )=I4 F→.i GO(I4,i)=I5 I7: T→T*.F GO(I7,F)=I10 F→.(E) GO(I7,( )=I4 F→.i GO(I7,i )=I5 I8: F→(E.) GO(I8,) )=I11 E→E.+T GO(I8,+)=I6 I9: E→E+T. T→T.*F GO(I9,)=I7 I5: F→i. I10: T→T*F. I6: E→E+.T T→.T*F GO(I6,T)=I9 T→.F GO(I6,F)=I3 F→.(E) GO(I6,( )=I4 F→.i GO(I6,i)=I5 I11: F→(E).

44 DFA i * I0: S'→.E E→ . E+T E→ . T T→ . T*F T→ . F F→ .(E) F→ . i
I2: E→T T→T . *F I5: F→i . I1: S'→E . E→E . +T I3: T→F . I4: F→(. E) I7: T→T* . F F →. i I6: E→E+ . T I8: F→(E .) I11: F→(E) . I9: E→E+T . T→T . *F I10: T→T*F . i * E F ( T + )

45 3、解决冲突 I1， I2， I9中有移进-归约冲突。 FOLLOW(S')= {#} FOLLOW(E)= {+，)，#}
FOLLOW(T)= {+，*，)，#} FOLLOW(F)= {+，*，)，#} 在I1中，由于FOLLOW(S‘)={#).而S’→E.是唯一的接受项目，所以当且仅当遇到句子的结束符“#”号时才被接受,又因{#}∩{+}=φ，故I1中的冲突可解决。 对于I2,因FOLLOW(E)={+,),#}∩{*}=φ,因此当面临输入符号为“+”，“ ）”或“#”号时，则用产生式E→T归约。当面临输入符为“*”时，则移进；其它情况则报错。 对于I9, 当面临输入符号为“+”，“）”或“#”时，则用产生式E→E+T归约；当面临输入符号为“*”时，则移进，其余情况报错。 演示Figure5.5LRDFA

46 4、构造SLR(1)分析表 对于上述三个冲突项目等均可用SLR(1)方法解决冲突。因此该 文法是SLR(1)文法。我们可造成其相应的SLR(1)分析表为： i * （ ） # E T F S S S acc R2 S R R2 R4 R R R4 S S R R R R6 S S S S S S11 R S R R1 R R R R3 R R R R5

47 规范LR分析表的构造 SLR(1)方法：若状态k含有A→. ，若a∈FOLLOW(A)，则用A→归约 演示Figure5.9LRDFA i=*i 状态2移进还是归约？ 为什么‘=’∈FOLLOW(R)，却不能归约？ S=>L=R =>*R=R 输入符号为=时，若把L归约为R,必须推导出 R=...，这是不可能的。 可见，SLR(1)方法：若状态k含有A→. ，若a∈FOLLOW(A)，则用A→归约，失于粗糙。

48 规范LR分析表的构造 LR(1)项目 (A→. β，x)表示： 在栈顶，输入串头部可由βx导出。 LR(1)状态 LR(1)项目的集合。 Closure(I)= repeat for any item(A→. Xβ，z) in I for any production X →γ for any w∈FIRST(βz) I←I∪{X → . γ, w} until I does not change GO (I,X)= J ←{} for any item(A→. Xβ，z) in I add (A→X . β，z) to J return Closure(J) 初态 Closure((S’→.S，#) )

49 LR(1)项目集和GO函数的例子 S b B a a I0:S’ →.S，# S’ →.BB，# B →.aB，a/b B →.b，a/b
I2:S →B.B，# B →.aB，# B →.b，# I3: B →a . B，a/b I4: B →b . ，a/b I8: B →aB . ，a/b I7: B →b . ，# I5: S→BB . ，# I6: B →a . B，# I9: B →aB . ，# S b B a a (0)S’→S (1) B→aB (2) S→BB(3) B→b

50 5.3.5 LALR分析表的构造 演示Figure5_10LR1DFA(aab#和aabab#)，观察状态4和状态7的区别 同心项目集：除去搜索符之外都相同的LR(1)项目集 合并同心项目集不会产生新的移进-归约冲突 合并同心项目集，如果没有归约-归约冲突，则为LALR(1)文法。 演示Table5.6LALRDFA(aab#和aabab#)，观察LALR和LR(1)对正确的句子和有错误的输入串的分析

51 5.3.6 二义文法的应用 演示ERYIWENFAdfa I1的移进-归约冲突SLR方法可以解决 I7的移进-归约冲突用优先级和结合性解决

52 5.3.7 LR分析中的错误处理 演示LRErrorHandling 缺少运算量的错误i+# 右括号不匹配的错误i*i)# 缺少运算符的错误（ii)# 缺少右括号的错误（i+i# 多个错误

53 文法体系 非二义文法 LR(k) LL(k) 二义文法 LR(1) LL(1) LALR(1) SLR LR(0) LL(0)

54 作业：1，2，3，5，8