《语法分析自下而上分析》由会员分享，可在线阅读，更多相关《语法分析自下而上分析（108页珍藏版）》请在金锄头文库上搜索。
1、国防科技大学计算机系602教研室,第五章 语法分析自下而上分析,自上而下分析法(Top-down) 自下而上分析法(Bottom-up),国防科技大学计算机系602教研室,语法分析的方法： 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约,国防科技大学计算机系602教研室,5.1.1 归约,采用“移进归约”思想进行自下而上分析。 基本思想：用一个寄存符号
2、的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。,国防科技大学计算机系602教研室,国防科技大学计算机系602教研室,b,d,b,a,c,e,分析树和语法树不一定一致。 自下而上分析过程：边输入单词符号，边归约。 核心问题：识别可归约串,国防科技大学计算机系602教研室,5.1.2 规范归约,定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且,则称是句型相对于非终结符A的短语。 特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。,国防科技大学
3、计算机系602教研室,在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。,国防科技大学计算机系602教研室,定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,国防科技大学计算机系602教研室,把上例倒过来写，则得到： S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。 规范归约是关于是
4、一个最右推导的逆过程 最左归约 规范推导 由规范推导推出的句型称为规范句型。,国防科技大学计算机系602教研室,5.2 算符优先分析,四则运算的优先规则： 先乘除后加减，同级从左到右 考虑二义文法文法G(E)： G(E)： E i| E+E|E-E|E*E|E/E|(E) 它的句子有几种不同的规范规约。 归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。 如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。,国防科技大学计算机系602教研室,起决定作用的是相邻的两个算符之间的优先关系。 所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归
5、约串”和进行归约。,国防科技大学计算机系602教研室,首先必须定义任何两个可能相继出现的终结符a与b的优先关系 三种关系 a b a的优先级低于b a b a的优先级等于b a b a的优先级高于b 注意：与数学上的=不同，a b并不意味着b a,国防科技大学计算机系602教研室,5.2.1 算符优先文法及优先表构造,一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部： QR 则我们称该文法为算符文法。 约定： a、b代表任意终结符； P、Q、R代表任意非终结符； 代表由终结符和非终结符组成的任意序列，包括空字。,国防科技大学计算机系602教研室,假
6、定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说： 1. ab 当且仅当文法G中含有形如Pab或PaQb的产生式；,如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一： ab，ab， ab 则称G是一个算符优先文法。,2. ab 当且仅当G中含有形如PaR的产生式， 而R b或R Qb；,3. ab 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。,国防科技大学计算机系602教研室,优先关系表,国防科技大学计算机系602教研室,从算符优先文法G构造优先关系表的算法。 通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。 确定满足关系和
7、的所有终结符对： 首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,国防科技大学计算机系602教研室,有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。 假定有个产生式的一个候选形为 aP 那么，对任何bFIRSTVT(P)，有 ab。 假定有个产生式的一个候选形为 Pb 那么，对任何aLASTVT(P)，有 ab。,国防科技大学计算机系602教研室,首先讨论构造集合FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合FIRSTVT(P)： 1. 若有产生式Pa或PQa，则aFIRSTVT(P)； 2. 若aFIRS
8、TVT(Q)，且有产生式PQ，则aFIRSTVT(P)。,国防科技大学计算机系602教研室,数据结构： 布尔数组FP，a，使得FP，a为真的条件是，当且仅当aFIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素FP，a赋初值。 栈STACK，把所有初值为真的数组元素FP，a的符号对(P，a)全都放在STACK之中。,国防科技大学计算机系602教研室,运算： 如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如 PQ 的产生式，若FP，a为假，则变其值为真且将(P，a)推进STACK栈。 上述过程必须一直重复，直至栈STACK拆空为止。,国防科技大学计算机系602教研室
9、,如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)： PROCEDURE INSERT(P，a)； IF NOT FP，a THEN BEGIN FP，a:=TRUE； 把(P，a)下推进STACK栈 END；,国防科技大学计算机系602教研室,主程序： BEGIN FOR 每个非终结符P和终结符a DO FP，a:=FALSE； FOR 每个形如Pa或PQa的产生式 DO INSERT(P，a)； WHILE STACK 非空 DO BEGIN 把STACK的顶项，记为(Q，a)，上托出去； FOR 每条形如PQ的产生式 DO INSERT(P，a)； END
10、 OF WHILE； END,国防科技大学计算机系602教研室,这个算法的工作结果得到一个二维数组F，从它可得任何非终结符P的FIRSTVT。 FIRSTVT(P)a | FP，a=TRUE 同理，可构造计算LASTVT的算法。 使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：,国防科技大学计算机系602教研室,FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF in-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置X
11、iXi+2； IF Xi为终结符而Xi+1为非终结符 THEN FOR FIRSTVT(Xi+1)中的每个a DO 置 Xia； IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1 END,国防科技大学计算机系602教研室,例: 考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 1. 计算文法G的FIRSTVT和LASTVT; 2. 构造优先关系表; 3. G是算符优先文法吗?,国防科技大学计算机系602教研室,国防科技大学计算机系602教研室,结论: G
12、是算符优先文法,G的算符优先关系表,国防科技大学计算机系602教研室,5.2.2 算符优先分析算法,可归约串，句型，短语，直接短语，句柄，规范归约。 一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。 最左素短语是指处于句型最左边的那个素短语。,国防科技大学计算机系602教研室,考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i,句型：T+F*P+i,短语：T+F*P+i, T, F， P, F*P, i, T+F*P 直接短语：T, F, P, i 句柄：T
13、素短语： F*P, i 最左素短语： F*P,国防科技大学计算机系602教研室,算符优先文法句型(括在两个之间)的一般形式写成： #N1a1N2a2NnanNn+1# 其中，每个ai都是终结符，Ni是可有可无的非终结符。 定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 NjajNiaiNi+1， aj-1aj aj aj+1，ai-1ai aiai+1,国防科技大学计算机系602教研室,算符优先分析算法 使用一个符号栈S，用它寄存终结符和非终结符，k代表符号栈S的使用深度。 1 k:=1; Sk:=#; 2 REPEAT 3 把下一个输入符号读进a中； 4 IF SkV
14、T THEN j:=k ELSE j:=k-1; 5 WHILE Sja DO 6 BEGIN 7 REPEAT 8 Q:=Sj; 9 IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 10 UNTIL SjQ;,国防科技大学计算机系602教研室,11 把Sj+1Sk归约为某个N； 12 k:=j+1; 13 Sk:=N 14 END OF WHILE; 15 IF Sja OR Sja THEN 16 BEGIN k:=k+1;Sk:=a END 17 ELSE ERROR /*调用出错诊察程序*/ 18 UNTIL a=#,国防科技大学计算机系602教研室,在算法的工作过
15、程中，若出现j减1后的值小于等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：# N #。 算法的第11行中的N是指那样一个产生式的左部符号，此产生式的右部和Sj+1Sk 构成如下一一对应关系：自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈S。,国防科技大学计算机系602教研室,算符优先分析一般并不等价于规范归约。,国防科技大学计算机系602教研室,算符优先分析法特点： 优点: 简单，快速 缺点: 可能错误接受非法句子，能力有限. 算符优先分析法是一种广为应用、行之有效的方法。 用于分析各类表达式 ALGOL 60,国防科技大学计算机系602教研室,5.2.3 优先函数,把每个终结符与两个自然数f()与g()相对应，使得 若1 2，则f(1) g(2) f称为入栈优先函数，g称为比较优先函数。 优点:便于比较，节省空间； 缺点:原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。,国防科技大学计算机系602教研室,文法G(E) (1) EE+T | T (2) TT*F | F (3) FP F
