第05章语法分析-自底向上分析

1S.PO.P语义分析及生成中间代码程序代码生成程序代码优化程序语法分析程序词法分析程序错误处理符号表管理2第五章语法分析－自底向上分析教学目标要求明确自底向上分析方法的一般过程。掌握LR分析方法。掌握构造LR(0)、SLR(1)、LR(1)、LALR(1)分析表的方法，会使用LR分析法分析句子。35.1规范推导、规范句型和规范归约5.2自底向上分析方法的一般过程5.3LR分析方法5.4LR(0)分析器5.5SLR(1)分析器5.6LR(1)分析器5.7LALR(1)分析器5.8语法分析程序的自动生成工具－YACC教学内容4任务：按照程序语言的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成作准备。语法分析的任务词法分析器语法分析器单词符号语法树源程序输入：Token序列输出：语法成分及组成表现形式：语法树错误报告出错处理：定位、续编译5语法分析的任务

递归子程序法自顶向下

LL(1)分析法TopDown

算符优先分析法自底向上

LR(0)、SLR(1)[LR(1)、LALR]BottomUp文法产生语言自动机识别语言6第5章语法分析——自底向上分析

在自底向上的分析方法中，分析过程从输入符号串开始，通过反复查找当前句型的句柄，并使用规则，将找到的句柄归约成相应的非终结符号，直到归约到开始符号，从而为输入符号串构造一棵分析树。开始符号字符串7概念回顾推导、归约最右推导、最左归约最左推导、最右归约句型、句子规范句型短语、简单短语、句柄8概念回顾推导如：S=>AB=>=>AaBb=>=>aabb归约如：aabb=>=>AaBb=>=>AB=>S最右推导与最左归约如：S=>AB=>ABb=>Abb=>Aabb=>aabb最左推导与最右归约如：S=>AB=>AaB=>aaB=>aaBb=>aabb文法：S::=ABA::=Aa|aB::=Bb|b9概念回顾句型从识别符号推导0步或多步产生的结果可由非终结符和终结符组成句子是特殊的句型完全由终结符号组成规范句型每个句子都有规范推导10概念回顾短语、简单短语、句柄例句型：Aabb文法：S::=ABA::=Aa|aB::=Bb|bSABAaBbb短语：Aabb、Aa、bb、b简单短语：Aa、b句柄：Aa115.1规范推导、规范句型和规范归约

规范推导：最右推导规范句型：通过规范推导能够得到的句型规范归约：最左归约文法S::=ABA::=Aa|aB::=Bb|b以下哪些句型是规范句型？aabb、Ab、Aab、aBb、Abb、AaBb125.1规范推导、规范句型和规范归约例5.1，有文法G[S]：

S::=aAcBeA::=bA::=AbB::=d试分析符号串abbcde是否为该文法的句子。

方法一：推导首先，我们从文法的开始符号进行规范推导，依次使用1、4、3、2规则，就可得到符号串abbcde。规范推导过程如下：S=>aAcBe=>aAcde=>aAbcde=>abbcde13方法二：归约从符号串开始，向上归约，如果最终能够规约到文法的开始符号S，则同样可以说明该输入符号串是这个文法的句子。其归约过程如图5.1所示。ScBcAaAbdbScBcAaAbdScBcAadScBcAaS(a)b归约为A(b)Ab归约为A(c)d归约为B(d)aAcBe归约为S(e)图5.1归约过程

145.2自底向上分析方法的一般过程

基本思想从输入符号串开始，通过重复查找当前句型的“可归约串”并利用有关规则进行规约若能规约为文法的识别符号,则表示分析成功,输入符号串是文法的合法句子,否则有语法错误.15【例】G[S]:SaAcBeAbAAb Bd分析句子abbcde#16文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→dabbcde步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进A3）#abbcde#归约(A→b)4）#aAbcde#移进A5）#aAbcde#归约(A→Ab)6）#aAcde#移进7）#aAcde#移进B8）#aAcde#归约(B→d)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约SaAcBeaAcdeaAbcdeabbcde17关键：找出当前句型的“可归约串”

