编译原理考试知识点新复习.docVIP

第一章： 编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成， 代码优化，目标代码生成 解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。 编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。 解释程序和编译程序的根本区别：是否生成目标代码 第三章： Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类： 0型文法（PSG） à 0型语言或短语结构语言 文法 Ｇ的每个产生式α→β中：若α∈Ｖ*ＶNＶ*, β∈(ＶN∪ＶT)* ， 则 Ｇ是0型文法，即短语结构文法。 1型文法（CSG） à 1型语言或上下文有关语言 在0型文法的基础上：若产生式集合中所有|α|≤|β|，除Ｓ→ε(空串)外， 则Ｇ是１型文法,即：上下文有关文法 另一种定义： 文法G的每一个产生式具有下列形式：αAδ→αβδ，其中α、δ∈V*，A∈VN，β∈V+； 2型文法（CFG） à 2型语言或上下文无关语言 文法Ｇ的每个产生式A→α，若A∈ＶN ,α∈(ＶN∪ＶT)*，则Ｇ是２型法，即：上下文无关文法。2型文法 1型文法 0型文法 3型文法 3型文法（RG） à 3型语言或正则(正规)语言 若Ａ、Ｂ∈ＶN，ａ∈ＶT或 e， 右线性文法：若产生式为Ａ→ａＢ或Ａ→ａ 左线性文法：若产生式为 Ａ→Ｂａ或Ａ→ａ 都是３型文法（即：正规文法） 最左（最右）推导 在推导的任何一步αT β，其中α、β是句型，都是对α中的最左（右）非终结符 进行替换 规范推导：即最右推导。 规范句型：由规范推导所得的句型。 句子的二义性（这里的二义性是指语法结构上的。） 文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 文法的二义性 一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 短语 若ST* αAδ且 A T +β，则称β是句型αβδ相对于非终结符A的短语。 简单短语（直接短语） 若ST * αAδ且ATβ，则称β是句型αβδ相对于非终结符A 的简单短语。 句柄 一个句型的最左简单短语。（产生式的右部） 子树与短语的关系 (1) 短语：子树的末端结点(即树叶)组成的符号串； (2) 直接短语：简单子树的末端结点组成的符号串； (3) 句柄：最左简单子树的末端结点组成的符号串； 左图所示的关于句型E+E*i的语法树来说： 它有3棵子树，即3个短语 分别为i、E*i和E+E*i； 直接短语、句柄均为i。 从语法树中可以看出， 所有树叶的组合就是其相对应的父结点的短语。 句型i+i*i的语法树 有8棵子树，短语和直接短语如下： 直接短语：i1， i2 ， i3 短语：i1，i2，i3，i1*i2，i1*i2+i3 句柄：i1 注意：i2+i3不是短语不是某棵子树的结果 第四章： 单词符号的输出形式 二元组：（单词种别，单词自身的值） 单词符号的分类 关键字，标识符 ，常数，运算符，界符等（这种分类不是唯一的） 【例4.2】 令S={a，b}， S上的正规式和相应的正规集的例子有: 正规式 正规集 a {a} a?b {a, b} ab {ab} (a?b)(a?b) {aa, ab, ba, bb} a * {e, a, aa, …任意个a的串} (a?b)* {e ,a,b,aa,ab …所有由a和b组成的串} (a?b)*(aa?bb)(a?b)* {S*上所有至少含有两个相继的a或两个相继的b组成的串} DFA定义:一个确定的有穷自动机Md是一个五元组：Md=（K,Σ, f, S, Z），其中： (1) K：有穷状态集；(2) Σ：有穷输入字母表； (3) f ：转换函数，K×Σ è K的单值映射； 即 f (ki , a)=kj ，其中 ki、kj∈K，a∈Σ； (4) S ： S∈K，惟一初态； (5) Z：ZíK，是一个终态集，也称可接受状态或结束状态。 【例】DFA M=({S,