[理学]第四章2 自下而上语法分析ppt课件

1、第四章第四章2 2 自下向上语法分析自下向上语法分析本章要求本章要求:1. 掌握自下向上语法分析的根本思想和根本概念掌握自下向上语法分析的根本思想和根本概念2. 理解算符优先语法分析；求理解算符优先语法分析；求FIRSTVT集和集和LASTVT集，构造算符优先关系表；能运用算集，构造算符优先关系表；能运用算符优先分析方法进展表达式分析选学符优先分析方法进展表达式分析选学3. 掌握句柄的定义与断定掌握句柄的定义与断定4. 理解标准归约的过程和理解标准归约的过程和LRLR分析过程中的实现分析过程中的实现 5. 掌握掌握LR语法分析的实现过程语法分析的实现过程例例S aABe A Abc | bB

2、d用归约的方法对句子用归约的方法对句子abbcde进展语法分析。进展语法分析。例例S aABe A Abc | bB dabbcde例例S aABe A Abc | bB dabbcdeaAbcdeaAbcde例例S aABe A Abc | bB dabbcdeaAbcdeaAde例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABe例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS 例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm

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

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

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

6、 在栈里符号串中找到一个可归约在栈里符号串中找到一个可归约串串； 归约可归约串 while 文法开场符号出如今栈顶或者发现错误；分析成功的条件分析成功的条件：栈顶为文法符号，输入串为空。该过程并未涉及如何在栈里找可归约串。实际上，不同的找可归约串的方法，构成了不同的分析算法。分析器的四种动作分析器的四种动作 1 1 移进移进：读入下一个输入符号并把它下推进栈。 2 2 归约归约：当栈顶符号串形成一个可归约的串如：句句柄柄时，直接进展归约，即用产生式左侧的非终结符交换栈顶的句柄。 3 3 承受承受：当栈底只有“#和开场符号，而输入也已经到达右端标志符号“#时，识别出符号串是句子，执行该动作，表示

7、分析成功，是归约的一种特殊情况。 4 4 出错出错：栈顶的内容与输入符号相悖，即当识别程序发现输入符号串不是句子时，进展出错处理。 注意：决定移进和归约的根据是什么？注意：决定移进和归约的根据是什么？ 栈顶是否出现了可归约的符号串。栈顶是否出现了可归约的符号串。 “移进归约语法分析小结： 从输入串的开场依次读入单词移进移进栈中 。 一旦发现可归约串可归约串某个产生式的右端就立即归归约约。 归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复屡次，然后继续移进。 假设最终能归约成文法的开场符号，那么分析成功承受承受；否那么出错出错。 由于总是将句型的最左边的可归约串交换成非终结符，该方法

8、通常得到是最右推导。 关键是如何识别可归约的符号串如何识别可归约的符号串？语法分析中问题的提出：语法分析中问题的提出： 在构造语法树的过程中，何时归约？ 当可归约串出如今栈顶时就进展归约。 如何知道在栈顶符号串中已经形成可归约串？ 如何进展归约？ 通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约边移进边归约。规范归约：使用句柄句柄来定义可归约串算符优先：使用最左素短语最左素短语来定义可归约串 自下而上语法分析主要有以下三种方法：自下而上语法分析主要有以下三种方法：简单优先分析法简单优先分析法标准归约标准归约文法按文法按一定原那么

9、规定文法符号的优先关系一定原那么规定文法符号的优先关系算符优先分析法算符优先分析法不标准归约不标准归约规定规定算符算符之间的优先关系之间的优先关系 LR分析法标准归约分析法标准归约 LR0、LR1、SLR1和和LALR1语法分析树的生成演示语法分析树的生成演示a b b c d ea b b c d eAABSAbAbAAbcAAbcBdBdSaABeSaABe1S aABe2A b 3A Abc4B dS aABe aAde aAbcde abbcde标准归约相关概念复习 有文法G，开场符号为S, 假如有S=xy,那么xy是文法G的句型句型，x,y是任意的符号串 假如有S=xAy, 且有A=

10、,那么是句型xy相对于非终结符A的短语短语 假如有S=xAy, 且有A-,那么是句型xy相对于A-的直接短语直接短语 位于一个一个句型最左边的直接短语称为句柄句柄. 句型- 短语 - 直接短语 -句柄 *+*注: 每次归约的部分就是分析为句柄句柄的字符串最右推导。在标准归约中，关键问题就转化为如何识别句柄如何识别句柄? ?回到上例用回到上例用句柄句柄对句子对句子abbcde进展归约有：进展归约有： 用句柄对句子进展归约的过程与用移进-归约过程是一致的，使用归约的产生式及其顺序是一致的。句型归约规那么abbcde1S aABe2A b 3A Abc4B d2 Ab3A AbcaAbcdeaAde

