编译原理及其习题解答武汉大学出版社教程chap2节.ppt

* 二义性其它问题 文法和语言 人们已证明，二义性问题是不可判定的，即不存在一个算法，它能在有限步骤内，确切地判断一个文法是否是二义的。我们所能做的就是为无二义性寻找一些充分条件。 例如对文法G[E]： E→ E+E | E*E | (E) | i 修改，规定运算符“+”与“*”的优先关系和结合规则，设“*”的优先性高于“+”，且服从左结合。 G’： E→ T | E+T T→ F | T*F F→ (E) | i * 文法和语言 2.6 分析方法简介 句型分析的任务就是按文法的产生式，识别输入的符号是否是该文法的句型。语法树——是句型推导过程的几何表示，可以十分直观的显示某句型的结构。因此在句型时，对输入符号串构造语法树，以此识别它是否是该文法的一个句型（或句子）。因此，语法树又可称为语法分析树或分析树。我们把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。 分析算法又分为： 从左到右分析算法； 从右到左分析算法； 自上而下的分析法 自下而上的分析法 * 文法和语言 自上而下的分析法 基本思想：从文法的开始符号出发，反复使用各种产生式，寻找“匹配”输入符号串的推导。即对任何输入符号串，从文法的开始符号（根结）出发，自上而下地为输入串建立一棵语法树，直到语法树结果正好是输入的符号串为止。 例如：文法G[S]: S→ xAy A→ aa | a，识别输入串xay是否是该文法的一个句子。 解： S S S S x A y (2) S S S x A y (3) a (1) * 文法和语言 自上而下分析法的缺陷 　　关键：回溯问题（∵ 其分析过程是一种试探过程） 回溯问题是从各种可能的候选式中任选一个，进行推导后发现该候选式是错误的，则退回去重新选择候选式的方式。例如上例中的(3)。 S S S x A y (3) —选用第1个候选式 a 回溯的产生使算法代价极低，效率很低。关于解决回溯问题将在第5章中介绍。 a * 自下而上的分析法 文法和语言 基本思想：从输入串开始，逐步进行“归约”，直至归约到文法的开始符号。即从语法树的末端开始，步步向上“归约”，直到根结。 归约：若V= γαδ，W=γβδ，α → β是文法的产生式，如有V=W，则W直接归约到V。 * 自下而上的语法分析举例 例1：文法G：S → cAd A → ab A → a识别输入串w=cabd是否该文法的句子 S A A c a b d c a b d c a b d 规约过程：S ? cAd ? cabd * 文法和语言 例2： 文法G[S]： (1)S→ aAcBe (2) A→ b (3)A→ Ab (4) B→ d 识别abbcde是否为文法S的一个句子。 解题思想：扫描abbcde，从中找出一个子串，该子串与某一产生式的右部相匹配。 * 自下而上分析法举例 文法和语言 例2解： a b b c d e (1) a b b c d e A A (2) a b b c d e A A (3) a b b c d e A A (4) B a b b c d e A A (5) B A S * 自下而上分析法存在的问题 文法和语言 可归约串的问题；（∵ 该分析的每一步就是从当前串中找一个子串（称“可归约串”），将它归约到某个非终结符号） 自下而上分析法的关键就是找哪个子串是“可归约串”，哪个不是“可归约串”。例如上例中的(3) a b b c d e A A (3) —用产生式(2)而非(3)，则不能归约到S 因此必须精确定义“可归约串”，事实上存在着种种不同的方法刻画“可归约串”，对这个概念的不同定义，形成了不同的自下而上的分析法。在“规范归约”的分析中，用“句柄”来刻画“可归约串”。 * 短语、直接短语、句柄 文法和语言 1、短语： 令文法G，开始符号为S，αβδ是G的句型（即S αβδ