《编译原理实践及应用》第2章高级语言设计基础素材.ppt

* * * * * 语言的设计与软件系统的设计类似 * * * * * * UV={aa00,aa11,bb00,bb11} * * * * * * * * * * * * * * * * * * * * * * * * * * * 最左推导在语法树中的表现主要是：总是沿最左分支替换到底，再是次左边…… 例3 : 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 对给定的文法，定义的语言是由利用所有的产生式经过各种方式推导出所有可能的句子构成的，并没有规定推导使用产生式的顺序。 因此从一个句型到另一个句型(句子)的推导过程不是唯一的。 最左推导: 在整个推导过程中,任何一步推导α=β都是对α中最左边的非终结符进行替换。 最右推导: 在推导之前确定推导的顺序，是对句子进行确定性分析所必须的 例3： G = ({E}, {i, +, *, (, ) } , P , E)  P： E ? E + E | E * E | ( E ) | i (i+i)*i的最左推导过程： E ? E*E ? (E)*E ? (E + E)*E ? (i + E)*E ?(i + i)*E ? (i + i)*i 最右推导过程： E ? E*E ? 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 并不是任何情况下一个句型就唯一地对应一棵语法树。 定义：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的 对二义文法中的某个句子的分析不是唯一的，因此总是希望文法是无二义的。 但是二义文法有时也是有用的。 证明下述文法是二义文法。 例：设if语句S的文法G=({E，S}，{if，then，else，a，e}，P，S)，其中P为： S?if E then S （1） S?if E then S else S （2） S?a （3） E?e （4） 推导(1)：S ? if E then S ? if E then if E then S else S 推导(2)：S ? if E then S else S ? if E then if E then S else S 文法的分类 文法有四种:设有G=(Vn,Vt,P,S),不同类型的文法只是对产生式的要求不同： ０型文法(短文文法)： G的每个产生式α?β满足：α∈V+且α中至少含有一个非终结符,β∈V* １型文法(上下文有关文法)：如果G的每个产生式α? β均满足|β|=|α|,仅当Ｓ?ε除外，但S不得出现在任何产生式的右部 ２型文法(上下文无关文法)：G的每个产生式为A?β, A是一非终结符，β∈V* ３型文