《编译原理语法分析(2)》由会员分享，可在线阅读，更多相关《编译原理语法分析(2)（108页珍藏版）》请在金锄头文库上搜索。
1、3.4 自下而上分析方法3.4.1 自下而上分析原理自下而上分析自左至右扫描输入串, 通过反复查找当前句型的句柄, 并将找到 的句柄归约为相应的非终结符, 这样逐步 归约, 直至文法开始符。即从语法树末端 开始步步向上归约, 直至根结点。 自下而上分析法是一种移进-归约法 。分析过程中采用了一个FIFO分析栈。分 析开始后，把输入符号自左至右逐个移进 分析栈，边移入边分析，一旦栈顶符号串 形成句柄就进行一次归约，再继续查看栈 顶是否形成新的句柄，若仍为句柄，则再 归约，如此重复直至栈顶不是句柄。此时 再继续向栈中移进后续输入符号。重复该 过程，直到将整个输入串处理完毕。若此 时分析栈只有文法开
2、始符，则输入串是一 个句子，否则输入串有错。 下面通过例子说明这种分析过程。文法GS：SaAbBAcAcBd试对输入串accbd进行分析，检查该符号串是否是GS的一个句子。假设“#”为输入串界符，将输入串前 的“#”放入分析栈，接着将输入串的符号 依次进栈，具体分析过程如下:步骤分析栈句柄输入串动 作 1# accbd#移进 2#a ccbd#移进 3#ac cbd#移进 4#aAccbd#归约(用Ac) 5#aAc bd#移进 6#aAAcbd#归约(用AAc) 7#aAb d#移进 8#aAbd #移进 9#aAbBd#归约(Bd) 10#SaAbB#归约(SaAbB)Sa c c b d
3、ABA(d)a c c b dABA(c)a c cAA(b)a cA(a)在自下而上分析过程中，每一步归 约都可画出一棵子树，随着归约的完成 ，这些子树连成一棵完整的分析树。上 述分析过程可用分析树表示如下:由上述建树过程知，自下而上分析过 程的每一步归约都是对当前句型的句柄进 行归约，即句柄一旦形成总是出现在分析 栈栈顶。由于每一步归约都把栈顶符号串 用某产生式左部符号替换，故把栈顶的这 样一串符号称为可归约串。上述第6步若不选AAc而选Ac进 行归约，则无法归约到S。如何确知栈顶 的Ac是可归约串而c不是呢？这需精确定 义“可归约串”的概念。若文法GS是无二义文法，则规范 推导的逆过程必
4、是规范归约(最左归约) 。对于移进-归约过程，句柄的最左性 和分析栈栈顶相关。对于规范推导所得 句型(规范句型)，句柄后面不会出现非 终结符，故可用句柄刻画“可归约串”， 规范归约的实质是在移进过程中当栈顶 呈现句柄时进行归约。为加深对句柄和归约等概念的理解 ，用修剪语法树方法进一步阐明自下而 上分析过程。语法树的一个子树由该树的某结点 及其所有子孙组成，子树的所有叶结点 的自左至右排列形成一个相对于子树根 的短语。一个句型的句柄是该句型对应 的语法树中最左简单子树的所有树叶的 自左至右排列。可采用修剪语法树方法实现归约， 即寻找当前语法树的句柄，将句柄中的 树叶剪去(归约)，不断修剪直到只剩
5、根 结点，完成整个归约过程：Sa A b BA cdcSa A b BA cdSa A b BdSa A b BS至此讨论了句柄和规范归约这两个 基本概念，但并没有解决规范归约的问 题，因为没有给出寻找句柄的算法。事 实上，规范归约的中心问题就是如何寻 找句柄。寻找句柄的不同算法对应不同 的规范归约方法，这一点将在LR分析 器中讨论。算符优先分析法是一种简单直观、广 为使用的自下而上分析法，特别适合于表 达式分析且宜于手工实现。它实际上是依 照表达式四则运算过程来进行语法分析。所谓算符优先分析，就是预先规定运 算符(确切地说是终结符)之间的优先关系 和结合性质，借助于这种优先关系来比较 相邻运
6、算符的优先级，以确定句型的可归 约串并进行归约。注意：算符优先分析不是规范归约。3.4.2 算符优先分析法1. 算符优先文法算符文法: 若一个文法的任一产生式的右部都不含两个相继的非终结符 ，即不含QR这样的右部，则称该文法为算符文法。算符优先文法: 算符优先文法首先应是算符文法, 其次还要定义任意两个可能相继出现的终结符的优先关系。具体定义如下:假定G是一个不含产生式的算符文法, 对任一对终结符a,b, 定义 (1) a=b当且仅当文法G中含有形如Pab 或 PaQb的产生式; (2) ab当且仅当G中含有形如PRb的产生式，而R a 或 R aQ。+若一个算符文法G中任一终结符对(a,b)
7、至多满足下述三种关系之一 :a=b，ab 则称文法G是一个算符优先文法。 例3.10 试说明下述文法G是算符文法，但不是算符优先文法。EE+EE*E(E)i 解: 由于文法G的任一产生式右部都不含两个相邻的非终结符，故文法G是算符文法。(1)由于存在EE+E，而E+E中第二个E可推出E*E，故有+*可见, 运算符+和*之间同时存在两种 不同的优先关系，故文法G不是算符优 先文法。2. 算符优先关系表的构造通过检查文法的每个产生式的各个侯 选式,可找出所有满足a=b的终结符对。为找出所有满足关系 “”的终结 符对,需先对文法的每个非终结符P构造两 个集合FIRSTVT(P)和LASTVT(P):
8、FIRSTVT(P)=a | P a或 P Qa,aVT而QVNLASTVT(P)=a | P a或 P aQ, aVT而QVN+FIRSTVT集的构造方法： (1)若有产生式Pa或PQa，则aFIRSTVT(P)； (2)若有产生式PQ,且 aFIRSTVT(Q),则aFIRSTVT(P)。例如 试构造文法GE的FIRSTVT集。GE: EE+TTTT*FFF(E)i 解: 根据规则(1)知：由EE+得, FIRSTVT(E)=+；由TT*得, FIRSTVT(T)=*；由F(和Fi得,FIRSTVT(F)=(,i根据规则(2)知：由TF和FIRSTVT(F)=(,i得, FIRSTVT(T
9、)=*, (, i；由ET和FIRSTVT(T)得, FIRSTVT(E)=+, *, (, iLASTVT集构造方法： (1)若有产生式Pa或PaQ，则aLASTVT(P)； (2)若有产生式PQ,且 aLASTVT(Q),则aLASTVT(P)。例如 试构造文法GE的LASTVT集。GE: EE+TTTT*FFF(E)i 解: 根据规则(1)知：由E+T得, LASTVT(E)=+由T*F得, LASTVT(T)=*由F)和Fi得,LASTVT(F)=),i根据规则(2)知：由TF和LASTVT(F)得,LASTVT(T)=*, ), i;由ET和LASTVT(T)得, LASTVT(E)
10、=+, *, ), i。构造优先关系表的方法： (1) 对形如Pab或PaQb的产生式, 有a=b； (2) 对形如PaR的产生式, 若 bFIRSTVT(R), 则ab。 (4) 对于语句括号#,有# = # # #例3.11 构造文法GE的算符优先关系表 。GE: EE+TTTT*FFF(E)i 解: 构造FIRSTVT集根据规则(1)知：由EE+得, FIRSTVT(E)=+；由TT*得, FIRSTVT(T)=*；由F(和Fi得 ,FIRSTVT(F)=(,i根据规则(2)知：由TF和FIRSTVT(F)=(,i得, FIRSTVT(T)=*, (, i；由ET和FIRSTVT(T)得
11、, FIRSTVT(E)=+, *, (, i构造LASTVT集 根据规则(1)知：由E+T得, LASTVT(E)=+；由T*F得, LASTVT(T)=*；由F)和Fi得,LASTVT(F)=),i 。 根据规则(2)知：由TF和LASTVT(F)得,LASTVT(T)=*, ), i;由ET和LASTVT(T)得, LASTVT(E)=+, *, ), i。构造优先关系表 根据规则(1), 由“(E)”知, (=)。 根据规则(2),由E+T知, + +，即+ +，* +，) +，i +由TT*知, LASTVT(T)*，即* *，) *，i *由FE)知, LASTVT(E)，即+ )
12、，* )，) )，i ) 由#E#知, # = #；#, 即+#,*#,)#,i#故算术表达式文法的优先关系表如下 :+*i()#+*i (#ai+1查找最左素短语的方法： (1) 最左子串法先找出句型中终结符由左至右满足 aj-1ai+1的最左子串。再检查文法的每个候选式,看其是否 满足:所有终结符由左至右的排列恰为 ajaj+1ai, 即终结符对应相等而非终结符 仅对应位置相同。若存在这样的候选式 , 则用该候选式进行归约。(2) 语法树法先画出句型的语法树, 再找语法树 中所有相邻终结符间的优先关系。确定相邻终结符间优先关系的原则:语法树中同层的优先关系为“= ”;不同层时, 层次在下的
13、优先级高,层次在上的优先级低;在句型两侧加上语句括号“#”,则有#。最后按最左素短语必须具备的条件确定最左素短语。例3.12 文法GE: EE+T | TTT*F | F F(E) | i试确定F+T*i的最左素短语。 解:画句型F+T*i的语法树,根据语法树确定相邻终结符间优先关系如图,故最左素短语为i。注意:最左直接短语为FEEE*TFTiF #*i#算符优先分析算法:k=1; Sk=#; /k代表栈S的使用深度doa=下一个输入符;if (SkVT) j=k;else j=k1; /j指栈顶终结符 while (Sja) /找最左SjadoQ=Sj; /j从最左素短语末逐步移向首if (
14、Sj1VT) j=j1; else j=j2;while (Sj=Q);把Sj+1Sk归约为某个N;k=j+1; Sk=N; /把N置于原Sj+1位置if (Sj+, 用Fi归约 #F+i*i#*, 用Fi归约 #F+F*i#, 用Fi归约 #F+F*F#+#, 用TT*F归约 #F+T#, 用EE+T归约 #E#E# 结束算符优先分析的归约只关心句型中 由左至右终结符序列的优先关系,不涉及 非终结符。再以i+i为例, 给出其算符优先 分析过程和规范归约过程。算符优先分析比规范归约要快得多 。这既是算符优先分析的优点,也是它的 缺点,因为这可能把本来不成句子的输入 串误认为是句子,这种缺点易于
15、弥补。 例3.14 试设计下述文法的算符优先分析表 :GS: SiBtSiBtAeSaAiBtAeSaBb 解: 首先构造FIRSTVT集和LASTVT集FIRSTVT(S)=i,a; FIRSTVT(A)=i,a;FIRSTVT(B)=b;LASTVT(S)=t,e,a; LASTVT(A)=e,a;LASTVT(B)=b;由AS知, LASTVT(S)LASTVT(A)即 LASTVT(A)=t,e,a然后构造优先关系表: (1)由产生式SiBtAeS和SiBtS可知:由SiB得, it；由StA得, te；由SeS得, ee和t=e, 由iBtAeS知, 此时应将iBtAeS同时归约为S或A,即取t=e。最后得到优先关系表如下:iteabi b =4. 优先函数用
