南京工程学院编译原理复习提纲水印.doc

编 译 原 理 复 习 提 纲 注： ? 为老师划红线的标了重点的； 未整理到的会注明“翻书“，或者有相关吐槽点； 欢迎使用继J2EE后，第二弹复习材料； 来 , 让 我 们 一 起 开 心 、快 乐 、 愉 悦 的 复 习 吧 ^_^ ? 选择，填空，简单(概念),综合(词法分析、自动机、中间代码)(四五六章)，例子，课后习题 第章编译原理=形式语言+编译技术 ? 程序设计语言的定义涉及：语法、语义、语用、语境。 ? 汇编程序：把汇编语言程序翻译成等价的机器语言程序（机器指令序列） ? 编译程序：把高级语言程序翻译成等价的低级语言程序 ? 程序的翻译的两种方式：解释方式和翻译方式 解释执行方式： 解释程序，逐个语句地模拟执行翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 ? 计算机程序的编译过程，一般分为五个阶段：词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 ? 词法分析的任务：扫描源程序的字符串，识别出的最小语法单位（标识符或无正负号数等） ? 语法分析是：语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。在词法分析的基础上的，语法分析不考虑语义。 语义分析是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。 语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译划分成前端和后端。 ? 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析? 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是：可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 编译程序的分类：1.诊断型编译程序（找错） 2.优化型编译程序（产生空间小速度快） 3.交叉型编译程序（一些设备上的嵌入式应用软件一般是在另外类型的计算机上设计和开发，经过编译、运行、和测试后再经过一次编译产生出在上述设备上可以运行的目标代码这类编译程序称之为交叉型编译程序） 4.可变目标型编译程序Lex是通用的词法分析生成器，它的输入是描述单词结构的正规式，输出的就是词法分析程序。 预处理器：它是在编译程序真正开始翻译源程序之前调用的一个独立的程序，以便加快和简化翻译工作。预处理器可以删除源程序中的注释、空格符等与程序无关的部分，执行宏代换等工作第二章 ? 符号，字母表，符号串，符号串的长度计算 P18，子符号串符号串的简单运算XY ，Xn 符号串集合的概念符号串集合的乘积运算方幂运算，闭包与正闭包的概念 P19，P20 A0 ={ε} 重写规则，简称规则(U,u)。写作： U::=u 。其中U是一个符号，u是有穷非空符号串。定义2.10 ? 非终结符（Vn）? 终结符（Vt）? 右部仅是单个非终结符号的规则构成了特殊的一类，称为单规则。 ? 文法的概念G[Z]是有穷非空的重写规则集合，其中Z是识别符号，G是文法名。定义2.11 P23 ? 识别符号.P23 文法的第一个重写规则的左部符号为识别符号。BNF表示法 P6 ? 直接推导和直接规约，广义推导广义规约，P24 G是一文法，如果对于某些符号串x与y，能写出v=xUy 与 w=wuy，且U::=u是G中的规则，则说符号串v直接推导到或直接产生符号串w，记作v=w。或者说，w是v的直接推导，w直接规约到v。 上述，v、w∈V+，x、y∈V*，可以有x=y=?，这样对文法G的任何规则U::=u，有U=u。总可由左部U直接推导到右部u，或由右部u直接规约到左部U。定义2.13 ? 最左推导，最右推导P62 ? 句型和句子 26 定义2.16 文法G[Z]，符号串x是从识别符号Z推导所得的，即Z=* x x∈V+，即称符号串x是该文法G的一个句型。如果一个句型x仅由终结符号所组成，即Z=* x x∈VT+，称该句型x为该文法G的一个句子或一个字。 ? 短语，简单短语2.17 文法G[Z]，w=xuy是该文法的一个句型，有Z=*xUy,U∈VN，且U=+ u，u∈V+。则称u是句型w中相应于U的短语。如果满足Z=* xUy，且U=u，则称u是句型w中相对于U的简单短语。 ? 句柄， 一个句型的最左简单短语称为该