C语言中的标识符：以字母或下划线开头，后跟零个或多个字母、数字或下划 线。如何用正则表达式表示？

(a|b|c|...|z|A|B|...|Z|_ )(a|b|c|...|z|A|B|...|Z|_ |0|1|2...|9)*

简单理解，就是输入一个字符串，输出这个字符串是否满足某个规则（true / false）。

实现原理: 就是先设定几个状态，然后根据输入的字符做状态转移，看最后能否转移到最终的状态。

如下图，输入 ，初始状态是 ，然后分别输入一个一个的字符，看最后能否将状态转移到 。

[图片上传失败...(image-d00190-1560422078662)]

有限状态自动机 FA 又分为两种：

• 确定的有限状态自动机 DFA 。针对一个状态，输入一个字符，最多只有一个出口。
• 非确定的有限状态自动机 NFA 。针对一个状态，输入一个字符，有多多于一个的出口。如上图中的 状态，输入 时有两个出口，所以它是 NFA 。

其实每一个正则表达式，都能对应一个 FA ，因此接下来看一下正则表达式如何生成 FA 。

从正则表达式 RE 到有限状态自动机 FA

转换过程概述

先将正则表达式生成 NFA ，再将 NFA 生成 DFA 。

这是因为：

• RE 生成 NFA 比直接生成 DFA 更加简单；
• NFA 做分析算法比较复杂，多个出口导致复杂度变高。因此，往往是将 NFA 转换为等价的 DFA ，然后再拿来做运算。

从RE生成NFA：Thompson算法。

其基本的逻辑是：

• 对基本的 RE（空串 、单个字符） 直接构造(直接对应)
• 对复杂的 RE （或、连接、闭包）递归构造(由外到内层层剥开)

a(b|c)*

实际上可分为两步：

• 从一个集合开始(最开始是{n0}即只有开始结点)，对集合中每一个元素通过某些输入(如n0到n1的a)转移到下一个状态集合(如{n1})(下面代码中记为delta运算)
• 从这个新状态集合出发，对每一个元素进行 闭包转换(可以一直沿着 转换走)，得到一个状态集合(如n1出发沿 转换可到达n2,n3,n4,n6,n9)

基于等价类的思想，Hopcroft 算法思路如下：

1. 等价类的意思是，这个范围内的结点经过转换后依然在这个范围内(可能还无法转换)
2. 一开始将DFA划分为两个集合N和A(非终止结点集合和终止结点集合)
3. 将集合不断细分，直到集合内的元素无法再区分为止(为一等价类)

hopcroft 算法示例一：

对于a(b|c)* 的DFA图如下，原来包含q0,q1,q2,q3四个结点：

1. q0是非终止结点，q1,q2,q3是终止结点，将它们划分为两类

2. q0无法再分，考虑q1,q2,q3是否可以继续划分：易发现q1,q2,q3之前可以通过c或b进行转换，而c、b转换使得这三个结点仍然处于这个三个结点的组成的集合的区域内，所以这个区域无法再分，将之记为q4

