理学自下而上语法分析.pptx

《理学自下而上语法分析.pptx》由会员分享，可在线阅读，更多相关《理学自下而上语法分析.pptx（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、例例S aABe A Abc|bB dabbcde 第1页/共51页例例S aABe A Abc|bB dabbcdeaAbcdeaAbcde 第2页/共51页例例S aABe A Abc|bB dabbcdeaAbcdeaAde 第3页/共51页例例S aABe A Abc|bB dabbcdeaAbcdeaAdeaABe 第4页/共51页例例S aABe A Abc|bB dabbcdeaAbcdeaAdeaABeS 第5页/共51页例例S aABe A Abc|bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm abbcde第

2、6页/共51页自下而上的语法分析的一般过程自下而上的语法分析的一般过程实现思想实现思想从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一一旦旦栈栈顶顶符符号号串串形形成成某某个个产产生生式式的的右右部部时时，就用该产生式的左部非终结符代替，称为归归约约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功，称为“移进-归约”方法。从语语法法树树的的角角度度看：从语法树的树叶开始，逐步向上归约构造分析树，直到形成根结点。是推导推导的逆过程。第7页/共51页最左推导最左推导(Left-most Derive)每次推导都替换当前句型的最左边的非终结符。与最右归

3、约对应。最右推导最右推导(Right-most Derive)每次推导都替换当前句型的最右边的非终结符。与最左归约(规范归约规范归约)对应，得规范句型。例：例：设有文法GS：(1)S aABe (2)A b (3)A Abc (4)B d 使用最右推导：因为S aABe aAde aAbcde abbcde，所以abbcde是文法G的句子。第8页/共51页 步骤步骤动作动作(1)S aABe(2)A b(3)A Abc(4)B d最左归约过程是最右推导的逆过程，对输入串abbcde的移进归约过程如下：该分析过程反复执行该分析过程反复执行“移进移进”和和“归约归约”两个动作，直到栈中只有开始符号

4、为止。两个动作，直到栈中只有开始符号为止。ab aA ab A acbA aA ad A aBA aeBA aS1移进a2移进b3归约24移进b5移进c6归约37移进d8归约49移进e10归约1第9页/共51页“移进-归约”分析法中栈的使用移进-归约分析器使用了一个符号栈和一个输入缓冲区1、句型表示 a1 a2 a3#X1X2X3#“移进-归约”分析程序输出栈(存放句型前缀)输入串符号栈内容符号栈内容 +输入缓冲区内容输入缓冲区内容#当前句型当前句型#一般形式：符号栈的内容剩余输入串初态：#输入串#终态：#S#2、分析器结构 第10页/共51页3.过程描述：过程描述：do do 将输入串最左边

5、的符号移入栈内;while(在栈里符号串中找到一个可归约串在栈里符号串中找到一个可归约串)；归约可归约串 while （文法开始符号出现在栈顶或者发现错误）；分析成功的条件分析成功的条件：栈顶为文法符号，输入串为空。注意：注意：注意：注意：该过程并未涉及如何在栈里找可归约串。实际上，不同的找可归约串的方法，构成了不同的分析算法。第11页/共51页分析器的四种动作分析器的四种动作1)1)移进移进：读入下一个输入符号并把它下推进栈。2)2)归约归约：当栈顶符号串形成一个可归约的串（如：句句柄柄）时，直接进行归约，即用产生式左侧的非终结符替换栈顶的句柄。3)3)接受接受：当栈底只有“#”和开始符号，

6、而输入也已经到达右端标志符号“#”时，识别出符号串是句子，执行该动作，表示分析成功，是归约的一种特殊情况。4)4)出错出错：栈顶的内容与输入符号相悖，即当识别程序发现输入符号串不是句子时，进行出错处理。注意：决定移进和归约的依据是什么？注意：决定移进和归约的依据是什么？栈顶是否出现了可归约的符号串。栈顶是否出现了可归约的符号串。第12页/共51页“移进归约”语法分析小结：从输入串的开始依次读入单词(移进移进栈中)。一旦发现可归约串可归约串(某个产生式的右端)就立即归约归约。归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。若最终能归约成文法的开始符号，则分析成功（