从自底向上分析的一般过程可看出，如何寻找或确定一个句型的句柄，是构造一个自左向右扫描、自底向上分析方法必须要解决的一个关键问题。185.3LR分析方法什么是LR(k)分析:

L：从左到右扫描

R：最右推导的逆过程（最左归约）

k：是指为了作出分析决定而向前看的输入符号的个数是一种规范归约过程LR(k)分析技术Knuth于1965年首先提出19Knuth/~knuth/《计算机程序设计艺术第1卷基本算法》

98元《计算机程序设计艺术第2卷半数值算法》98元《计算机程序设计艺术第3卷排序与查找》98元205.3.1LR分析器逻辑结构LR分析器有一个给定的输入符号串，一个分析栈和一个有穷的控制系统。#…

…a2a1输入符号串:分析栈:S0#......SnA有穷的控制系统：分析表(动作、转换)总控程序215.3.2LR分析表的构成动作部分,ACTION表示当前状态面临输入符号时应采取的动作;状态转换部分，GOTO表示当前状态面临文法符号时应转向的下一个状态;。分析器的各个状态文法的终结符号及右界符#文法的非终结符号225.3.2LR分析表的构成分析表的动作有下列四种：移进(Sn)：将输入符号aj移进符号栈，将状态n移进状态栈，输入指针指向下一个输入符号。归约(R)：当栈顶形成句柄时，按照相应的产生式U→W进行归约。若产生式右部W的长度为n，则将符号栈栈顶n个符号和状态栈栈顶n个状态出栈，然后将归约后的文法符号U移入符号栈，并根据此时状态栈顶的状态Si及符号栈顶的符号U，查GOTO表，将GOTO[Si，U]移入状态栈。235.3.2LR分析表的构成分析表的动作有下列四种：（续）接受(A)：当输入符号串到达右界符#时，且符号栈只有文法的开始符号时，则分析成功结束，接受输入符号串并结束分析。报错(E)：在状态栈的栈顶状态为Si时，如果输入符号为不应该遇到的符号时，即ACTION[Si，aj]=空白，则报错，说明输入符号串有语法错误。24例：步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进4）#aAbcde#移进6）#aAcde#移进7）#aAcde#移进9）#aAcBe#移进11）#S#接受3）#abbcde#归约(A→b)5）#aAbcde#归约(A→Ab)8）#aAcde#归约(B→d)10）#aAcBe#归约25LR分析器的关键就是构造分析表。表5.2给出了文法G：

0)S→A，1)A→(A)，2)A→a的分析表。表5.3LR分析表265.3.3LR分析过程分析开始时，栈内的初始状态为0，符号栈为#。当状态栈顶为p，当前输入指针指向的符号是a时，查分析动作表p行、a列。如果得到的动作指示ACTION[p,a]是移进Si，则将a压入符号栈，将状态i压入状态栈，然后将输入指针指向输入符号串的下一个符号；如果得到的动作指示是归约Ri，且归约产生式为B→β，则从符号栈内弹出|β|个符号，从状态栈内弹出|β|个状态，假设此时出栈后的状态栈栈顶为p，查状态转换表的p行、B列，得到下一个状态GOTO[p,B]=q，并将该后继状态q压入状态栈；如果得到的动作指示是接受，则接受输入的符号串，分析成功结束；27开始初始状态0和#入栈读符号根据栈顶状态和输入符号查分析动作表归约?移进?接受?查状态转换表新状态入状态栈

按产生式i归约

根据产生式i的右部符号的个数，符号栈和状态栈相应元素出栈

产生式i的左部符号入栈

输入符号入符号栈