3. 可以用多种方式来进行DFA的代码表示：

   • 转移表(类似于邻接矩阵)
   • 跳转表
   • 哈希表(课程没有介绍)

   至于选用哪种方式，取决于对时间和空间的权衡

   转移表法

   包括两个部分，转移表和驱动代码。

   转移表就是一个存储状态和输入字符对应的状态转移情况

   驱动代码就是读取输入，然后与转移表内容相比较，看输入的串是否满足DFA的条件。

   转移表示例如下：

   [图片上传失败...(image-61d03e-1560422078662)]

   图中第一列是状态，第一行是字符，例如：

   • 在状态 时，输入字符 ，行列交叉点是 ，表示可以转向状态
   • 在状态 时，输入字符 ，行列交叉点是 ，表示可以转向状态
   • 在状态 时，输入字符 ，行列交叉点是 ，表示可以转向状态

   有了以上所有的逻辑，就可以判断一个字符串是否符合一个 RE 的规定，如果符合则可以将字符串拆分为一个一个的记号(token,单词)。

   • 输入一个程序语法的表示(上下文无关文法)，判断是否符合程序的语法

     给定一个文法 G 和句子 s ，要确定：是否能在 G 的推导结果中，找到 s （即，是否存在对句子的推导

   • 如果符合，就根据输入的符号集，生成抽象语法树 AST

   路线图

   • 数学理论：上下文无关文法(CFG)
     • 描述语言语法规则的数学工具
   • 自顶向下分析
     • 递归下降分析算法(预测分析算法)
     • LL分析算法
   • 自底向上分析
     • LR分析算法

   一个形式语言是上下文无关的，如果它是由上下文无关文法生成的。

   示例

   [图片上传失败...(image-db91e5-1560422078662)]

   上图的左侧就是一个 CFG 的简单示例，其中每一条叫做 “产生式”（即规则），图中的 即“或”的意思。简单解释一下这个 CFG 的意思：

   • “S -> N V N” 就是一个句型，其中 S 是开始符号
   • N 和 V 都是非终结符，即它可以继续再往下扩展拆分，就像 “S -> N V N” 那样拆分
   • t g e 等这些都是终结符，即已经表述一个具体的事情了，没法再往下拆分了

   [图片上传失败...(image-10a19a-1560422078662)]

   推导

   按以下方法可以从文法中推导出它所代表的语言

   推导概念

   • 给定文法G，从G的开始符号S开始，用产生式(规则)的右侧替换左侧的非终结符
   • 此过程不断重复，直到不出现非终结符为止
   • 最终的串称为句子(中间过程的包含非终结符的串称为句型)

   从上面的例子来看，可以根据一个 CFG 推导出若干个句子，例如上图的 CFG 可以推导出 或者 或者 或者 ……

   语法分析就是：给定一个文法 G 和句子 s ，要确定：是否能在 G 的推导结果中，找到 s （即，是否存在对句子的推导）**

   如果能推导出来，说明句子 s 符合文法 G 的语法，否则不符合。如下图：

   [图片上传失败...(image-717bca-1560422078662)]

   最左推导和最右推导

   推导方式一般有两种：

   • 最左推导：每次推导过程当中总是选择最左侧的符号进行替换
   • 最右推导：同理，选择最右侧
   • 当然还可以乱来随便顺序推导，但是为了方便一般只考虑上面两种

   乔姆斯基文法体系

   分类

   文法被分为4类，分别是0型文法、1型文法、2型文法、3型文法。

   具体释义和特点如下：

   • 0型文法: 也叫短语结构文法或无限制文法，其描述能力相当于图灵机，可使用任何语法描述形式；
   • 1型文法: 也叫上下文有关文法，其描述能力相当于线性有界自动机，语法形式如下： 。也就是说，S推导出A是和上下文x, y相关的，即S只有在上下文x, y的环境中才能推导出A；
   • 2型文法: 也叫上下文无关文法，其描述能力相当于下推自动机，语法形式如下: 。S可以无条件的推导出A，和上下文无关，上下文无关文法因此得名；
   • 3型文法: 也叫正则文法，等价于正则表达式，其描述能力相当于有穷自动机，语法形式如下:S -> Aa。其中最后一个a必须为非终结符。

   判断方法

   四种文法就是规定产生式的左和右边的字符的组成规则不同而已

   如何根据产生式左边和右边的特征来进行判断。首先，应该明确，四种文法，从0型到3型，其规则和约定越来越多，限制条件也越来越多，所以，我们判断时可以从最复杂的3型进行判断，依次向下判断，如果不符合3型的，那再看是不是2型的，不是2型的，再看是不是1型的。

   先看3型文法(正则文法)：

   • 左边必须只有一个字符，且必须是非终结符；

   • 其右边最多只能有两个字符，且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时，此字符必须为终结符。

   • 对于3型文法中的所有产生式，其右边有两个字符的产生式，这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定，也就是说如果一个产生式右边的两个字符的排列是：终结符＋非终结符，那么所有产生式右边只要有两个字符的，都必须前面是终结符而后面是非终结符。反之亦然。

     例如这样：

     或 ,（右线性文法）

     或 ,（左线性文法）

   再看2型文法如何判断：

   • 与3型文法的第一点相同，即：左边必须有且仅有一个非终结符。

   • 2型文法所有产生式的右边可以含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）。 例如这样： 这个文法有两个产生式，每个产生式左边只有一个非终结符S，这就是上下文无关文法，因为你只要找到符合产生式右边的串，就可以把它归约为对应的非终结符。

   再看1型文法如何判断：

   • 1型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符。
   • 与2型文法第二点相同。 例如这样： 这就是上下文相关文法，因为它的第一个产生式左边有不止一个符号，所以你在匹配这个产生式中的S的时候必需确保这个S有正确的“上下文”，也就是左边的a和右边的b，所以叫上下文相关文法。

   最后是0型文法，只要能描述出来，都属于这个类型，即0型。

   文法、上下文无关文法、句子、句型、语言的概念辨析

   文法 是描述语言的语法结构的形式规则（即语法规则）。

   上下文无关文法 就是文法的一种，它所定义的语法单位是完全上下文无关的。

   假设G是一个文法，S是开始符号，如果S经过零步或者若干步推出 α，那么称α是一个句型。只包含终结符号的句型是一个句子。文法G产生的所有句子构成一门语言，记为L（G）。

   如上图，在文法的推导过程中，可以用树的形式来表示，即分析树。

   二义性

   所谓“二义性”就是指文法的书写会产生一些歧义，例如上图中 和 表达式的文法，采用不同的推导顺序得到的结果是不一样的，得到了不同的分析树，虽然它们的叶子结点都相同(即得到的句子相同)，但是分析树的含义取决于树的后序遍历，可能分别得出 和 ，显然计算结果不同。

   为了避免文法的二义性，只能是重写文法，将文法表述的更加详细一些。

   重写文法验证例子

   对文法的重写要具体问题具体分析，不存在统一的算法。

   • 常规的自顶向下分析算法

   • 递归下降分析算法(预测分析算法)

   • LL(1)分析算法

   自顶向下分析算法的思路

   上文已经明确了语法分析的定义，即看一个文法 G 是否存在对句子 s 的推导。

   自顶向下分析就是其中一个比较典型的算法，其基本逻辑是：

   • 从文法 G的开始符号出发， 随意推导出一个句子 t ，然后拿 t 和目标句子 s 进行对比
   • 如果 t == s ，则成功
   • 如果 t != s ，则回溯，重新计算一个 t1 ，再比较

   因为这是从开始符号出发推出句子，因此称为自顶向下分析，对应于分析树自顶向下的构造顺序

   缺点与简单的改进方案

   但是，上述过程比较笨重，因为一个 G 能推导出来的句子可能有非常多种，都拿来跟 s 做比较，会发生很多回溯，非常耗时。可以用以下方式进行优化：

   按照从左到右的推导顺序，可以最先得到句子 t 的左侧，得到第一个元素就可以开始和s的第一个元素进行匹配了，如果匹配成功则对下一个字符进行匹配，否则该元素回溯，寻找对应产生式(文法的行)的下一个终结符，如果都匹配不上就回溯到父节点...知道遍历完找不到才是匹配失败。

   体现在下面的例子中则为将S与句子匹配这个任务拆解为 分别将N V N 与对应位置的句子中的字符相匹配

