自下而上分析和优先分析法

1、第六章 自下而上分析和优先分析法1、教学目的及要求：要求理解算符优先文法、最左素短语、有效项目的基本概念；掌握算符优先分析方法。 对给定的文法能够判断该文法是否是算符文法 对给定的算符文法能够判断该文法是否是算符优先文法 对给定的算符文法能构造算符优先关系表，并能利用算符优先关系表判断该文法是否是算符优先文法。 能应用算符优先分析算法对给定的输入串进行移进-归约分析，在分析的每一步能确定当前应移进还是归约，并能判断所给的输入串是否是该文法的句子。 了解算符优先分析法的优缺点和实际应用中的局限性。2、教学内容：自下而上语法分析（算符优先分析法），算符优先分析。3、教学重点：归约，算符优先表构造。

2、4、教学难点： 通过本章学习后，学员应该能知道算符文法的形式。 对一个给定的算符文法能构造算符优先关系分析表，并能判别所给文法是否为 算符优先文法。 分清规范句型的句柄和最左素短语的区别，进而分清算符优先归约和规范归约的区别。 算符优先分析的可归约串是句型的最左素短语，在分析过程中如何寻找可归约串是算符优先分析的关键问题。对一个给定的输入串能应用算符优先关系分析表给出分析（归约）步骤，并最终判断所给输入串是否为该文法的句子。5、课前思考 什么是自下而上语法分析的策略？ 什么是移进-归约分析？ 移进-归约过程和自顶向下最右推导有何关系？ 自下而上语法分析成功的标志是什么？ 什么是可归约串？ 移进

3、-归约过程的关键问题是什么？ 如何确定可归约串？ 如何决定什么时候移进，什么时候归约？ 什么是算符文法？什么是算符优先文法？ 算符优先分析是如何识别可归约串的？ 算符优先分析法的优缺点和局限性有哪些？6、章节内容第一节 自下而上语法分析第二节 算符优先分析法6.1 自下而上语法分析自底向上的语法分析是从给定的符号串本身出发，试图逐步将它归约为文法的开始符号，由于在进行自底向上的语法分析时，通常所采用的是最左归约，即规范归约，因此实现此种语法分析的关键，是在分析的每一步，如何寻找或确定当前句型的句柄以及确定将句柄归约为什么非终结符号。 一、自下而上语法分析方法的分类根据寻找句柄策略的不同，形成不

4、同的自底向上的分析方法，如优先分析法及LR分析法。1、优先分析法优先分析法是在文法的一些符号之间建立优先关系，并根据此优先关系来确定句型的句柄。2、LR分析法LR分析法则根据分析过程中迄今已经取得的信息，并向前查看若干个输入符号来确定当前应采取的分析动作。二、自下而上分析法的实现思想实现自底向上的分析，使用一个先进后出的分析栈存放分析过程中所得的文法符号；开始状态：分析栈底放置一个界符#，然后将输入符号逐个推入栈内；一旦在分析栈的栈顶出现句柄，就用相应产生式的左部去替换这个句柄，即进行一次归约，由于归约，得到新的栈顶，此时再查看栈的顶部是否形成新的句柄，若是，再进行归约；反之，则继续将后续的输

5、入符号移入栈内；分析成功：重复上述过程，若最终能将全部输入符号移掉，且分析栈中只留下栈底符号#及最后一步归约所得文法开始符号，则表明输入串的分析成功；语法错误：若全部输入符号已被移掉，而分析栈不能出现上述格局，则表明输入符号串不是文法的句子，存在语法错误。三、自下而上语法分析过程例：有文法GS：S®AB|c，A ®bA|a，B ®aSb|c，用上述“移进归约”分析方法对输入串bbaacb所作的分析过程：移进归约分析过程可能采取的动作有四种：移进、归约、接受和报错。因采用最左归约，故一旦句柄在分析栈形成，必然出现在栈顶。当一个貌似句柄的符号串出现在栈顶时，不能贸然按