状态i入状态栈读符号分析结束错误YYYNNN28例5.2，利用表5.3分析表分析符号串(a)。解：根据图5.3所示的分析流程，表5.4列出了符号串(a)的整个分析过程。S2(a)##01S3a)##(0224R2)##(a0233S5)##(A02441R1##(A)02455ACCEPT##A016295.4LR(0)分析方法拓广文法：使识别符号唯一例5.3,对文法G∶E→T|E+T|E－TT→i|(E)进行拓广。解：引入一个新的开始符号S，使得文法的开始符号所在的规则唯一。G[S]：S→EE→T|E+T|E－TT→i|(E)305.4.1活前缀和可归前缀LR(k)分析法通过活前缀来帮助确定句柄前缀：句型的任意首部如：abc的前缀有ε,a,b,ab,abc规范句型：通过规范推导（规约）得到的句型活前缀：规范句型中不含句柄右边任何符号的前缀可归前缀：含有句柄的活前缀315.4.1活前缀和可归前缀对于一个规范句型来说，其活前缀定义如下：设λβt是一个规范句型，即λβt是能用最右推导得到的句型，其中β表示句柄，t∈Vt*，如果λβ=u1u2…ur，那么称符号串u1u2…ui(其中1≤i≤r)是句型λβt的活前缀。含有句柄的活前缀u1u2…ur称为可归前缀。对一个规范句型来说，活前缀可有多个，可归前缀只有一个。32例：文法G∶E→T|E+T|E-TT→i|(E)，找规范句型E+(i-i)的活前缀和可归前缀。ET+E）E（T－ETiiE+(i-i)的语法树：活前缀为：E，E+，E+(，E+(i，可归前缀：E+(i33课堂练习文法G[E]：

E→E+T|TT→T*F|FF→(E)|i1、拓广文法？2、找规范句型:E+i*i的活前缀和可归前缀？拓广文法G[S]：

S→EE→E+T|TT→T*F|FF→(E)|i活前缀为：E，E+，E+i可归前缀：E+i34课堂练习文法G[S]：S→A

A→(A)A→a找规范句型:（a）的活前缀和可归前缀？活前缀为：（，（a可归前缀：（aSA（A）a语法树：35S2(a)##01S3a)##(0224R2)##(a0233S5)##(A02441R1##(A)02455ACCEPT##A016均为活前缀文法G[S]：S→A，A→(A)，A→a36LR分析器的工作过程逐步产生文法的规范句型活前缀的过程当栈顶形成句柄时，立即进行归约375.4.2LR(0)项目1、项目的定义对某个文法G来说，如果A→α1α2为G的一条规则，那么，对规则的右部加上一个圆点，就成为一个项目。其形式为：A→α1·α2圆点是表示项目的一种标记，也就是说，如果一条规则的右部标有圆点，那么它就是项目。因为圆点的位置不同，一条规则可以有几个项目。项目的直观意义:在分过程中的某一时刻已经规约的部分和等待规约部分385.4.2LR(0)项目【例】

文法G[S]：S→aS|b写出其所有的LR(0)项目。S→·aSS→a·SS→aS·

S→·b

S→b·395.4.2LR(0)项目【例】有文法S→E，E→T|E+T|E-T，T→i|(E)，规则S→E，有下面两个项目：

S→·E，S→E·规则E→E－T，有下面四个项目∶E→·E－T，E→E·－T，E→E－·T，E→E－T·

一个产生式对应的项目个数是右部符号长度加1产生式A→ε的项目个数只有一个，即A→·

40根据项目中点的位置和后继符号，项目分为四类：①移进项目：E→E·－T圆点后面是终结符，表示栈内是句柄的一部分，期待从输入串中移进一个符号，以形成句柄。②待约项目：E→E－·T圆点后面是非终结符的项目，表示栈内是句柄的一部分，为了形成句柄，期待从剩余的输入串中进行归约而得到Ｂ，然后才能继续分析A的右部。41③归约项目：E→E－T·④接受项目：S→E·特殊的归约项目，使用产生式S’→α进行归约，表示整个句子已经分析完毕，分析成功，也即输入串为该文法的句子。圆点在最后，表示栈顶的部分内容已构成所期望的句柄，应使用产生式A→α进行归约。422、项目有效性一个项目A→α1·α2对于某个活前缀λα1是有效的，当且仅当存在某个最右推导。