7、接接受受）；否则出错出错。由于总是将句型的最左边的可归约串替换成非终结符，该方法通常得到是最右推导。关键是如何识别可归约的符号串如何识别可归约的符号串？第13页/共51页语法分析中问题的提出：语法分析中问题的提出：在构造语法树的过程中，何时归约？当可归约串出现在栈顶时就进行归约。如何知道在栈顶符号串中已经形成可归约串？如何进行归约？通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约边移进边归约。规范归约：使用句柄句柄来定义可归约串算符优先：使用最左素短语最左素短语来定义可归约串第14页/共51页自下而上语法分析主要有以下三种方法：

8、自下而上语法分析主要有以下三种方法：简单优先分析法简单优先分析法(规范归约规范归约)文法按文法按一定原则规定文法符号的优先关系一定原则规定文法符号的优先关系算符优先分析法算符优先分析法(不规范归约不规范归约)规定规定算符算符之间的优先关系之间的优先关系 LR分析法（规范归约）分析法（规范归约）LR(0)、LR(1)、SLR(1)和和LALR(1)第15页/共51页语法分析树的生成演示语法分析树的生成演示a b b c d ea b b c d eAABSAbAbAAbcAAbcBdBdSaABeSaABe(1)S aABe(2)A b(3)A Abc(4)B dS aABe aAde aAbc

9、de abbcde第16页/共51页规范归约相关概念复习有文法G，开始符号为S,如果有S=xy,则xy是文法G的句型句型，x,y是任意的符号串如果有S=xAy,且有A=,则是句型xy相对于非终结符A的短语短语如果有S=xAy,且有A-,则是句型xy相对于A-的直接短语直接短语位于一个一个句型最左边的直接短语称为句柄句柄.句型-短语-直接短语-句柄*+*注:每次归约的部分就是分析为句柄句柄的字符串(最右推导)。在规范归约中，关键问题就转化为如何识别句柄如何识别句柄?第17页/共51页回到上例用回到上例用句柄句柄对句子对句子abbcde进行归约有：进行归约有：用句柄对句子进行归约的过程与用移进-归

10、约过程是一致的，使用归约的产生式及其顺序是一致的。句型归约规则abbcde(1)S aABe(2)A b(3)A Abc(4)B d(2)Ab(3)A AbcaAbcdeaAde(4)B d(1)S aABeaABeS第18页/共51页练习：有文法如下练习：有文法如下(1)E-E+T|T(2)T-T*F|F(3)F-(E)|id1）写出输入串）写出输入串 id1+id2*id3 的规范归约过程；的规范归约过程；2）给出该文法）给出该文法“移进移进-归约归约”语法分析的过程。语法分析的过程。第19页/共51页E=E+T =E+T*F =E+T*id =E+F*id =E+id*id =T+id*

11、id =F+id*id =id+id*id第20页/共51页 动作动作 栈栈 输入缓冲区输入缓冲区1)1)准备准备#id#id1 1+id+id2 2*id*id3 3#2)2)移进移进#id#id1 1 +id +id2 2*id*id3 3#3)3)归约归约 Fid#F +idFid#F +id2 2*id*id3 3#4)4)归约归约 TF#T +idTF#T +id2 2*id*id3 3#5)5)归约归约 ET#E +idET#E +id2 2*id*id3 3#6)6)移进移进#E+id#E+id2 2*id*id3 3#7)7)移进移进#E+id#E+id2 2 *id *id3

12、 3#8)8)归约归约 Fid#E+F *idFid#E+F *id3 3#9)9)归约归约 TF#E+T *idTF#E+T *id3 3#10)10)移进移进#E+T*id#E+T*id3 3#11)11)移进移进#E+T*id#E+T*id3 3#12)12)归约归约 Fid#E+T*F#Fid#E+T*F#13)13)归约归约 TT*F#E+T#TT*F#E+T#14)14)归约归约 EE+T#E#EE+T#E#15)15)接受接受所得的结果是：用产生式序列表示语法分析树所得的结果是：用产生式序列表示语法分析树(1)E-E+T|T(2)T-T*F|F(3)F-(E)|ididid1 1