6、某一产生式进行归约，否则将导致错误结果。如上例步骤7。如何正确确定句型的句柄，如何正确地用产生式进行归约，是实现自底向上语法分析的关键。6.2 算符优先分析法一、概述算符优先分析法是仿照算术式的四则运算过程的一种语法分析方法，该方法首先规定运算符之间的优先关系和结合性质，然后利用这种关系，用比较相邻运算符的优先顺序来确定句型的“句柄”和进行归约，这种归约未必是严格的最左归约，每一步未必是当前句型的句柄。例：有文法GE：E ®E+E|E-E|E*E|E/E|(E)|i该文法为二义性文法，其句子有不同的规范推导，归约过程中句柄不唯一，若采用运算符优先顺序和结合原则的规定，并按这种规定进行

7、归约，则该句子的归约过程就是唯一的。如i+i*i的归约过程：(1) i+i*i 按E ®i 归约(2)E+i*i 按E ®i 归约(3) E+E*i 按E ®i 归约(4) E+E*E 按E ®E*E 归约(5) E+E按E ®E+E 归约(6) E该归约过程是唯一的。在上述的整个归约过程中，起决定作用的是相邻两个终结符的优先关系，所以应用算符优先分析法自底向上地分析句子。可以只根据相邻运算符的优先关系，就能方便地并且唯一的确定归约的“句柄”。可以用来分析二义性文法所产生的语义。直观算符优先分析对一个给定文法G，人为地规定其算符的优先顺序，即给

8、出优先级别和同一个级别中的结合性质，算符间的优先关系有三种：Ø a ba的优先级高于bØ a ba的优先级等于bØ a ba的优先级低于bØ 这三个关系不同于数学中的<,>,=,它们是有序的，如a b不意味着b a，a b不意味b a。如有文法GE：E®E+E|E*E|(E)|i，其终结符的优先关系如下表：优先关系矩阵二、直观算符优先分析法用已经建立起来的文法GE的优先关系矩阵，构造一个分析该文法句子的算法，即直观算符优先分析法，为便于比较相邻运算符的优先级，使用两个工作栈，一个为运算符栈，以OPTR表示，用来存放运算符（包括括号和

9、#）；另一个称运算对象栈，以OPND表示，用来存放运算对象（包括最基本的运算对象和运算结果），用#代表分析句子的左右分界符。分析开始时，OPTR栈中压入左界符#，OPND栈为空，同时令q代表OPTR当前栈顶符号，a存放新输入的符号，则分析算法的步骤：(1)把下一个输入符号读至a中；(2)若a为i，则把它推进OPND栈，转第一步。(3)若q a，则应根据规则E® E1q E2进行归约，E1和E2代表OPND栈顶的次高元和最高元中的运算对象，先将E1和E2从OPND栈中弹出，然后把代表该子表达式运算结果的E压入OPND中，同时把q从OPTR栈顶弹出，然后重新进入第(2)步；(4)若q a