4. 用“前看符号”指导当前产生式规则的选择（即读取输入的句子的下一个字符，直接与当前非终结符的全部右部比较，而不是顺序挨个入栈出栈比较)。

   词法分析器的自动生成需要输入的声明式规范是正则表达式，语法分析器的自动生成需要输入的声明式规范是CFG(上下文无关文法)

   所谓“LL(1)”，是指：从左（L）向右读入程序，最左（L）推导，采用 1 个前看符号。分析高效，也是线性时间复杂度。

   其基本思想是 —— 表驱动的算法，如下图。

   LL(1)分析表

   第一列都是非终结符，第一行都是终结符，行列交叉点表示对应的产生式序号（注意要是在非终止符及其FIRST集中的元素的交叉点填写）。

   [图片上传失败...(image-2cac5e-1560422078662)]

   回顾之前讲过的自顶向下分析算法，最大的问题就在于去盲目推导，盲目匹配出句子，然后再去和目标句子 s 做对比，对比出错就要回溯，时间复杂度非常高。因此，就需要在推导过程中就需要做分析预测，就可以从参考这个分析表。从分析表中，通过预测输入能得到产生式的序号，就知道接下来要匹配哪个产生式了，就不需要回溯了。

   如何得到分析表--FIRST集

   FIRST集定义及示例

   FIRST(N)= 从非终结符N开始推导，得出的全部句子中的开头的所有可能的终结符集合。如下面的FIRST(N)={s,t,g,w}

   注意其定义也是递归的，如果N的右部有非终结符的话，还要接着递归知道终结符

   其实本质就是扫描每一条产生式，然后按照每一条产生式中所包含的字符的排列顺序，求解每个非终结符后面跟的第一个终结符，然后把这个终结符并入该非终结符的跟随集中。循环这个过程。

   FIRST_S集的计算就是在FIRST的基础上，将NULLABEL集的问题考虑在内

   基本思想

   最右推导：每一步替换最右边的非终结符，最右推导称为规范推导

   算法思想

   画出有限状态自动机

   状态和字符结合 移进

   如上图，先看下抽象语法树 AST 和高级语言如何对应，根据代码对比一下，应该不难理解。其中，if 的最左侧节点是判断条件，中间节点是成功分支，右侧节点是 else 分支。

   再来回顾一下上文讲的 CFG 的分析树（上文有示意图），它详细编码了句子的推导过程，并且包含了很多无关信息（非终结符），会占用很多存储空间，会增加算法的空间和时间复杂度。如果能把这些“无关信息”给去掉，只留下运算符，数字，标识符等和程序相关的信息，就构成了抽象语法树 AST ，如下图。

   [图片上传失败...(image-93b432-1560422078662)]

   既然是一棵树，那么就是一个标准的数据结构，各个类型的节点的数据结构，也就可以固定了。如下图

   [图片上传失败...(image-2f5363-1560422078662)]

   AST 是编译器中非常重要的数据结构，因为它是编译器前端和后端的接口形式。后续的过程仅仅依赖于 AST ，不会再依赖于前面的源码或者字符集。因此，一旦生成了 AST ，前面的源码就会被丢弃。因此，AST 中要有很详细的信息，不仅仅是本课程中讲的这个简单的树。例如，AST 要存储当前程序的文件、行、列，这样在语法报错时才能准确的给出具体的错误位置。

   语法分析输出 AST ，然后对 AST 进行语义分析（有些教材也会叫做 “类型检查” 或者 “上下文相关分析” 等名字）。注意，程序如果能通过了语义分析这个阶段，那再往后就不应该出现任何语法错误，除非是编译器自己的 bug 。

   上文中的语法分析用到的是 CFG 即上下文无关的语法，即不依赖于上下文。例如 C 语言中 不符合语法，而 就符合语法，但是其中的 变量是否在上文已经定义了，语法分析是不知道的。

   因此，语义分析是在 AST 基础上，结合上下文来分析：

   • 变量在使用前先进行声明
   • 每个表达式都有合适的类型
   • 函数调用和函数定义一致
   • 等等 ……（每种语言的要求不一样）

   例如表达式的类型检查，定义一个类型检查函数，传入 AST 的某个表达式的节点，然后判断最后返回的类型。如果类型检查错误，就报错。如下图。

   [图片上传失败...(image-f8e536-1560422078662)]

   上下文相关分析，就涉及到上下文信息的记录和读取，这些信息就被记录到符号表中，一个非常核心的数据结构。符号表用来存储程序中的变量相关信息（表的信息要足够丰富）：

   • 类型
   • 作用域
   • 访问控制信息（例如 等）
   • ……

   其数据结构最简单的可以使用一个 的字典来实现，例如 。但是编译器要处理的程序规模可能非常庞大，因此这个数据结构必须要合理规划。在实际工程中，高效的查询方式可以有一下选择：

   • 选择一：为了高效，使用哈希表来实现符号表，查找是 的时间复杂度
   • 选择二：为了节约空间，可以使用红黑树等平衡树，查找是 的时间复杂度

   变量都有“作用域”的概念，不同作用域可以有相同的变量名。符号表处理作用域的方式：

   • 第一，进入作用域时插入元素，退出作用域时删除元素
   • 第二，采用栈：进入作用域时插入新的符号表（push），退出作用域时删除栈顶符号表（pop），如下图。 （栈的实现方式很很多种，例如链表）

   [图片上传失败...(image-615737-1560422078662)]

   经过语义分析的 AST ，即可用来做代码生成，即生成最终的机器（物理机或者虚拟机）代码。注意，这里直接从 AST 到目标代码，是一种最简单的编译器模型，暂时忽略了优化的部分。优化过程下文会详细解说。

   代码生成是把源程序翻译成“目标机器”（可能是真实的机器，也可能是虚拟机）上的代码，而且要保证和源程序的“等价性”（重要！！！）。主要的任务是：

   • 给源程序的数据（全局变量，局部变量等）分配计算资源（寄存器、数据区、代码区、栈区、堆区）
   • 给源程序的代码（运算 语句 函数）选择指令（算数运算 逻辑运算 跳转 函数调用等）
   • （而且要考虑空间和时间的效率，在满足等价性的前提下）

   接下来通过两个示例来看代码生成的过程：

   • 栈计算机 Stack —— 代表了虚拟机，例如 JVM
   • 寄存器计算机 Reg —— 代表了 RISC 精简指令集，如 ARM 芯片

   70 年代有栈计算机的物理机，但是今天已经退出了历史舞台，因为执行效率太低。但是这里还要研究 Stack ，一来是因为在 Stack 上代码生成比较简单，二来是很多虚拟机是这样设计的，例如 JVM 。

   [图片上传失败...(image-c53112-1560422078662)]

   上图就是一个 Stack 的原型图，简单解释一下图中各个部分。

   • 内存，存放程序变量
     • 给变量 分配内存空间的伪指令： （伪指令，不会被 ALU 执行）
   • stack ，进行计算的空间（计算的输入、计算的中间结果和最终结果）
   • ALU ，计算单元 。指令集是：
     • ，把一个立即数压栈
     • ，得到内存中的变量 的值，并压栈
     • ，把栈顶元素弹出，并赋值给
     • ，加法，pop 赋值给 ，再 pop 赋值给 ，然后 push
     • ，减法，同上
     • ，乘法，同上
     • ，除法，同上

   PS：以上这几条指令，就是 java 字节码的一个子集。真实的 java 字节码有 200+ 个。

   [图片上传失败...(image-b62eb6-1560422078662)]

   上图就是高级语言到最终的 Stack 计算机机器语言的对应，展示了最终的输入和输出。至于代码生成如何实现，在文章一开始的“Sum 语言 + Stack”的例子中这部分已经写的比较详细，就不再赘述了，翻看上文吧。

   这种机器类型是基于寄存器架构，所有操作都在寄存器完成，执行效率非常高（因为寄存器访问速度是内存访问速度的百倍），访存都通过 或 指令（RISC 指令集特点）。

   [图片上传失败...(image-4336da-1560422078662)]

   上图就是寄存器计算机的原型图，解释一下图中各个部分。

   • 内存：存放“溢出”的变量（寄存器中放不开的变量，如果假设寄存器有无限多个的话，就不用考虑“溢出”了）
   • 寄存器：进行计算的空间，有 r1 r2 ... rn 无限个寄存器（假定无限个，实际上寄存器个数是有限的）
     • 给变量 分配寄存器的伪指令 （伪指令不会被 ALU 执行）
   • ALU 计算单元。指令集：
     • 把立即数 n 存入寄存器 r1
     • 把 r1 的值赋值给 r2
     • 将 x 地址的值取出，放在 r1 。其中 x 是指针，[x] 即取出指针对应内存的值。
     • 将 r1 的值赋值给 x 内存地址
     • 加法，表示 r3 = r1 + r2
     • 减法，同理
     • 乘法，同理
     • 除法，同理

   [图片上传失败...(image-69743d-1560422078662)]

   上图就是高级语言和目标代码的对应关系。图中有对应的 AST ，对这棵树进行后续遍历（先左、再右、最后根），每遍历一个节点都会对应到右侧的一行指令。

   • “1” 节点会对应第一行指令
   • “2” 节点会对应第二行指令
   • “+” 节点会对应第三行指令
   • “3” 节点会对应第四行指令
   • ……

   最后，实际的物理机器上不可能有无限多的寄存器，因此要确定哪些变量被用于寄存器？哪些变量被“溢出”放在内存？—— 这个问题是另外一个编译器的重要部分：编译器分配。如何进行编译器分配，这个问题会在下文介绍。

   中间表示是一个统称，有很多种表示形式，AST 就是其中之一。上文提到，从 AST 直接生成目标代码是比较原始的编译技术，现代编译器中往往会在编译器的“后端”进行各种各样的代码优化，不同的优化形式就需要不同的表示形式。

   [图片上传失败...(image-e26a41-1560422078662)]

   常见的中间代码形式：

   • 树和有向无环图：高层表示，适用于程序源代码
   • 三地址码：低层表示，靠近目标机器
   • 控制流图：更精细的三地址码，程序的图状表示
   • 静态单赋值形式 SSA ：更精细的控制流图
   • 连续传递风格：更一般的 SSA （函数式语言中用的比较多）
   • 还有很多。。。

   所谓“三地址码”，即一个指令有一个运算符，最多有三个操作数。这样就使得每一条指令都比较简单，易于和机器语言对应。

   [图片上传失败...(image-f5e86e-1560422078662)]

   上图就是一个高级语言和三地址码的对应关系（虽然三地址码是通过 AST 生成的，已经和源代码没有关系）。从图中可以看出三地址码的特点：

   • 给每个中间变量和计算结果命名，即没有复合表达式。例如将 拆解成一个一个的中间变量
   • 只有最基本的控制流，即没有各种控制结构，只有 和 。例如将 改为 （条件跳转指令）

   三地址码是一种线性的表示方式，这就没法通过它来分析和确定流程。例如上图中，哪些指令会跳转到 和 ？并不好确定。控制流图是一种更加精细的三地址码（本质上还是三地址码），将程序中的各个控制流块都表示了出来，如下图。

   [图片上传失败...(image-828b69-1560422078662)]

   控制流图就是一个有向图 ，其中节点 表示程序的基本块，边 表示基本块之间的跳转关系。生成控制流图的目的有很多，但都是为了做代码优化，例如：

   • 做控制流分析，例如程序中有没有循环？
   • 做数据流分析，例如程序中某行的变量 可能的值是什么？

   所谓“数据流分析”，就是通过静态的观察程序（并不执行）来判断其中的变量和数据的一些变化，例如某程序第五行的 x 变量的值会有几种可能？

   [图片上传失败...(image-32689a-1560422078662)]

   如上图，通过控制流图，既可以判断一个变量 的赋值可能性。如果 能编译器识别为一个固定的值，直接 并且把一开始的 删掉。这就是一个优化过程。

   但是这仅仅是静态的分析，程序并未执行，因此如果 在一个逻辑分支中出现，就不好预估其准确结果，但是至少能预估一个结果集（称为“保守信息”）。如果能将这个结果集做到最小，和执行的结果越接近，就越好优化。这仍然是编译器现在的一个热门话题。

   类似数据流分析的还有“到达定义分析”，即分析一个变量是如何一步一步的被定义和使用的，原理和目的基本一致，这里不再赘述。

   上文中提到 REG 机器假设有无限个寄存器，但实际情况不是。因此需要寄存器分配 —— 即用到活性分析。所谓“活性分析”，即分析变量的活跃区间（可以理解为声明周期）然后来做寄存器的分配。

   [图片上传失败...(image-e42d64-1560422078662)]

   如上图，三个变量，只有一个寄存器，该如何分配？答案是：计算出每个变量的活跃区间，即可共享寄存器。寄存器分配，就依赖于变量的活动区间数据。如下图：

   [图片上传失败...(image-d59a1e-1560422078662)]

   现代生产环境下的编译器，代码优化是其重要工作之一，而且一直在不断的持续优化中。

   代码优化的目的是让目标程序更精简、更快速、更节省空间、更节能（所谓的多快好省），当然在不改变语义的前提下 —— 这些应该都比较好理解。但是还有几点关于优化的需要重点说明一下。

   • 没有完美的优化，即“没有最好只有更好”。因为编译器本来就是一个庞大复杂的工程，优化过程复杂度很高，不确定性很大。
   • 优化必须要在语义分析完成之后再进行，即确保源程序没有任何语法和语义的问题。因为优化可能会删改代码，如果优化之后再报错，错误信息就不准确了。
   • 优化并不是一个单独的阶段（如词法分析、语法分析等），而是在各个阶段都可能进行。可以对 AST 进行优化，也可以对各种中间表示进行优化，还可以对目标代码再继续优化，每一步的优化针对想都不一样。
   • 一般针对一个数据优化之后不会产生新的格式（但会产生新的数据，即函数式编程的思维），优化不是翻译过程。

   [图片上传失败...(image-ca8235-1560422078662)]

   即对 AST 进行优化，下面列举几个例子来说明。

   第一，常量折叠。静态计算，可以在数字类型和 bool 类型进行优化，例如：

   • 变为 （少了一步 计算，就相当于帮 AST 节省了一个分支）
   • 变为 。而且， 还可以进行“不可达代码”优化（见下文）

   第二，代数化简。利用代数的恒等式，进行优化，例如：

   • 变为 （少一个运算符，简化 AST）
   • 变为 （少一个运算符，简化 AST）
   • 变为 （因为乘法运算复杂度高）
   • 变为 （位运算效率最高）

   第三，死代码（不可达）代码优化，例如

   • 不会被执行，测试环境的 debug 代码，到了线上环境就会是死代码
   • 函数的 之后的语句，不会被执行

   如常量传播、拷贝传播，在上文讲数据流分析的时候已经写过，不再赘述。

   选择题

   • 第一个编译器是？(Fortran编译器)

   • 有限状态自动机、正则表达式、上下文无关文法的应用阶段

     (词法分析、词法分析、语法分析)

   • 关于LR(0)、SLR的一些的性质、优缺点

   • //还有两题忘了是啥了，反正挺简单的...

   简答题

   • 编译模式和翻译模式的比较

   • 列举至少三种中间代码形式，并说明为什么要有不同的表示方式

   • 语法制导翻译的主要思想

   • 具体语法和抽象语法的区别

   分析与计算题

   • (15分) 画出最基本的词法分析器模块化结构图 (词法分析、语法分析、语义分析、代码生成及其对应的数据流)

   • (15分) 依照示例写一段代码(简单，照猫画虎就行了)

   • (20分）正则表达式 -> NFA(Thompson算法) 、NFA -> DFA(子集构造算法), DFA 的优化( Hopcroft 最小化算法) (PPT原题)

   • [2] 编译原理 中科大华宝健_bilibili(带目录索引)

         以上就是本篇文章【朱娜斐编译原理复习笔记-北京工业大学软件学院】的全部内容了，欢迎阅览 ！ 文章地址：http://lanlanwork.gawce.com/quote/9005.html 
          行业      资讯      企业新闻      行情      企业黄页      同类资讯      网站地图      返回首页 阁恬下移动站 http://lanlanwork.gawce.com/mobile/ , 查看更多