ch3-new文法和语言.ppt

* 文法的二义性和语言的二义性 文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G′，其中G是二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的。 二义文法改造为无二义文法 G‘[E]:E → i G[E]： E → T|E+T E → E+E T → F|T*F E → E*E F → （E）|i E → (E) 规定算符优先性和结合性 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。 * 3.6 句型的分析（上下文无关文法） 句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。 * 句型的分析算法分类 分析算法可分为： 自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。 自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 * 两种方法反映了两种语法树的构造过程。 自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串 自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树 * 1、自上而下的语法分析 例：文法G： S → cAd A → ab A → a识别输入串w=cabd是否为该文法的句子 S S S c A d c A d a b 推导过程：S ? cAd cAd ? cabd * 2、自下而上的语法分析 例：文法G： S → cAd A → ab A → a识别输入串w=cabd是否该文法的句子 S A A c a b d c a b d c a b d 规约过程构造的推导： cAd ? cabd S ? cAd * 自上而下的语法分析(1)S → cAd (2) A → ab (3) A → a 识别输入串w=cad是否为该文法的句子 若S ? cAd 后选择(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=cabd是否为该文法的句子自下而上的语法分析 对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A， 那么在c A b d中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子 c a b d c A b d a * 3、句型分析的有关问题 1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？ 2）在自下而上的分析方法中如何识别可归约的串？ 在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串” * 3、句型分析的有关问题 若G是一文法，S是文法的开始符号，αβδ是文法的一个句型。如有S =* αAδ且A=+ β,则称β是句型 αβδ相对于非终结符A的短语。 如果A=β，则称β是句型 αβδ相对于规则A-β的直接短语。（或简单短语） 一个句型的最左直接短语称为句柄