《自底向上的解读课件》由会员分享，可在线阅读，更多相关《自底向上的解读课件（103页珍藏版）》请在金锄头文库上搜索。
1、School of Computer Science & Technology Harbin Institute of Technology重点：重点：自底向上分析的基本思想，算符优先分析法的基本思想，自底向上分析的基本思想，算符优先分析法的基本思想，简单算符优先分析法。简单算符优先分析法。LR LR 分析器的基本构造思想，分析器的基本构造思想，LRLR分析算法，分析算法，规范句型活前缀及其识别器规范句型活前缀及其识别器DFADFA，LR(0)LR(0)分析表的构造，分析表的构造，SLR(1)SLR(1)分析表的构造分析表的构造, LR(1), LR(1)分析表的构造。分析表的构造。难点：难点
2、：求求FIRSTOP FIRSTOP 和和LASTOPLASTOP，算符优先关系的确定，算符优先分，算符优先关系的确定，算符优先分析表的构造，素短语与最左素短语的概念。规范句型活前缀，析表的构造，素短语与最左素短语的概念。规范句型活前缀，LR(0)LR(0)项目集闭包与项目集规范族，它们与句柄识别的关系，活前项目集闭包与项目集规范族，它们与句柄识别的关系，活前缀与句柄的关系缀与句柄的关系, LR(1), LR(1)项目集闭包与项目集规范族。项目集闭包与项目集规范族。 第五章第五章 自底向上的自底向上的语法分析语法分析2024/9/212第第5章章自底向上的语法分析自底向上的语法分析 5.1 自
3、底向上的语法分析概述自底向上的语法分析概述5.2 算符优先分析法算符优先分析法5.3 LR分析法分析法5.4 语法分析程序的自动生成工具语法分析程序的自动生成工具Yacc5.5 本章小结本章小结2024/9/2135.1 自底向上的语法分析概述自底向上的语法分析概述n思想思想n从输入串出发，反复利用产生式进行归约，如果从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。则输入串有语法错误。n核心核心n寻找句型中的当前归约对象寻找句型中的当前归约对象“句柄句柄”进行归约进行归约, ,用不同的方法寻找
4、句柄，就可获得不同的分析方法用不同的方法寻找句柄，就可获得不同的分析方法2024/9/214例例5.1 一个简单的归约过程一个简单的归约过程n设文法设文法G为：为：SaABe AAbc|b Bd句子分析：句子分析：句子分析：句子分析： a a a ab b b bbcdebcdebcdebcdea a a aAbcAbcAbcAbcdedededeaAaAaAaAd d d de e e e aABeaABeaABeaABe S S S S语法树的形成过程语法树的形成过程语法树的形成过程语法树的形成过程2024/9/215语法分析树的生成演示语法分析树的生成演示a b b c d eAABSA
5、bAbAAbcAAbcBdBdSaAcBeSaAcBe2024/9/2165.1.1 移进移进-归约分析归约分析n系统框架系统框架n采用表驱动的方式实现采用表驱动的方式实现n输入缓冲区：保存输入符号串输入缓冲区：保存输入符号串n分析栈：保存语法符号分析栈：保存语法符号已经得到的那部已经得到的那部分分析结果分分析结果n控制程序：控制分析过程，输出分析结果控制程序：控制分析过程，输出分析结果产生式序列产生式序列n格局：格局：栈栈+ +输入缓冲区剩余内容输入缓冲区剩余内容= =“句型句型”2024/9/217移进移进-归约语法分析器的总体结构归约语法分析器的总体结构 id +id + id id i
6、d #id # #移进移进-归约归约控制程序控制程序输出输出输出输出产生式序列产生式序列产生式序列产生式序列栈内容栈内容+ +输入缓冲区内容输入缓冲区内容 # # “当前句型当前句型 ” # #栈栈输入缓冲区输入缓冲区 分析表分析表分析表分析表MM2024/9/218与与LL(1)的体系结构比较的体系结构比较 输入缓冲区输入缓冲区( (符号序列符号序列) )栈栈控制程序控制程序P132预测分析表预测分析表M M输出输出输出输出产生式序列产生式序列产生式序列产生式序列2024/9/219移进移进-归约分析的工作过程归约分析的工作过程n系统运行系统运行n开始格局开始格局n栈：栈：# #；输入缓冲区
7、：；输入缓冲区：w#w#n存放已经分析出来的结果存放已经分析出来的结果, ,并将读入的符号送入栈，并将读入的符号送入栈，一旦句柄在栈顶形成，就将其弹出进行归约，并一旦句柄在栈顶形成，就将其弹出进行归约，并将结果压入栈将结果压入栈n问题：系统如何发现句柄在栈顶形成？问题：系统如何发现句柄在栈顶形成？n正常结束正常结束: : 栈中为栈中为 #S#S，输入缓冲区只有，输入缓冲区只有 # #2024/9/2110输出结果表示：输出结果表示：用产生式序列表示语法分析树用产生式序列表示语法分析树E idid + id * id EEEEEE idE idE E * EE E + E例例5.2 EE+E|E
8、*E|(E)|id2024/9/2111动作动作动作动作 栈栈栈栈 输入缓冲区输入缓冲区输入缓冲区输入缓冲区1) # id1) # id1) # id1) # id1 1 1 1+id+id+id+id2 2 2 2*id*id*id*id3 3 3 3# # # #id + id * id + id * idid2) 2) 2) 2) 移进移进移进移进 #id#id#id#id1 1 1 1 +id +id +id +id2 2 2 2*id*id*id*id3 3 3 3# # # #例例5.2 分析过程分析过程3) 3) 3) 3) 归约归约归约归约 Eid #E +idEid #E +
9、idEid #E +idEid #E +id2 2 2 2*id*id*id*id3 3 3 3# # # #E E4) 4) 4) 4) 移进移进移进移进 #E+ id#E+ id#E+ id#E+ id2 2 2 2*id*id*id*id3 3 3 3# # # #5) 5) 5) 5) 移进移进移进移进 #E+id#E+id#E+id#E+id2 2 2 2 *id *id *id *id3 3 3 3# # # #6) 6) 6) 6) 归约归约归约归约 Eid #E+E *idEid #E+E *idEid #E+E *idEid #E+E *id3 3 3 3# # # #E E
10、E E7) 7) 7) 7) 移进移进移进移进 #E+E* id#E+E* id#E+E* id#E+E* id3 3 3 3# # # #8) 8) 8) 8) 移进移进移进移进 #E+E*id#E+E*id#E+E*id#E+E*id3 3 3 3 # # # #9) 9) 9) 9) 归约归约归约归约 Eid #E+E*E #Eid #E+E*E #Eid #E+E*E #Eid #E+E*E #10) 10) 10) 10) 归约归约归约归约 EE*E #E+E #EE*E #E+E #EE*E #E+E #EE*E #E+E #E E11) 11) 11) 11) 归约归约归约归约
11、EE+E #E #EE+E #E #EE+E #E #EE+E #E #12) 12) 12) 12) 接受接受接受接受E E2024/9/2112分析器的四种动作分析器的四种动作1) 1) 移进：将下一输入符号移入栈移进：将下一输入符号移入栈2) 2) 归约：用产生式左侧的非终结符替换栈顶归约：用产生式左侧的非终结符替换栈顶的句柄（某产生式右部）的句柄（某产生式右部）3) 3) 接受：分析成功接受：分析成功4) 4) 出错：出错处理出错：出错处理？决定移进和归约的依据是什么？决定移进和归约的依据是什么回头看是回头看是否可以找到答案否可以找到答案2024/9/2113移进移进-归约分析中的问题
12、归约分析中的问题n1) 1) 移进归约冲突移进归约冲突 n例例5.25.2中的中的 6)6)可以移进可以移进 * * 或按产生式或按产生式EE+EEE+E归约归约 2024/9/211412) 12) 12) 12) 接受接受接受接受1) # id1) # id1) # id1) # id1 1 1 1+id+id+id+id2 2 2 2*id*id*id*id3 3 3 3# # # #id + id * id + id * idid2) 2) 2) 2) 移进移进移进移进 #id#id#id#id1 1 1 1 +id +id +id +id2 2 2 2*id*id*id*id3 3
13、3 3# # # #例例5.25.2分析过程分析过程3) 3) 3) 3) 归约归约归约归约 EidEidEidEid #E +id #E +id #E +id #E +id2 2 2 2*id*id*id*id3 3 3 3# # # #E E4) 4) 4) 4) 移进移进移进移进 #E+ id#E+ id#E+ id#E+ id2 2 2 2*id*id*id*id3 3 3 3# # # #5) 5) 5) 5) 移进移进移进移进 #E+id#E+id#E+id#E+id2 2 2 2 *id *id *id *id3 3 3 3# # # #6) 6) 6) 6) 归约归约归约归约
14、EidEidEidEid #E+E *id #E+E *id #E+E *id #E+E *id3 3 3 3# # # #E EE E7) 7) 7) 7) 移进移进移进移进 #E+E* id#E+E* id#E+E* id#E+E* id3 3 3 3# # # #8) 8) 8) 8) 移进移进移进移进 #E+E*id#E+E*id#E+E*id#E+E*id3 3 3 3 # # # #9) 9) 9) 9) 归约归约归约归约 EidEidEidEid #E+E*E # #E+E*E # #E+E*E # #E+E*E #10) 10) 10) 10) 归约归约归约归约 EE*E #E
15、+E #EE*E #E+E #EE*E #E+E #EE*E #E+E #E E11) 11) 11) 11) 归约归约归约归约 EE+E #E #EE+E #E #EE+E #E #EE+E #E #E E动作动作动作动作 栈栈栈栈 输入缓冲区输入缓冲区输入缓冲区输入缓冲区2024/9/2115移进移进-归约分析中的问题归约分析中的问题1) 1) 移进归约冲突移进归约冲突 n例例5.25.2中的中的 6)6)可以移进可以移进 * * 或按产生式或按产生式EE+EEE+E归约归约 2) 2) 归约归约冲突归约归约冲突 n存在两个可用的产生式存在两个可用的产生式n各种分析方法处理冲突的方法不同各
16、种分析方法处理冲突的方法不同n如何识别句柄？如何识别句柄？n如何保证找到的直接短语是最左的如何保证找到的直接短语是最左的? ?利用栈利用栈n如何确定句柄的开始处与结束处？如何确定句柄的开始处与结束处？2024/9/21165.1.2 优先法优先法n根据归约的先后次序为句型中相邻的文法符号根据归约的先后次序为句型中相邻的文法符号规定优先关系规定优先关系n句柄内相邻符号同时归约，是同优先的句柄内相邻符号同时归约，是同优先的n句柄两端符号的优先级要高于句柄外与之相邻的句柄两端符号的优先级要高于句柄外与之相邻的符号符号na1ai-1 aiai+1aj-1aj aj+1ann定义了这种优先关系之后，语法
17、分析程序就可定义了这种优先关系之后，语法分析程序就可以通过以通过ai-1 ai和和aj aj+1这两个关系来确定句柄的这两个关系来确定句柄的头和尾了头和尾了 2024/9/2117根据句柄的识别状态（根据句柄的识别状态（句柄是逐步形成的句柄是逐步形成的）用状态来描述不同时刻下形成的那部分句柄用状态来描述不同时刻下形成的那部分句柄因为句柄是产生式的右部，可用产生式来表示句因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态柄的不同识别状态例如：例如： SbBB可分解为如下识别状态可分解为如下识别状态S.bBB 移进移进bSbB.B 等待归约出等待归约出BSb.BB 等待归约出等待归约出BS
18、bBB. 归约归约采用这种方法，语法分析程序根据当前的分析状采用这种方法，语法分析程序根据当前的分析状态就可以确定句柄的头和尾，并进行正确的归约。态就可以确定句柄的头和尾，并进行正确的归约。 5.1.3 状态法状态法2024/9/21185.2 算符优先分析法算符优先分析法n算术表达式分析的启示算术表达式分析的启示n算符优先关系的直观意义算符优先关系的直观意义n+ * + + * + 的优先级低于的优先级低于 * *n( ) ( ( ) ( 的优先级等于的优先级等于 ) )n+ + + + + + 的优先级高于的优先级高于 + +n方法方法n将句型中的终结符号当作将句型中的终结符号当作“算符算
19、符”，借助于算，借助于算符之间的优先关系确定句柄符之间的优先关系确定句柄2024/9/2119算术表达式文法的再分析算术表达式文法的再分析nEE+EnEE-EnEE*EnEE/E nE(E) nEidnEE+T| E-T| T TT*F| T/F| F F(E)|id从如何去掉二义性从如何去掉二义性从如何去掉二义性从如何去掉二义性, ,看看看看对算符优先级的利用对算符优先级的利用对算符优先级的利用对算符优先级的利用句型的特征：句型的特征：句型的特征：句型的特征：( (E E+ +E E)*()*(E E- -E E)/ )/E E/ /E E+ +E E* *E E* *E E2024/9/2
20、120算符文法算符文法n如果文法如果文法G=（ V，T，P，S）中不存在形如）中不存在形如ABC 的产生式，则称之为算符文法的产生式，则称之为算符文法(OG Operator Grammar)即：如果文法即：如果文法 中不存在具有相邻非终结符的中不存在具有相邻非终结符的产生式，则称为算符文法。产生式，则称为算符文法。2024/9/2121定义定义5.1 假设假设G是一个不含是一个不含-产生式的文法，产生式的文法，A、B和和C均是均是G的语法变量，的语法变量，G的任何一对终结符的任何一对终结符a和和b之间之间的的优先关系定义优先关系定义为：为： ab，当且仅当文法，当且仅当文法G中含有形如中含有
21、形如Aab或或AaBb的产生式；的产生式； a b，当且仅当文法，当且仅当文法G中含有形如中含有形如AaB的产生的产生式，而且式，而且Bb或或BCb； a b，当且仅当文法，当且仅当文法G中含有形如中含有形如ABb的产生的产生式，而且式，而且Ba或或BaC； a与与b无关系，当且仅当无关系，当且仅当a与与b在在G的任何句型中都不的任何句型中都不相邻。相邻。问题：什么是算符优先文法？问题：什么是算符优先文法？5.2.1 算符优先文法算符优先文法2024/9/21225.2.1 算符优先文法算符优先文法n设设G=（V，T，P，S）为）为OG，如果，如果 a,bVT, ab, a b, a b 至多
22、有一个成立，则称至多有一个成立，则称之为算符优先文法之为算符优先文法(OPG Operator Precedence Grammar) 在无在无产生式的算符文法中，如果任意两产生式的算符文法中，如果任意两个终结符之间至多有一种优先关系，则称为个终结符之间至多有一种优先关系，则称为算符优先文法。算符优先文法。2024/9/21235.2.2 算符优先矩阵的构造算符优先矩阵的构造n优先关系的确定n根据优先关系的定义nab AaBP且(B+b或者B+Cb)n需要求出非终结符B派生出的第一个终结符集nab ABbP且(B+a或者B+aC)n需要求出非终结符B派生出的最后一个终结符集n设G=（V，T，P
23、，S）为OG，则定义nFIRSTOP(A)=b|A+b或者A+Bb,bT,B VnLASTOP(A)=b|A+b或者A+bB,bT,B V2024/9/2124算符优先关系矩阵的构造算符优先关系矩阵的构造nAab ; AaBb, 则则abnAaB,则对则对 bFIRSTOP(B),a bnABb,则对则对 aLASTOP(B), a bnif ABP,then FIRSTOP(B) FIRSTOP(A)nif ABP,then LASTOP(B) LASTOP(A)n问题：编程求问题：编程求FIRSTOP、LASTOP2024/9/2125算符优先关系矩阵的构造算符优先关系矩阵的构造nA AX
24、X1 1X X2 2X Xn n如果如果X Xi iX Xi+1i+1TTTT则：则： X Xi iX Xi+1i+1如果如果X Xi iX Xi+1i+1X Xi+2i+2TVTTVT则：则：X Xi iX Xi+2i+2如果如果X Xi iX Xi+1i+1TVTV则：则： a aFIRSTOP(XFIRSTOP(Xi+1i+1) )，X Xi iaa如果如果X Xi iX Xi+1i+1VTVT则：则： a aLASTOP(XLASTOP(Xi i) )， a aX Xi+1i+12024/9/2126例例 5.6 表达式文法的算符优先关系表达式文法的算符优先关系 acc+ +- -*
25、*/ /( () )idid# #+ +- -* */ /（）idid# # 2024/9/21275.2.3 算符优先分析算法算符优先分析算法n 原理原理n识别句柄并归约识别句柄并归约n各种优先关系存放在算符优先分析表中各种优先关系存放在算符优先分析表中n利用利用识别句柄尾，利用识别句柄尾，利用识别句柄头，分析栈存识别句柄头，分析栈存放已识别部分，比较栈顶和下一输入符号的关系，如放已识别部分，比较栈顶和下一输入符号的关系，如果是句柄尾，则沿栈顶向下寻找句柄头，找到后弹出果是句柄尾，则沿栈顶向下寻找句柄头，找到后弹出句柄，归约为非终结符。句柄，归约为非终结符。2024/9/2128例例5.7
26、EE+T|E-T|T TT*F|T/F|F F(E)|id，试利用算符优先分析法对试利用算符优先分析法对id+id进行分析进行分析步骤步骤栈栈输入串输入串优先关系优先关系动作动作1#id1+id2#2# id1+id2# id1移进移进id13#F+id2# id1 +用用Fid归约归约4#F+id2# 移进移进+5#F+ id2# 移进移进id26#F+F#+ id2 #用用Fid归约归约7#E# + #用用EE+T归约归约2024/9/2129问题问题n有时未归约真正的句柄（有时未归约真正的句柄（F）n不是严格的最左归约不是严格的最左归约n归约的符号串有时与产生式右部不同归约的符号串有时与
27、产生式右部不同n仍能正确识别句子的原因仍能正确识别句子的原因nOPG未定义非终结符之间的优先关系，不能未定义非终结符之间的优先关系，不能识别由单非终结符组成的句柄识别由单非终结符组成的句柄n定义算符优先分析过程识别的定义算符优先分析过程识别的“句柄句柄”为为最最左素短语左素短语LPP（Leftmost Prime Phase）2024/9/2130素短语与最左素短语素短语与最左素短语n什么是短语？当前我们要找什么样的短语什么是短语？当前我们要找什么样的短语？至少有一个算符至少有一个算符n* and A+，至少含一个终结符，至少含一个终结符，且不含更小的含终结符的短语且不含更小的含终结符的短语,
28、则称则称是句型是句型的相对于变量的相对于变量A的素短语的素短语(Prime Phrase)n句型的至少含一个终结符且不含其它素短句型的至少含一个终结符且不含其它素短语的短语语的短语2024/9/2131例例nEE+T|T TT*F|F F(E)|id句型句型 T+T*F+i 的短语有的短语有T T*F i T+T*F T+T*F+i其中的素短语为其中的素短语为T*F iT*F为最左素短语，是被归约的对象为最左素短语，是被归约的对象问题：按照文法问题：按照文法EE+E|E*E|(E)|id，求求i+E*i+i的短语和素短语的短语和素短语 E E E E T T T TE E F FT + T *
29、 F + iT + T * F + i2024/9/2132文法：文法：EE+E|E*E E(E)|id句型句型i+E*i+i的短语的短语 E E E E E EE E E E E Ei + E * i + ii + E * i + i问题：归约过程中如何发现问题：归约过程中如何发现问题：归约过程中如何发现问题：归约过程中如何发现“ “中间句型中间句型中间句型中间句型” ” 的最左素短语？的最左素短语？的最左素短语？的最左素短语？i i E*i i i+E*i i+E*i+i其中的素短语为其中的素短语为i i i2024/9/2133素短语与最左素短语素短语与最左素短语设句型的一般形式为设句型
30、的一般形式为#N1a1 N2a2 Nnan # (Ni V,ai VT）它的最左素短语是满足下列条件的最左子串它的最左素短语是满足下列条件的最左子串Niai Ni+1ai+1 Njaj Nj+1其中：其中：ai-1 ai,， aiai+1aj-1aj ， aj aj+12024/9/2134算符优先分析的实现算符优先分析的实现n系统组成系统组成n移进归约分析器移进归约分析器 + + 优先关系表优先关系表n分析算法分析算法n参照输入串、优先关系表，完成一系列归约，生参照输入串、优先关系表，完成一系列归约，生成语法分析树成语法分析树输出产生式输出产生式2024/9/2135算符优先分析算法算符优先
31、分析算法 算法算法5.3 算符优先分析算法。算符优先分析算法。输入：文法输入：文法G=(V, T, P, S)，输入字符串，输入字符串w和优先关系表和优先关系表;输出：如果输出：如果w是一个句子则输出一个分析树架子，否则指出错误是一个句子则输出一个分析树架子，否则指出错误;步骤：步骤：begin S1:=#; i:=1;repeat 将下一输入符号读入将下一输入符号读入R; if Si T then j:=i else j:=i-1; while Sj R do beginrepeat Q:=Sj;if Sj-1 T then j:=j-1 else j:=j-2until Sj Q;将将Sj
32、+1Si归约为归约为N; i:=j+1;Si:=N end; if Sj R or SjR then begin i:=i+1; Si:=R end else erroruntil i=2 and R=# end;2024/9/2136id+id*id 的分析过程的分析过程id + id * id #算符优先分析算符优先分析控制器控制器E idE idE idE idE idE idE E * EE E * EE E + EE E + E算符优先关系表算符优先关系表# id#+#id+#+#*+#id*+#*+#+#2024/9/21375.2.4 优先函数优先函数n为了节省存储空间（为了节省
33、存储空间（n2 2n）和便于执行比较运算，）和便于执行比较运算，用两个优先函数用两个优先函数f和和g，它们是从终结符号到整数的映，它们是从终结符号到整数的映射。对于终结符号射。对于终结符号a和和b选择选择f和和g，使之满足：，使之满足：n f(a)g(b)，如果如果a b。n损失损失n错误检测能力降低错误检测能力降低n如：如：id id不存在，但不存在，但f(id)g(id)可比较可比较2024/9/2138表表5.2 对应的优先函数：对应的优先函数：1) 构造优先函数的算法不是唯一的。构造优先函数的算法不是唯一的。2) 存在一组优先函数，那就存在无穷组优存在一组优先函数，那就存在无穷组优先函
34、数。先函数。+-*/()id#f22440440g113350502024/9/2139优先函数的构造优先函数的构造算法算法5.4 优先函数的构造。优先函数的构造。输入：算符优先矩阵输入：算符优先矩阵;输出：表示输入矩阵的优先函数，或指出其不存在输出：表示输入矩阵的优先函数，或指出其不存在;步骤：步骤：1. 对对 a T#，建立以，建立以fa和和ga为标记的顶点；为标记的顶点；2. 对对 a, b T#，若，若a b或者或者ab，则从，则从fa至至gb画一条有向画一条有向弧；若弧；若a b或者或者ab，则从，则从gb至至fa画一条有向弧；画一条有向弧；3. 如果构造的有向图中有环路，则说明不存
35、在优先函数；如如果构造的有向图中有环路，则说明不存在优先函数；如果没有环路，则对果没有环路，则对 a T#，将，将f(a)设为从设为从fa开始的最长开始的最长路经的长度，将路经的长度，将g(a)设为从设为从ga开始的最长路经的长度。开始的最长路经的长度。 2024/9/2140例例5.10 Ges :EE+T|T TT*F|F Fid+*id#+*id#+*id#f2440g1350根据根据Ges的优先矩阵建立的的优先矩阵建立的有向图和优先函数有向图和优先函数 Ges的优先矩阵的优先矩阵2024/9/21415.2.5 算符优先分析的出错处理算符优先分析的出错处理 栈顶的终结符号和当前输入符号
36、之间不存在任何优栈顶的终结符号和当前输入符号之间不存在任何优先关系；先关系； 发现被发现被“归约对象归约对象”，但该，但该“归约对象归约对象”不能满足不能满足归约要求。归约要求。n对于第对于第种情况，为了进行错误恢复，必须修改栈、种情况，为了进行错误恢复，必须修改栈、输入或两者都修改。输入或两者都修改。n对于优先矩阵中的每个空白项，必须指定一个出错对于优先矩阵中的每个空白项，必须指定一个出错处理程序，而且同一程序可用在多个地方。处理程序，而且同一程序可用在多个地方。n对于第对于第种情况，由于找不到与种情况，由于找不到与“归约对象归约对象”匹配匹配的产生式右部，分析器可以继续将这些符号弹出栈，的
37、产生式右部，分析器可以继续将这些符号弹出栈，而不执行任何语义动作。而不执行任何语义动作。2024/9/2142算符优先分析法小结算符优先分析法小结n优点优点n简单、效率高简单、效率高n能够处理部分二义性文法能够处理部分二义性文法n缺点缺点n文法书写限制大文法书写限制大强调算符之间的优先关系的强调算符之间的优先关系的唯一性唯一性n占用内存空间大占用内存空间大n不规范、存在查不到的语法错误不规范、存在查不到的语法错误n算法在发现最左素短语的尾时，需要回头寻找对算法在发现最左素短语的尾时，需要回头寻找对应的头应的头2024/9/21435.3 LR分析法分析法 5.3.1 LR分析算法分析算法nLR
38、(kLR(k) )分析法可分析分析法可分析LR(kLR(k) )文法产生的语言文法产生的语言nL L ：从左到右扫描输入符号：从左到右扫描输入符号nR R ：最右推导对应的最左归约：最右推导对应的最左归约nk k ：超前读入：超前读入k k个符号，以便确定归约用的产生式个符号，以便确定归约用的产生式n使用语言的文法描述内涵解决句柄的识别问题，从语言的使用语言的文法描述内涵解决句柄的识别问题，从语言的形式形式描述描述入手，为语法分析器的入手，为语法分析器的自动生成自动生成提供了前提和基础提供了前提和基础n分析器根据当前的状态，并至多向前查看分析器根据当前的状态，并至多向前查看k k个输入符号，个
39、输入符号，就可以确定是否找到了句柄，如果找到了句柄，则按相就可以确定是否找到了句柄，如果找到了句柄，则按相应的产生式归约，如果未找到句柄则移进输入符号，并应的产生式归约，如果未找到句柄则移进输入符号，并进入相应的状态进入相应的状态2024/9/2144LR语法分析器的总体结构语法分析器的总体结构a1 ai an #LR分析程序分析程序动作表动作表action转移表转移表gotogoto产生式产生式产生式产生式序列序列序列序列状态状态/符号栈符号栈输入缓冲区输入缓冲区分析表分析表SmSm-1S1S0XmXm-1X1#2024/9/2145LR 分析表分析表：actions,a；gotos,X 动
40、作表动作表动作表动作表 转移表转移表转移表转移表状态状态状态状态 action action action action gotogotogotogoto a b # S B a b # S B a b # S B a b # S B 0 s3 s4 1 2 0 s3 s4 1 2 0 s3 s4 1 2 0 s3 s4 1 2 1 acc 1 acc 1 acc 1 acc 2 s3 s4 5 2 s3 s4 5 2 s3 s4 5 2 s3 s4 5 3 s3 s4 6 3 s3 s4 6 3 s3 s4 6 3 s3 s4 6 4 r3 4 r3 4 r3 4 r3 r3r3r3r3 r
41、3r3r3r3 5 5 5 5 r1 r1 r1 r1 r1r1r1r1 r1r1r1r1 6 r2 6 r2 6 r2 6 r2 r2r2r2r2 r2r2r2r2 LR(0)、SLR(1)、LR(1)、LALR(1)将以不同的原则将以不同的原则构造这张分析表构造这张分析表约定：约定：sn:将符号将符号a、状、状态态n压入栈压入栈rn:用第用第n个产生个产生式进行归约式进行归约2024/9/2146LR分析器的工作过程分析器的工作过程n书上的下式（格局）书上的下式（格局）(s0s1sm，X1X2 Xm ， aiai+1an#)n在这里表示为在这里表示为s0s1sm#X1Xm aiai+1an
42、#2024/9/2147LR分析器的工作过程分析器的工作过程n n1. 初始化初始化s0# a1a2an# 对应对应对应对应“ “句型句型句型句型” ” a a1 1a a2 2aan nn n2. 在一般情况下，假设分析器的格局如下：在一般情况下，假设分析器的格局如下：s0s1 sm#X1Xm aiai+1an n# # 对应对应对应对应“ “句型句型句型句型” ” X X1 1XXmma ai ia ai+1i+1aan nnIf actionsm,ai= si(shift i) then 格局变为格局变为s0s1 sm i#X1Xmai ai+1an#2024/9/2148s0s1sm#
43、X1Xm aiai+1an#If actionsm,ai=acc then 分析成功分析成功If actionsm,ai=err then 出现语法错出现语法错If actionsm,ai= ri(Reduce i) then 表示用第表示用第i个产个产生式生式AXm-(k-1)Xm进行进行归约，格局归约，格局变为变为s0s1 sm-k#X1Xm-kA aiai+1an#查查goto表表，如果如果gotosm-k,A=i then 格局格局变为变为s0s1 sm-k i#X1Xm-kA aiai+1an#2024/9/2149LR分析算法分析算法 算法算法5.5 LR分析算法。分析算法。输入：
44、文法输入：文法G的的LR分析表和输入串分析表和输入串w;输出：如果输出：如果w L(G)，则输出，则输出w的自底向上分析，否则报错的自底向上分析，否则报错;步骤：步骤：1将将#和初始状态和初始状态S0压入栈，将压入栈，将w#放入输入缓冲区；放入输入缓冲区；2令输入指针令输入指针ip指向指向w#的第一个符号；的第一个符号；3令令S是栈顶状态，是栈顶状态，a是是ip所指向的符号所指向的符号;4repeat5if actionS,a=Si then /* Si表示移进表示移进a并转入状态并转入状态i*/6 begin7 把符号把符号a和状态和状态i先后压入栈；先后压入栈；8 令令ip指向下一输入符号
45、指向下一输入符号9 end2024/9/2150 10elseif actionS,a=rkthen /* ri表示按第表示按第k个个产生式产生式A归约归约 */11 begin12 从栈顶弹出从栈顶弹出2*|个符号；个符号；13 令令S是现在的栈顶状态；是现在的栈顶状态；14 把把A和和gotoS,A先后压入栈中；先后压入栈中；15 输出产生式输出产生式 A16 end17elseif actionS,a= acc then18 return19else20 error();2024/9/2151例例5.12文法文法1) SBB2) BaB3) Bb分析表分析表 动作表动作表动作表动作表 转
46、移表转移表转移表转移表状态状态状态状态 action action action action gotogotogotogoto a b # S B a b # S B a b # S B a b # S B 0 s3 s4 1 2 0 s3 s4 1 2 0 s3 s4 1 2 0 s3 s4 1 2 1 acc 1 acc 1 acc 1 acc 2 s3 s4 5 2 s3 s4 5 2 s3 s4 5 2 s3 s4 5 3 s3 s4 6 3 s3 s4 6 3 s3 s4 6 3 s3 s4 6 4 r3 4 r3 4 r3 4 r3 r3r3r3r3 r3r3r3r3 5 r1
47、5 r1 5 r1 5 r1 r1r1r1r1 r1r1r1r1 6 r2 6 r2 6 r2 6 r2 r2r2r2r2 r2r2r2r2 请跟随讲请跟随讲解，快速解，快速抄下右侧抄下右侧的表格！的表格！2024/9/2152bab 的分析过程的分析过程: :1) SBB1) SBB2) 2) BaBBaB3) 3) BbBb0236#BaB # action(6,#)=r20202#BB # goto(2,B)=5#BB # goto(2,B)=5025025#BB # action(5,#)=r1 #BB # action(5,#)=r1 0 0#S # goto(0,S)=1 #S #
48、 goto(0,S)=1 0101#S # action(1,#)=acc#S # action(1,#)=acc栈栈 输入输入 动作说明动作说明0# bab# action(0,b)=s404#b ab# action(4,a)=r30#B ab# goto(0,B)=202#B ab# action(2,a)=s3023#Ba b# action(3,b)=s40234#Bab # action(4,#)=r3023#BaB # goto(3,B)=62024/9/2153规范句型活前缀规范句型活前缀n分析栈中内容分析栈中内容+剩余输入符号剩余输入符号=规范句型规范句型n分析栈中内容为某一
49、句型的前缀分析栈中内容为某一句型的前缀n来自分析栈的来自分析栈的活前缀活前缀(Active Prefix)n不含句柄右侧任意符号的规范句型的前缀不含句柄右侧任意符号的规范句型的前缀n例：例：id + id * id 的分析中的分析中n句型句型 E + id . * id 和和 E + E * . id活前缀活前缀活前缀活前缀S*rmAw rm 12w 2024/9/2154规范句型活前缀规范句型活前缀n规范归约所得到的规范句型规范归约所得到的规范句型(Canonical Sentential Form)的活前缀是出现在分析栈中的活前缀是出现在分析栈中的符号串，所以，不会出现句柄之后的任何的符号
50、串，所以，不会出现句柄之后的任何字符，而且相应的后缀正是输入串中还未处字符，而且相应的后缀正是输入串中还未处理的终结符号串。理的终结符号串。n活前缀与句柄的关系活前缀与句柄的关系n包含句柄包含句柄 A .n包含句柄的部分符号包含句柄的部分符号A 1. 2 n不含句柄的任何符号不含句柄的任何符号A. 2024/9/21555.3.2 LR(0)分析表的构造分析表的构造nLR(0)项目项目从产生式寻找归约方法从产生式寻找归约方法n右部某个位置标有园点的产生式称为相应右部某个位置标有园点的产生式称为相应文法的文法的LR(0)项目项目（Item）n例例 S.bBB SbB.B Sb.BB SbBB.n
51、归约（归约（Reduce）项目）项目: SaBB.n移进（移进（Shift）项目：）项目：S.bBBn待约项目：待约项目：Sb.BB SbB.B2024/9/2156项目的意义项目的意义n用项目表示分析的用项目表示分析的进程进程( (句柄的识别状句柄的识别状态态) )n方法：在产生式右方法：在产生式右部加一园点以分割已部加一园点以分割已获取的内容和待获取获取的内容和待获取的内容：构成句柄的内容：构成句柄b a b BBBSS B . B B . a B2024/9/2157拓广拓广(Augmented)文法文法n需要一个对需要一个对“归约成归约成S” 的表示（只有一个接受状态）的表示（只有一个
52、接受状态）n文法文法 G= (V, T, P, S)的拓广文法的拓广文法 G：nG=（V S，T，P SS，S）nS Vn对应对应S.S（分析开始）和（分析开始）和SS.（分析成功）（分析成功）n例例5.13 0) SS1) SBB2) BaB3) Bb2024/9/2158构造识别构造识别G G的所有规范句型活前的所有规范句型活前缀的缀的DFADFAn问题：如何设计能够指导分析器运行，问题：如何设计能够指导分析器运行，并且能够根据当前状态（栈顶）确定句并且能够根据当前状态（栈顶）确定句柄柄归约对象的头归约对象的头的装置的装置2024/9/2159项目集项目集 I 的闭包（的闭包（Closur
53、e）CLOSURE(I)=I B.| A .BI, BP 算法算法 J:=I;repeat J=JB.|A.BJ, BPuntil J不再扩大不再扩大项目集闭包的计算项目集闭包的计算2024/9/2160闭包之间的转移闭包之间的转移n后继项目（后继项目（Successive Item）nA.X的后继项目是的后继项目是AX.n闭包之间的转移闭包之间的转移ngo(I,X)=CLOSURE(AX.| A.XI2024/9/2161状态转移的计算状态转移的计算n确定在某状态遇到一个文法符号后的确定在某状态遇到一个文法符号后的状态转移目标状态转移目标function GO(I, X);beginJ:=;
54、for I中每个形如中每个形如A.X的项目的项目dobegin J:=JAX. end;return CLOSURE(J)end; 2024/9/2162识别拓广文法所有规范句型活前缀的识别拓广文法所有规范句型活前缀的DFAn识别文法识别文法G=（V，T，P，S）的拓广文法）的拓广文法G的所有规范句型活前缀的的所有规范句型活前缀的DFA :M=(C, VT, go, I0, C)nI0=CLOSURE(S .SnC=I0I| JC,XVT,I=go(J,X)称为称为G的的LR(0)项目集规范族项目集规范族(Canonical Collection)2024/9/2163计算计算LR(0)项目集
55、规范族项目集规范族即：分析器状态集合即：分析器状态集合beginC := closure( S.S); repeat for IC， X VT if go(I,X) & go(I,X) C then C=Cgo(I,X) until C不变化不变化end.2024/9/2164例例4-13SBBBaBBbI0:S.SS.BBB.aBB.bI I1 1: :S SS.S.SBI I2 2: :SB.BSB.BB.aBB.aBB.bB.baI I4 4: :Ba.BBa.BB.aBB.aBB.bB.bbI I3 3: :BbBb. .BI I5 5: :SBB.SBB.abBI I6 6: :Ba
56、BBaB. .ab核心项目核心项目Kernel Item2024/9/2165LR(0)分析表的构造算法分析表的构造算法算法算法5.6 LR(0)分析表的构造。分析表的构造。输入：文法输入：文法G=(V, T, P, S)的拓广文法的拓广文法G ;输出：输出：G 的的LR(0)分析表，即分析表，即action表和表和goto表表;步骤：步骤：1.令令I0= CLOSURE(S .S)，构造，构造G 的的LR(0)项目集规范族项目集规范族C= I0,I1,In2让让Ii对应状态对应状态i，I0对应状态对应状态0，0为初始状态。为初始状态。3for k=0 to n do begin if A.a
57、 Ik & a T & GO(Ik, a)=Ij then actionk,a:=Sj; if A.B Ik & B V & GO(Ik, B)=Ij then gotok,B:=j; if A. Ik & A为为G的第的第j个产生式个产生式then for a T# do actionk,a:=rj; if SS. Ik then actionk,#:=acc end;4上述上述到到步未填入信息的表项均置为步未填入信息的表项均置为error。 2024/9/2166LR(0)不是总有效的不是总有效的( S S ) 1) S A|B2) A aAc3) A a4) B bBd5) B b上下文
58、无关文法上下文无关文法不是都能用不是都能用LR(0)方法进行方法进行分析的，也就是分析的，也就是说，说，CFG不总是不总是LR(0)文法文法.2024/9/2167I I0 0: :S.S S.S S.AS.AS.BS.BA.aAcA.aAcA.aA.aB.bBdB.bBdB.bB.bSI I1 1:S:SS.S.AI I2 2:SA.:SA.BI I3 3:SB.:SB.aI I4 4: :Aa.AcAa.AcAa.Aa.A.aAcA.aAcA.aA.abI I5 5: :Bb.BdBb.BdBb.Bb.B.bBdB.bBdB.bB.bAI I6 6:AaA.c:AaA.cabBI I7 7
59、: BbB.d: BbB.dcI I8 8:AaAc.:AaAc.dI I7 7: BbBd.: BbBd.S S S S S S S A|BS A|BS A|BS A|BA A A A aAcaAcaAcaAcA aA aA aA aB B B B bBdbBdbBdbBdB bB bB bB b2024/9/2168项目集项目集 I 的相容的相容n如果如果 I 中至少含两个归约项目，则称中至少含两个归约项目，则称 I 有归约有归约归归约冲突（约冲突（Reduce/Reduce Conflict）n如果如果 I 中既含归约项目，又含移进项目，则称中既含归约项目，又含移进项目，则称 I 有有移
60、进移进归约冲突（归约冲突（Shift/Reduce Conflict）n如果如果 I 既没有归约既没有归约归约冲突，又没有移进归约冲突，又没有移进归约归约冲突，则称冲突，则称 I 是相容的是相容的(Consistent)，否则称，否则称 I 是不是不相容的相容的n对文法对文法G，如果，如果 IC,都是相容的，则称都是相容的，则称G为为LR(0)文法文法2024/9/2169I I0 0: :S.S S.S S.AS.AS.BS.BA.aAcA.aAcA.aA.aB.bBdB.bBdB.bB.bSI I1 1:S:SS.S.AI I2 2:SA.:SA.BI I3 3:SB.:SB.aI I4
61、4: :Aa.AcAa.AcAa.Aa.A.aAcA.aAcA.aA.abI I5 5: :Bb.BdBb.BdBb.Bb.B.bBdB.bBdB.bB.bAI I6 6:AaA.c:AaA.cabBI I7 7: BbB.d: BbB.dcI I8 8:AaAc.:AaAc.dI I7 7: BbBd.: BbBd.S S S S S S S A|BS A|BS A|BS A|BA A A A aAcaAcaAcaAcA aA aA aA aB B B B bBdbBdbBdbBdB bB bB bB b问题问题:如何构造如何构造其分析表其分析表?2024/9/21705.3.3 SLR(1
62、)分析表的构造算法分析表的构造算法 算法算法5.6 LR(0)分析表的构造。分析表的构造。输入：文法输入：文法G=(V, T, P, S)的拓广文法的拓广文法G;输出：输出：G的的LR(0)分析表，即分析表，即action表和表和goto表表;步骤：步骤：1.令令I0= CLOSURE(S.S)，构造，构造G的的LR(0)项目集规范族项目集规范族C= I0,I1,In2让让Ii对应状态对应状态i，I0对应状态对应状态0，0为初始状态。为初始状态。3for k=0 to n do begin if A.a Ik & a T & GO(Ik, a)=Ij then actionk,a:=Sj; i
63、f A.B Ik&B V&GO(Ik, B)=Ij then gotok,B:=j; if A. Ik & A为为G的第的第j个产生式个产生式then for a FOLLOW(A) do actionk,a:=rj; if SS. Ik then actionk,#:=acc end;4上述上述到到步未填入信息的表项均置为步未填入信息的表项均置为error。 识别表达式文法的所有活前缀的识别表达式文法的所有活前缀的DFA 拓广文法 0) 1) + 2) 3) 3) * * 4) 4) 5) 5) ( () ) 6) 6) idid2024/9/2172I I0 0: :E.E E.E E.E
64、+TE.E+TE.TE.TT.T*FT.T*FT.FT.FF.(E)F.(E)F.idF.idEI I1 1: :EE. EE. EE.+TEE.+TTI I2 2: :ET.ET.TT.*FTT.*FFI I3 3: :TF.TF.(I I4 4: :F(.E )F(.E )E.E+TE.E+TE.TE.TT.T*FT.T*FT.FT.FF.(E)F.(E)F.idF.ididI I5 5: :FidFid. .+I I6 6: :EE+.TEE+.TT.T*FT.T*FT.FT.FF.(E)F.(E)F.idF.id*I I7 7: :TT*.FTT*.FF.(E)F.(E)F.idF.i
65、dEI I8 8: :F (E.)F (E.)EE.+TEE.+TTF(idTI I9 9: :EE+T.EE+T.TT.*FTT.*FF(idFI I1010: :TT*F.TT*F.()I I1111: :F(E).F(E).+*id2024/9/2173表达式文法的表达式文法的 LR(0)分析表含有冲突分析表含有冲突n在状态 2、9 采用归约，出现移进归约冲突2024/9/2174表达式文法的表达式文法的SLR(1)分析表分析表n求非终结符的求非终结符的 FISRT 集集和和 FOLLOW 集集nFIRST( F ) = id, ( nFIRST( T ) = id, ( nFIRST(
66、 E ) = id, ( nFOLLOW( E ) = ), +, # nFOLLOW( T ) = ), +, #, * nFOLLOW( F ) = ), +, #, * 1) 1) + + 2) 2) 3) 3) * * 4) 4) 5) 5) ( () ) 6) 6) idid2024/9/2175 si 表示移进到状态表示移进到状态i, ri 表示用表示用i号产生式归约号产生式归约2024/9/2176SLR(1) 分析的特点分析的特点n描述能力强于描述能力强于 LL(1) nSLR(1)还考虑还考虑Follow集中的符号集中的符号nLL(1) 仅考虑产生式的首符号仅考虑产生式的首符
67、号nSLR(1) 文法：文法：SLR(1)分析表无冲突的分析表无冲突的CFG2024/9/2177SLR(1)分析的局限性分析的局限性n如果如果 SLR(1) 分析表仍有多重入口（移分析表仍有多重入口（移进归约冲突或归约归约冲突），则说进归约冲突或归约归约冲突），则说明该文法不是明该文法不是 SLR(1) 文法；文法；n说明仅使用说明仅使用 LR(0) 项目集和项目集和 FOLLOW 集集还不足以分析这种文法还不足以分析这种文法2024/9/2178I0:S.SS.L=RS.RL.*RL.idR.LI1:SS.I2:SL.=RRL.LI3:SR.RI4:L*.RR.LL.*RL.idI5:Li
68、d .*idI6:SL=.RR.L L.*RL.id=I7:L*R.RI8:RL.LI9:SL=R.R*LidS2024/9/2179SLR分析中的冲突分析中的冲突需要更强的分析方法需要更强的分析方法 I2 =S L.=R, R L. n输入符号为输入符号为 = 时，出现了移进归约冲突：时，出现了移进归约冲突： S L .=R I2 and go(I2,=)=I6 action2,= = Shift 6 R L . I2 and = FOLLOW(R)=,# action2,= = Reduce R Ln说明该文法不是说明该文法不是SLR(1)文法，分析这种文法需要更多文法，分析这种文法需要更
69、多的信息。的信息。2024/9/2180SLR分析中存在冲突的原因分析中存在冲突的原因nSLR（1）只孤立地考察输入符号是否属于归约项目）只孤立地考察输入符号是否属于归约项目A.相关联的集合相关联的集合FOLLOW（A），而没有考察符号），而没有考察符号串串所在规范句型的所在规范句型的“上下文上下文”。n所以试图用某一产生式所以试图用某一产生式A归约栈顶符号串归约栈顶符号串时，不仅时，不仅要向前扫描一个输入符号，还要查看栈中的符号串要向前扫描一个输入符号，还要查看栈中的符号串，只有当只有当Aa的确构成文法某一规范句型的活前缀时才能的确构成文法某一规范句型的活前缀时才能用用A归约。归约。亦即要考
70、虑归约的有效性：亦即要考虑归约的有效性：n问题：怎样确定问题：怎样确定Aa是否是文法某一规范句型的活前缀是否是文法某一规范句型的活前缀2024/9/21815.3.4 LR(1)分析表的构造分析表的构造nLR(0)不考虑后继符不考虑后继符(搜索符搜索符)，SLR(1)仅在归仅在归约时考虑后继符约时考虑后继符(搜索符搜索符)，因此，对后继符，因此，对后继符(搜搜索符索符)所含信息量的利用有限，未考虑栈中内容。所含信息量的利用有限，未考虑栈中内容。n希望在构造状态时就考虑后继符希望在构造状态时就考虑后继符(搜索符搜索符)的作的作用：考虑对于产生式用：考虑对于产生式 A的归约，不同使用位的归约，不同
71、使用位置的置的 A 会要求不同的后继符号会要求不同的后继符号2024/9/2182后继符后继符(搜索符搜索符)的概念的概念EE + T( E )T * F 不同的归约中有不同不同的归约中有不同的后继符。的后继符。 特定位置的后继符是特定位置的后继符是FOLLOW集的子集集的子集2024/9/2183LR(k) 项目项目n定义定义5.11n A.,a1a2ak为为LR（k）项目）项目，根据圆点所处，根据圆点所处位置的不同又分为三类：位置的不同又分为三类：n归约项目归约项目: A.,a1a2akn移进项目：移进项目：A.a,a1a2akn待约项目：待约项目：A.B,a1a2akn利用利用LR(k)
72、项目进行项目进行(构造构造)LR(k)分析分析(器器)，当，当k=1时，为时，为LR(1)项目，相应的分析叫项目，相应的分析叫LR(1)分分析析(器器)2024/9/2184LR(1) 项目的有效性项目的有效性n形式上形式上n 称称LR(1)项目项目A.,a对活前缀对活前缀=是有效的，如果存是有效的，如果存在规范推导在规范推导nS *Aw wn其中其中a为为w的首字符，如果的首字符，如果w=，则，则a=#n与与LR(0)文法类似，识别文法全部活前缀的文法类似，识别文法全部活前缀的DFA的每一的每一状态也是用一个状态也是用一个LR(1)项目集来表示，为保证分析时，项目集来表示，为保证分析时，每一
73、步都在栈中得到规范句型的活前缀，应使每一个每一步都在栈中得到规范句型的活前缀，应使每一个LR(1)项目集仅由若干个对相应活前缀有效的项目组成项目集仅由若干个对相应活前缀有效的项目组成2024/9/2185识别文法全部活前缀的识别文法全部活前缀的DFAnLR(1) 项目集族的求法项目集族的求法nCLOSURE（I）：求）：求I的闭包，目的是为了合并某的闭包，目的是为了合并某些状态，节省空间些状态，节省空间nGO（I，X）：转移函数）：转移函数2024/9/2186闭包的计算闭包的计算nCLOSURE(I)的计算的计算n(核心位置：核心位置：A.B,a 扩展成扩展成闭包闭包)n同时考虑可能出现的后
74、继符同时考虑可能出现的后继符nb FIRST( a ) 2024/9/2187闭包的计算闭包的计算n如果如果A.B,a对对=有效有效 /*即存在即存在S*Aaxax*/n假定假定ax*by，则对任意的，则对任意的B有：有：nB.，b对对=也是有效的，其中也是有效的，其中nbFIRST（a）2024/9/2188闭包的计算闭包的计算J:=I; repeat J=JB.,b|A.B,aJ, bFIRST(a)until J 不再扩大不再扩大n当当+时，此时时，此时b=a叫继承的后继符，否则叫继承的后继符，否则叫自生的后继符叫自生的后继符2024/9/2189状态状态 I 和文法符号和文法符号 X
75、的转移函数的转移函数go(I,X) = closure(AX.,a|A.X,aI)2024/9/2190计算计算LR(1)项目集规范族项目集规范族即：分析器状态集合即：分析器状态集合C=I0I| JC，XVT，I=go(J,X)称为称为G的的LR(1)项目集规范族（算法：项目集规范族（算法：P185) beginC:= closure( S.S,#); repeat for IC， X VT if go(I,X) & go(I,X) C then C=Cgo(I,X) until C不变化不变化end.2024/9/2191识别活前缀的关于识别活前缀的关于LR(1) 的的DFAn识别文法识别文
76、法G=（V，T，P，S）的拓广文法）的拓广文法G的所有活前缀的的所有活前缀的DFA M=(C, VT, go, I0, C)nI0=CLOSURE(S .S, #n如果如果CFG G的的LR(1)分析表无冲突则称分析表无冲突则称G为为LR(1)文法文法2024/9/2192LR(1) 分析表的构造分析表的构造1令令I0= CLOSURE(S.S)，构造，构造C= I0, I1, , In，即，即G的的LR(1)项目集规范族。项目集规范族。2从从Ii构造状态构造状态i，0为初始状态。为初始状态。for k=0 to n dobegin if A.a, b Ik & a T & GO(Ik, a)
77、=Ij then actionk,a:=Sj; if GO(Ik, B)=Ij & B V then gotok,B:=j; if A., a Ik & A为为G的第的第j个产生式个产生式then actionk,a:=rj; if SS., # Ik then actionk,#:=acc;endn上述上述到到步未填入信息的表项均置为步未填入信息的表项均置为error。 2024/9/2193LR(1) 分析表的构造分析表的构造n与与LR(0)的的不同点主要在不同点主要在归约动作的选择：归约动作的选择：nLR(0) 分析考虑所有终结符分析考虑所有终结符nSLR(1) 分析参考分析参考 FOL
78、LOW 集集nLR(1) 分析仅考虑分析仅考虑 LR(1)项目中的后继符项目中的后继符2024/9/21942024/9/21955.3.5 LALR(1)分析表的构造分析表的构造nLR(1)对应的对应的C太大太大n问题：是否可以将某些闭包问题：是否可以将某些闭包/状态合并？状态合并？n不同的不同的LR(1)项目闭包可能有相同的项目闭包可能有相同的LR(0)项目，但后继符项目，但后继符可能不同可能不同同心同心n合并后可能带来归约归约冲突合并后可能带来归约归约冲突n合并那些不会带来冲突的同心的合并那些不会带来冲突的同心的LR(1)闭包闭包/状态状态n ( lookahead-LR )n在不带来移
79、进归约冲突的条件下，合并状态，重构分析表在不带来移进归约冲突的条件下，合并状态，重构分析表2024/9/2196LALR(1) 的分析能力的分析能力n强于强于 SLR(1)n合并的后继符仍为合并的后继符仍为 FOLLOW 集的子集集的子集n局限性局限性n合并中不出现归约合并中不出现归约-归约冲突归约冲突n如果如果CFG G的的LALR(1)分析表无冲突则称分析表无冲突则称G为为LALR(1)文法文法2024/9/21975.3.6 二义性文法的应用二义性文法的应用I1:EE. EE . +EEE.*EI7:EE+E.EE.+E EE.*EI8:EE*E.EE.+E EE.*E采用二义性文法，可
80、以减少结果分析器的状态数，并采用二义性文法，可以减少结果分析器的状态数，并能减少对单非终结符（能减少对单非终结符（ ET ET ）的归约。）的归约。在构造分析表时采用消除二义性的规则在构造分析表时采用消除二义性的规则(按优先级按优先级)2024/9/21985.3.6 二义性文法的应用二义性文法的应用I4:SiS.eS SiS . 选择移进选择移进elseelse，以便让它与前面以便让它与前面的的thenthen配对配对2024/9/21995.3.7 LR分析中的出错处理分析中的出错处理n当分析器处于某一状态当分析器处于某一状态S，且当前输入符号，且当前输入符号为为a时，就以符号对时，就以符
81、号对(S，a)查查LR分析表，如分析表，如果分析表元素果分析表元素actionS，a为空为空(或出错或出错)，则，则表示检测到了一个语法错误。表示检测到了一个语法错误。 n紧急方式的错误恢复：从栈顶开始退栈，直紧急方式的错误恢复：从栈顶开始退栈，直至发现在特定语法变量至发现在特定语法变量A上具有转移的状态上具有转移的状态S为止，然后丢弃零个或多个输入符号，直至为止，然后丢弃零个或多个输入符号，直至找到符号找到符号a FOLLOW(A) 为止。接着，分为止。接着，分析器把状态析器把状态gotoS，A压进栈，并恢复正常压进栈，并恢复正常分析。分析。 2024/9/21100LR分析的基本步骤分析的
82、基本步骤1、编写拓广文法，求、编写拓广文法，求Follow集集2、求识别所有活前缀的、求识别所有活前缀的DFA3、构造、构造LR分析表分析表2024/9/211015.4 语法分析程序的自动生成工具语法分析程序的自动生成工具Yacc nYSP(Yacc Specification)%变量定义：头文件和全局变量变量定义：头文件和全局变量%开始符号开始符号词汇表：词汇表：%Token n1,n2,(自动定义种别码自动定义种别码) %Token n1,i1（用户指定种别码）（用户指定种别码） %Token nh,ih（用户指定种别码）（用户指定种别码）类型说明类型说明 %type其它说明其它说明%规
83、则部分规则部分 给出文法规则的描述给出文法规则的描述%程序部分程序部分 扫描器和语义动作程序扫描器和语义动作程序n输出：输出：LALR(1)分析器分析器2024/9/21102用用Yacc和和Lex合建编译程序合建编译程序2024/9/21103本章小结本章小结n自底向上的语法分析从给定的输入符号串自底向上的语法分析从给定的输入符号串w出发，出发，自底向上地为其建立一棵语法分析树。自底向上地为其建立一棵语法分析树。n移进移进-归约分析是最基本的分析方式，分为优先法归约分析是最基本的分析方式，分为优先法和状态法。和状态法。n算符优先分析法是一种有效的方法，通过定义终算符优先分析法是一种有效的方法，通过定义终结符号之间的优先关系来确定移进和归约。结符号之间的优先关系来确定移进和归约。nLR分析法有着更宽的适应性。该方法通过构建识分析法有着更宽的适应性。该方法通过构建识别规范句型活前缀的别规范句型活前缀的DFA来设计分析过程中的状来设计分析过程中的状态。可以将态。可以将LR分析法分成分析法分成LR(0)、SLR(1)、LR(1)、LALR(1)。n通过增加附加的信息可以解决一些二义性问题。通过增加附加的信息可以解决一些二义性问题。nYacc是是LALR(1)语法分析器的自动生成工具。语法分析器的自动生成工具。