13、+id+id2 2 *id *id3 3FTEFTFTE第21页/共51页移进归约分析中的问题移进归约分析中的问题1)1)移进移进-归约冲突归约冲突 在分析到某一步时，既可以移进，又可以归约上例第10)步可以移进*，也可以按产生式EE+T进行归约。2)2)归约归约-归约冲突归约冲突存在两个可选的句柄，可对栈顶符号进行归约例如上述第13)步，可以用TF进行归约，又可以按TT*F进行归约。各种分析方法中处理冲突的技术不同各种分析方法中处理冲突的技术不同第22页/共51页第23页/共51页算符优先分析算符优先分析算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归约串。将句型

14、中的终结符号当作“算符”，借助于算符之间的优先关系确定句柄。显然，在一个符号串中，任意两个相邻终结符号a和b之间，只可能存在以下四种优先关系：(1)a,b优先性相同，记作a b。(2)a优先性高于b，记作a b。(3)a优先性低于b，记作a b。(4)a与b不可能相邻，即此符号串不是句型(出错)。如果以上四种关系中的任意两种都不会同时成立，则可以根据终结符号之间的归约关系进行语法分析。第24页/共51页1.算符文法:一个上下无关文法G,如果没有P-,且没有P-.QR.(P,Q,R属于非终结符),则G是一个算符文法。算符文法。2.算符优先关系算符优先关系的定义(自底向上,可通过树形结构观察)a

15、b,G中有P-.ab.或P-.aQb.(在同一产生在同一产生式中式中)a b,G中有P-.aR.的产生式,且R=b.或R=Qb.(注意注意ab相邻相邻)a b,G中有P-.Rb.的产生式,且R=.a或R=.aQ(注意注意ab相邻相邻)算符优先文法的定义+第25页/共51页例：EE+E|E*E|(E)|i 证明不是算符优先文法。因为：EE+E，EE*E 则有+*又因为：EE*E,EE+E 则有+*所以不是算符优先文法。3.算符优先文法算符优先文法算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有=,中的一种成立,则G为一算符优先文法算符优先文法。第26页/共51页算符优先关系

16、表算符优先关系表的构造的构造 用表格形式来表示各终结符号的优先关用表格形式来表示各终结符号的优先关系，这种表称为优先表。系，这种表称为优先表。构造优先关系表的方法：构造优先关系表的方法：按照定义手工计算按照定义手工计算使用算法使用算法 第27页/共51页由F-(E)得(=)T =i,得+T*F,得+(E),得+E+TE=i,得i +E =E+T,得+E =T*F,得*+E =(E),得)+*i()#+*i()#例:P:E-E+T|T T-T*F|F F-(E)|i 求算符优先表。终结符+#终结符+#对于结束符#和其它终结符a有关系:#*第28页/共51页在优先表中，空白部分是一种错误关系相同的

17、终结符之间的优先关系不一定是如果有a b,不一定有b a(不具传递性)，因为只定义相邻运算符之间的优先关系，a,b相邻时，不一定b,a相邻。a,b之间未必有优先关系(,)第29页/共51页算符优先关系表的构造算法算符优先关系表的构造算法1.FIRSTVT1.FIRSTVT集集定义：对每个非终结符P,FIRSTVT(P)=a|P=a.或P=Qa.,a为终结符,P，Q为非终结符+由优先性低于的定义和FIRSTVT集合的定义可以得出：若存在某个产生式：aP，对所有：bfirstVT(P)都有：a a.或P-Qa.,则aFIRSTVT(P)若有产生式P-R.,则FIRSTVT(R)包含在FIRSTVT

