《自底向上的解读复习课程.ppt》由会员分享，可在线阅读，更多相关《自底向上的解读复习课程.ppt（103页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、自底向上的解读5.1 自底向上的语法分析概述自底向上的语法分析概述n思想思想n从输入串出发，反复利用产生式进行归约，如果从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。则输入串有语法错误。n核心核心n寻找句型中的当前归约对象寻找句型中的当前归约对象“句柄句柄”进行归约进行归约,用不同的方法寻找句柄，就可获得不同的分析方法用不同的方法寻找句柄，就可获得不同的分析方法2022/12/162例例5.1 一个简单的归约过程一个简单的归约过程n设文法设文法G为：为：SaABe AAbc|b Bd句子分析
2、：句子分析：句子分析：句子分析：a a a ab b b bbcdebcdebcdebcdea a a aAbcAbcAbcAbcdedededeaAaAaAaAd d d de e e e aABeaABeaABeaABe S S S S语法树的形成过程语法树的形成过程语法树的形成过程语法树的形成过程2022/12/163语法分析树的生成演示语法分析树的生成演示a b b c d eAABSAbAbAAbcAAbcBdBdSaAcBeSaAcBe2022/12/1645.1.1 移进移进-归约分析归约分析n系统框架系统框架n采用表驱动的方式实现采用表驱动的方式实现n输入缓冲区：保存输入符号串
3、输入缓冲区：保存输入符号串n分析栈：保存语法符号分析栈：保存语法符号已经得到的那部已经得到的那部分分析结果分分析结果n控制程序：控制分析过程，输出分析结果控制程序：控制分析过程，输出分析结果产生式序列产生式序列n格局：格局：栈栈+输入缓冲区剩余内容输入缓冲区剩余内容=“句型句型”2022/12/165移进移进-归约语法分析器的总体结构归约语法分析器的总体结构 id+id+id id id#id#移进移进-归约归约控制程序控制程序输出输出输出输出产生式序列产生式序列产生式序列产生式序列栈内容栈内容+输入缓冲区内容输入缓冲区内容#“当前句型当前句型 ”#栈栈输入缓冲区输入缓冲区 分析表分析表分析表
4、分析表MM2022/12/166与与LL(1)的体系结构比较的体系结构比较 输入缓冲区输入缓冲区(符号序列符号序列)栈栈控制程序控制程序P132预测分析表预测分析表M M输出输出输出输出产生式序列产生式序列产生式序列产生式序列2022/12/167移进移进-归约分析的工作过程归约分析的工作过程n系统运行系统运行n开始格局开始格局n栈：栈：#；输入缓冲区：；输入缓冲区：w#w#n存放已经分析出来的结果存放已经分析出来的结果,并将读入的符号送入栈，并将读入的符号送入栈，一旦句柄在栈顶形成，就将其弹出进行归约，并一旦句柄在栈顶形成，就将其弹出进行归约，并将结果压入栈将结果压入栈n问题：系统如何发现句
5、柄在栈顶形成？问题：系统如何发现句柄在栈顶形成？n正常结束正常结束:栈中为栈中为#S#S，输入缓冲区只有，输入缓冲区只有#2022/12/168输出结果表示：输出结果表示：用产生式序列表示语法分析树用产生式序列表示语法分析树E idid +id *id EEEEEE idE idE E*EE E+E例例5.2 EE+E|E*E|(E)|id2022/12/169动作动作动作动作 栈栈栈栈 输入缓冲区输入缓冲区输入缓冲区输入缓冲区1)#id1)#id1)#id1)#id1 1 1 1+id+id+id+id2 2 2 2*id*id*id*id3 3 3 3#id+id *idid+id *id
6、2)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 +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
7、 3 3#6)6)6)6)归约归约归约归约 Eid#E+E *idEid#E+E *idEid#E+E *idEid#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)归约归约归约归约 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
8、E11)11)11)11)归约归约归约归约 EE+E#E#EE+E#E#EE+E#E#EE+E#E#12)12)12)12)接受接受接受接受E E2022/12/1610分析器的四种动作分析器的四种动作1)1)移进：将下一输入符号移入栈移进：将下一输入符号移入栈2)2)归约：用产生式左侧的非终结符替换栈顶归约：用产生式左侧的非终结符替换栈顶的句柄（某产生式右部）的句柄（某产生式右部）3)3)接受：分析成功接受：分析成功4)4)出错：出错处理出错：出错处理？决定移进和归约的依据是什么？决定移进和归约的依据是什么回头看是回头看是否可以找到答案否可以找到答案2022/12/1611移进移进-归约分析
9、中的问题归约分析中的问题n1)1)移进归约冲突移进归约冲突 n例例5.25.2中的中的 6)6)可以移进可以移进*或按产生式或按产生式EE+EEE+E归约归约 2022/12/161212)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 *idid+id *id2)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.25.2分析过程分析过程3)3)3)3)归约
10、归约归约归约 Eid#E +idEid#E +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 EE E7)7)7)7)移进移进移进移进#E+E*i
11、d#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)归约归约归约归约 EE+E#E#EE+E#E#EE+E#E#EE+E#E#E E动作动作动作动作 栈栈栈栈 输入缓冲区输入缓冲区输入缓冲区输入缓冲区2022/12/1613移进移
12、进-归约分析中的问题归约分析中的问题1)1)移进归约冲突移进归约冲突 n例例5.25.2中的中的 6)6)可以移进可以移进*或按产生式或按产生式EE+EEE+E归约归约 2)2)归约归约冲突归约归约冲突 n存在两个可用的产生式存在两个可用的产生式n各种分析方法处理冲突的方法不同各种分析方法处理冲突的方法不同n如何识别句柄？如何识别句柄？n如何保证找到的直接短语是最左的如何保证找到的直接短语是最左的?利用栈利用栈n如何确定句柄的开始处与结束处？如何确定句柄的开始处与结束处？2022/12/16145.1.2 优先法优先法n根据归约的先后次序为句型中相邻的文法符号根据归约的先后次序为句型中相邻的文
13、法符号规定优先关系规定优先关系n句柄内相邻符号同时归约，是同优先的句柄内相邻符号同时归约，是同优先的n句柄两端符号的优先级要高于句柄外与之相邻的句柄两端符号的优先级要高于句柄外与之相邻的符号符号na1ai-1 aiai+1aj-1aj aj+1ann定义了这种优先关系之后，语法分析程序就可定义了这种优先关系之后，语法分析程序就可以通过以通过ai-1 ai和和aj aj+1这两个关系来确定句柄的这两个关系来确定句柄的头和尾了头和尾了 2022/12/1615根据句柄的识别状态（根据句柄的识别状态（句柄是逐步形成的句柄是逐步形成的）用状态来描述不同时刻下形成的那部分句柄用状态来描述不同时刻下形成的
14、那部分句柄因为句柄是产生式的右部，可用产生式来表示句因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态柄的不同识别状态例如：例如：SbBB可分解为如下识别状态可分解为如下识别状态S.bBB 移进移进bSbB.B 等待归约出等待归约出BSb.BB 等待归约出等待归约出BSbBB.归约归约采用这种方法，语法分析程序根据当前的分析状采用这种方法，语法分析程序根据当前的分析状态就可以确定句柄的头和尾，并进行正确的归约。态就可以确定句柄的头和尾，并进行正确的归约。5.1.3 状态法状态法2022/12/16165.2 算符优先分析法算符优先分析法n算术表达式分析的启示算术表达式分析的启示n算符优
15、先关系的直观意义算符优先关系的直观意义n+*+*+的优先级低于的优先级低于*n()()(的优先级等于的优先级等于 )n+的优先级高于的优先级高于 +n方法方法n将句型中的终结符号当作将句型中的终结符号当作“算符算符”，借助于算，借助于算符之间的优先关系确定句柄符之间的优先关系确定句柄2022/12/1617算术表达式文法的再分析算术表达式文法的再分析nEE+EnEE-EnEE*EnEE/E nE(E)nEidnEE+T|E-T|T TT*F|T/F|F F(E)|id从如何去掉二义性从如何去掉二义性从如何去掉二义性从如何去掉二义性,看看看看对算符优先级的利用对算符优先级的利用对算符优先级的利用
16、对算符优先级的利用句型的特征：句型的特征：句型的特征：句型的特征：(E E+E E)*()*(E E-E E)/)/E E/E E+E E*E E*E E2022/12/1618算符文法算符文法n如果文法如果文法G=（V，T，P，S）中不存在形如）中不存在形如ABC 的产生式，则称之为算符文法的产生式，则称之为算符文法(OG Operator Grammar)即：如果文法即：如果文法 中不存在具有相邻非终结符的中不存在具有相邻非终结符的产生式，则称为算符文法。产生式，则称为算符文法。2022/12/1619定义定义5.1 假设假设G是一个不含是一个不含-产生式的文法，产生式的文法，A、B和和C
17、均是均是G的语法变量，的语法变量，G的任何一对终结符的任何一对终结符a和和b之间之间的的优先关系定义优先关系定义为：为：ab，当且仅当文法，当且仅当文法G中含有形如中含有形如Aab或或AaBb的产生式；的产生式；a b，当且仅当文法，当且仅当文法G中含有形如中含有形如AaB的产生的产生式，而且式，而且Bb或或BCb；a b，当且仅当文法，当且仅当文法G中含有形如中含有形如ABb的产生的产生式，而且式，而且Ba或或BaC；a与与b无关系，当且仅当无关系，当且仅当a与与b在在G的任何句型中都不的任何句型中都不相邻。相邻。问题：什么是算符优先文法？问题：什么是算符优先文法？5.2.1 算符优先文法算
18、符优先文法2022/12/16205.2.1 算符优先文法算符优先文法n设设G=（V，T，P，S）为）为OG，如果，如果 a,bVT,ab,a b,a b 至多有一个成立，则称至多有一个成立，则称之为算符优先文法之为算符优先文法(OPG Operator Precedence Grammar)在无在无产生式的算符文法中，如果任意两产生式的算符文法中，如果任意两个终结符之间至多有一种优先关系，则称为个终结符之间至多有一种优先关系，则称为算符优先文法。算符优先文法。2022/12/16215.2.2 算符优先矩阵的构造算符优先矩阵的构造n优先关系的确定n根据优先关系的定义nab AaBP且(B+b
19、或者B+Cb)n需要求出非终结符B派生出的第一个终结符集nab ABbP且(B+a或者B+aC)n需要求出非终结符B派生出的最后一个终结符集n设G=（V，T，P，S）为OG，则定义nFIRSTOP(A)=b|A+b或者A+Bb,bT,B VnLASTOP(A)=b|A+b或者A+bB,bT,B V2022/12/1622算符优先关系矩阵的构造算符优先关系矩阵的构造nAab;AaBb,则则abnAaB,则对则对 bFIRSTOP(B),a bnABb,则对则对 aLASTOP(B),a bnif ABP,then FIRSTOP(B)FIRSTOP(A)nif ABP,then LASTOP(B
20、)LASTOP(A)n问题：编程求问题：编程求FIRSTOP、LASTOP2022/12/1623算符优先关系矩阵的构造算符优先关系矩阵的构造nA AXX1 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
21、)，a aX Xi+1i+12022/12/1624例例 5.6 表达式文法的算符优先关系表达式文法的算符优先关系 acc+-*/()idid#+-*/（）idid#2022/12/16255.2.3 算符优先分析算法算符优先分析算法n 原理原理n识别句柄并归约识别句柄并归约n各种优先关系存放在算符优先分析表中各种优先关系存放在算符优先分析表中n利用利用识别句柄尾，利用识别句柄尾，利用识别句柄头，分析栈存识别句柄头，分析栈存放已识别部分，比较栈顶和下一输入符号的关系，如放已识别部分，比较栈顶和下一输入符号的关系，如果是句柄尾，则沿栈顶向下寻找句柄头，找到后弹出果是句柄尾，则沿栈顶向下寻找句柄头
22、，找到后弹出句柄，归约为非终结符。句柄，归约为非终结符。2022/12/1626例例5.7 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归约归约2022/12/1627问题问题n有时未归约真正的句柄（有时未归约真正的句柄（F）n不是严格的最左归
23、约不是严格的最左归约n归约的符号串有时与产生式右部不同归约的符号串有时与产生式右部不同n仍能正确识别句子的原因仍能正确识别句子的原因nOPG未定义非终结符之间的优先关系，不能未定义非终结符之间的优先关系，不能识别由单非终结符组成的句柄识别由单非终结符组成的句柄n定义算符优先分析过程识别的定义算符优先分析过程识别的“句柄句柄”为为最最左素短语左素短语LPP（Leftmost Prime Phase）2022/12/1628素短语与最左素短语素短语与最左素短语n什么是短语？当前我们要找什么样的短语什么是短语？当前我们要找什么样的短语？至少有一个算符至少有一个算符n*and A+，至少含一个终结符，
24、至少含一个终结符，且不含更小的含终结符的短语且不含更小的含终结符的短语,则称则称是句型是句型的相对于变量的相对于变量A的素短语的素短语(Prime Phrase)n句型的至少含一个终结符且不含其它素短句型的至少含一个终结符且不含其它素短语的短语语的短语2022/12/1629例例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的短语和素短语
25、的短语和素短语 E E E E T T T TE E F FT +T*F +iT +T*F +i2022/12/1630文法：文法：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 i2022/12/1631素短语与最左素短语素
26、短语与最左素短语设句型的一般形式为设句型的一般形式为#N1a1 N2a2 Nnan#(Ni V,ai VT）它的最左素短语是满足下列条件的最左子串它的最左素短语是满足下列条件的最左子串Niai Ni+1ai+1 Njaj Nj+1其中：其中：ai-1 ai,，aiai+1aj-1aj，aj aj+12022/12/1632算符优先分析的实现算符优先分析的实现n系统组成系统组成n移进归约分析器移进归约分析器 +优先关系表优先关系表n分析算法分析算法n参照输入串、优先关系表，完成一系列归约，生参照输入串、优先关系表，完成一系列归约，生成语法分析树成语法分析树输出产生式输出产生式2022/12/16
27、33算符优先分析算法算符优先分析算法 算法算法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 S
28、j Q;将将Sj+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;2022/12/1634id+id*id 的分析过程的分析过程id+id*id#算符优先分析算符优先分析控制器控制器E idE idE idE idE idE idE E*EE E*EE E+EE E+E算符优先关系表算符优先关系表#id#+#id+#+#*+#id*+#*+#+#2022/12/16355.2.4 优先函数优先函数n为了节省存储空间（为了节省存储空间（n2
29、2n）和便于执行比较运算，）和便于执行比较运算，用两个优先函数用两个优先函数f和和g，它们是从终结符号到整数的映，它们是从终结符号到整数的映射。对于终结符号射。对于终结符号a和和b选择选择f和和g，使之满足：，使之满足：n f(a)g(b)，如果如果a b。n损失损失n错误检测能力降低错误检测能力降低n如：如：id id不存在，但不存在，但f(id)g(id)可比较可比较2022/12/1636表表5.2 对应的优先函数：对应的优先函数：1)构造优先函数的算法不是唯一的。构造优先函数的算法不是唯一的。2)存在一组优先函数，那就存在无穷组优存在一组优先函数，那就存在无穷组优先函数。先函数。+-*
30、/()id#f22440440g113350502022/12/1637优先函数的构造优先函数的构造算法算法5.4 优先函数的构造。优先函数的构造。输入：算符优先矩阵输入：算符优先矩阵;输出：表示输入矩阵的优先函数，或指出其不存在输出：表示输入矩阵的优先函数，或指出其不存在;步骤：步骤：1.对对 a T#，建立以，建立以fa和和ga为标记的顶点；为标记的顶点；2.对对 a,b T#，若，若a b或者或者ab，则从，则从fa至至gb画一条有向画一条有向弧；若弧；若a b或者或者ab，则从，则从gb至至fa画一条有向弧；画一条有向弧；3.如果构造的有向图中有环路，则说明不存在优先函数；如如果构造的
31、有向图中有环路，则说明不存在优先函数；如果没有环路，则对果没有环路，则对 a T#，将，将f(a)设为从设为从fa开始的最长开始的最长路经的长度，将路经的长度，将g(a)设为从设为从ga开始的最长路经的长度。开始的最长路经的长度。2022/12/1638例例5.10 Ges:EE+T|T TT*F|F Fid+*id#+*id#+*id#f2440g1350根据根据Ges的优先矩阵建立的的优先矩阵建立的有向图和优先函数有向图和优先函数 Ges的优先矩阵的优先矩阵2022/12/16395.2.5 算符优先分析的出错处理算符优先分析的出错处理 栈顶的终结符号和当前输入符号之间不存在任何优栈顶的终
32、结符号和当前输入符号之间不存在任何优先关系；先关系；发现被发现被“归约对象归约对象”，但该，但该“归约对象归约对象”不能满足不能满足归约要求。归约要求。n对于第对于第种情况，为了进行错误恢复，必须修改栈、种情况，为了进行错误恢复，必须修改栈、输入或两者都修改。输入或两者都修改。n对于优先矩阵中的每个空白项，必须指定一个出错对于优先矩阵中的每个空白项，必须指定一个出错处理程序，而且同一程序可用在多个地方。处理程序，而且同一程序可用在多个地方。n对于第对于第种情况，由于找不到与种情况，由于找不到与“归约对象归约对象”匹配匹配的产生式右部，分析器可以继续将这些符号弹出栈，的产生式右部，分析器可以继续
33、将这些符号弹出栈，而不执行任何语义动作。而不执行任何语义动作。2022/12/1640算符优先分析法小结算符优先分析法小结n优点优点n简单、效率高简单、效率高n能够处理部分二义性文法能够处理部分二义性文法n缺点缺点n文法书写限制大文法书写限制大强调算符之间的优先关系的强调算符之间的优先关系的唯一性唯一性n占用内存空间大占用内存空间大n不规范、存在查不到的语法错误不规范、存在查不到的语法错误n算法在发现最左素短语的尾时，需要回头寻找对算法在发现最左素短语的尾时，需要回头寻找对应的头应的头2022/12/16415.3 LR分析法分析法 5.3.1 LR分析算法分析算法nLR(k)LR(k)分析法
34、可分析分析法可分析LR(k)LR(k)文法产生的语言文法产生的语言nL L：从左到右扫描输入符号：从左到右扫描输入符号nR R：最右推导对应的最左归约：最右推导对应的最左归约nk k：超前读入：超前读入k k个符号，以便确定归约用的产生式个符号，以便确定归约用的产生式n使用语言的文法描述内涵解决句柄的识别问题，从语言的使用语言的文法描述内涵解决句柄的识别问题，从语言的形式形式描述描述入手，为语法分析器的入手，为语法分析器的自动生成自动生成提供了前提和基础提供了前提和基础n分析器根据当前的状态，并至多向前查看分析器根据当前的状态，并至多向前查看k k个输入符号，个输入符号，就可以确定是否找到了句
35、柄，如果找到了句柄，则按相就可以确定是否找到了句柄，如果找到了句柄，则按相应的产生式归约，如果未找到句柄则移进输入符号，并应的产生式归约，如果未找到句柄则移进输入符号，并进入相应的状态进入相应的状态2022/12/1642LR语法分析器的总体结构语法分析器的总体结构a1 ai an#LR分析程序分析程序动作表动作表action转移表转移表gotogoto产生式产生式产生式产生式序列序列序列序列状态状态/符号栈符号栈输入缓冲区输入缓冲区分析表分析表SmSm-1S1S0XmXm-1X1#2022/12/1643LR 分析表分析表：actions,a；gotos,X 动作表动作表动作表动作表 转移表
36、转移表转移表转移表状态状态状态状态 action action action action goto goto goto goto 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 r3 r3 4 r3 r3 r3 4 r3 r3 r3 4 r3 r3 r3 5 5 5
37、5 r1 r1 r1 r1 r1 r1 r1 r1 r1 r1 r1 r1 6 r2 r2 r2 6 r2 r2 r2 6 r2 r2 r2 6 r2 r2 r2 LR(0)、SLR(1)、LR(1)、LALR(1)将以不同的原则将以不同的原则构造这张分析表构造这张分析表约定：约定：sn:将符号将符号a、状、状态态n压入栈压入栈rn:用第用第n个产生个产生式进行归约式进行归约2022/12/1644LR分析器的工作过程分析器的工作过程n书上的下式（格局）书上的下式（格局）(s0s1sm，X1X2 Xm，aiai+1an#)n在这里表示为在这里表示为s0s1sm#X1Xm aiai+1an#20
38、22/12/1645LR分析器的工作过程分析器的工作过程n n1.初始化初始化s0#a1a2an#对应对应对应对应“句型句型句型句型”a a1 1a a2 2aan nn n2.在一般情况下，假设分析器的格局如下：在一般情况下，假设分析器的格局如下：s0s1 sm#X1Xm aiai+1an#对应对应对应对应“句型句型句型句型”X X1 1XXmma ai ia ai+1i+1aan nnIf actionsm,ai=si(shift i)then 格局变为格局变为s0s1 sm i#X1Xmai ai+1an#2022/12/1646s0s1sm#X1Xm aiai+1an#If actio
39、nsm,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#2022/12/1647LR分析算法分析算法 算法算法5.5 LR分析算法。分析算法。输入：文法输入：文法G的的LR分析表和输入串分析表和
40、输入串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指向下一输入符号指向下一输入符号9 end2022/12/164
41、8 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();2022/12/1649例例5.12文法文法1)SBB2)BaB3)Bb分析表分析表 动作表动作表动作表动作表 转移表转移表转移表转移表状态状态状态状态 action a
42、ction action action goto goto goto goto 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 r3 r3 4 r3 r3 r3 4 r3 r3 r3 4 r3 r3 r3 5 r1 r1 r1 5 r1 r1 r1 5 r1 r1 r1
43、 5 r1 r1 r1 6 r2 r2 r2 6 r2 r2 r2 6 r2 r2 r2 6 r2 r2 r2 请跟随讲请跟随讲解，快速解，快速抄下右侧抄下右侧的表格！的表格！2022/12/1650bab 的分析过程的分析过程:1)SBB1)SBB2)BaB2)BaB3)Bb3)Bb0236#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#goto(0,S)=1 0101#S#action(1,#)=acc#S#
44、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)=62022/12/1651规范句型活前缀规范句型活前缀n分析栈中内容分析栈中内容+剩余输入符号剩余输入符号=规范句型规范句型n分析栈中内容为某一句型的前缀分析栈中内容为某一句型的前缀n来自分析栈的来自分析栈的活前缀活前缀(Active Prefi
45、x)n不含句柄右侧任意符号的规范句型的前缀不含句柄右侧任意符号的规范句型的前缀n例：例：id+id*id 的分析中的分析中n句型句型 E+id.*id 和和 E+E*.id活前缀活前缀活前缀活前缀S*rmAw rm 12w 2022/12/1652规范句型活前缀规范句型活前缀n规范归约所得到的规范句型规范归约所得到的规范句型(Canonical Sentential Form)的活前缀是出现在分析栈中的活前缀是出现在分析栈中的符号串，所以，不会出现句柄之后的任何的符号串，所以，不会出现句柄之后的任何字符，而且相应的后缀正是输入串中还未处字符，而且相应的后缀正是输入串中还未处理的终结符号串。理的
46、终结符号串。n活前缀与句柄的关系活前缀与句柄的关系n包含句柄包含句柄 A.n包含句柄的部分符号包含句柄的部分符号A 1.2 n不含句柄的任何符号不含句柄的任何符号A.2022/12/16535.3.2 LR(0)分析表的构造分析表的构造nLR(0)项目项目从产生式寻找归约方法从产生式寻找归约方法n右部某个位置标有园点的产生式称为相应右部某个位置标有园点的产生式称为相应文法的文法的LR(0)项目项目（Item）n例例 S.bBB SbB.B Sb.BB SbBB.n归约（归约（Reduce）项目）项目:SaBB.n移进（移进（Shift）项目：）项目：S.bBBn待约项目：待约项目：Sb.BB
47、SbB.B2022/12/1654项目的意义项目的意义n用项目表示分析的用项目表示分析的进程进程(句柄的识别状句柄的识别状态态)n方法：在产生式右方法：在产生式右部加一园点以分割已部加一园点以分割已获取的内容和待获取获取的内容和待获取的内容：构成句柄的内容：构成句柄b a b BBBSS B.B B .a B2022/12/1655拓广拓广(Augmented)文法文法n需要一个对需要一个对“归约成归约成S”的表示（只有一个接受状态）的表示（只有一个接受状态）n文法文法 G=(V,T,P,S)的拓广文法的拓广文法 G：nG=（V S，T，P SS，S）nS Vn对应对应S.S（分析开始）和（分
48、析开始）和SS.（分析成功）（分析成功）n例例5.13 0)SS1)SBB2)BaB3)Bb2022/12/1656构造识别构造识别G G的所有规范句型活前的所有规范句型活前缀的缀的DFADFAn问题：如何设计能够指导分析器运行，问题：如何设计能够指导分析器运行，并且能够根据当前状态（栈顶）确定句并且能够根据当前状态（栈顶）确定句柄柄归约对象的头归约对象的头的装置的装置2022/12/1657项目集项目集 I 的闭包（的闭包（Closure）CLOSURE(I)=I B.|A.BI,BP 算法算法 J:=I;repeat J=JB.|A.BJ,BPuntil J不再扩大不再扩大项目集闭包的计算
49、项目集闭包的计算2022/12/1658闭包之间的转移闭包之间的转移n后继项目（后继项目（Successive Item）nA.X的后继项目是的后继项目是AX.n闭包之间的转移闭包之间的转移ngo(I,X)=CLOSURE(AX.|A.XI2022/12/1659状态转移的计算状态转移的计算n确定在某状态遇到一个文法符号后的确定在某状态遇到一个文法符号后的状态转移目标状态转移目标function GO(I,X);beginJ:=;for I中每个形如中每个形如A.X的项目的项目dobegin J:=JAX.end;return CLOSURE(J)end;2022/12/1660识别拓广文法所
50、有规范句型活前缀的识别拓广文法所有规范句型活前缀的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)2022/12/1661计算计算LR(0)项目集规范族项目集规范族即：分析器状态集合即：分析器状态集合beginC:=closure(S.S);repeat for IC，X VT if go(I,X)&go(I,X)C the