编译原理 课件 第三章 语法分析3.ppt

《编译原理 课件 第三章 语法分析3.ppt》由会员分享，可在线阅读，更多相关《编译原理 课件 第三章 语法分析3.ppt（114页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.4 3.4 自下而上语法分析自下而上语法分析本节要求本节要求1.掌握自下而上语法分析的基本思想和基掌握自下而上语法分析的基本思想和基本概念本概念2.了解算符优先语法分析了解算符优先语法分析3.掌握句柄的定义与判定掌握句柄的定义与判定4.理解规范归约的过程和理解规范归约的过程和LR分析过程中的分析过程中的实现实现5.掌握掌握LR语法分析的实现过程语法分析的实现过程【例例】回顾：回顾：一个简单的归约过程一个简单的归约过程 设文法为：设文法为：SaAcBeSaAcBeAAb|bAAb|bBdBdA Aa b b c d ea b b c d eB BA AS S自下而上自下而上自下而上自下而上构

2、造语法构造语法构造语法构造语法树的过程树的过程树的过程树的过程句子分析：句子分析：句子分析：句子分析：a a a ab b b bbcdebcdebcdebcdea a a aA A A Ab b b bcdecdecdecdea a a aA A A Ac c c cd d d de e e e aAcaAcaAcaAcB B B Be e e e S S S S对应的是最右推导对应的是最右推导注意：每次归约的是句柄注意：每次归约的是句柄3.4.1自下而上语法分析的原理自下而上语法分析的原理实现思想实现思想从从输输入入符符号号串串开开始始，从从左左到到右右进进行行扫扫描描，将将输输入入符符号

3、号逐逐个个移移入入一一个个栈栈中中，边边移移入入边边分分析析，一一旦旦栈栈顶顶符符号号串串形形成成某某个个产产生生式式的的右右部部时时，就就用用该该产产生生式式的的左左部部非非终终结结符符代代替替，称称为为归归约约。重重复复这这一一过过程程，直直到到归归约约到到栈栈中中只只剩剩下下文文法法的的开开始始符符号号时时，则则分分析析成成功功，称称为为“移移进进-归归约约”方方法法。从从语语法法树树的的角角度度看看：从从语语法法树树的的树树叶叶开开始始，逐逐步步向向上上归归约约构构造造分分析析树树，直直到到形形成成根根结结点点。是是推导推导的逆过程的逆过程。“移移进进-归约归约”分析法分析法移进移进-

4、归约分析器使用了一个分析栈和一个输入缓冲区。归约分析器使用了一个分析栈和一个输入缓冲区。1、句型表示、句型表示a1a2a3#X1X2X3#“移进-归约”分析程序输出栈(存放句型前缀)输入串即：分析栈内容即：分析栈内容+输入缓冲区内容输入缓冲区内容#当前句型当前句型#一般形式一般形式分析栈的内容分析栈的内容剩余输入串剩余输入串初态：初态：#输入串输入串#终态：终态：#S#2、分析器结构分析器结构、“移进移进-归约归约”分析法的栈实现分析法的栈实现“移进移进归约归约”分析器使用一个栈和一个存放输分析器使用一个栈和一个存放输入符号串入符号串w w的缓冲器。分析器的初始状态为的缓冲器。分析器的初始状态

5、为:栈栈输入输入w w工作过程：工作过程：自左至右把串自左至右把串ww的符号一一移进栈里，一的符号一一移进栈里，一旦栈顶形成可归约的串（如旦栈顶形成可归约的串（如句柄句柄）时，就进行归约。）时，就进行归约。这种归约可能持续多次，直至栈顶不再呈现句柄为止。这种归约可能持续多次，直至栈顶不再呈现句柄为止。然后，继续向栈里移进符号，重复这个过程，直至最然后，继续向栈里移进符号，重复这个过程，直至最终形成如下格局：终形成如下格局：栈栈输入输入SS分析栈分析栈输入串输入串动作动作【例例】文法文法GS:SaAcBeAb AbBd待分析的句子为：待分析的句子为：待分析的句子为：待分析的句子为：abbcdea

6、bbcde#abbcde#移进移进#abbcde#移进移进#abbcde#归约归约Ab#aAbcde#移进移进分析栈分析栈输入串输入串动作动作cde#aAcde#移进移进#aAcde#归约归约Bd#aAcde#移进移进#aAb归约归约AAb#aAcBe#移进移进#aAcBe#归约归约SaAcBe#S#接受接受小结小结 分析器的四种动作分析器的四种动作1)1)移进移进：读入下一个输入符号并把它下推进栈。：读入下一个输入符号并把它下推进栈。2)2)归约归约：当栈顶符号串形成一个可归约的串（如：当栈顶符号串形成一个可归约的串（如：句柄句柄）时，直接进行归约，即用产生式左侧的非终结符替换栈时，直接进行