18、(P)中abcPQ所有终结符所有非终结符数组值为真假，为真的条件是c FIRSTVT(Q)通过构造一个二维数组F来实现,该从数组F反映任何一个非终结符P的FIRSRVT集中的元素。步骤：先用第一条规则进行初始化先用第一条规则进行初始化第31页/共51页使用第二条规则对数组使用第二条规则对数组F F进行修改，进行修改，修改方法是：(1)用一个栈，将所有F数组中值为真的元素FP,a的符号对(P,a)压入堆栈；(2)对栈施行如下操作：若栈不空，将栈顶符号对出栈，记为(Q,a)，检查所有的产生式，若有形为：PQ的产生式，且FP,a为假，则使FP,a为真，且将(P,a)压入堆栈；(3)重复这一过程，直到

19、栈空第32页/共51页求文法各非终结符的firstVT：定义数组：+*()iE1T1F11EE+T|TTT*F|FF(E)|i11111从而得到：从而得到：FirstVT(E)=+,*,(,IFirstVT(T)=*,(,IFirstVT(F)=(,I第33页/共51页BeginFor 对每个非终结符对每个非终结符P和终结符和终结符a doFP,a=falseFor 对每个形如对每个形如Pa或或PQa的产生式的产生式 doInsert(P,a)While stack 非空非空Begin把栈顶项出栈，记为把栈顶项出栈，记为(Q,a)For 对每条形如对每条形如PQ的产生式的产生式 do inse

20、rt(P,a)End;End.PROCEDURE insert(P,a);IF not FP,a then begin fp,a=true;(P,a)进栈进栈 end;对数组初始化应用规则1应用规则2第34页/共51页2.求求LASTVT集集 定义：LASTVT(P)=a|P=.a或P=.aQ,a为终结符,P，Q为非终结符+构造LASTVT集算法:(思考？)第35页/共51页3.3.构造优先关系表构造优先关系表如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。若产生式右部有.aP.的形式,则对于每个bFIRSTVT(P)都有a b(优先集)若产生式右部有.Pb的形式,

21、则对于每个aLASTVT(P)集,都有a b 若产生是形如：Aab 或 AaBb形式，则有a b构造优先关系表的算法如下：第36页/共51页For 每条形如每条形如PX1X2Xn的的产生式产生式 dofor i=1 to n-1 dobeginif Xi和和Xi+1都是终结符都是终结符 then Xi =Xi+1if i=n-2 且且 xi和和Xi+2都是终结符都是终结符,Xi+1为非终结符为非终结符 then Xi =Xi+2if Xi为终结符为终结符,Xi+1为非终结符为非终结符 then for firstVT中的每个元素中的每个元素a do Xi Xi+1;end;构造优先关系表第37

22、页/共51页算符优先分析算法算符优先分析算法通过比较终结符间的优先关系来实现根据优先分析的原理原理：语法分析程序的任务是：不断移进输入符号，识别句柄并进行归约。分析的方法分析的方法：根据优先性“高于”来识别句柄的头，根据优先性“低于”来识别句柄的尾。各种优先关系已经存于优先关系表中。第38页/共51页1.不能识别只由一个非终结符组成的句柄。不能保证每次对句柄进行归约,在算符优先分析过程中,每次归约的符号串,是当前句型的最左素短语.2.素短语：素短语：至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。3.最左素短语最左素短语(leftmost prime phrase)(leftmo

23、st prime phrase)：是指位于句型最左边的那个素短语。第39页/共51页例：下述文法的一个句型：T*F+i 其短语、素短语、最左素短语分别是？ET|E+TTF|T*FFi|(E)EE +TFiTT *F短语有：i,T*F,T*F+i素短语有：i,T*F最左素短语是：T*F第40页/共51页一个算符文法一个算符文法G的某个句型的最左素短语可描述：的某个句型的最左素短语可描述：设句型的一般形式为设句型的一般形式为(NiVVN N,ai VVT T#N1a1 N2a2 Nnan#它的它的最左素短语最左素短语是满足下列条件的最左子串：是满足下列条件的最左子串：Niai Ni+1ai+1 N

24、jaj Nj+1其中：其中：ai-1ai,aiai+1.aj-1aj，ajaj+1该定理说明了最左素短语与周围符号之间的关系第41页/共51页例:文法G E-E+T|T T-T*F|F F-(E)|i句型T+T*F+i的语法树如图：EET+E+TFTT*FPi根据语法树可知：句型#T+T*F+i#的短语短语有：T 相对非终结符E的短语T*F 相对非终结符T的短语T+T*F 相对非终结符E的短语i 相对非终结符P、F、T的短语T+T*F+i 相对非终结符E的短语根据素短语素短语的定义可知：i和T*F为素短语。其中：T+T*F (含T*F素短语)、T+T*F+i(含T*F素短语)和 T(不含终结符

25、)也不是素短语T*F为最左素短语最左素短语。第42页/共51页3.算符优先分析过程：(根据最左素短语的定义)句型句型的一般形式:#N1a1N2a2.NnanNn+1#(ai为终结符,Ni为可有可无的非终结符)从左向右扫描各符号,依次查看算符优先矩阵,直至找到满足ai ai+1的终结符为止,一直移进.再从ai开始往左扫描,直至找到满足关系aj-1 aj的终结符为止,进行归约。此时,形如:Nj aj Nj+1 aj+1.Ni ai Ni+1的子串即为最左素短语，应被归约。分析过程的结束：分析栈中为#S，输入串为#第43页/共51页例:E-E+T|T T-T*F|FF-(E)|i把#入栈,读一符号i

26、,因为#+,所以归约:F-i因#+,所以+入栈 因+*,所以归约:F-i因+*,所以*入栈 因*#,所以归约:F-i因*#,所以归约:T-F*F因+#,所以归约:E-T+F分析成功求i+i*i的算符优先分析过程栈栈 输入缓冲区输入缓冲区#i+i*i#i+i*i#i +i*i#+i*i#F +i*i#+i*i#F+i*i#i*i#F+i *i#*i#F+F *i#*i#F+F*i#i#F+F*i#F+F*F#F+T#E#第44页/共51页k:=1;sk=#;Repeat a:=下一个输入符号下一个输入符号;If sk Vt THEN j:=k ELSE j:=k-1;WHILE sj a DO

27、BEGINrepeatq:=sj;if sj-1 Vt THEN j:=j-1 else j:=j-2;UNTIL sj q;把把sj+1.sk归约为某个归约为某个N；k:=j+1;sk:=N;ENDIf sj a or sj =a THEN begin k:=k+1;sk:=a;end;else error;UNTIL a=#;第45页/共51页算符优先分析一般并不等价于规范规约并不对文法的非终结符定义优先关系，无法发现由单个非终结符组成的“可归约串”。即无法使用单非产生式(如：TF)进行归约。算符优先分析比规范归约过程要快，跳过了所有的单非产生式。可能将本来不是句子的输入串误认为是句子。第

28、46页/共51页总结归约的策略:在文法中寻找这样的产生式:它的右部形如:uj aj uj+1 aj+1.ui ai ui+1,其中每个终结符号与最左素短语对应位置上的终结符号完全相同终结符号完全相同,而每一个非终结符号非终结符号uk应与相应位置上的非终结符号Nk相对应,不必完全相同不必完全相同。第47页/共51页算符优先分析法小结算符优先分析法小结优点优点简单、效率高简单、效率高能够处理部分二义性文法能够处理部分二义性文法缺点缺点文法书写限制大文法书写限制大占用内存空间大占用内存空间大不规范、存在查不到的语法错误不规范、存在查不到的语法错误第48页/共51页设文法为：设文法为：E#E#TF EE+T FPF|P ET P（E）TT*F PI求算符优先关系表。求算符优先关系表。(分析过程见吕映芝课本分析过程见吕映芝课本)练习第49页/共51页第50页/共51页感谢观看！感谢观看！第51页/共51页