S|*=>λAt|=>

λα1·α2t

，其中t是终结符号串。43活前缀与句柄的关系①活前缀已含有句柄的全部符号表示符号栈顶已形成句柄，可以归约例：产生式：A→α，活前缀：λα，项目A→α·

对活前缀λα有效。当一个点在最后的项目对活前缀有效时，则可以进行归约，所以把点在最后的项目称为归约项目。44活前缀与句柄的关系②活前缀只含有句柄的部分符号正期待从剩余输入串中看到句柄的其余符号例：产生式：A→α１α２，活前缀：λα１，项目A→α１·α２对活前缀λα１有效。45活前缀与句柄的关系③活前缀不含有句柄的任何符号需将余流的输入符号移进例：产生式：A→α，活前缀：λ，项目A→·α

对活前缀λ有效。一般来说，活前缀与有效项目是多对多关系。46例5.5，有文法S→E，E→T|E+T|E-T，T→i|(E)，列出该文法的所有项目，并找出对活前缀E－有效的项目。解：首先列出每条规则对应的多个项目：S→E，有项目S→·E，S→E·E→T，有项目E→·T，E→T·E→E+T，有项目E→·E+T，E→E·+T，E→E+·T，E→E+T·E→E-T，有项目E→·E-T，E→E·-T，E→E-·T，E→E-T·T→i，有项目Ｔ→·i，Ｔ→i·T→(E)，有项目T→·(E)，T→(·E)，T→(E·)，T→(E)·

47例5.5，有文法S→E，E→T|E+T|E-T，T→i|(E)，列出该文法的所有项目，并找出对活前缀E－有效的项目。对活前缀E－有效的项目：E→E－·T，T→·i和T→·(E)S=>E=>E－TS=>E=>E－T=>E－iS=>E=>E－T=>E－(E)485.4.3构造识别活前缀的有穷自动机

回顾：有穷自动机——一种识别装置两种：DFA－－确定的有穷自动机NFA－－不确定的有穷自动机0Ｓ13104

Ｚ151识别1(0|1)*101的NFA49正规文法NFA正规式654312DFA最小化8750有穷自动机的输入字符：终结符和非终结符状态转换：每把一个符号进栈，就看成识别过了该符号，进行状态转换。因为LR分析时栈中始终保持是活前缀，所以有穷自动机识别过的符号串也是活前缀。终态：当识别到可归约前缀（表明在栈中形成句柄），认为到达了识别句柄的终态，执行归约5.4.3构造识别活前缀的有穷自动机515.4.3构造识别活前缀的有穷自动机有两种方法：（1）求出文法的所有项目，按一定规则构造NFA再确定化为DFA－－工作量大，不适用（2）直接构造DFA－－分析DFA状态的项目集之间、项目集内的项目之间的规律性直接构造出DFA（重点掌握）52直接构造DFA若项目集中有Y→·X，另一项目集中有Y→X·，则这两个项目集之间必有一条X弧。将一个活前缀的可能的无穷集对应到一个有穷的有效项目集上。先给出两个定义：项目集的闭包运算状态转移函数GO比较（P43）：状态集Ｐ的ε闭包状态集Ｐ的α弧转换集531、项目集的闭包运算设I为一项目集，I的闭包运算CLOSURE(I)定义如下：I中的每一个项目都属于CLOSURE(I)。如项目A→α1·Xα2属于CLOSURE(I)，且X为非终结符号，则将形式为X→·λ的项目添加到CLOSURE(I)中。重复(1)和(2)，直到CLOSURE(I)封闭为止。54例5.6，有文法：E’→E，E→E+T，E→T，T→T*F，T→F，F→(E)，F→i，设项目集I={E’→·E}，求CLOSURE(I)。解：根据闭包运算的第1条，CLOSURE(I)={E’→·E}根据第2条，E→·E+T和E→·T，加进CLOSURE(I)中：CLOSURE(I)={E’→·E，E→·E+T，E→·T}根据第3条，T→·T*F和T→·F，加进CLOSURE(I)中：CLOSURE(I)={E’→·E，E→·E+T，E→·T，T→·T*F，T→·F}将F→·(E)和F→·i，加进CLOSURE(I)中：CLOSURE(I)={E’→·E，E→·E+T，E→·T，T→·T*F，T→·F，F→·(E)，F→·i}至此，CLOSURE(I)封闭。55文法：