7、归约，即用产生式左侧的非终结符替换栈顶的句柄。顶的句柄。3)3)接受接受：当栈底只有：当栈底只有“#”#”和开始符号，而输入也已经到和开始符号，而输入也已经到达右端标志符号达右端标志符号“#”#”时，识别出符号串是句子，执行时，识别出符号串是句子，执行该动作，表示分析成功，是归约的一种特殊情况。该动作，表示分析成功，是归约的一种特殊情况。4)4)出错出错：栈顶的内容与输入符号相悖，即当识别程序发现栈顶的内容与输入符号相悖，即当识别程序发现输入符号串不是句子时，进行出错处理。输入符号串不是句子时，进行出错处理。注意：决定移进和归约的依据是什么？注意：决定移进和归约的依据是什么？栈顶是否出现了可归

8、约的符号串。栈顶是否出现了可归约的符号串。关键：关键：如何识别可归约的符号串？如何识别可归约的符号串？通过不同的自下而上的通过不同的自下而上的分析算法分析算法来解释，不同来解释，不同的算法的算法对可归约串的定义是不同的对可归约串的定义是不同的，但分析过，但分析过程都有一个共同的特点：程都有一个共同的特点：边移进边归约边移进边归约。规范归约：使用规范归约：使用句柄句柄来定义可归约串来定义可归约串算符优先：使用算符优先：使用最左素短语最左素短语来定义可归约串来定义可归约串自下而上语法分析主要有以下三种方法自下而上语法分析主要有以下三种方法简单优先分析法简单优先分析法(规范归约规范归约)文法按文法按

9、一定原则规定文法符号的优先关系。一定原则规定文法符号的优先关系。算符优先分析法算符优先分析法(非规范归约非规范归约)规定规定算符算符之间的优先关系。之间的优先关系。LR分析法（规范归约）分析法（规范归约）LR(0)、LR(1)、SLR(1)和和LALR(1)。规范归约相关概念复习有文法有文法G G，开始符号为开始符号为S,S,如果有如果有S=xy,S=xy,则则xyxy是是文法文法G G的的句型句型，x,yx,y是任意的符号串。是任意的符号串。如果有如果有S=S=xAyxAy,且有且有A=,A=,则则是句型是句型xyxy相对于相对于非终结符非终结符A A的的短语。短语。如果有如果有S=S=xA

10、yxAy,且有且有AA,则则是句型是句型xyxy相对相对于于AA的的直接短语。直接短语。位于一个句型最左边的直接短语称为位于一个句型最左边的直接短语称为句柄。句柄。句型句型短语短语直接短语直接短语句柄句柄*+*注注:采用规范归约的算法，每次归约的部分就是分析为采用规范归约的算法，每次归约的部分就是分析为句柄句柄的字符串的字符串。因此，在规范归约中，因此，在规范归约中，关键问题就转化为关键问题就转化为如何识别句柄如何识别句柄?练习练习有文法如下有文法如下:(1)EE+T|T(2)TT*F|F(3)F(E)|id分析输入串分析输入串id+id*id，给出对该句子进行，给出对该句子进行“移移进进-归

11、约归约”语法分析的过程。语法分析的过程。栈栈 输入缓冲区输入缓冲区 动作动作#id+idid+id*id#*id#移进移进#id +id*id#id +id*id#归约归约 FidFid#F +id*id#F +id*id#归约归约 TF TF#T +id*id#T +id*id#归约归约 ET ET#E +id*id#E +id*id#移进移进#E+id*#E+id*idid#移进移进#E+idE+id *id#*id#归约归约FidFid#E+F *id#E+F *id#归约归约 TF TF#E+T *id#E+T *id#移进移进#E+T*id#E+T*id#移进移进#E+T*id#E+

12、T*id#归约归约 FidFid#E+T*F#E+T*F#归约归约 TT*F TT*F#E+T#E+T#归约归约 EE+T EE+T#E#E#接受接受(1)EE+T|T(2)TT*F|F(3)F(E)|ididid1 1+id+id2 2 *id *id3 3FTEFTFTEE=E+T=E+T*F=E+T*id=E+F*id=E+id*id=T+id*id=F+id*id=id+id*id移进归约分析过程中存在的问题移进归约分析过程中存在的问题移进移进-归约冲突归约冲突 在分析到某一步时，既可以移进，又可以归约。在分析到某一步时，既可以移进，又可以归约。上例第上例第9)9)步可以移进步可以移进