11、4B d1S aABeaABeS练习：有文法如下练习：有文法如下 E-E+T|T T-T*F|F F-E|id1写出输入串写出输入串 id1+id2*id3 的标准归约过程；的标准归约过程；2给出该文法给出该文法“移进移进-归约语法分析的过程。归约语法分析的过程。E=E+T =E+T*F =E+T*id =E+F*id =E+id*id =T+id*id =F+id*id =id+id*id 动作动作 栈栈 输入缓冲区输入缓冲区1 1 准备准备 # id# id1 1+id+id2 2* *idid3 3# #2 2 移进移进 #id#id1 1 +id +id2 2* *idid3 3# #

12、3 3 归约归约 Fid #F +idFid #F +id2 2* *idid3 3# #4 4 归约归约 TF #T +idTF #T +id2 2* *idid3 3# # 5 5 归约归约 ET #E +idET #E +id2 2* *idid3 3# #6 6 移进移进 #E+ id#E+ id2 2* *idid3 3# #7 7 移进移进 #E+id#E+id2 2 * *idid3 3# #8 8 归约归约 Fid #E+F Fid #E+F * *idid3 3# #9 9 归约归约 TF #E+T TF #E+T * *idid3 3# # 1010 移进移进 #E+T#E

13、+T* * id id3 3# #1111 移进移进 #E+T#E+T* *idid3 3 # #1212 归约归约 Fid #E+TFid #E+T* *F #F #1313 归约归约 TTTT* *F #E+T #F #E+T #1414 归约归约 EE+T #E # EE+T #E # 1515 承受承受所得的结果是：用产生式序列表示语法分析树所得的结果是：用产生式序列表示语法分析树E-E+T|TT-T*F|FF-E|ididid1 1 + id + id2 2 * * id id3 3FTEFTFTE移进归约分析中的问题移进归约分析中的问题 1 1 移进移进- -归约冲突归约冲突 在分

14、析到某一步时，既可以移进，又可以归约上例第10步可以移进*，也可以按产生式EE+T进展归约。 2 2 归约归约- -归约冲突归约冲突存在两个可选的句柄，可对栈顶符号进展归约例如上述第13步，可以用TF进展归约，又可以按TT*F进展归约。 各种分析方法中处理冲突的技术不同各种分析方法中处理冲突的技术不同算符优先分析算符优先分析 算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归约串。 将句型中的终结符号当作“算符，借助于算符之间的优先关系确定句柄。 显然，在一个符号串中，任意两个相邻终结符号a和b之间，只可能存在以下四种优先关系：1 a, b优先性一样，记作a b。2

15、a优先性高于b， 记作a b。3 a优先性低于b ，记作a b。4 a与b不可能相邻，即此符号串不是句型出错。 假如以上四种关系中的任意两种都不会同时成立，那么可以根据终结符号之间的归约关系进展语法分析。 1.算符文法:一个上下无关文法G,假如没有P-,且没有P-.QR.P,Q,R属于非终结符,那么G是一个算符文法。算符文法。 2.算符优先关系算符优先关系的定义自底向上,可通过树形构造观察 a b,G中有P-.ab.或P-.aQb. 在同一产在同一产生式中生式中a b,G中有P-.aR.的产生式,且R=b.或R=Qb. 注意注意ab相邻相邻a b,G中有P-.Rb.的产生式,且R=.a或R=.

16、aQ 注意注意ab相邻相邻算符优先文法的定义+例：EE+E | E*E | E | i 证明不是算符优先文法。因为：EE+E ， EE*E 那么有 + *又因为：EE*E, EE+E 那么有 + *所以不是算符优先文法。 3.算符优先文法算符优先文法算符文法G的任何终结符a,b之间要么没有优先关系，假设有优先关系,至多有 = , 中的一种成立,那么G为一算符优先文法算符优先文法。算符优先关系表算符优先关系表的构造的构造 用表格形式来表示各终结符号的优先关用表格形式来表示各终结符号的优先关系，这种表称为优先表。系，这种表称为优先表。 构造优先关系表的方法：构造优先关系表的方法： 按照定义手工计算

17、按照定义手工计算 使用算法使用算法 由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有关系: # # * 在优先表中，空白部分是一种错误关系 一样的终结符之间的优先关系不一定是 假如有a b,不一定有b a不具传递性，因为只定义相邻运算符之间的优先关系，a,b相邻时，不一定b,a相邻。 a,b之间未必有优先关系 , , 算符优先关系表的构造

18、算法算符优先关系表的构造算法 1.FIRSTVT1.FIRSTVT集集定义：对每个非终结符P, FIRSTVTP=a|P=a.或P=Qa.,a为终结符,P，Q为非终结符+由优先性低于的定义和FIRSTVT集合的定义可以得出：若存在某个产生式：aP，对所有：bfirstVT(P)都有：a a.或P-Qa.,那么aFIRSTVTP 假设有产生式P-R.,那么FIRSTVTR包含在FIRSTVTP中abcPQ所有终结符所有非终结符数组值为真假，为真的条件是c FIRSTVTQ 通过构造一个二维数组F来实现,该从数组F反映任何一个非终结符P的FIRSRVT集中的元素。步骤： 先用第一条规那么进展初始化

