ch3-文法和语言.ppt

* 例：G‘[E]: E → i E → E+E E → E*E E → (E) E E + E E * E i i i E E * E i E + E i i 句型 i*i+i 的两个不同的最左推导： 推导1：E ? E+E ? E*E+E ? i*E+E ? i*i+E ? i*i+i 推导2：E ? E*E ? i*E ? i*E+E ? i*i+E ?i*i+i * 二义文法 若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的 若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的 判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件 * 文法的二义性和语言的二义性 文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法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中无法找