10、，则只有一种情况， q=“(”,a=“)”，此种情况下，弹出OPTR栈顶最高元的“(”,放弃a中的右括号，转第(1)步；(5)若q a，把a移进OPTR栈，转第(1)步；(6)若q=a=“#”，分析过程结束；(7)若q与a不存在优先关系，即矩阵元素为空，输入串有错，调错误处理程序进行处理。分析成功的标志是（必要条件）：OPTR栈底的“#”与输入串后的“#”相遇，而OPND栈中仅含一项，这一项代表整个表达式的分析结果，若非这种情况，意味着分析失败，即表达式有语法错误；在(3)和(4)，当要形成Eq E和(E)时，若OPND栈中没有足够的项数，也表示输入串有错。上面算法对GE所定义的算术表达式的分

11、析有效，所有算符优先分析大体上如此工作。在该分析过程中由于使用了两个栈，当读进的符号一旦被判断出是运算对象时，就立即推进运算对象栈，而不与运算符栈的栈顶符号比较优先级，故没有用到作为终结符的运算对象与其它算符之间的优先关系。使用算符优先分析法便于直接将表达式翻译成目标指令。三、算符优先文法的定义1、算符文法定义设有一文法G，如果G中没有形如A ®BC的产生式，其中B和C为非终结符，称G为算符文法（OG文法），即在OG文法中，不存在包含两个相邻非终结符号的产生式的右部。2、算符文法性质(性质一)在算符文法中，任何句型都不包含两个相邻的非终结符。证明：用归纳法，设r是句型，有S=W0&#

12、222;W1Þ.ÞWn=r，推导长度为n。(1)归纳基础：n=1时， S=W0ÞW1=r，即SÞr，必存在产生式S® r，而有算符文法定义，文法的产生式中无相邻的非终结符，该性质成立。(2)假设n>1， Wn-1满足性质若Wn-1=aAd,AÎVN，由假设a的尾符号与的d首符号不可能为非终结符，否则与假设矛盾，又若Ab®是文法的产生式，则有Wn-1 Þ Wn = dba= r， Ab®不含有两个相邻的非终结符，所以adb也不含有两个相邻的非终结符。(性质二)如果Ab或bA出现在算符文法的句型r中，其

13、中AÎVN ， bÎVT,则r中任何含b的短语必含有A。证明：用反证法， S r=abAb，若存在B ab，则A和B不同时归约，则有S B Ab，与性质一矛盾。得证。含b的短语必含A，含A的短语不一定含b。四、算符优先关系定义设G是一个算符文法，a和b是任意两个终结符，A,B,C ÎVN，算符优先关系定义如下：Ø a b，当且仅当G中含有形如A®ab或A®aBb的产生式。Ø a b，G中含有形如A®aB，且B b或B CbØ a b，G中含有形如A®Bb，且B a或B aC。以上关系可用语法树说

14、明：五、算符优先文法的定义设一不含e产生式的算符文法，如果任意两个终结符对a，b之间至多有, 三种关系的一种成立，则称G是一个算符优先文法(OPG文法)。两个终结符之间的优先关系是有序的，允许有a b，b a同时存在，而不允许有ab，ab，ab中两种同时存在。例1、有文法GE：E®E+T|T，T ®T*F|F，F ®(E)|i因为 E®E+T，EÞE+T，故+ EÞT Þ T*F， 故*+ EÞT ÞF Þ(E) 故)+ EÞT ÞF Þ i 故i+可得前面优先关系

15、矩阵，文法GE是OG文法，并在任意两个终结符号之间至多有一个优先关系成立，故该文法为OPG文法。例2、GE：E®E+E|E*E|(E)|iE ® E1+E2，E1ÞE*E， *+E ® E1*E2，E2ÞE+E，*+故该文法是算符文法，但不是算符优先文法。六、算符优先关系表的构造通过检查G的每条规则的每一个选择，可以找出所有满足ab的终结符号对，为找出所有满足关系和的终结符号对，首先需要对G的每个非终结符号B构造两个集合FIRSTVT(B)和LASTVT(B)：Ø FIRSTVT(B)=b|Bb.或BCbØ LASTVT(B

16、)=a|Ba或BaC三种关系：Ø 关系：A ®ab或A ®aBb则有abØ 关系：求出每个非终结符B的FIRSTVT(B)，对形如产生式A ®aB，对于每一 bÎ FIRSTVT(B)，则有ab成立。Ø 关系：求出每个非终结符B的LASTVT(B)，对形如产生式A ®Bb，对于每一aÎ LASTVT(B)，则有ab成立。例3、有表达式文法E®#E#， E®E+T|T，T®T*F|F，F®P­F|P，P ®(E)|i(1)计算优先关系由E®

17、;#E#， P ®(E)有#，()(2)计算FIRSTVT和LASTVT集合FIRSTVT(E)=#FIRSTVT(E)=+,*, ­,(,iFIRSTVT(T)=*, ­,(,i FIRSTVT(F)=­,(,iFIRSTVT(P)=(,i LASTVT(E)=#LASTVT(E)=+,*, ­,),i LASTVT(T)=*, ­,),iLASTVT(F)=­,),i LASTVT(P)=),i(3)关系#E #FIRSTVT(E)，+T +FIRSTVT(T)*F *FIRSTVT(F)，­F ­F

