编译原理第三版部分知识点整理.docx

编译原理知识点整理 编译原理是一门研究如何将高级语言转换为低级语言的学科。编译程序是将高级语言程序转换为低级语言程序的过程。编译程序的工作过程一般可划分为五个阶段：词法分析、语法分析、语义分析与中间代码生成、优化、目标代码生成。 编译程序的结构包括词法分析器、语法分析器、语义分析和中间代码生成器、优化器、目标代码生成器、表格管理和出错处理。词法分析器对源程序进行词法分析，输出单词符号。语法分析器对单词符号进行语法分析，识别各类语法单位，判断输入串是否构成语法上正确的“程序”。语义分析和中间代码生成器按照语义规则对语法分析器规约出的语法单位进行语义分析，并把它们翻译成一定形式的中间代码。优化器对中间代码进行优化。目标代码生成器把中间代码翻译成目标程序。 编译程序的结构还包括表格管理和出错处理。表格管理中最重要的符号表，用来登记源程序中出现的每个名字以及名字的各种属性。出错处理程序如果源程序有错误，编译程序应该设法发现错误，把有关错误信息报告给用户。 高级语言分类有强制式语言、应用式语言、基于规则的语言、面向对象的语言等。Pascal 是一个允许子程序嵌套定义的语言。常见的初等数据类型包括数值数据、逻辑数据、字符数据、指针类型等。 文法是描述语言的语法结构的形式规则（语法规则）。上下文无关文法是一个特殊的文法，所有的产生式左边只有一个非终结符。一个上下文无关文法包括四个组成部分：一组终结符号、一组非终结符号、一个开始符号、一组产生式。开始符号 S 至少必须在某个产生式的左部出现一次。 文法定义语言的过程称为推导。直接推导：称 αAβ 直接推出 αγβ，即 αAβ⟹ αγβ，仅当 A → γ 是一个产生式。最左推导：任一步 α⟹ β，都是对 α 中的最左非终结符进行替换。最右推导：任一步 α⟹ β，都是对 α 中的最右非终结符进行替换。 假定 G 是一个文法，S 是它的开始符号。若 S 经 0 步或多步推导出 α，则称 α 是一个句型。仅含终结符号的句型是一个句子。文法 G 所产生的句子的全体是一个语言，记为 L(G)。用一张图表示一个句型的推导，称为语法树。树的根结点为开始符号，随着推导逐步展开。 二义文法：如果一个文法存在某个句子对应两颗不同的语法树，也就是存在两个不同的最左（右）推导，则说这个文法是二义的。对于程序设计语言，分析时希望分析过程唯一，所以对二义文法应消除二义性。 词法分析是编译程序的第一阶段。词法分析器的功能：输入源程序、输出单词符号。单词符号的种类包括关键字、标识符、常数、运算符、界符。单词输出形式：<单词种别，单词属性值>。状态转换图是一张有限方向图，结点代表状态，用圆圈表示。状态之间用箭弧连结，箭弧上的标记代表射出结点状态下可能出现的输入字符或字符类。 字母表∑：一个程序设计语言只使用有限字符集，此字符集称为字母表。字符：∑中每一个元素称为一个字符。字(字符串)：是指由∑中的字符所构成的一个有穷序列。空字：不包含任何字符的序列称为空字，记为 ε。空集：不包含任何元素的集合，记为 Φ。∑*（闭包）：取字母表中的 0 个、1 个…多个字符构成的字符串的集合。