《编译原理第4讲(第三章).ppt》由会员分享，可在线阅读，更多相关《编译原理第4讲(第三章).ppt（21页珍藏版）》请在三一办公上搜索。
1、1,第三章文法和语言,符号和符号串文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明,2,（上下文无关文法）句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,3,句型的分析算法分类,分析算法可分为：自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一
2、个最左推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,4,两种方法反映了两种语法树的构造过程,自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树,5,自上而下的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,SSScAdcAd a b推导过程：S cAd cAd cabd,6,自下而上的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否该文法的句子,7,若S cAd
3、后选择(2)扩展A，S cAd cabd那将会？w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。,S c A d a b 这时应该回朔，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）,自上而下的语法分析(1)S cAd(2)A ab(3)A a 识别输入串w=cad是否为该文法的句子,8,自下而上的语法分析(1)S cAd(2)A ab(3)A a识别输入串w=cabd是否为该文法的句子,对串cabd
4、的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在c A b d中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子,c a b d c A b d a,9,句型分析的有关问题,1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？2）在自下而上的分析方法中如何识别可归约的串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,10,短语、直接短语和句柄的定义,文法GS句
5、型的短语S=*A且 A=+，则称是句型相对于非终结符A的短语句型的直接短语若有A，则称是句型相对于非终结符A 的直接短语句型的句柄一个句型的最左直接短语称为该句型的句柄,不一定是终结符串,11,直观理解,直观理解：短语是前面句型中的某个非终结符所能推出的符号串。,注意：短语、直接短语是相对于句型而言，一个句型可能有多个短语、直接短语，句柄只能有一个。,可以通过刚才的定义来寻找短语，直接短语，句柄。但是一般我们按照语法树来找，因为这个更简单更快捷。下面，我们介绍这种方法。,12,用语法树找短语，直接短语，句柄,子树：语法树中的某个非叶结点连同它所有子孙所组成的树。,短语：一棵子树的所有叶子自左至
6、右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的语法树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。,13,例子,E E+T T FT*F i3F i2i1,GE：EE+T|T TT*F|F F(E)|i句型：i*i+I短语：i1*i2+i3，i1*i2，i1，i2，i3直接短语：i1，i2，i3句柄：i1,14,例子(续),=,短语,短语,短语,直接短语i3,15,例子(续),=,=,短语,短语,短语,直接短语,直接短语i1,16,例子(续),*,+,i+i 都不是短语。原因很简单：不存在一棵这样的子
7、树，该子树叶结点是由它们构成的。,=,最左直接短语i1，即为句柄,17,文法实用中的一些说明,限制化简文法文法中不含有有害规则和多余规则有害规则：形如UU的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则 文法中不含有不可到达和不可终止的非终结符1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。,18,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1.A必须在某句型中出现 即有S=*A，其中，属于V*2.必须能够从A推出终结符号串t来 即A=*t，
8、其中tVT*,19,化简文法,例：GS：1)SBe 2)BCe D为不可到达 3)BAf C为不可终止 4)AAe 5)Ae 6)CCf 7)Df 产生式 2），6），7）为多余规则应去掉。,20,上下文无关文法中的规则,上下文无关文法中某些规则可具有形式A，称这种规则为规则因为规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现两种定义的唯一差别是句子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果语言L有一个有穷的描述，则L1=L也同样有一个有穷的描述，并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L和L-分别是上下文有关语言、上下文无关语言和正规语言。,21,习题,P47 1 25(2)14,
