《自下而上语法分析》PPT课件.ppt

第四章(2) 自下向上语法分析,本章要求: 1. 掌握自下向上语法分析的基本思想和基本概念 2. 了解算符优先语法分析；求FIRSTVT集和LASTVT集，构造算符优先关系表；能运用算符优先分析方法进行表达式分析（选学） 3. 掌握句柄的定义与判定 4. 理解规范归约的过程和LR分析过程中的实现 5. 掌握LR语法分析的实现过程,回顾: 归约和推导的概念 例S aABe A Abc | b B d 用归约的方法对句子abbcde进行语法分析。,例S aABe A Abc | b B d abbcde,例S aABe A Abc | b B d abbcde aAbcde aAbcde,例S aABe A Abc | b B d abbcde aAbcde aAde,例S aABe A Abc | b B d abbcde aAbcde aAde aABe,例S aABe A Abc | b B d abbcde aAbcde aAde aABe S,例S aABe A Abc | b B d abbcde aAbcde aAde aABe S S rm aABe rm aAde rm aAbcde rm abbcde,自下而上的语法分析的一般过程,实现思想 从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功， 称为“移进-归约”方法。 从语法树的角度看：从语法树的树叶开始，逐步向上归约构造分析树，直到形成根结点。是推导的逆过程。,最左推导(Left-most Derive) 每次推导都替换当前句型的最左边的非终结符。 与最右归约对应。 最右推导(Right-most Derive) 每次推导都替换当前句型的最右边的非终结符。 与最左归约(规范归约)对应，得规范句型。,例：设有文法GS： (1) S aABe (2) A b (3) A Abc (4) B d 使用最右推导： 因为S aABe aAde aAbcde abbcde，所以 abbcde是文法G的句子。,步骤 动作,(1)S aABe(2)A b (3)A Abc(4)B d,最左归约过程是最右推导的逆过程， 对输入串abbcde的移进归约过程如下：,该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。,a,b a,A a,b A a,c b A a,A a,d A a,B A a,e B A a,S,“移进-归约”分析法中栈的使用,移进-归约分析器使用了一个符号栈和一个输入缓冲区 1、句型表示,符号栈内容 + 输入缓冲区内容 # 当前句型 #,2、分析器结构,3. 过程描述：do do 将输入串最左边的符号移入栈内; while (在栈里符号串中找到一个可归约串)； 归约可归约串 while （文法开始符号出现在栈顶或者发现错误）；,分析成功的条件：栈顶为文法符号，输入串为空。 注意：该过程并未涉及如何在栈里找可归约串。实际上，不同的找可归约串的方法，构成了不同的分析算法。,分析器的四种动作,1) 移进：读入下一个输入符号并把它下推进栈。 2) 归约：当栈顶符号串形成一个可归约的串（如：句柄）时，直接进行归约，即用产生式左侧的非终结符替换栈顶的句柄。 3) 接受：当栈底只有“#”和开始符号，而输入也已经到达右端标志符号“#”时，识别出符号串是句子，执行该动作，表示分析成功，是归约的一种特殊情况。 4) 出错：栈顶的内容与输入符号相悖，即当识别程序发现输入符号串不是句子时，进行出错处理。 注意：决定移进和归约的依据是什么？ 栈顶是否出现了可归约的符号串。,“移进归约”语法分析小结： 从输入串的开始依次读入单词(移进栈中) 。 一旦发现可归约串(某个产生式的右端)就立即归约。 归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。 若最终能归约成文法的开始符号，则分析成功（接受）；否则出错。 由于总是将句型的最左边的可归约串替换成非终结符，该方法通常得到是最右推导。 关键是如何识别可归约的符号串？,语法分析中问题的提出： 在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶时就进行归约。 如何知道在栈顶符号串中已经形成可归约串？ 如何进行归约？ 通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。,自下而上语法分析主要有以下三种方法： 简单优先分析法(规范归约)文法按 一定原则规定文法符号的优先关系 算符优先分析法(不规范归约)规定 算符之间的优先关系 LR分析法（规范归约） LR(0)、LR(1)、SLR(1)和LALR(1),语法分析树的生成演示,a b b c d e,A,A,B,S,Ab,AAbc,Bd,SaABe,(1)S aABe(2)A b (3)A Abc(4)B d,S aABe aAde aAbcde abbcde,规范归约相关概念复习,有文法G，开始符号为S, 如果有S=xy,则xy是文法G的句型，x,y是任意的符号串 如果有S=xAy, 且有A=,则是句型xy相对于非终结符A的短语 如果有S=xAy, 且有A-,则是句型xy相对于A-的直接短语 位于一个句型最左边的直接短语称为句柄. 句型- 短语 - 直接短语 -句柄,注: 每次归约的部分就是分析为句柄的字符串(最右推导)。 在规范归约中，关键问题就转化为如何识别句柄?,回到上例用句柄对句子abbcde进行归约有：,用句柄对句子进行归约的过程与用移进-归约过程是一致的，使用归约的产生式及其顺序是一致的。,(1)S aABe(2)A b (3)A Abc(4)B d,(2) Ab,(3)A Abc,aAbcde,aAde,(4)B d,(1)S aABe,aABe,S,练习：有文法如下 E-E+T|T T-T*F|F F-(E)|id 1）写出输入串 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) 准备 # id1+id2*id3# 2) 移进 #id1 +id2*id3# 3) 归约 Fid #F +id2*id3# 4) 归约 TF #T +id2*id3# 5) 归约 ET #E +id2*id3# 6) 移进 #E+ id2*id3# 7) 移进 #E+id2 *id3# 8) 归约 Fid #E+F *id3# 9) 归约 TF #E+T *id3# 10) 移进 #E+T* id3# 11) 移进 #E+T*id3 # 12) 归约 Fid #E+T*F # 13) 归约 TT*F #E+T # 14) 归约 EE+T #E # 15) 接受,所得的结果是：用产生式序列表示语法分析树,E-E+T|T T-T*F|F F-(E)|id,id1 + id2 * id3,F,T,E,F,T,F,T,E,移进归约分析中的问题,1) 移进-归约冲突 在分析到某一步时，既可以移进，又可以归约 上例第10)步可以移进*，也可以按产生式EE+T进行归约。 2) 归约-归约冲突 存在两个可选的句柄，可对栈顶符号进行归约 例如上述第13)步，可以用TF进行归约，又可以按TT*F进行归约。 各种分析方法中处理冲突的技术不同,算符优先分析,算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归约串。 将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定句柄。 显然，在一个符号串中，任意两个相邻终结符号a和b之间，只可能存在以下四种优先关系：(1) a, b优先性相同，记作a b。(2) 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=.aQ (注意ab相邻),算符优先文法的定义,例：EE+E | E*E | (E) | i 证明不是算符优先文法。 因为：EE+E ， EE*E 则有 + * 又因为：EE*E, EE+E 则有 + * 所以不是算符优先文法。,3.算符优先文法 算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有 = , 中的一种成立,则G为一算符优先文法。,算符优先关系表的构造,用表格形式来表示各终结符号的优先关系，这种表称为优先表。 构造优先关系表的方法： 按照定义手工计算 使用算法,由F-(E) 得 ( = ),例:P:E-E+T|T T-T*F|F F-(E)|i 求算符优先表。,终结符+#,终结符+#,对于结束符#和其它终结符a有关系: # #,在优先表中，空白部分是一种错误关系 相同的终结符之间的优先关系不一定是 如果有a b,不一定有b a(不具传递性)，因为只定义相邻运算符之间的优先关系，a,b相邻时，不一定b,a相邻。 a,b之间未必有优先关系( , , ),算符优先关系表的构造算法,1.FIRSTVT集 定义：对每个非终结符P, FIRSTVT(P)=a|P=a.或P=Qa.,a为终结符,P，Q为非终结符,由优先性低于的定义和FIRSTVT集合的定义可以得出： 若存在某个产生式：aP，对所有：bfirstVT(P) 都有：a b。,构造FIRSTVT集算法:,按照下面两条规则来构造FIRSTVT集： 若有产生式P-a.或P-Qa.,则aFIRSTVT(P) 若有产生式P-R.,则FIRSTVT(R)包含在FIRSTVT(P)中,所有终结符,所有非终结符,数组值为真假，为真的条件是c FIRSTVT(Q),通过构造一个二维数组F来实现,该从数组F反映任何一个非终结符P的FIRSRVT集中的元素。步骤：,先用第一条规则进行初始化,使用第二条规则对数组F进行修改，修改方法是： (1) 用一个栈，将所有F数组中值为真的元素FP,a的符号对(P,a)压入堆栈； (2) 对栈施行如下操作：若栈不空，将栈顶符号对出栈，记为(Q,a)，检查所有的产生式，若有形为：PQ的产生式，且FP,a为假，则使FP,a为真，且将(P,a)压入堆栈； (3) 重复这一过程，直到栈空,求文法各非终结符的firstVT：,定义数组：,EE+T | TTT*F | FF(E) | i,从而得到： FirstVT(E) = +, *,(, I FirstVT(T) = *,(,I FirstVT(F) = (,I,Begin For 对每个非终结符P和终结符a do FP,a = false For 对每个形如Pa或PQa的产生式 do Insert(P,a) While stack 非空 Begin 把栈顶项出栈，记为(Q,a) For 对每条形如PQ的产生式 do insert(P,a) End; End.,PROCEDURE insert(P,a); IF not FP,a then begin fp,a = true; (P,a)进栈 end;,对数组初始化,应用规则1,应用规则2,2. 求LASTVT集 定义：LASTVT(P)=a|P = .a或P =. aQ,a为终结符,P，Q为非终结符,+,+,构造LASTVT集算法: (思考？),3.构造优先关系表 如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。 若产生式右部有.aP.的形式,则对于每个bFIRSTVT(P)都有a b(优先集) 若产生式右部有.Pb的形式,则对于每个aLASTVT(P)集,都有a b 若产生是形如：Aab 或 AaBb形式，则有a b 构造优先关系表的算法如下：,For 每条形如PX1X2Xn的产生式 do for i =1 to n-1 do begin if Xi和Xi+1都是终结符 then Xi = Xi+1 if i Xi+1 ; end;,构造优先关系表,算符优先分析算法,通过比较终结符间的优先关系来实现 根据优先分析的原理：语法分析程序的任务是：不断移进输入符号，识别句柄并进行归约。 分析的方法：根据优先性“高于”来识别句柄的头，根据优先性“低于”来识别句柄的尾。各种优先关系已经存于优先关系表中。,1.不能识别只由一个非终结符组成的句柄。不能保证每次对句柄进行归约,在算符优先分析过程中,每次归约的符号串,是当前句型的最左素短语. 2.素短语：至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。 3.最左素短语(leftmost prime phrase)：是指位于句型最左边的那个素短语。,例：下述文法的一个句型： T * F + i 其短语、素短语、最左素短语分别是？,ET | E+T TF | T*F Fi | (E),短语有：i, T * F, T * F + i 素短语有： i, T * F 最左素短语是：T * F,一个算符文法G的某个句型的最左素短语可描述： 设句型的一般形式为(NiVN,ai VT #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的语法树如图：,根据语法树可知： 句型#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(不含终结符)也不是素短语 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的算符优先分析过程,栈 输入缓冲区 # i+i*i# #i +i*i# #F +i*i# #F+ i*i# #F+i *i# #F+F *i# #F+F* i# #F+F*i # #F+F*F # #F+T # #E #,k:=1;sk = #; Repeat a := 下一个输入符号; If sk Vt THEN j:=k ELSE j:=k-1; WHILE sj a DO BEGIN repeat q:=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; END If sj a or sj = a THEN begin k:=k+1; sk:=a; end; else error; UNTIL a=#;,算符优先分析一般并不等价于规范规约 并不对文法的非终结符定义优先关系，无法发现由单个非终结符组成的“可归约串”。即无法使用单非产生式(如：TF)进行归约。 算符优先分析比规范归约过程要快，跳过了所有的单非产生式。 可能将本来不是句子的输入串误认为是句子。,总结归约的策略: 在文法中寻找这样的产生式:它的右部形如:uj aj uj+1 aj+1. ui ai ui+1,其中每个终结符号与最左素短语对应位置上的终结符号完全相同,而每一个非终结符号uk应与相应位置上的非终结符号Nk相对应,不必完全相同。,算符优先分析法小结,优点 简单、效率高 能够处理部分二义性文法 缺点 文法书写限制大 占用内存空间大 不规范、存在查不到的语法错误,设文法为： E#E# TF EE+T FPF|P ET P（E ） TT*F PI 求算符优先关系表。(分析过程见吕映芝课本),练习,