13、*，也可以按产生式，也可以按产生式EE+TEE+T进行归约。进行归约。归约归约-归约冲突归约冲突存在存在两个两个可选的句柄可对栈顶符号进行归约。可选的句柄可对栈顶符号进行归约。例如上述第例如上述第12)12)步，可以用步，可以用TFTF进行归约，又可进行归约，又可以按以按TT*FTT*F进行归约。进行归约。各种分析方法中处理冲突的技术不同！各种分析方法中处理冲突的技术不同！3.4.2算符优先分析法算符优先分析法算符优先分析法的算符优先分析法的思想思想源于表达式的分析，利用相邻终源于表达式的分析，利用相邻终结符号之间的关系来寻找可归约串。结符号之间的关系来寻找可归约串。将句型中的终结符号当作将句

14、型中的终结符号当作“算符算符”，借助于算符之间的，借助于算符之间的优先关系确定句型的优先关系确定句型的“可归约串可归约串”。在一个符号串中，任意两个相邻终结符号在一个符号串中，任意两个相邻终结符号a和和b之间，只之间，只可能存在以下四种可能存在以下四种优先关系优先关系：(1)a,b优先性相同，记作优先性相同，记作ab。(2)a优先性高于优先性高于b，记作记作ab。(3)a优先性低于优先性低于b，记作记作ab。(4)a与与b不可能相邻，即此符号串不是句型不可能相邻，即此符号串不是句型(出错出错)。如果以上四种关系中的任意两种都不会同时成立，则可如果以上四种关系中的任意两种都不会同时成立，则可以根

15、据终结符号之间的归约关系进行语法分析。以根据终结符号之间的归约关系进行语法分析。注意：注意：注意：注意：在整个归约过程中起决定作用的是相继两个终结在整个归约过程中起决定作用的是相继两个终结符的符的优先关系优先关系。1、算符文法算符文法:一个上下无关文法一个上下无关文法G,如果没有如果没有P,且没有且没有P.QR.(P,Q,R属于非终结符属于非终结符),则则G是一个是一个算符文法。算符文法。2、算符优先关系算符优先关系的定义：假定的定义：假定GS是一个不含是一个不含 产生式的产生式的算符文法，对于任何一对终结符算符文法，对于任何一对终结符a和和b，有：，有：ab，当且仅当，当且仅当GS中有中有P

16、.ab.或或P.aQb.的产的产生式生式(在同一产生式中在同一产生式中)ab，当且仅当，当且仅当GS中有中有P.aR.的产生式的产生式,且且R=b.或或R=Qb.(注意注意ab相邻相邻)ab,G中有中有P.Rb.的产生式的产生式,且且R=.a或或R=.aQ(注意注意ab相邻相邻)算符优先文法算符优先文法+【例例】有文法有文法GE:EE+E|E*E|(E)|i证明该文法不是算符优先文法。证明该文法不是算符优先文法。因为：因为：EE+E，EE*E则有则有+*又因为：又因为：EE*E,EE+E则有则有+*所以不是算符优先文法。所以不是算符优先文法。3.算符优先文法算符优先文法算符文法算符文法G的任何

17、终结符的任何终结符a,b之间可能没有优之间可能没有优先关系，若有优先关系先关系，若有优先关系,至多有至多有中的一种成立中的一种成立,则则G为一算符优先文法。为一算符优先文法。算符优先关系表算符优先关系表的构造的构造用表格形式来表示各终结符号的优先关用表格形式来表示各终结符号的优先关系，这种表称为系，这种表称为优先表优先表。构造优先关系表的方法构造优先关系表的方法按照定义手工计算按照定义手工计算使用算法使用算法由F(E)得(=)T=i,得+T*F,得+(E),得+i,得i +E=E+T,得+E=T*F,得*+E=(E),得)+*i()#+*i()#【例例】文法文法GE:EE+T|T TT*F|F

18、 F(E)|i求其算符优先表。求其算符优先表。终结符+#终结符+#对于结束符对于结束符#和其它终结符和其它终结符a有关系有关系:#*GE的算符优先关系表：的算符优先关系表：在优先表中，在优先表中，空白部分空白部分是一种错误关系。是一种错误关系。相同的相同的终结符之间的优先关系不一定是。终结符之间的优先关系不一定是。如果有如果有a b,a b,不一定有不一定有b a(b a(不具传递性不具传递性)，因为算符优先只定义了相邻运算符之间的优因为算符优先只定义了相邻运算符之间的优先关系。当先关系。当a,b相邻时，不一定相邻时，不一定b,a相邻。相邻。a,b之间之间未必有未必有优先关系优先关系、和。、和

19、。说明1、FIRSTVT集合集合定义：定义：对每个非终结符对每个非终结符P,FIRSTVT(P)=a|P=a.或或P=Qa.,aVT,QVN+按照下面两条按照下面两条规则规则来来构造构造FIRSTVT集合：集合：若有产生式若有产生式Pa.或或PQa.，则，则aFIRSTVT(P)。若有产生若有产生式式PR.，且有，且有aFIRSTVT(R)，则，则aFIRSTVT(P)中。中。2、LASTVT集合集合定义：定义：LASTVT(P)=a|P=.a或或P=.aQ,aVT,QVN+按照下面两条按照下面两条规则规则来来构造构造LASTVT集合：集合：若有产生式若有产生式P.a或或P.aQ，则，则aLA

