编译概述 程序设计语言及翻译程序 程序设计语言的发展 机器语言 汇编语言 高级语言 翻译程序大家族 翻译程序 能够将某种语言写的程序转换成另一种语言的程序，而且后者与前者在逻辑上是等价的。 分类 解释程序 编译程序 汇编程序 反汇编程序 交叉编译程序 交叉汇编程序 转换程序(一种高级语言转换成另一种高级语言) 高级语言的运行方式 编译方式 利用编译程序将高级语言程序翻译为机器语言程序，然后再运行这个机器语言程序 解释方式 利用解释程序直接读取高级语言程序中的每个语句，翻译并直接执行 编译程序 将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。 解释程序 将高级程序设计语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标程序的翻译程序 编译系统 高级语言编译流程 预处理、编译、汇编和链接 高级语言编译实例 gcc如何编译c程序 静态链接 在生成可执行文件的时候（链接阶段），把所有需要的函数的二进制代码都包含到可执行文件中去。 动态链接 动态链接仅记录动态链接库的路径信息。允许程序运行前才加载所需的动态链接库。 编译过程和编译程序的结构 编译过程概述 编译过程主要分为5个阶段（词法分析、语法分析、语义分析和中间代码生成、代码优化、 目标代码生成） 编译程序的结构 词法分析...目标代码生成 编译阶段的组合 编译前端 主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化 编译后端 指与目标机器有关的部分。如与机器有关的优化、目标代码生成 分析阶段：根据源语言的定义，分析源程序的结构 词法分析 语法分析 语义分析 综合阶段：根据分析结果构造出所要求的目标程序 中间代码生成 代码优化 目标代码生成 遍 是指对源程序或其中间形式从头到尾扫描一遍，并作相关的加工处理，生产新的中间形式或目标程序 分遍的好处 减少对主存容量的要求 功能独立、单纯、相互联系简单，结构清晰 实现更充分的优化工作，获得高质量目标程序 将前端和后端分开，为移植创造条件 缺点 增加不少重复性的工作 编译程序的构造方法 构造编译程序要考虑的三个要素 源语言 目标语言与目标机器 编译方法与工具 构造编译程序的方法 用机器语言或汇编语言编写 用高级语言编写（普遍使用） 自编译方式，先构造一个小的编译程序，再进一步构造较大的编译程序 用编译工具自动生成部分程序 移植，同种语言的编译程序在不同机器之间移植 认识Sample语言 高级语言的构成成分 语法和语义 程序的结构 程序 函数 语句 表达式 运算符 数据引用 关键词 单词 Sample语言规范 符合Sample语言规范的源程序举例 编译程序的发展及编译技术的应用 编译程序的发展 20世纪50年代，IBM开发了FORTRAN语言 同时开始自然语言的研究，导致根据语言文法的难易程度以及识别它们所需的算法来分类。 接着研究编译器的自动构造，出现了词法和语法分析自动生成工具。 如今将串行程序转换成并行程序的自动并行编译技术正在深入研究中，交叉编译技术火热发展， 专用语言及其编译技术不断深化。 编译技术的应用 各种软件工具的开发 语言的结构化编辑器 程序的格式化工具 语言程序的调试工具 语言程序的测试工具 程序理解工具 为什么要学习编译原理及其构造技术 深刻理解和正确使用程序设计语言 加深对整个计算机系统的理解 设计开发编译程序的软件技术同样可以用于其他软件的设计开发 编译技术的地位变得越来越重要，处理器性能很多程度上取决于编译器质量 词法分析 词法分析概述 词法分析，是分析源程序中的字符流能否构成正确的单词 词法分析的主要工作 扫描源程序 识别单词，输出单词及其种别码 过滤掉源程序中的注释、空格、回车换行等 调用出错处理程序 两种实现方式 手工编写高级语言程序实现 自动构造：使用词法分析自动生成工具来生成词法分析程序 高级语言中的单词 单词的分类 关键字 标识符 运算符 界符 如逗号，分号，花括号，注释符号等 常量 数字常量，字符串常量 单词的种别码 单词的种别码，又称token值，表示单词的种类。 单词的识别 状态转换图 状态转换图，是有限方向图，是描述单词构成规则的一种工具。 构成 有限个结点，称为状态。 结点间用带箭头的弧线连接，称为边。 边上标记的符号，表示从一个状态转换为另一个状态的输入字符。 开始状态，又称初态，用双箭头 => 标识 接受状态，又称终态，至少有一个 单词识别程序 过程 初始时位于初态，输入指针指向输入缓冲区开始。 读入一个字符，状态发生转换，寻找与之匹配的边 指针不断后移，状态不断改变，直到终态 由状态转换图可生成单词识别程序 一个大的switch case语句，每个状态对应一个case语句 case语句中根据读入的字符进行判断转入下一个状态 超前搜索技术和双界符的识别 单界符:'<' 双界符:'<=' 对于双界符来说，读取了一个字符，并不能确定是否识别了单界符和双界符，还需要向前看一个或多个字符才能确定，这种技术就是超前搜索技术。 通过提前查看而不读取的方式， 只有向前看到某个符号确定了单词或单词类别后才继续读入。 数值型常量的识别与状态转换图的合并 1.初态合并 2.边上标记的符号相同的状态合并 词法分析器的设计 词法分析器的任务就是扫描源程序，识别单词，查找单词的token值，转换并输出token值，输出相应的错误信息。 词法分析工作主要由扫描程序、识别单词、查找token值、插入token表、输出token串等组成。 正则表达式与有穷自动机 符号和符号串 单词的构成规则，需要用更加形式化的工具来描述。即正则表达式和有穷自动机。 正则表达式，是用数学表达式的形式来描述单词构成模式。 有穷自动机，是状态转换图的形式化描述。 集合的运算及语言的定义 并:AUB 其中的符串包含A与B的全部符号串 连接:AB 也叫AB的乘积，表示由A中的任一符号和B中任意符号连接构成的符号串集合 方幂:A的n次方 集合A自身的n次乘积 闭包:A* A* = A^0 U A^1 U A^2 U A^3 U ... A^0 = {空} 正闭包:A+ A+ = A^1 U A^2 U A^3 U ... 正则表达式 正则表达式也称为正规式，可以描述所有通过对某个字母表上的符号串集合应用并、连接和闭包运算而得到的语言，是一种描述字符串构成模式的方法。运用正则表达式可以来检查一个字符串是否符合匹配某种特征的子模式串。 有穷自动机 有穷自动机 要素 有穷状态集合 有穷输入字母表 状态转换函数 初始状态(初态) 接受状态集合(终态集合) DFA(确定的有穷自动机)与NFA(不确定的有穷自动机)的主要区别 （1）DFA任何状态都没有ε转换，即没有任何状态可以不进行输入符号的匹配就直接进入下一个状态； （2）DFA对任何状态s和任何输入符号a，最多只有一条标记为a的边离开s， （3）DFA的初态唯一，NFA的初态为一集合。 NFA确定化: NFA转DFA NFA确定化的基本思路是： DFA的每一个状态对应NFA的一组状态. 子集法：NFA转换时每个符号可能对应多个状态，多个状态形成一个集合，转换时根据不同符号在不同集合转换，然后这个集合对应DFA中的一个状态 DFA最小化 每个正则表达式可以对应多个DFA，但存在一个状态数最少的DFA，可用分割法求最小DFA 分割法：之所以不是最小，是因为可能存在等价的状态。分割法的思想是由终态集合和非终态集合不断分割，直到所有的子集都是不等价的为止 把DFA的全部状态划分成一些互不相交的子集，使得任何不同的两子集的状态都是可区别的（不等价），而同一子集中的任何两个状态都是等价的. DFA的最小化就是寻求状态数最少的DFA，即： 它没有多余状态；（消去） 它的状态中没有两个是互相等价的。（合并） 正则式转NFA(Thompson算法) 每个正则表达式都有相应的规则 正规式ε 正规式a 正规式R=s|t 正规式R=st 正规式R=s* 正则表达式与有穷自动机的等价性 正则表达式和有穷自动机的等价，是指由正则表达式所描述的语言和有穷自动机所识别的语言是相同的。 词法分析器的自动生成工具 Lex概述 Lex是一个基于正则表达式的描述来构造词法分析器的工具。它的输入是用Lex语言编写的源程序 。在Lex中，要将基于正则表达式的模式说明与词法分析器要完成的动作组织在一起。输出则是词法分析器的C语言程序。 Lex源文件的书写 Lex的工作原理 读取Lex的源程序，对每个正则表达式分别生成对应的不确定的有穷自动机 将这些NFA合并为一个NFA 将该NFA确定化，最小化为DFA 写出该DFA的分析控制程序 如果出现二义性，遵循最长匹配原则和优先匹配原则 Lex使用中的一些注意事项 使用Lex自动生成词法分析器 词法分析中的错误处理 词法分析的常见错误 非法字符错误 拼写错误 注释、字符常数、字符串常数不闭合 错误的“与”“或”运算 变量声明有重复 语法分析 语法分析概述 语法分析就是根据高级语言的语法规则对程序的语法结构进行分析。 文法分类 乔姆斯基体系是计算机科学中刻画形式文法表达能力的一个分类谱系，是由语言学家乔姆斯基于1956年提出。包括四个层次： 0-型文法（无限制文法或短语结构文法）包括所有的文法。 1-型文法（上下文相关文法）生成上下文相关语言 2-型文法（上下文无关文法）生成上下文无关语言 3-型文法（正则文法）生成正则语言 上下文无关文法 文法的定义 文法是描述语言的语法结构的形式规则（即语法规则），这些规则必须准确且可理解 上下文无关文法四部分组成： 终结符号集 非终结符号集 开始符号 产生式集合 推导 从上下文无关文法得到某个符号串的方法 从文法的开始符号出发，连续使用产生式右部去替换左部某个非终结符，直到全部为终结符为止，这个过程就称为推导 直接推导 又称一步推导(用符号=>表示),就是用某条规则的右部去替换该规则的左部 归约 推导的逆过程 文法产生的语言 文法等价 如果两个文法产生的语言相同，则这两个文法等价 语法树 语法树就是用一棵树来表示一个句型的推导过程，有时也称为语法分析树。 推导的形式化表示，有助于理解句子语法结构的层次 二义文法 如果一个文法存在某个句型对应两棵或两棵以上不同的语法树，则称为这个文法为二义文法 消除二义性 利用运算符之间的优先级和结合性来消除算术表达式文法的二义性 Sample语言文法描述 自上而下的语法分析 概述 从文法开始符号（根结点）出发，自上而下的为输入串建立一棵语法树 自上而下分析方法中的问题探究 问题 分析器不稳定（回溯） 提取公共左因子 无限循环（左递归） 消除左递归 试探与回溯 即当文法中存在形如A->αβ1|αβ2......的产生式，即某个非终结符 存在多个候选式的前缀相同（也称为公共左因子），则可能造成虚假匹配（即当前的匹配可能是暂时的） 试探与回溯是一种穷尽一切可能的办法，效率低，代价高，导致分析器不稳定。 解决： 改造文法，提取公共左因子 左递归 导致分析过程无限循环。假如文法中存在形如：A->Aa的产生式（称为左递归） 消除文法的直接左递归 A->Aα|β => A->βA' A'->αA'|ε 消除文法中的间接左递归 对于间接左递归，可以采用先代入，然后再消除直接左递归的方法 LL(1)文法 First集 Follow集 LL(1)文法的条件 文法不含左递归 每个非终结符A的各个候选式的First集交集为空 每个非终结符A候选式的First集中包含ε， 则 First(A) ∩ Follow(A) = ∅ 递归下降分析方法 分析程序由一组函数组成。每个函数对应于文法的一个非终结符号。 每一个函数的功能是：判断选择该非终结符的哪个候选式，并按该候选式的要求处理 完输入符号串。 预测分析方法 构成 总控程序、文法符号栈、预测分析表 预测分析表的构造 也是通过 First集、Follow集来构造的 自下而上的语法分析 自下而上分析方法概述 自下而上的语法分析，构造过程是先以被分析符号串的各个符号为叶子结点，根据文法规则，以产生式左部的非终结符为父结点，逐步向上构造子树，最后得到以文法开始符号为根的语法树。 “移进-归约”分析方法 用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。 规范规约、短语、句柄 句型 若S是文法G的开始符号,从开始符号S出发推导出的符号串称为文法G的一个句型(Sentential Form)。 句子 仅含终结符的句型是一个句子。 语言 把文法G产生的所有句子的集合称为G产生的语言(Language),记为L(G), 文法等价 若文法G1和文法G2所产生的语言相同，即L(G1) = L(G2) 短语 子树(可以一层也可以多层)的末端结点形成的符号串。 简单子树 只有一层分支的子树。 直接短语（简单短语） 简单子树的末端结点形成的符号串。 句柄 最左边的直接短语 规范规约(最左规约) 始终对句柄进行规约而形成的序列成为规范归约。 由最左规约得到的句型称为规范句型 最左规约和最右推导(规范推导)一致 句柄的最左性刚好和分析栈的栈顶特性相匹配 算符优先分析 算法文法(OG文法 Operator Grammar) 产生式右部不含两个相继的非终结符 算符优先文法(OPG文法 Operator Precedence Grammar) 素短语 素短语是一个短语，它至少含有一个终结符，而且除他之外不含有其他素短语。 最左素短语 句型最左边的素短语 原理 算符优先分析规约的是最左素短语 算符优先表的构造 FirstVT 产生式的第一个非终结符号 LastVT 产生式的最后一个非终结符号 根据FirstVT、LastVT构造算符优先表 LR分析法 构成 总控程序、状态栈和符号栈、分析表 LR（0） 活前缀 活前缀(Viable Prefix)是指规范句型的一个前缀,它不含句柄之后的任何符号 就是识别了部分字符，但没有全部识别句柄，一旦把都识别了(即在栈顶形成了可归约串)，即表示句柄已形成，则用产生式进行归约，包含了完整句柄的活前缀称为可归约前缀。 项目 文法G的一个LR(0)项目(简称项目)是在G的某个产生式右部的某个位置添加一个圆点。 分类 归约项目 接受项目 移进项目 待约项目 SLR 求一个Follow集，规约时，看到Follow集中的记号才选择规约 缺点：仍然不够精确 LR(1) 求.Ab,c，后面跟一个符号集位First_S(bc) LALR 仅仅后面符号集不同的项目集合并 语法分析器的自动生成工具YACC YACC概述 YACC源文件的格式 YACC的翻译规则 YACC的辅助程序 语法分析中的错误处理 语法分析中的错误处理的一般原则 错误处理原则 发现错误为主，校正错误为辅 错误局部化 准确报告，应尽早给出错误发生的位置 错误恢复策略 应急模式的恢复 短语层次的错误恢复 添加错误产生式 自上而下语法分析的错误处理 递归下降分析程序中的错误处理方式 在推导过程中当前输入符号和文法推导的符号不相匹配 在递归过程中调用形成死循环 自下而上语法分析的错误处理 算符优先分析中的错误检测 LR分析中的错误检测 YACC中的错误处理 语义分析 语义分析概述 语义是指源程序及其组成部分所表述的含义，和语法不同，语法是关于程序及其组成部分的构成 规则的描述，是上下文无关的；而语义是关于语法结构的含义及其使用规则的描述，是上下文有 关的。语法上正确，其语义不一定正确。 语义分析的任务 语义检查 一致性检查（数据类型是否一致、操作是否合法） 越界检查（数组维数是否正确、下标是否越界） 语义处理 说明语句的翻译（相关信息登记到符号表中） 执行语句的翻译（生成等价的中间代码） 静态语义 静态语义是指在编译阶段能够检查的语义，比如标识符未定义，类型不匹配等。 动态语义 动态语义是指在目标程序运行阶段能够检查的语义，比如除数为0，无效指针，数组下标越界等 语义分析的任务 对结构上正确的源程序进行上下文有关性质的审查，审查源程序是否有无语义错误，为代码生成阶段收集类型信息。 主要功能包括建立符号表，进行静态语义检查，发现语义错误。 Sample语言的语义描述 程序的语义 函数的语义 各种名字的声明和使用的语义 各种语句的语义 表达式的语义 符号表管理技术 符号表概述 功能 收集符号信息 进行语义的合法性检查 包含 常量表 常量的符号表至少要保存入口、常量名、常量类型、值等几项 变量表 变量的符号表则需要入口、变量名、变量长度、变量类型、值、地址等 函数表 符号表的组织方式 常量 变量 需考虑作用域：块级作用域 函数作用域。用作用域路径表示 函数 字符串 符号表的操作 静态语义检查 静态语义检查概述 相关名字检查 类型检查 控制流检查 一致性检查 声明与定义语义检查 变量未声明就使用、变量重定义 函数未声明就定义和调用、函数重定义、函数声明与定义不匹配、函数调用与声明不匹配、 函数和变量重名等 数组长度必须是正整数、数组名不能和变量名、函数名同名 变量不能声明为void, 变量初始化类型错误等 表达式语义检查 函数调用时实参和形参的类型不匹配，参数个数不相等 有void返回值的函数不能参与表达式运算 如果操作符作用于不相容的操作数，需要报告出错信息 赋值表达式中，左边只能是变量、数组下标或指针等 赋值表达式的类型不匹配 语句语义检查 break语句必须在循环和switch语句内使用 continue语句必须在循环语句内使用 return语句必须在函数中使用 中间代码生成 中间代码生成概述 生成中间代码的好处有 便于进行与机器无关的代码优化工作 使编译程序改变目标机更容易 使编译程序的结构在逻辑上更为简单、明确 中间代码 逆波兰式 三地址代码 三元式 四元式 抽象语法树 有向无环图表示 属性文法和语法制导的翻译 属性文法 通过一系列属性来定义语义信息，把属性附加到上下文无关文法的文法符号上，并定义与文法产生式相关联的“语义规则”来计算和传递属性值，构成了属性文法。 在语法分析过程中，可以计算和传递语义信息，也可以进行语义翻译，这种由语法结构驱动的方法称为语法制导的翻译法。 综合属性 继承属性 综合属性用于自下而上传递信息，继承属性用于自上而下传递信息。 属性的计算 综合属性的计算 继承属性的计算 属性的计算顺序 可以在产生式的左中右的进行计算 语法制导翻译的实现方法 翻译模式 S-属性文法的自下而上的翻译，遍历一遍语法树即可 L-属性文法的自上而下的翻译，遍历一遍语法树即可 常见语句的语法制导的翻译 声明语句的语义处理 表达式的翻译 布尔表达式的翻译 控制语句的翻译 函数定义及函数调用的翻译 中间代码生成器的设计 运行时存储组织 存储组织 程序执行时存储器的划分 即程序运行时的内存模型：代码区 静态数据区 动态数据区 活动记录 为了管理一个函数在一次执行中所需的全部信息 ，将它们放在一块连续的存储区中，称为活动记录 局部数据布局 数据对象所需的存储空间由数据类型确定。如int占4字节。 对于数组等集合体，会分配一块连续的字节区 函数调用 源程序中的函数 函数执行时的活动 如果函数没有退出当前活动又开始新的活动，称为递归。 用一颗树表示程序执行期间的所有函数活动，称为活动树。 名字的作用域 参数的传递 传地址 得结果，每个形参对应两个单元，一个存放实参地址，一个存放实参的值 传值，是一种最简单的参数传递 传名，是一种替换规则 名字的绑定 环境 表示将名字映射到存储单元 状态 标识将存储单元映射到它所保存的值 存储分配策略 静态存储分配 局限性 数据对象大小和在内存中位置必须已知 一个过程的所有活动使用同一个局部名字绑定，所以不允许递归 数据结构不能动态建立 栈式存储分配 堆式存储分配 实现 定长块管理 变长块管理 分配策略 最先匹配法 最佳匹配法 最差匹配法 垃圾回收机制 可达性 引用计数回收器 缺陷 回收一个对象可能对其他对象的计数器-1，当回收计数为零的对象时，很难回收产生 循环指向的数据结构对象 开销比较大，引用计数器需要频繁修改 优势 垃圾能够被及时回收，空间使用相对低 以增量方式完成，运算分布在程序运行整个过程 标记-清扫回收器 复制回收器 空间一分为二 C语言编译程序运行时存储实例 内存的划分及程序执行的总体情况 案例：程序运行时内存的变化 代码优化 代码优化概述 代码优化的地位 代码优化是指为了提高目标程序的质量而对源程序或中间代码进行的各种合理的等价变换，使得从变换后的程序出发能生成更有效的目标代码。 目的：节省时间和空间 按阶段分 与机器无关的优化--对中间代码进行 依赖于机器的优化--对目标代码进行 程序范围分 局部优化:(基本块) 循环优化:对循环中的代码进行优化 全局优化:大范围的优化 优化的原则 等价原则：不改变运行结果 有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果 基本块的概念及流图 是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口是其 第一个语句，出口是其最后一个语句 局部优化 删除公共子表达式 复写传播 删除无用代码 代数恒等变换 简单的代数变换 强度削弱 合并已知量(常量) 应用交换律和结合律进行代数变换 基本块的DAG表示及优化 合并已知量 删除公共子表达式 删除无用代码 循环优化 循环的定义 代码外提 强度削弱 删除归纳变量 目标代码生成 概述 代码生成器固有的问题 指令选择 指令地址的决定 寄存器分配 计算次序选择 存储管理 代码生成器的输入 符号表信息 中间代码 代码生成器的输出：目标程序 绝对机器语言 可重定位的机器语言 汇编语言 存储管理 目标机及指令系统简介 x86体系结构 x86中的寄存器 x86指令系统介绍 三类指令 数据传送指令（MOV） 算术逻辑运算指令（ADD，SUB，MUL，DIV，AND，OR，CMP等） 控制转移指令（无条件跳转、条件跳转、函数调用和返回） 一个简单的代码生成器 基本块的代码生成器 引用信息和活跃信息 寄存器描述和地址描述 基本块的代码生成 从DAG生成目标代码 代码优化及目标代码生成器的设计 目标代码生成器的结构 汇编指令的选择 构成完整的汇编语言程序 参考链接 [编译原理 13007 思维导图模板_ProcessOn思维导图、流程图](https://www.processon.com/view/65fcfca9c71c473fd0f8904c)