S'→S S→aS S→b例：I={S'→·S}closure(I)=？{S'→·S,S→·aS,S→·b}练习：I={S→a·S}closure(I)=？{S→a·S,S→·aS,S→·b}562、项目集之间的转换函数GO假设有一项目为A→α·Xβ，令X是一个字汇表中的符号，则对项目A→α·Xβ进行读X操作，结果为项目A→αX·β。设I是一个项目集,X是任一文法符号，则项目集之间的转换用GO[I,X]函数表示，定义为：GO[I,X]=CLOSURE(J)其中J={任何具有[A→αX·β]的项目|[A→α·Xβ]∈I}，即对项目集I中所有的项目进行读X操作的结果。572、项目集之间的转换函数GOCLOSURE(J)为对J进行了闭包运算得到的项目集，称为I的后继项目集。令状态I代表项目集I，状态J代表后继项目集CLOSURE(J)，用状态图表示则为：IJX58例5.7，文法：E’→E，E→E+T，E→T，T→T*F，T→F，F→(E)，F→i，有项目集I={E’→E·，E→E·+T},

求GO[I，+]解：在I中挑出点后是+的项目有：E→E·+T,将点移到+后面得J={E→E+·T}对J进行闭包运算得CLOSURE(J)={E→E+·T,T→·F,T→·T*F,F→·(E),F→·i}GO(I,+)={E→E+·T,T→·F,T→·T*F,F→·(E),F→·i}用状态图表示为：+I：E’→E·E→E·+TJ:E→E+·T,T→·FT→·T*F,F→·(E),F→·i59文法：

S'→S S→aS S→b求GO(I,b)=?GO(I,b)=closure({S→b·})={S→b·}求GO(I,a)=?GO(I,a)=closure({S→a·S})={S→a·S,S→·aS,S→·b}例：I={S'→·S,S→·aS,S→·b

}603、举例说识别活前缀的有穷自动机的构造方法直接构造DFA的思想从S‘→·S开始，得到DFA的初态项目集然后通过状态转换函数GO求其所有的后继项目集61【例】文法：0)S→A1)A→(A)2)A→a1、构造初态项目集C0C0＝closure（｛S→·A｝）＝｛S→·A，A→·(A)，A→·a｝2、通过状态转换函数GO求其所有的后继项目集0:

S→·AA→·(A)A→·a1:

S→A·2:

A→(·A)A→·(A)A→·a

3:

A→a·A(a62R1

A→(A)·5GO[4，)]=5A→(A·)4R2

