编译原理第7节课第二章.pptVIP

文法的二义性存在这样的文法G，其某个句子w?L(G)，可对应结构不同的语法树，即w对应了多个不同的最左（右）推导，这类文法称为二义性文法。存在一些判定文法是否具有二义性的充分条件若一文法含有既是左递归又是右递归的文法符号，即：AAvA，v?V* 或 AA或 AA?且A?A则G必定是二义性的。句柄的定义定义2.9一个句型的最左直接短语称为此句型的句柄。问题：如何确定一规范句型的句柄？句柄应被归约成哪个非终结符？这个问题留到第四章介绍。2.4文法的化简与改造2.4.1无用符号和无用产生式的删除设G=(VN,VT,P,S)是一文法，X?VN∪VT，X称为是有用的，是指X至少出现在一个句子的推导过程中，即X满足:(1)存在?,??V*,有S?X? (2.12)(2)存在w?VT*,使?X?w(2.13)否则，称X是无用的。2.4文法的化简与改造若一产生式含有无用符号，则此产生式称为无用产生式。无用产生式给语法分析带来了许多麻烦，应予以删除。例S?aS|W|U U?aV?bV|ac W?aW因为符号V不在任何句型中出现，而由符号W不能推出终结符号串来，故V和W都是无用符号。消除无用产生式的算法算法2.1将文法G=(VN,VT,P,S)，改造为G1=(VN′,VT,P′,S)，使得对于每个X?VN′,存在w?VT*，满足Xw。(1)置VN′,P′为空；(2)对于P中每个产生式A??，若??(VN′∪VT)*，则将A加入VN′中；(3)重复(2)，直到VN′不再增大；(4)对于每个A???P，若??(VN′∪VT)*,则置A??于P′中。算法2.2任给文法G=(VN,VT,P,S)，构造G′=(VN′,VT′,P′,S)，使?x?(VN′∪VT′)，??,??(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′}例2.6设有文法G=({S,U,V,W},{a,b,c},P,S)，其中P为:S?aS|W|U U?aV?bV|ac W?aW现对G执行算法2.1:1.由U?a和V?ac右部都是终结符,VN′={U,V};2.对于S?U,由U?VN′，有VN′={S,U,V};此外再无可放入VN′的符号，得G1为：S?aS|UU?aV?bV|acG1为：S?aS|UU?aV?bV|ac现对G1执行算法2.2:1.置VT〞=?，VN〞={S};2.由S?U及U?a，将U及a分别放入VN〞和VT〞中，VN〞={S,U}，VT〞={a}3.此外,VN〞和VT〞不再增大，得G2为：S?aS|UU?a注意,在删除无用符和无用产生式时，应先执行算法2.1，再执行算法2.2，就可得到“干净”的文法；若先执行算法2.2，再执行算法2.1，所得文法不一定“干净”。2.4.2?-产生式的消除?-产生式是指右部为一空符号串?的产生式。因为某些语法分析算法要求不含?,此时应消除之。若一语言不含?（即??L(G)），则可将其完全消除；若??L(G)，则可将文法改造为只有开始符S可推导出?(即S???P)，而且S不出现在任何产生式的右部，此外再无其它?-产生式。例如，文法G[S]：