编译原理 第 四 讲.ppt

1.文法的类型 通过对产生式施加不同的限制，Chomsky将文法分为四种类型： 0型文法：对任一产生式α→β，都有α∈(VN∪VT)+， β∈(VN∪VT)* 1型文法：对任一产生式α→β，都有|β|≥|α|， 仅仅 S→ε除外 2型文法：对任一产生式α→β，都有α∈VN ， β∈(VN∪VT)* 3型文法：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN ，B∈VN ，a∈VT 文法的类型 例：1型（上下文有关）文法 文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD 文法的类型 例：2型（上下文无关）文法 文法G[S]： S→AB A→BS|0 B→SA|1 3型文法 G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 G[I]： I → lT I → l T → lT T → dT T → l T → d 2.文法之间的包含关系 四种文法之间的逐级“包含”关系 3.文法和语言 0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ） 上下文无关文法及其语法树 上下文无关文法有足够的能力描述程序设计语言的语法结构 语法树---句型推导的直观表示 描述简单算术表达式的文法 G=(｛E｝,｛+,*,i,(,)｝,P,E)其中P为： {E→i , E→E+E , E→E*E , E→(E) } 描述一种简单赋值语句的产生式： 〈赋值语句〉→i∶=E 描述条件语句的产生式： 〈条件语句〉→if〈条件〉then〈语句〉｜ if〈条件〉then〈语句〉else〈语句〉 1.规范推导和规范归约 G[s]: ① S→aAS　　② A→SbA　　③ A→SS　　④ S→a　　⑤ A→ba 推导过程一：S ? aAS ? aAa ? aSbAa ? aSbbaa ? aabbaa推导过程二：S ? aAS ? aSbAS ? aabAS ? aabbaS ? aabbaa推导过程三：S ? aAS ? aSbAS ? aSbAa ? aabAa ? aabbaa 1.规范推导 规范句型 最左（最右）推导：在推导的任何一步α?β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型 规范推导的逆过程，称为最左归约，也称为规范归约。 例：设有文法G[E]： E→E+T|T T→T*F|F F→(E)|a给出句子a+a*a的最左和最右推导 2.语法树 设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）： 1. 每个结点都有一个标记，此标记是V的一个符号 2. 根的标记是S 3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定A∈VN 4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一个产生式 语法树的结果： 从左到右读出叶子的标记而构成的行谓之 ? 构造语法树 G[E]： E→E+T|T T→T*F|F F→(E)|a E?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a E?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a E?E+T ?E+T*F ?E+T*a ?E+F*a ?E+a*a ?T+a*a ?F+a*a ?a+a*a E?E+T ?T+T ?T+T*F ?F+T*F ?F+F*F ?a+F*F ?a+F*a ?a+a*a E E + T T T * F F F a a a 看不出句型中的符号被替代的顺序 一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导