《编译原理及实践教程》第2章高级语言设计基础要点.ppt

语言的有穷表示 语言的有穷表示有两种方法： 用产生的观点来表示语言。方法：为语言定义一组规则，利用规则产生语言中的每个句子。 用识别的观点表示语言。方法：利用一个算法（有限自动机）来判断某个给定的符号串（句子）是否在某语言中。 本章先从“产生的观点”来描述语言——文法。 有时为书写简洁，常把相同左部的产生式进行缩写。如： 其中，每个αi是A的一个候选式。 例2.4：下面是一个文法的几种等价写法。 文法的分类 例2.10 例2.11 4类文法总结： 4类文法的定义是对产生式逐渐加限制的，对应的语言描述能力越来越弱。 每种正规文法也都是上下文无关文法，每种上下文无关文法也都是上下文有关文法，而每种上下文有关文法也都是0型文法。 4类文法应用 在编译技术中通常使用正规文法（3型文法）描述高级程序设计语言的词法部分，用有限自动机来识别单词。 使用上下文无关文法（2型文法）描述高级程序语言的语法结构，用下推自动机识别语法成分。 例：考虑文法G2: 它定义的语言是： S ? AB A ? aA|a B ? bB|b L(G2) = {ambn |m,n≥1} 例2.8：构造一个文法G使得： L(G) = {anbn |n≥1 } S ? aSb S ? ab a,b的个数相同,则文法G为： 文法等价： 若文法G1和文法G2所产生的语言相同，即L(G1) = L(G2)，则称文法G1和文法G2等价。 例：有如下两个文法，判断它们是否等价？ G1=（{S}，{0}，{S?0S，S?0}，S） G2=（{S}，{0}，{S?S0，S?0}，S） S?0 S?0S?00 …………… S?0S ?00S?… ?000……0 L(G1) = {0n | n≥1} 对于G2： 对于G1 ： S?S0 ? S00?… ?000……0 L(G2) = {0n | n≥1} G1?G2，但L(G1) = L(G2)，文法G1和G2等价 例 : G = ({E}, {i, +, *, (, ) } , P , E) P： E ? E + E | E * E | ( E ) | i 表达式 (i+i)*i的推导过程： (1) E ? E*E ? (E)*E ? (E + E)*E ? (i + E)*E ?(i + i)*E ? (i + i)*i (2) E ? E*E ? E*i ? (E)* i ? (E + E)*i ? (E+ i)*i ?(i + i)*i 对给定的文法，定义的语言是由利用所有的产生式经过各种方式推导出所有可能的句子构成的，并没有规定推导使用产生式的顺序。 因此从一个句型到另一个句型(句子)的推导过程不是唯一的。 文法的二义性 语法树（分析树）：推导的形式化表示，有助于理解句子语法结构的层次 每个结点都有一个标记，该标记属字母集中的一个符号，根由开始符号Ｓ标记。 随着推导，当某个非终结符被它的某个候选式所替换时，就产生相应的下一层的结点，候选式中自左至右的每个符号对应一个新的结点，并标记它，画出其与父结点之间的连线。 末结点从左到右排列起来构成一个句型。 如果自左至右端末结点排列起来都是终结符，则这颗树表示了一个句子的推导过程。 例：对文法G = ({E}, {i, +, *, (, ) } , P , E)  P： E ? E + E | E * E | ( E ) | i 句子(i+i)*i 的最左推导的语法树是？ 在语法树的推导过程中的任何时刻，没有后代的端末结点自左至右排列起来就是一个句型 一棵语法树表示了一个句型很多可能的不同推导过程。(包括最左推导和最右推导) 例3： G = ({E}, {i, +, *, (, ) } , P , E)  P： E ? E + E | E * E | ( E ) | 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 注意：并不是任何情况一个句型就唯一地对应一棵语法树。 正常优先级 +优先 定义：如果一个文法存在某个句型对应两棵或两颗以上的语法树，则称这个文法是二义文法。 对二义文法中的某个句子的分析（最左或最右推导）不是唯一的，因此有些程序设计语言的分析器要求文法是无二义的。 例2.9 证明下述文法是二义文法。 设if语句S的文法G=({E，S}，{if，then，els