编译原理第15章-参考资料.ppt

句型 (sentential forms) 设 CFG G = (VN, VT, P , S )，称 ??(VN?VT)* 为 G 的一个句型，当且仅当 S ? ?. 若 S ? ? ，则 ? 是一个左句型; 若 S ? ? ，则 ? 是一个右句型. 若句型 ?? VT* ，则称 ? 为一个句子（sentence）. ? lm rm ? ? 上下文无关语言及其描述 上下文无关文法的语言 设 CFG G = (VN, VT , P , S )，定义 G 的语言为 L(G) = { w ?w?VT*? S ? w } G ? 上下文无关语言（context-free languages） 如果一个语言 L 是某个 CFG G 的语言，即 L(G) = L， 则L是上下文无关语言. 上下文无关语言及其描述 文法与语言的 Chomsky 分类方法 文法（grammar）是一个四元组 G = (VN, VT, P , S )， VN、VT、P 及 S 的含义如前. Chomsky 通过对产生式施加不同的限制，把文法 及其对应的语言分成四种类型，即0 型、 1 型、 2 型和 3 型. 上下文无关语言及其描述 文法与语言的 Chomsky 分类方法 0 型 0 型文法 G = (VN, VT, P , S ) 的产生式形如 ? ? ? , 其中 ?, ? ?(VN?VT)*，但 ? 中至少包含一 个非终结符. 能够用 0 型文法定义的语言称为0 型语言 或递归可枚举语言. 上下文无关语言及其描述 文法与语言的 Chomsky 分类方法 1 型 1 型文法 G = (VN, VT, P , S ) 的产生式形如 ? ? ? , 满足 ???????，仅 S ? ? 例外，且要求 S 不得出现在任何产生式的右部. 1 型文法也称为上下文有关文法（context- sensitive grammars）. 能够用 1 型文法定义的语言称为 1 型语言 或 上下文有关语言. 上下文无关语言及其描述 文法与语言的 Chomsky 分类方法 2 型 2 型文法 G = (VN, VT, P , S ) 的产生式形如 A ? ? , 其中A?VN，? ?(VN?VT)*. 2 型文法也称为上下文无关文法. 能够用 2 型文法定义的语言称为2 型语言， 或上下文无关语言. 上下文无关语言及其描述 文法与语言的 Chomsky 分类方法 3 型 3 型文法 G = (VN, VT, P , S ) 的产生式形如 A ? aB 或A ? a, 其中A, B?VN，a?VT ?{?}. 能够用 3 型文法定义的语言称为3 型语言， 或正规语言. 3 型文法也称为正规文法. 上下文无关语言及其描述 语法分析树 (1) E ? EOE (2) E ? (E) (3) E ? v (4) E ? d (5) O ?＋ (6) O ? ? 归约过程自下而上构造了一棵树 如对于文法Gexp ，关于 v ?(v＋d) 的一个归约过程可以认为是构造了如下一棵树： v ?(v＋d) （4） v ?(v＋E) （6） vO(v＋E) （3） vO(E＋E) （5） vO(EOE) （1） vO(E) （2） vOE （3） EOE （1） E E E O E E O E E d ＋ v ( ) ? v 上下文无关语言及其描述 语法分析树 推导过程自上而下构造了一棵树 如对于文法Gexp ，关于 v ?(v＋d) 的一个推导过程可以认为是构造了如下一棵树： (1) E ? EOE (2) E ? (E) (3) E ? v (4) E ? d (5) O ?＋ (6) O ? ? E d ＋ v ? v O E E E ( ) E E O v ?(v＋d) （4） v ?(v＋E) （6） E ?(E) （3） （1） v ?(EOE) （