A→a·3GO[2，A]=4GO[2，(]=2GO[2，a]=3A→(·A)A→·(A)A→·a2ACCEPTS→A·1GO[0，A]=1GO[0，(]=2GO[0，a]=3S→·AA→·(A)A→·a0转换函数项目集状态3、继续上述后继项目构造过程，直到没有新的项目集产生。630:S→·AA→·(A)A→·a1:S→A·2:A→(·A)A→·(A)A→·a

3:A→a·A(a图5.8识别活前缀的有穷自动机

4:A→(A·)5:A→(A)·A)(a644、识别活前缀的有穷自动机构造算法给定一文法G，该文法的开始符号为S。C={C0,C1,…,Cn},其中C0是开始项目集，C称为LR(0)项目集规范族。构造DFA的算法：C={closure({S’→·S})};do{for(C中的每个项目集I和每个符号X）

if(GO(I,X)非空,且不在C中)

把GO(I,X)加入C中;}while(C增大)returnC;655.4.4LR(0)分析表的构造1)若项目A→α·aβ∈Ci且GO[i，a]=Cj，其中a为终结符，置ACTION[i，a]=“把状态j和符号a移进栈”，简记为“Sj”；

2)若项目A→α·∈Ci，则对于任何输入符号a或结束符#，置ACTION[i，a]=“用产生式A→α进行归约”，简记为“Rj”(假定A→α是文法G’的第j条产生式)；

3)若项目S→δ·∈Ci，则置ACTION[i，#]=“接收”，简记为‘A’；

4)若GO[i，A]=Cj，A为非终结符，则置GOTO[i，A]=j；

5)分析表中凡不能用规则①-④添入信息的单元为空或均置上ERROR，表示有错。66R1

A→(A)·5GO[4，)]=5A→(A·)4R2