18、IRSTVT(F)(E (FIRSTVT(E)(4)关系E# LASTVT(E)#，E+ LASTVT(E)+T* LASTVT(T)*，P­ LASTVT(P)­E) LASTVT(E)七、构造FIRSTVT(A)的算法按照定义，可用下面两条规则构造集合FIRSTVT(A)：(1)若有产生式A®a或A®Ba，则aÎFIRSTVT(A)。(2)若有产生式A®B，且bÎFIRSTVT(B)，则bÎFIRSTVT(A)。建立一布尔数组F，使得FA,a为真的条件是当且仅当aÎFIRSTVT(A)。开始时：按规则

19、(1)对每个数组元素FA,a赋初值，用一个栈STACK把所有初值为真的数组元素FA,a的符号对(A,a)全部放在STACK栈中，然后，对栈STACK施加如下运算：如果STACK不空，将栈顶元素弹出，记为(B,a)，用规则(2)对每个形如A®B的产生式，若FA,a为假，则变其值为真，并将(A,a)推进STACK栈。上述过程重复到STACK为空为止。（具体算法用程序描述如下： ）先定义一个过程：PROCEDURE INSERT(A,a); IF NOT FA,a THEN BEGIN FA,a:=TRUE PUSH(A,a) ONTO STACK END;主程序为：BEGIN FOR 每

20、一个非终结符A和终结符a DO FA,a:=FALSE; FOR 每个形如A®a或A®Ba的产生式DO INSERT(A,a) WHILE STACK 非空 DO BEGIN 把STACK栈顶记为(B,a)上托出去; FOR 每个形如A®B的产生式 DO INSERT(A,a) ENDEND. 该算法的工作结果得到一个二维数组F，从它可得到任何非终结符A的FIRSTVT(A)。FIRSTVT(A)=a|FA,a=TRUE八、构造LASTVT(A)的算法构造集合计算LASTVT(1)若有产生式A® a或A®a B，则aÎLASTVT(A

21、)。(2)若有产生式A®,B，且aÎLASTVT(B)，则aÎLASTVT(A)。使用每个终结符A的FIRSTVT(A)和LASTVT(A)即可构造文法G的算符优先关系表，算法为：FOR 每个产生式A®X1X2Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符 THEN 置 XiXi+1; IF i£n-2且Xi和Xi+2均为终结符, Xi+1为非终结符 THEN 置 XiXi+2; IF Xi为终结符而Xi+1为非终结符 THEN FOR FIRSTVT(Xi+1)中的每个b DO 置 Xib; IF

22、 Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1; END九、算符优先分析算法算符优先分析算法是一种自底向上的分析算法，但不是严格从左到右的，在每一步分析中，它将识别和归约所谓的最左素短语。1、最左素短语的定义文法句型的素短语是一个短语，它至少包含一个终结符号，并且除它自身外，不再包含其它素短语，最左边的素短语称最左素短语。例如有表达式文法GE为：E®E+T|T,T®T*F|F,F®P­F|P,P ®(E)|i,现有句型#T+T*F+i#，该句型的短语为：T+T*F+i, T+T*F,

23、T, T*F, i素短语：包含终结符且不含其它素短语，故为T*F， i。而句柄为T，但不是素短语，T*F为最左素短语。2、算符优先文法的句型算符优先文法的任何一个句型应为如下形式#N1a1N2a2NnanNn+1#，其中ai为终结符号，Ni(1£i £n+1)为非终结符或e。若有NiaiNjajNj+1为句柄，则Ni和Nj+1在句柄中。该句柄中终结符之间的关系：§ ai-1 ai§ ai ai+1 ai+2 aj§ aj aj+1 定理：一个OPG句型的最左素短语是满足下列条件的左子串NiaiNjajNj+1Ø ai-1 aiØ ai ai+1 ai+2 ajØ aj aj+1 出现在ai左端或aj右端的非终结符号一定属