20、STVT(P)。若有产生若有产生式式P.R，且有，且有aLASTVT(R)，则，则aLASTVT(P)。3 3、构造优先关系表、构造优先关系表如果每个非终结符的如果每个非终结符的FIRSTVT和和LASTVT集均已知集均已知,则则可构造优先关系表可构造优先关系表。若产生式右部有若产生式右部有.aR.的形式的形式,则对于每则对于每个个bFIRSTVT(R)都有都有ab。若产生式右部有若产生式右部有.Rb的形式的形式,则对于每个则对于每个aLASTVT(R)集集,都有都有ab。若产生式形如若产生式形如Pab或或PaQb形式，则有形式，则有ab。【例例3.11】文法文法GE:EE+T|T TT*F|

21、F F(E)|i试构造其算符优先表。试构造其算符优先表。、构造、构造FIRSTVT集。集。(1)根据规则根据规则可知：可知：由由EE+得得FIRSTVT(E)=+;由由TT*得得FIRSTVT(T)=*;由由F(和和Fi得得FIRSTVT(F)=(,i;(2)根据规则根据规则可知：可知：由由FIRSTVT(F)=(,i和和TF得得FIRSTVT(T)=*,(,i;由由FIRSTVT(T)=*,(,i和和ET得得FIRSTVT(E)=+,*,(,i。、构造、构造LASTVT集。集。(1)根据规则根据规则可知：可知：由由E+T得得LASTVT(E)=+;由由T*F得得LASTVT(T)=*;由由F

22、)和和Fi得得LASTVT(F)=),i;(2)根据规则根据规则可知：可知：由由LASTVT(F)=),i和和TF得得LASTVT(T)=*,),i;由由LASTVT(T)=*,),i和和ET得得LASTVT(E)=+,*,),i。EE+TTTT*FFF(E)|i3、构造优先关系表。、构造优先关系表。(1)根据规则根据规则可知可知,由由“(E)”得（）。得（）。(2)根据规则根据规则可知：可知：由由E+T得得+FIRSTVT(T)，即，即+*,(,i;由由T*F得得*FIRSTVT(F)，即，即*(,i;由由F(E得得(FIRSTVT(E)，即，即(+,*,(,i;(3)根据规则根据规则可知：

23、可知：由由EE+得得LASTVT(E)+，即，即+,*,),i+;由由TT*得得LASTVT(T)*，即，即*,),i*;由由FE)得得LASTVT(E)，即，即+,*,),i)。得得GE的算符优先关系表：的算符优先关系表：此外，由此外，由#E#得得#;#FIRSTVT(E)，即，即#+,*,(,i;LASTVT(E)#，即，即+,*,),i#。算符优先分析法的设计算符优先分析法的设计通过比较终结符间的通过比较终结符间的优先关系优先关系来实现；来实现；根据优先分析的原理：语法分析程序的根据优先分析的原理：语法分析程序的任务是不断移进输入符号，识别任务是不断移进输入符号，识别可归约可归约串串并进

24、行归约。并进行归约。问题：如何识别可归约的串？问题：如何识别可归约的串？分析的基本方法：分析的基本方法：根据优先关系根据优先关系“高于高于”来识来识别可归约串的别可归约串的尾尾，根据优先关系，根据优先关系“低于低于”来识来识别可归约串的别可归约串的头头。分析栈存放已识别部分，比较栈顶和下一输入分析栈存放已识别部分，比较栈顶和下一输入符号的关系，如果是符号的关系，如果是可归约串的尾可归约串的尾，则沿栈顶，则沿栈顶向下寻找向下寻找可归约串的可归约串的头，找到后弹出可归约串，头，找到后弹出可归约串，归约为非终结符。归约为非终结符。注注:各种优先关系已经存于优先关系表中。各种优先关系已经存于优先关系表

25、中。分析输入串：分析输入串：i+ii+i#+#F F+#F F+#F F+#E#E#表达式文法表达式文法GE:EE+T|TTT*F|FF(E)|i可见可见,每次归约的不是句柄每次归约的不是句柄每次归约的串是什么？每次归约的串是什么？复习复习素短语：素短语：至少含有一个终结符至少含有一个终结符,且除自身外且除自身外,不再包含任何其它更小的素短语。不再包含任何其它更小的素短语。最左素短语：最左素短语：是指位于句型最左边的那个素短语。是指位于句型最左边的那个素短语。回忆：如何求素短语和最左素短语？回忆：如何求素短语和最左素短语？【例例】对于表达式文法的一个句型：对于表达式文法的一个句型：T*F+i求

26、其短语、素短语、最左素短语。求其短语、素短语、最左素短语。EE+TTTT*FFF(E)|iEE+TFiTT*F短语有：短语有：i,T*F,T*F+i素短语有：素短语有：i,T*F最左素短语是：最左素短语是：T*F一个算符文法一个算符文法G的某个句型的最左素短语可的某个句型的最左素短语可描述描述为：为：设句型的一般形式为（设句型的一般形式为（NiVVN N,aiVVT T）#N1a1N2a2Nnan#它的它的最左素短语最左素短语是满足下列条件的最左子串：是满足下列条件的最左子串：NjajNj+1aj+1NiaiNi+1其中：其中：aj-1aj,ajaj+1.ai-1ai，aiai+1注意：该描述

27、说明了最左素短语与周围符号之间的关系。注意：该描述说明了最左素短语与周围符号之间的关系。小结：算符优先分析过程小结：算符优先分析过程句型的一般形式句型的一般形式:#N:#N1 1a a1 1N N2 2a a2 2.N.Nn na an nN Nn+1n+1#(其中其中a ai i为终结符为终结符,N,Ni i为可有可无的非终结符为可有可无的非终结符)从左向右扫描各符号从左向右扫描各符号,依次查看算符优先表依次查看算符优先表,一一直移进，直至找到满足直移进，直至找到满足a ai i a ai i+1+1的终结符为止。的终结符为止。再从再从a ai i开始往左扫描开始往左扫描,直至找到满足关系直

28、至找到满足关系a aj-1j-1 a aj j的终结符为止的终结符为止,进行归约。进行归约。此时此时,形如形如N Nj j a aj j N Nj+1j+1 a aj+1j+1.N.Ni i a ai i N Ni+1i+1的子串的子串即为即为最左素短语最左素短语，应被应被归约归约。分析过程的结束：分析栈中为分析过程的结束：分析栈中为#S#S，输入串为输入串为#。k=1;sk=#;do把下一个输入符号读进把下一个输入符号读进a中中;if（skVt）j=kelsej=k-1;while（sja）doQ=sj;if(sj-1Vt)j=j-1;elsej=j-2;while(sjQ);把把sj+1.

29、sk归约为某个归约为某个N；k=j+1;sk=N;if(sja|sj=a)k=k+1;sk=a;elseerror();while(a!=#);分分析析算算法法描描述述【例例3.13】已知文法已知文法GE和优先关系表如下，和优先关系表如下，GE:EE+T|TTT*F|FF(E)|i试给出输入串试给出输入串i+ii+i*i*i的算符优先分析过程。的算符优先分析过程。i+ii+i*i*i算符优先分析过程算符优先分析过程符号栈符号栈输入串输入串动作动作i+i*i i i，移进，移进i+i*i+，归，归约约F+i*i+，移进，移进F+i*i+i，移进，移进F+i*i+*，归，归约约i+ii+i*i*i

30、算符优先分析过程（续）算符优先分析过程（续）F+F*i+*，移进，移进F+F*i+*i，移进，移进F+F*i+*#，归，归约约F+F*F+#，归约，归约F+T#，归约，归约EE#，结束，结束注意注意算符优先分析只关心句型中自左向右的算符优先分析只关心句型中自左向右的终结符序列终结符序列的优先关系的优先关系,不涉及终结符之不涉及终结符之间可能存在的非终结符间可能存在的非终结符,即即可认为这些非可认为这些非终结符是同一个符号终结符是同一个符号。算符优先分析比规范归约要快，跳过了算符优先分析比规范归约要快，跳过了所有形如所有形如PQ的产生式所对应的归约步的产生式所对应的归约步骤。（这也有可能会出错）

31、骤。（这也有可能会出错）算符优先函数算符优先函数为了节省存储空间（为了节省存储空间（n22n）和便于执和便于执行比较运算，用两个优先函数行比较运算，用两个优先函数f和和g，它它们是从终结符号的优先关系到整数的映们是从终结符号的优先关系到整数的映射。射。对一个终结符对一个终结符a，定义其左优先函数，定义其左优先函数f(a)和右优先函数和右优先函数g(a)。f称为称为入栈函数入栈函数，g称为称为比较函数比较函数。对于终结符号对于终结符号a a和和b b选择选择f f和和g g，使之满足：，使之满足：f f(a a)g g(b b)，如果，如果a a b b。注意：注意：注意：注意：(1)(1)构造

32、优先函数的算法不是唯一的。构造优先函数的算法不是唯一的。(2)(2)存在一组优先函数，那就存在无穷组优先函存在一组优先函数，那就存在无穷组优先函数。数。问题：问题：问题：问题：如何构造优先函数？如何构造优先函数？方法一方法一关系图法关系图法1、a VT，建立两个结点，建立两个结点fa和和ga，画出，画出n个终结符所对应个终结符所对应的的2n个结点个结点;2、a，b VT，若若a b或或ab，则从，则从fa至至gb画一条有向边；画一条有向边；若若a b或或ab，则从，则从gb至至fa画一条有向边；画一条有向边；3、对图中每个结点都赋予一个数，该数等于从该结点出、对图中每个结点都赋予一个数，该数等

33、于从该结点出发所能到达的所有结点的个数，赋给发所能到达的所有结点的个数，赋给fa的数作为的数作为f(a)，赋，赋给给gb的数作为的数作为g(b)；4、检查所构造出来的函数、检查所构造出来的函数f和和g，看它们同原来的关系表，看它们同原来的关系表是否有矛盾。如果没有矛盾，则是否有矛盾。如果没有矛盾，则f和和g就是所要的优先函数；就是所要的优先函数；如果有矛盾，那么就不存在优先函数。如果有矛盾，那么就不存在优先函数。.【例例】有算术表达式文法有算术表达式文法GE:EE+TTT*PPid构造该文法的优先函数。构造该文法的优先函数。gidfidf*g*g+f+方法二方法二由定义直接构造（迭代法）由定义

34、直接构造（迭代法）对于对于 a VT，令，令f(a)=g(a)=1，则：，则：1、如果、如果ab而而f(a)g(b)，则令，则令f(a)=g(b)+1;2、如果、如果ab而而f(a)g(b)，则令，则令g(b)=f(a)+1;3、如果、如果ab而而f(a)g(b)，则令，则令f(a)=g(b)=maxf(a),g(b);4、重复、重复13步直到过程收敛。如果重复过程中有步直到过程收敛。如果重复过程中有一个值大于一个值大于2n，则表明该算符优先文法不存在优，则表明该算符优先文法不存在优先函数。先函数。.算符优先分析法小结算符优先分析法小结优点优点简单、效率高简单、效率高能够处理部分二义性文法能够

35、处理部分二义性文法缺点缺点文法书写限制大文法书写限制大占用内存空间大占用内存空间大不规范、存在查不到的语法错误不规范、存在查不到的语法错误作业P883.133.143.16(3)3.5 LR3.5 LR分析法分析法本节重点：本节重点：LR分析方法与分析过程分析方法与分析过程LR(0)项目、项目集规范族及其构造项目、项目集规范族及其构造closure和和goto函数的定义函数的定义LR(0)文法及文法及LR(0)分析表的构造分析表的构造SLR(1)文法及文法及SLR(1)分析表的构造分析表的构造LR分析法分析法：是另一种有效的自底向上的分析方法，：是另一种有效的自底向上的分析方法，仍然是一种仍然

36、是一种“移进移进-归约归约”分析方法。分析方法。L从左向右扫描输入串从左向右扫描输入串（readfromLefttoright）；R构造最右推导的逆过程构造最右推导的逆过程（forconstructingaRightmostderivationinreverse）。）。大多数用上下文无关文法描述的高级语言的语法成大多数用上下文无关文法描述的高级语言的语法成分可以用分可以用LR分析器来识别。分析器来识别。LR分析分析根据当前分析栈中的符号串和向右顺序查根据当前分析栈中的符号串和向右顺序查看输入串的看输入串的K(K0)个符号就可以唯一确定分析的个符号就可以唯一确定分析的动作是移进还是归约。动作是移

37、进还是归约。LRLR分析法的优缺点分析法的优缺点优点：优点：比其他比其他“移进移进-归约归约”分析法，如算符优先分析法，如算符优先分析法使用更加广泛，识别效率高。分析法使用更加广泛，识别效率高。能用能用LL(1)分析法分析的所有文法都能使用分析法分析的所有文法都能使用LR方法来进行分析。方法来进行分析。LR分析法在自左至右扫描输入串的过程中分析法在自左至右扫描输入串的过程中就能发现其中的任何错误，并能准确地指出就能发现其中的任何错误，并能准确地指出出错位置。出错位置。缺点：缺点：手工构造分析表工作量太大。必须使用自动手工构造分析表工作量太大。必须使用自动生成器。如使用专用工具生成器。如使用专用

38、工具YACC。自底向上分析法的关键问题是如何确定自底向上分析法的关键问题是如何确定可归约可归约的串的串。LR分析法与算符优先方法一样，分析法与算符优先方法一样，LR方方法是通过求法是通过求句柄逐步归约句柄逐步归约来进行语法分析。来进行语法分析。在算符优先分析中，通过算符的优先关系得到在算符优先分析中，通过算符的优先关系得到可归约串（最左素短语），可归约串（最左素短语），LR方法中句柄是通方法中句柄是通过求过求活前缀活前缀而求得。而求得。LRLR分析法的关键问题及解决方案分析法的关键问题及解决方案关键问题：关键问题：寻找句柄。寻找句柄。LR分分析析方方法法的的基基本本思思想想是是：在在规规范范归

39、归约约过过程程中中，一一方方面面记记住住已已移移进进和和归归约约出出的的整整个个符符号号串串(历历史史)，另另一一方方面面又又根根据据所所用用产产生生式式推推测测未未来来可可能能碰碰到到的输入符号的输入符号(对未来的展望对未来的展望)。当当某某一一符符号号串串类类似似于于句句柄柄出出现现在在栈栈顶顶时时，需需要要根根据据已已记记载载的的“历历史史”、“展展望望”和和“现现实实”的的输输入入符符号号三三方方面面的的内内容容来来决决定定栈栈顶顶的的符符号号串串是是否否构构成了真正的句柄，是否需要归约。成了真正的句柄，是否需要归约。3.5.1 LR3.5.1 LR分析器的工作原理分析器的工作原理一个

40、一个LR分析器由分析器由3个部分组成：个部分组成：LR分析程序分析程序：又称：又称总控程序总控程序。所有的。所有的LR分析器都是相同的。分析器都是相同的。分分析析表表(分分析析函函数数)：不不同同的的文文法法分分析析表表不不同同，同同一一个个文文法法采采用用的的LR分分析析器器不不同同时时，分分析析表表也也不不同同，分分析析表表又又可可分分为为动动作作表表(ACTION)和和状状态态转换转换(GOTO)表表两个部分，它们都可用二维数组表示。两个部分，它们都可用二维数组表示。分析栈分析栈：包括文法符号栈和相应的状态栈，它们均是先进后出栈。：包括文法符号栈和相应的状态栈，它们均是先进后出栈。状态栈

41、：状态栈：(S0,#)为预先放为预先放到栈中的初始状态和符号。到栈中的初始状态和符号。文法符号：文法符号：X1X2Xm是是目前已移进并归约出的句目前已移进并归约出的句型部分。其实它是多余的，型部分。其实它是多余的，已经概括到状态里。已经概括到状态里。分析器分析器实际上是一个带有先进后出栈的确定的有穷自动机。将实际上是一个带有先进后出栈的确定的有穷自动机。将“历史历史”和和“展望展望”综合成综合成“状态状态”，分析栈用来存放状态，分析栈用来存放状态，状态概括了从分析开始直到某一归约阶段的全部历史和展望资状态概括了从分析开始直到某一归约阶段的全部历史和展望资料，只需料，只需根据栈顶状态和输入符号就

42、可以唯一决定下一个动作根据栈顶状态和输入符号就可以唯一决定下一个动作。LR分析器结构 LR 分析表分析表-使用两张表，使用两张表，动作表动作表(ACTION)和和状态转换状态转换(GOTO)表表ACTION表表告诉分析控制程序：在栈顶状态为告诉分析控制程序：在栈顶状态为k,当前当前输入符号是输入符号是a时做什么时做什么?ACTIONk,a=si，移进移进Shift：状态状态i 移进栈顶移进栈顶ACTIONk,a=rj，归约归约Reduce：按第按第j 条产生式归约条产生式归约ACTIONk,a=acc，接受接受Accept：分析完成分析完成ACTIONk,a=err，出错出错Error：发现错

43、误，发现错误，空白空白GOTO表表GOTOi,A=j告诉分析控制程序：告诉分析控制程序：在依产生式在依产生式A 归约之后，栈顶状态为归约之后，栈顶状态为i 时，要将新时，要将新状态为状态为j 移进栈顶。移进栈顶。（依产生式（依产生式A 归约时，要将栈顶的归约时，要将栈顶的|个状态弹出）个状态弹出）显然：分析表定义了一个以文法符号为字母表的显然：分析表定义了一个以文法符号为字母表的DFA DFA。用三元式用三元式:(状态栈，符号栈，输入符号状态栈，符号栈，输入符号)表示分析过程中状态栈，符号栈，输入符号的变化。表示分析过程中状态栈，符号栈，输入符号的变化。将将初始初始状态状态S0和和#进分析栈。

44、三元式为：进分析栈。三元式为：(S0,#,a1a2an#)任一时刻的三元式为：任一时刻的三元式为：(S0S1Sm,#X1X2Xm,aiai+1an#)分析器的分析器的下一步动作下一步动作是由栈顶状态是由栈顶状态Sm和和当前面临的当前面临的输入符号输入符号ai唯一确定的。唯一确定的。LRLR分析过程分析过程根据栈顶状态根据栈顶状态Sm和输入符号和输入符号ai查查action表表,根据表中的内根据表中的内容不同完成不同的动作，若容不同完成不同的动作，若actionSm,ai为：为：移进移进Si：当前输入符号当前输入符号ai进符号栈，下一输入符号变成进符号栈，下一输入符号变成当前输入符号，将当前输入

45、符号，将action表中指出的状态表中指出的状态Si进状态栈进状态栈。三元式变为：三元式变为：(S0S1SmSi,#X1X2Xmai,ai+1an#)归约归约ri：按某个产生式按某个产生式A(其其编编号号为为i)i)进行归约，若进行归约，若产生式的右端长度为产生式的右端长度为r，则两个栈顶的则两个栈顶的r个元素同时出个元素同时出栈。将归约后的符号栈。将归约后的符号A进符号栈进符号栈;根据新栈顶状态根据新栈顶状态Sm-r和归约符号和归约符号A查查goto表，表，S=gotoSm-r,A进状态栈。三进状态栈。三元式变为：元式变为：(S0S1Sm-rS,#X1X2Xm-rA,aiai+1an#)接受

46、：接受：分析成功，终止分析。三元式不再变化。分析成功，终止分析。三元式不再变化。出错：出错：报告出错信息。三元式的变化过程终止。报告出错信息。三元式的变化过程终止。为了介绍为了介绍LR分析过程，直分析过程，直接给出该文法的分析表，接给出该文法的分析表，以后再介绍如何生成。以后再介绍如何生成。状状态态ACTIONGoToi+*()#E TF0 0S5S41231 1S6acc2 2r2S7r2r23 3r4r4r4r44 4S5S48235 5r6r6r6r66 6S5S4937 7S5S4108 8S6S119 9r1S7r1r11010r3r3r3r31111r5r5r5r5ri表示按第表示

47、按第i个产生个产生式进行归约式进行归约Si表示把当前输入表示把当前输入符号移进栈，第符号移进栈，第i个个状态进状态栈。状态进状态栈。i表示转第表示转第i个状态，个状态，即第即第i个状态进状个状态进状态栈。态栈。空白表示分空白表示分析动作出错析动作出错LRLR分析过程举例分析过程举例(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi产生式产生式的序号的序号设文法为设文法为GE：根据上述分析表，对输入串根据上述分析表，对输入串i*i+i的分析过程如下：的分析过程如下：序号序号状态栈状态栈符号栈符号栈产生式产生式输入串输入串说明说明10#i*i+i#0和和#进栈进栈205#i*

48、i+i#i和和S5进栈进栈303#FFi*i+i#i和和S5退栈退栈,F和和S3进栈进栈402#TTF*i+i#F和和S3退栈退栈,T和和S2进栈进栈5027#T*i+i#*和和S7进栈进栈60275#T*i+i#i和和S5进栈进栈702710#T*FFi+i#i和和S5退栈退栈,F和和S10进栈进栈802#TTT*F+i#F*T和和S10,7,2退栈退栈,T和和S2进栈进栈901#EET+i#T和和S2退栈退栈,E和和S1进栈进栈10016#E+i#+和和S6进栈进栈110165#E+i#i和和S5进栈进栈120163#E+FFi#i和和S5退栈退栈,F和和S3进栈进栈130169#E+TT

49、F#F和和S3退栈退栈,T和和S9进栈进栈1401#EEE+T#T+E和和S9,6,1退栈退栈,E和和S1进栈进栈LR文法：文法：对一个对一个文法文法，如果能够构造一张，如果能够构造一张LR分析表，使得它的每个入口均是唯一的。分析表，使得它的每个入口均是唯一的。说明：说明：对于一个对于一个LR文法，当分析器对输入串进文法，当分析器对输入串进行自左至右的扫描时，一旦句柄出现于栈顶，行自左至右的扫描时，一旦句柄出现于栈顶，就能及时对它实行归约。就能及时对它实行归约。LR分析法解决了语法分析过程中寻找每一次归分析法解决了语法分析过程中寻找每一次归约的约的句柄句柄问题。问题。注意：注意：并非所有的上下

50、文无关文法都是并非所有的上下文无关文法都是LR文法，文法，但对于大多数程序设计语言而言，都可以用但对于大多数程序设计语言而言，都可以用LR文法描述。文法描述。重点：如何由文法构造重点：如何由文法构造LR分析表？分析表？-移进移进 归约归约（shift-reduce）冲突冲突归约归约 归约归约（reduce-reduce）冲突冲突移进移进-归约分析过程确定化的关键：归约分析过程确定化的关键：解决两类冲突解决两类冲突对应解决方法不同，主要有对应解决方法不同，主要有四种四种LR分析方分析方法法，它们的分析表也有不同。后面将以，它们的分析表也有不同。后面将以LR(0)分析表分析表的构造方法为基础介绍。