19、先用第一条规那么进展初始化 使用第二条规那么对数组使用第二条规那么对数组F F进展修改，进展修改，修改方法是： 1 用一个栈，将所有F数组中值为真的元素FP,a的符号对P,a压入堆栈； 2 对栈施行如下操作：假设栈不空，将栈顶符号对出栈，记为Q,a，检查所有的产生式，假设有形为：PQ的产生式，且FP,a为假，那么使FP,a为真，且将P,a压入堆栈； 3 重复这一过程，直到栈空求文法各非终结符的firstVT： 定义数组：+*iE1T1F11EE+T | TTT*F | FFE | i11111从而得到：从而得到：FirstVTE = +, *, IFirstVTT = *,IFirstVTF

20、= ,IBeginFor 对每个非终结符对每个非终结符P和终结符和终结符a doFP,a = falseFor 对每个形如对每个形如Pa或或PQa的产生式的产生式 doInsertP,aWhile stack 非空非空Begin把栈顶项出栈，记为把栈顶项出栈，记为Q,aFor 对每条形如对每条形如PQ的产生式的产生式 do insertP,aEnd;End.PROCEDURE insertP,a;IF not FP,a then begin fp,a = true; P,a进进栈栈 end;对数组初始化应用规那么1应用规那么2 2. 求求LASTVT集集 定义：LASTVTP=a|P = .a

21、或P =. aQ,a为终结符,P，Q为非终结符+构造LASTVT集算法: 考虑？ 3.3.构造优先关系表构造优先关系表假如每个非终结符的FIRSTVT和LASTVT集均,那么可构造优先关系表。假设产生式右部有.aP.的形式,那么对于每个bFIRSTVTP都有a b优先集假设产生式右部有.Pb的形式,那么对于每个aLASTVTP集,都有a b 假设产生是形如：Aab 或 AaBb形式，那么有a b 构造优先关系表的算法如下：For 每条形如每条形如PX1X2Xn的的产生式产生式 dofor i =1 to n-1 dobeginif Xi和和Xi+1都是终结符都是终结符 then Xi = Xi

22、+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;构造优先关系表算符优先分析算法算符优先分析算法 通过比较终结符间的优先关系来实现 根据优先分析的原理原理：语法分析程序的任务是：不断移进输入符号，识别句柄并进展归约。 分析的方法分析的方法：根据优先性“高于来识别句柄的头，根据优先性“低于来识别句柄的尾。各种优先关系已经存于优先关系表中。 1.不能识别只由一个非终结符组

23、成的句柄。不能保证每次对句柄进展归约,在算符优先分析过程中,每次归约的符号串,是当前句型的最左素短语. 2.素短语：素短语：至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。 3.最左素短语最左素短语leftmost prime leftmost prime phrasephrase：是指位于句型最左边的那个素短语。例：下述文法的一个句型： T * F + i 其短语、素短语、最左素短语分别是？ET | E+TTF | T*FFi | EEE + TFiTT * F短语有：i, T * F, T * F + i素短语有： i, T * F最左素短语是：T * F 一个算符文法一个算

24、符文法G的某个句型的最左素短语可描述：的某个句型的最左素短语可描述：设句型的一般形式为设句型的一般形式为(NiVVN N,ai VVT T#N1a1 N2a2 Nnan #它的它的最左素短语最左素短语是满足下列条件的最左子串：是满足下列条件的最左子串：Niai Ni+1ai+1 Njaj Nj+1其中：其中：ai-1ai, aiai+1.aj-1aj ， ajaj+1该定理说明了最左素短语与周围符号之间的关系 例:文法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

25、的短语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不含终结符也不是素短语T*F为最左素短语最左素短语。 3.算符优先分析过程：根据最左素短语的定义句型句型的一般形式: #N1a1N2a2.NnanNn+1#ai为终结符,Ni为可有可无的非终结符从左向右扫描各符号,依次查看算符优先矩阵,直至找到满足ai ai+1的终结符为止,一直移进.再从ai开场往左扫描,直至找到满足关系aj-1 aj的终结符为止,进展归约。此时,形如:Nj aj Nj+1 aj+1.Ni ai Ni+1的子串即为最左素短语，应被归约。分析过程的完毕：分析栈中为#S，输入串为# 例: E-E+T|T T-T*F|FF-E|i 把#入栈,读一符号i, 因为# + ,所以归约:F-i 因# + , 所以+入栈 因+ * , 所以归约:F-i 因+ * , 所以*入栈 因* # , 所以归约:F-i 因* # , 所以归约:T-F*F 因+ # , 所以归约:E-T+F 分析成功求i+i*i的算符优先分析过