《前后文无关文法和语言 2》由会员分享，可在线阅读，更多相关《前后文无关文法和语言 2（26页珍藏版）》请在金锄头文库上搜索。
1、2.3 句型的分析 句型的分析：构造一算法，用以判断所给 的符号串是否为某文法的句型（句子） 常见分析方法有自顶向下分析和自底向上 分析两类； 自顶向下 从开始符出发试图推导出给定的 符号串； 自底向上 推导的逆过程（称归约）：从已 给的符号串出发，试图将其归约为开始符 。2.3.1 规范推导和规范归约 对于一文法而言，从开始符到某句型的推导过程 可能不唯一。例如，文法GE中从 E 到 i+i*i 的 推导有： (1)E E+T E+T*F T+T*F T+T*i F+T*i i+T*i i+F*ii+i*i (2)E E+T T+T F+T i+T i+T*F i+F*F i+i*F i+i
2、*F i+i*i (3)E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i (4) 规范推导 为了让计算机自动地进行推导，通常我们只考虑最左或最 右推导。 最左（右）推导：在推导序列的每一步直接推导中，被替 换的总是当前句型中最左（右）的非终结符。 例如，上页中的（2）、（3）分别是最左、最右推导。 形式上，从符号串到符号串的推导序列 * xUy xuy * 总有 xVT* (yVT*) 时，称为最左（右）推导 定义：最左（右）推导所得句型称为左（右）句型；最右 推导称为规范推导；右句型称为规范句型。句子、句型的推导方法 每个句子都有相应的最左和最右
3、推导，因此，句子即是左句型 也是右句型（规范句型） 并不是每个句型都有最左和最右推导 例如，E + E+i*T即不是左句型，也不是右句型 对于给定的符号串w，采用自顶向下的分析来判断w是否为 L(GS)的句子的常见方法是：试图建立从开始符 S到w最左推 导: S* w 显然，每步推导时，对应于最左非终结符相应的产生式可能会 有多个，若无特殊的办法，只能一个一个地试探。因此，推导 过程可能是带回溯的。 为提高效率，就应尽量避免回溯自底向上的语法分析就是从已给的符号串w出发，试图以相反的方向为w建立一个规 范推导，最终得到文法的开始符。 推导的逆过程称作归约，它是把当前的符号串中的构成文法 某个产
4、生式A右部的子串替换成产生式的左部符号A，得到 一个新的符号串A 。这样的一步动作，称为进行了一步归约。 例如，符号串F+i*i中的F可按产生式TF归约为T，从而得到新 的符号串T+i*i。 若从给定的符号串w出发，一步步地将其归约，最终得到文法的 开始符号，则说明w是该文法定义的一个句子。归约成功，否则 ，归约失败。 若归约的每一步都归约的是当前符号串中最左边的某产生式的右 部，则称该归约是规范归约（即最左归约）。 规范归约是规范推导的逆过程。 关于最左（右）归约、直接归约、归约等的形式定义不再赘述。符号串符号串i+i*ii+i*i的归约过程的归约过程由上表可以看出，归约过程是最左归约，它恰
5、好是规 范推导的逆过程。这正是把最左归约定义为规范归约 的原因。关于归约的一点说明 注意，前面例子中归约的第五步中，当前的符号 串为 E+T*i，除了可将i归约成F外，还可将E+T 或T归约成E，分别得到符号串E*i和E+E*i。但是 ，若真按这两个方案进行归约，则当我们把其归 约成E*E或E+E*E时，就再也归约不下去了。这 就告诉我们在第五步时，唯一正确的归约是将i 归约为F，也就是说，i是唯一可被归约的最左子 串。 那么，对于规范归约的每一步，如何确定符号串 中的当前应被归约的最左子串呢？ 这里暂且按下不提，且听2.3.32.3.3小节分解。2.3.2 语法树和二义性语法树用于直接地描述
6、一个句型右句子的语法结构 语法树是一有向树（连通的） 1）有且仅有一个无任何前驱的结点，称为根 （S）； 2）除根外，每个结点恰有一个直接前驱； 3）对于任一结点m，从根到m可达; 4) 每个结点的后继是有序的（从左到右） 设G=(VN,VT,P,S)是一文法，则满足下述条件的树称为语法树： 1）每个结点有一标记X， XV； 2）根的标记为S（开始符）； 3）若结点X有后继，则XVN； 4）A有k个后继，自左至右为X1, X2, , Xk，则A X1X2Xk P语法树的性质及实例语法树的性质及实例语法树的所有叶结点自左 至右排列构成了文法G的 一个句型 对一语法树而言，其构造 过程不同对应了不
7、同的推 导（归约）过程 例如，文法GE的句型 i+i*i相应的语法树见右图 。EE+TTFiT*FFii文法的二义性 存在这样的文法G，其某个句子wL(G),可对应结构不 同的语法树，即w对应了多个不同的最左（右）推导， 这类文法称为二义性文法二义性文法。 例如，G3E：EE+E|E*E|(E)|i 的句型i+i*ii+i*i及文法 Cif B then C|if B then C else CC S的句型：if B1 then if B2 then S1 else S2 上面两个句型均有两个不同的语法推导树（见下页）， 所以，它们是二义性文法EEEEE+*iiiE EEEE+*iiiif B
8、1 then C else CCif B2 then CS1 S2Cif B1 then CS1 S2if B1 then C else C二义性语法的例子二义性语法的例子关于二义性文法 应指出，二义性是一种常见的语法现象，然而，对于编译 程序而言，二义性文法是有害的。 为解决二义性文法带来的不确定性问题，通常的方法一是 修改文法，例如，文法G3可用本章（P20 (2.2)式）定义 的文法G2E取代，而G2不是二义性的。 二是利用附加条件。例如， i+i*i的归约过程中，若规定 *比+优先级高，则可强制性地让系统先按E*E进行归约， 而不是先按E+E进行归约；又比如，若强制规定else只能 和
9、距其最近的尚未被匹配的then进行匹配，就可解决else 悬空的问题。关于二义性文法（续）应指出，任一前后文无关文法是否是二义性的是不可判定的。 对于某个具体的文法而言，其二义性还是可判定的。 存在一些判定文法是否二义性的充分条件： 若一文法含有既是左递归又是右递归的文法符号，即有 A+ AvA vV*或 A+ A或 A+ A及 AA则G必定是二义性的。 并非所有的文法可消除二义性。即存在这样的CFL，定义它的一切文 法都是二义性的。这样的语言称为先天二义性语言。例如，为一先天二义性语言。CFL的先天二义性也是不可判定的。2.3.3 短语和句柄问题: 在自底向上(简记为)的语法分析中, 对于每
10、一步直接归约,应如何正确地确定当 前句型中应被归约的最左子串? 考虑文法G2E的句型= E+T*F+i,从开始符 E 推导出 的语法树见右图 该树中含有若干子树,如T(2)为根的子树对应 的叶结点为T(3)*F(3),由于它是一直接子树,文 法中必有产生式T-T*F;因此,称T*F是句型 相对于产生式T-T*F的直接短语.同理,F(1) 对应的直接短语为i. 以E(1)为根的子树相应的叶结点为 E(2)+T(3)*F(3),所以,称为句型相对于非终结 符E 的短语.同理,i是相对于T(1)的短语E EE E(1)(1) + T+ T(1)(1)E E(2)(2) + T + T(2)(2)T
11、T(3)(3) * F * F(3)(3)F F(1)(1)i i短语、直接短语及句柄的定义例如，对句型= E+T*F+i，由定义，有： (1)E* E+T+i(=E+,A=T, =+i)及TT*F(=),故T*F是 相对于产 生式T-T*F的直接短语; (2)E* E+T*F+F Fi,i是 相对于产生式F-i的直接短语; (3)E* E+i与 E + E+T*F,E+T*F是相对于非终结符E的短语; (4)E* E及E* E+T*F+i(= ), 是相对于E的短语 注:由定义可知,直接短语也是短语,但短语不一定是直接短语.归约时被替换子串的选择 从句型=E+T*F+i的语法树可知,E+T绝
12、不是它的一个直接 短语,因为虽然E-E+T是G2的一个产生式,但不存在从E到 E*F+i的推导,所以,当判断一符串是否为某一句型的短语 时,须检查定义2.8的两个条件是否同时满足. 采用分析时,每步归约就是将一个产生式右部替换其左 部,也就是把该句型的语法树中的一棵直接子树的末端结 点剪去.即每次归约的符号串必是当前句型的一个直接短 语. 但是,对一句型而言,其直接短语可能不唯一.为了让分析 能够机械地进行,我们只考虑规范归约(最左归约),即归约 过程替换的是归左直接短语. 我们以L(G2)的句子i+i*i+i为例,给出其最右推导(规范归 约的逆过程),来说明每次规范归约的子符号串句柄的定义E
13、E+T E+F E+i E+T +i E+T*F+i E+T*i+i E+F*i+i E+i*i+i T+i*i+i F+i*i+i i+i*i+i 上面的推导过程的逆过程就是规范归约的 过程。从其逆过程可看出，每步归约的均 是当前句型的最左直接短语（最左直接子 树的叶结点）。我们把它称为当前句型的 句柄。 定义2.9 一个句型的最左直接短语称为此 句型的句柄。 问题：如何确定一规范句型的句柄？句柄 应被归约成哪个非终结符？ 这个问题留到第四章介绍。EE + TE + TT * FTFiFFiii12345678910112.4 文法的化简与改造2.4.1 无用符号和无用产生式的删除 设G=(
14、VN,VT,P,S)是一文法,XVNVT,X称为是有用的,若X至 少出现在一个句子的推导过程中,即X满足: (1) 存在, V* ,有 S* X(2.12) (2)存在w VT*,使 X * w(2.13) 否则,称X是无用的.若一产生式含有无用符号,则此产生式称 为无用产生式. 无用产生式给语法分析带来了许多麻烦,应予以删除.消除无用产生式的算法算法2.1 将文法G = (VN,VT,P,S),改造为 G1=(VN,VT,P,S),使得对于 每个X VN,存在w VT*, 满足 X* w. (1)置VN,P为空; (2)对于P中每个产生式A, 若 (VNVT)*,则将A加 入VN中; (3)重复(2),直到VN不再增大; (4)对于每个A P,若 (VNVT)*,则置A 于P 中.算法2.2 任给文法G= (VN,VT,P,S),构造 G=(VN,VT,P,S), 使x (VNVT), , (VN VT)*, 有 S * x (1)置VT为空,VN=S; (2)对于 A P,若 A VN则置中所有非终结符 入VN ,所有终结符入VT ; (3)重复(2),直到V不再增大; (4)令P=A | A P, (VN VT)*,A VN消除无用产生式的例子例 G=(S,U,V,W,a,b,c,P,S),其 中,P: SaS | W | UUa V bV |ac W aW 现对
