编译原理chpt4 文法和语言.ppt

* 但也有一些上下文无关语言，它的每一个文法都是二义的，则说此语言是先天二义的。 判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。 在编译实践中形成了一些比较实用的技术，可以为无二义性寻找一组充分条件，用于将二义性文法变换为无二义性文法。比如利用优先级规则，左结合或右结合规则和最近嵌套规则等。 G[S]：S-〉if B then S | if B then S else S | A G’[S]：S-〉C | U C-〉if B then C else S | A U-〉if B then S 就近匹配 * §4 句型的分析 句型分析就是识别一个符号串是否为某文法句型的过程。 编译程序中，完成句型分析的模块称为分析程序或识别程序。 两类分析方式： 自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。 自下而上分析法：从输入串开始，进行归约，直至归约到开始符号 不同分析方式反映了语法树的的不同构造过程 * 1 S →cAd 2 A →ab 3 A →a 自上而下的语法分析识别输入串w cad是否为该文法的句子 若S ? cAd 后选择 2 扩展A，S ? cAd ? cabd 那将会？w的第二个符号可以匹配，但第三个符号却不能匹配 ？宣告分析失败，显然结论错误。