A→a·3GO[2，A]=4GO[2，(]=2GO[2，a]=3A→(·A)A→·(A)A→·a2ACCEPTS→A·1GO[0，A]=1GO[0，(]=2GO[0，a]=3S→·AA→·(A)A→·a0转换函数项目集状态（1）若A→α·aβ∈Ci，且GO[i，a]=Cj(a∈VT)，则置ACTION[i，a]=Sj；（2）若A→α·∈Ci，则对任意终结符a或#，置ACTION[i，a]=Rj；（3）若项目S→δ·∈Ci，则置ACTION[i，#]=ACC；（4）若GO[i，A]=Cj，A为非终结符，则置GOTO[i，A]=j；（5）凡不能用规则①-④添入信息的单元为空或均置ERROR。项目集规范族R1R1R1R15S54R2R2R2R234S3S22ACC11S3S20A#a)(GOTOACTION状态LR(0)分析表67【例】文法G[S′]：（1）S′→S（2）S→aS|b构造识别G所有活前缀的DFA。解题步骤：（1）写出文法G的拓广文法G′；（2）利用函数closure和GO，求出相应的项目集规范族C；（3）根据项目集和转换函数，构造识别文法G′所有活前缀的DFA；68【例】文法G[S′]：（1）S′→S（2）S→aS|b构造G的LR(0)分析表。解题步骤：（1）写出文法G的拓广文法G′；（2）利用函数closure和GO，求出相应的项目集规范族C；（3）根据项目集和转换函数，构造LR(0)分析表。695.4.5LR(0)分析器的工作过程若ACTION[S，a]=Sj，a为终结符，则把a移入符号栈，状态j移入状态栈。若ACTION[S，a]=Rj，a为终结符或#号，则用第j个产生式归约。设k为第j个产生式右部的符号串长度，将符号栈和状态栈顶的k个元素出栈，将产生式左部符号入符号栈。若ACTION[S，#]=ACC，则为接受，表示分析成功。若GOTO[S，A]=j，A为非终结符号并且是符号栈的栈顶，表示前一个动作是归约，A是归约后移入符号栈的非终结符，则将状态j移入状态栈。若ACTION[S，a]=空白，则转入错误处理。70文法：0)S→A1)A→(A)2)A→a符号串“((a))”的分析过程如下：4R1)##((A)022456S5)##(A02471R1##(A)02458ACC##A019S5))##((A022454R2))##((a02234S3a))##((0223S2(a))##(022S2((a))##01GOTOACTION输入符号串符号栈状态栈步骤715.4.6LR(0)文法定义如果一个文法G的识别活前缀的DFA的每个状态不存在任何冲突项目：（1）移进项目和归约项目并存；（2）多个归约项目并存。则称G是一个LR(0)文法。C0={S→·A,A→·(A),A→·a}：移进项目和待约项目共存。C2={A→(·A),A→·(A),A→·a}：移进项目和待约项目共存。{S→E·,E→E·+T}：移进项目和归约项目并存。{S→E·,E→E+E·}：多个归约项目并存。72【例】文法G[S]：0)S→A1)A→ab2)A→a判断文法G[S]是否为LR(0)文法。构造项目集规范族：移进项目和归约项目并存所以，该文法不是LR(0)文法。73LR(0)分析表：多重定义745.5SLR(1)分析法若LR(0)项目集规范族中有项目集Ck含移进-归约或归约-归约冲突，Ck={X→α·bβ,Aγ·，Bδ·}若FOLLOW(A)∩FOLLOW(B)=FOLLOW(A)∩{b}=FOLLOW(B)∩{b}=则解决冲突的SLR(1)技术：对于归约项目向前查看一个符号a若a=b，则移进a。若a∈FOLLOW(A)，则用产生式A→γ归约。若a∈FOLLOW(B)，则用产生式B→δ归约。其它报错当文法的LR(0)项目集规范族中存在移进-归约冲突或归约-归约冲突，但能用SLR(1)技术解决冲突称此文法为SLR(1)文法。75SLR解决方法FOLLOW(A)＝｛#｝FOLLOW(A)∩{b}=

表中每个入口不含多重定义765.5.2SLR(1)分析表的构造1、若A→α·aβ∈Ci且GO[i，a]=Cj，其中a为终结符，置ACTION[i，a]=“把状态j和符号a移进栈”，简记为“Sj”；2、若项目A→α·∈Ci，则对a(或#)∈FOLLOW(A)，置ACTION[i，a]=“用产生式A→α进行归约”，简记为“Rj”(假定A→α是文法G’的第j条产生式)；3、若项目S’→S·∈Ci，则置ACTION[i，#]＝“ACCEPT”；4、若GO[i，A]=Cj，A为非终结符，则置GOTO[i，A]＝j；5、分析表中凡不能用规则1-4添入信息的元素为空或均置上ERROR。77【例】文法G[S]：0)S→A1)A→ab2)A→aFOLLOW(A)＝｛#｝FOLLOW(A)∩{b}=

78SLR分析法构造SLR分析表的步骤如下：1)文法拓广；2)构造LR(0)项目集规范族；3)求出非终结符的FOLLOW集；4)由构造SLR分析表的算法构造SLR分析表79例5.11文法：0)S→E1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)6)F→i构造LR(0)项目集规范族：80求出非终结符的FOLLOW集：文法：0)S→E1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)6)F→iFOLLOW(S)＝｛#｝FOLLOW(E)＝｛＋，），#｝FOLLOW(T)＝｛*，＋，），#｝FOLLOW(F)＝｛*，＋，），#｝81构造SLR分析表：FOLLOW(S)＝｛#｝FOLLOW(E)＝｛＋，），#｝FOLLOW(T)＝｛*，＋，），#｝FOLLOW(F)＝｛*，＋，），#｝82符号串“i*(i+i)”的分析过程：8R2+i)##T*(T0274292R4+i)##T*(F027438

S5i+i)##T*(027463R6+i)##T*(i027457

S4(i+i)##T*0275

S7*(i+i)##T0242R4*(i+i)##F0333R6*(i+i)##i052

S5i*(i+i)##01GOTOACTION输入符号串符号栈状态栈步骤

S11)##T*(E027481510R5##T*(E)0274811168R1)##T*(E+T0274859149R4)##T*(E+F0274863133R6)##T*(E+i027486512

S5i)##T*(E+02748611

