《语法分析——自下而上分析》由会员分享，可在线阅读，更多相关《语法分析——自下而上分析（108页珍藏版）》请在金锄头文库上搜索。
1、第五章 语法分析自下而上分析5.1自下而上的语法分析n实现思想q从输入符号串开始，从左到右进行扫描，将输入符号 逐个移入一个栈中，边移入边分析，一旦栈顶符号串 形成某个产生式的右部时，就用该产生式的左部非终 结符代替，称为归约。重复这一过程，直到归约到栈 中只剩下文法的开始符号时，则分析成功， 称为“移 进-归约”方法。q从语法树的角度看：从语法树的树叶开始，逐步向上 归约构造分析树，直到形成根结。是推导的逆过程。自下而上分析的关键问题是寻找自下而上分析的关键问题是寻找可归约串可归约串 。 对对“ “可归约串可归约串” ”概念的不同定义，就形成了概念的不同定义，就形成了不同的自下而上的分析方法
2、。不同的自下而上的分析方法。q核心在算符优先分析法中：在算符优先分析法中：用用“ “最左素短语最左素短语” ”来刻画来刻画“ “可归约串可归约串” ”，在在“ “规范归约规范归约” ”中：中：则用则用“ “句柄句柄” ”来刻画来刻画“ “可归约串可归约串” ”规范归约概念n有文法G，开始符号为S, 如果有 S=xy,则xy是文法G的句型 ，x,y是任意的符号串n如果有S=xAy, 且有 A=,则是句型xy相对于非终结符A的短 语n如果有S=xAy, 且有A-,则是句型xy相对于A-的直接短 语n位于一个句型最左边的直接短语称为句柄.n句型- 短语 - 直接短语 -句柄 *+*注: 每次归约的部
3、分必须是称之为句柄的字符串(最右推导) 。关键的问题是如何识别句柄n例1：下述文法的另一个句型：E+T * F + i其短语、直接短语、句柄分别是？ET | E+TTF | T*FFi | (E)EE + TFiE + TT * F短语有：i, T * F, E+T * F, E + T * F + i直接短语有： i, T * F句柄是：T * F例2考虑文法：E T|E+TT F|T*FF i | (E) （5.2） 对于句型i*i+i 推导解： EE+TT+TT*F+TF*F+Ti*F+Ti*i+F i*i+i尽管有E +i+i 但是, i+i 并不是该句型的一个短语，因为不存在从E(文
4、法开始符）到i*E的推导。但是，i, i*i,和i*i+ i 自身都是句型i*i+i 的短语。而且为为直接短语。n最左推导(Left-most Derive)q 每次推导都替换当前句型的最左边的非终结符 与最右归约对应n最右推导(Right-most Derive)q每次推导都替换当前句型的最右边的非终结符 与最左归约(规范归约)对应，得规范句型规范归约的定义：n假定是文法G的一个句子，如果序列：n, n-1, , 0 (=S)满足如下条件，则序列n, n-1, , 0是一个规范归约: (1) n = 是给定的句子 (2) 0 =S 是文法的开始符号 (3) 对任何i, 0,且没有P-.QR.
5、(P,Q,R属于非终结符),则G是 一个算符文法 n2.算符优先关系的定义(自底向上,可通过树形结构观 察)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 证明不是OPG文法 。因为：EE+E ， EE*E 则有 + *又因为：EE*E, EE+E 则有 + *所以不是算符优先文法。n 算符优先文法算符文法G的任何终结符a,b之间要么没有 优先关系，若
6、有优先关系,至多有 = , 中的一种成立,则G为一算符优先文法。算符优先关系表的构造 n用表格形式来表示各终结符号的优 先关系，这种表称为优先表。n构造优先关系表的方法：q按照定义手工计算q使用算法 1、通过检查G的每个产生式的每个候选式，可以找出满足 a=b的终结符对。2、为了找出所有满足关系的终结符对，我们需要对G的 每个非终结符P 构造两个集合FIRSTVT(P)和LASTVT(P):FIRSTVT(P)=a | P+a或P +Qa,aVT而 Q VN LASTVT(P)=a | P+a或P +aQ,aVT而 Q VN 3、有了这两个集合后，就可以通过检查每个产生式的候选式 确定满足关系
7、的所有终结符对。例如：假定有个产生式的一个候选式为 aP 那么，对任何bFISTVT(P),我们有ab.构造集合FIRSTVT(P)的算法。（1）若有产生式Pa或P Qa,则 aFIRSTVT(P)（2）若aFIRSTVT(Q)，且有产生式P Q则aFIRSTVT(P)构造文法G的优先表算法： FOR 每一条产生式PX1X2XnFOR i:=1 TO n-1 DOBEGINIF Xi 和 Xi+1 均为终结符THEN 置 Xi=Xi+1IF IaEND算符优先分析算法n通过比较终结符间的优先关系来实现n根据优先分析的原理：语法分析程序的任 务是：不断移进输入符号，识别句柄并进 行归约。n分析的
8、方法：根据优先性“高于”来识别句 柄的头，根据优先性“低于”来识别句柄的 尾。各种优先关系已经存于优先关系表中 。n1.不能识别只由一个非终结符组成的 句柄。不能保证每次对句柄进行归约 ,在算符优先分析过程中,每次归约的 符号串,是当前句型的最左素短语.n2.素短语：至少含有一个终结符,且 除自身外,不再包含任何其它更小的 素短语。n3.最左素短语(leftmost prime phrase)：是指位于句型最左边的那 个素短语。例5：下述文法的一个句型：T * F + i其短语、素短语、最左素短语分别是？ET | E+TTF | T*FFi | (E)EE + TFiTT * F短语有：i,
9、T * F, T * F + i素短语有： i, T * F最左素短语是：T * F我们把算符优先文法句型（括在两个#号之间）的一般形式写成：#N1a1N2a2Nnan Nn+1# （5.4）其中每个ai都是终结符，Ni是可有可无的非终结符。一个算符优先文法G的任何句型（5.4）的最左素短语是满足如下条 件的最左子串：NjajNia i+1, a j-1a i+1 根据这个最左素短语的定义我们可以构造算符优先分析算法。最左素短语的特点：算符优先分析法小结n优点q简单、效率高q能够处理部分二义性文法n缺点q文法书写限制大q占用内存空间大q不规范、存在查不到的语法错误第五章 语法分析-自下而上分析
10、例5.1考虑下面文法：1。 EE+T|T2. T T*F|F3. F PF|P4. P (E)|i 构造优先关系表解： 根据产生式4 我们有(=), 从产生式1，2 的+T和T*我们有+,同理可得：。由产生式P (E)和E E+T T+T T*F+T F*F+T PF*F+T iF*F+T 我们可以得到 ( ; # a且aa, ba, ca, da 且ab且bb, cb, db 且b d 第五章 语法分析-自下而上分析优先函数优先函数在实际实现算符优先分析算法时，一般不用优先表而是用两个优在实际实现算符优先分析算法时，一般不用优先表而是用两个优 先函数先函数f f 和和g g。我们把每个终结符
11、号。我们把每个终结符号 与两个自然数与两个自然数f(f( ) )和和g(g( ) ) 相对应，使得相对应，使得若若 1g(1)g( 2)2)函数函数f f 称为入栈优先函数，称为入栈优先函数，g g称为比较优先函数。称为比较优先函数。构造优先函数的方法应在必须掌握之列。构造优先函数的方法应在必须掌握之列。如果优先函数存在，那么，从优先表构造优先函数的一个简如果优先函数存在，那么，从优先表构造优先函数的一个简 单方法是：单方法是：（1 1）对于每个终结符）对于每个终结符a(a(包括包括# #）令其对应两个符号）令其对应两个符号fafa和和g ga a , , 画一张画一张以所有符号以所有符号fa
12、fa和和gaga为结点的方向图，如果为结点的方向图，如果a a = b,b,那么，就从那么，就从fafa画画 一箭弧至一箭弧至g gb;b;如果如果acapable of growing and developingqqcapable of being put into practice : workablecapable of being put into practice : workablen n定义：定义：qqS S A A 是文法是文法GG中的一个规范推导，如果中的一个规范推导，如果 符号串是的前缀，则称是符号串是的前缀，则称是GG的一个的一个活前缀活前缀。n nLRLR分析需要构造
13、识别分析需要构造识别活前缀活前缀的的有穷自动机有穷自动机qq我们可以把文法的终结符和非终结符都看成有穷自我们可以把文法的终结符和非终结符都看成有穷自 动机的输入符号，每次把一个符号进栈看成已识别动机的输入符号，每次把一个符号进栈看成已识别 过了该符号，同时状态进行转换，当识别到可归前过了该符号，同时状态进行转换，当识别到可归前 缀时，相当于在栈中形成句柄，认为达到了识别句缀时，相当于在栈中形成句柄，认为达到了识别句 柄的终态。柄的终态。步骤 符号栈 输入符号串动作1） # abbcde# 移进 0 S22） #a bbcde# 移进 02 S4 4） #aA bcde# 移进 023 S66） #aA cde# 移进 023 S57） #aAc de# 移进 0235 S89） #aAcB e# 移进 02357 S911） #S # 接受 01 acc对输入串abbcde#的LR分析过程3）