S6+i)##T*(E027481083课后习题2证明下面文法是SLR(1)文法，但不是LR(0)文法。S→AA→Ab|bBaB→aAc|a|aAb思路：1、构造LR(0)项目集规范族，看是否有归约－归约冲突及归约－移进冲突。如有，则不是LR(0)文法，转步骤2。2、求出非终结符的FOLLOW集，构造SLR(1)分析表，如表中无重定义，则证明该文法是SLR(1)文法，但不是LR(0)文法。84项目集Ci含有项目A→α·，在i下，若a∈FOLLOW(A)，则用A→α归约SLR分析法存在的问题因为FOLLOW(A)是指所有可能推导出的句型中，可以跟随在A后的终结符号集但LR分析法的归约应该仅对规范句型中跟随在A后的终结符有效这种归约可能导致归约扩大化？？？？？85LR(1)分析、LALR(1)分析通过寻找新的向前搜索符来解决A→α·Bβ∈I，则B→·γ∈IFOLLOW(B)FIRST(β)用FIRST(β)代替FOLLOW(B)作为用产生式B→γ进行归约的超前符号信息5.6LR(1)分析器86归约－归约冲突考虑如下拓广文法：0)G→S1)S→E=E2)S→i3)E→T4)E→E+T5)T→i6)T→T*i

项目集规范族如下表：该文法不是SLR(1)文法FOLLOW(S)={#}FOLLOW(T)={#,+,=,*}8702134567891011i0SET=+T*iEi+iTi*图5.9识别活前缀的自动机FOLLOW(S)={#}FOLLOW(T)={#,+,=,*}R5面临的输入符号集是:T→i

{+,=,*}R2面临的输入符号集是: S→i{#}把即将面临的输入符号集称为超前信息885.6.1LR(1)项目LR(1)项目定义：

一个LR(1)项目的形式为[A→α·β，u]其中第一部分是一个LR(0)项目，即带有圆点的产生式A→α·β，称为LR(1)项目的核；第二部分u是一个超前扫描字符，且u∈Vt∪{ε}。对于一个LR(1)项目(A→α·β，u)，如果存在最右推导 S|=*>λAt|=>λαβt其中λα是活前缀，且u是t的第一个符号或者是#，那么说这个LR(1)项目对活前缀λα有效。89例5.11有文法如下：0)G→S1)S→E=E2)S→i3)E→T4)E→E+T5)T→i6)T→T*i考虑哪些项目对活前缀E=T有效最右推导G|=*>E=T+i|=>E=T*i+i，所以项目[T→T·*i，+]对活前缀E=T是有效的。最右推导G|=*>E=T*i|=>E=T*i*i,所以项目[T→T·*i，*]对活前缀E=T是有效的。具有相同的核的项目,可以组合成复合项目。因此上两项目复合成：[T→T·*i,+:*]。复合项目一般形式：

[A→α·β,α1:α2:…:αm]

905.6.2LR(1)项目集规范族构造算法

1、LR(1)项目集的闭包运算

设I为一LR(1)项目集，LR(1)闭包(closure)运算CLOSURE(I)定义如下：

1)I中的任何LR(1)项目都属于CLOSURE(I)。

2)如项目[A→α·Xβ，a]属于CLOSURE(I)，且X为非终结符号，则所有形为[X→·δ，b]的项目均添加到CLOSURE(I)中，其中，b∈FIRST(βa)。

3)重复(1)和(2),直到CLOSURE(I)封闭为止。

91例5.12有文法如下：0)G→S1)S→E=E2)S→i3)E→T4)E→E+T5)T→i6)T→T*i对[E→·T,=]进行闭包运算因为有产生式T→i,所以[T→·i,=]也属于该项目集。有产生式T→T*i,所以[T→·T*i,=]也是该项目集成员。项目[T→·T*i,=]的闭包将产生两个新项目[T→·i,*]和[T→·T*i,*]。最后对[E→.T,=]进行闭包运算得到的项目集为：CLOSURE（[E→·T,=]）＝{[E→·T,=]、[T→·i,=]、[T→.T*i,=]、[T→.i,*]、[T→.T*i,*]}

925.6.2LR(1)项目集规范族构造算法2、LR(1)项目集转换函数GO

设I是一个项目集，X是任一文法符号，则GO[I，X]定义为：GO[I，X]=CLOSURE(J)其中J={任何具有[A→αX·β,a]的项目|[A→α·Xβ,a]∈I},