编译原理

Posted by QingJun's Blog on July 4, 2021

本文笔记针对的是西安电子科技大学计算机科学与技术专业计算机软件与理论方向或数字媒体方向在大三下学期方向限选的课程《编译原理》

参考教材为 鱼滨,王小兵,张琛.编译原理[M].西安.西安电子科技大学出版社.2014.3，配图参考的是张南老师给的 PPT 或 PDF

第一章 绪论

1.1 语言翻译与编译程序

(这一块考试也不怎么考，属于知道就行)

在计算机上执行一个高级语言程序：

  • 编译程序将高级语言翻译成机器语言程序
  • 运行机器语言程序求得计算结果

编译程序：一种能够把高级语言程序翻译成低级语言(汇编语言、机器语言)程序的程序。

宿主机：运行编译程序的计算机

目标机：运行编译程序产生目标代码的计算机

交叉编译程序：编译程序产生不同于宿主机的机器代码

源程序(源语言编写)→编译器→目标程序(目标语言编写的等价程序)

1.2 编译器与解释器

image-20210304153554852

编译器：先编译后执行。时间快、空间省；交互性与动态特性差、可移植性差

解释器：不产生目标程序，边解释边执行源程序。时间慢、空间费；交互性与动态特性好、可移植性好

编译与解释的根本区别：是否生成目标代码

1.3 编译程序的工作原理与基本结构

主要工作：

  • 词法分析，对构成源程序的字符进行扫描和分解，识别单词(记号)
  • 语法分析，层次结构分析，建立语法树
  • 语义分析与中间代码生成，考察结构正确的句子是否语义合法，合法则翻译成中间代码
  • 代码优化，对中间代码进行优化处理
  • 目标代码生成，把中间代码翻译成目标程序

逻辑结构：

编译阶段划分.png

解释器没有代码优化和目标代码生成。中间代码生成和代码优化不是每个编译程序必须的。

解释程序处理语言时,大多数采用的是先将源程序转化为中间代码，再解释执行的方法。

编译器前端主要由与源语言有关但与目标机无关的部分组成,通常包括词法分析、语法分析、语义分析与中间代码生成,有的代码优化工作也可包括在前端。编译器后端包括编译程序中与目标机有关的部分,如与目标机有关的代码优化和目标代码生成等。通常,后端不依赖于源语言而仅仅依赖于中间语言。

遍，对源程序或源程序的中间结构从头到尾扫描一次,并做有关的加工处理,生成新的中间结果或目标程序

决定遍数的因素：(1)计算机存贮容量大小;(2)编译程序功能强弱;(3)源语言繁简;(4)目标程序优化程度;(5)设计和实现编译程序时使用工具的先进程度;(6)参加人员多少和素质等等。

多遍扫描编译程序的优点：加工充分;出错处理细致;目标程序质量高;缺点:编译时间长,开销大。

第二章 词法分析

2.1 词法分析概述

词法：规定单词形成的规则，规定什么样的输入序列是语言所允许的合法单词

词法分析：根据构词规则识别输入序列

上述两点是构造词法分析器所需要解决的问题，第一个问题我们用正规式来描述模式，从而定义词法；第二个问题我们用有限自动机实现记号的识别。

模式，即词法，产生和识别元素的规则

记号(词法记号)，单词的归类，按某个模式识别的一类元素。表示源程序中信息单元的字符序列

单词(词法单元)，即记号的实例

属于同种记号的单词用记号的属性区别不同单词

比如，变量这个记号，模式是以字母或下划线开头且由字母、数字、下划线组成，用这个模式就可以识别任意变量，但如果有两个变量 cat 和 dog，两者虽然都是变量记号，但是是不同的单词，通过属性来区分，比如 cat.val = 1 ，dog.val = 2。

词法分析器的功能：

  • 识别记号并将其转为内部编码形式
  • 删除无用的空白符、回车符以及无用的非实质性字符
  • 删除注释
  • 进行词法检查，报告所发现的错误

2.2 模式的形式化描述

语言是有限字母表上有限长度的字符串的集合

因为计算机的表示能力有限，所以定义强调两个有限性

用集合的方式枚举一个记号中的所有元素，并不方便(集合可能过大)，所以引入正规式与正规集，建立正规式与正规集的映射，从而用正规式表示一个记号，并且正规式可以简化，最后可以利用正规式方便地表示一个记号。

image-20210311155058987

一个正规式 r 表示一个正规集 L(r)

正规式的运算优先级：闭包运算 > 连接运算 > 或运算。三种运算都是左结合的

若两个正规式表示同一正规集，则两者等价。

image-20210626145901431

文法分类：

  • 0 型文法，短语文法
  • 1 型文法，上下文有关文法(CSL)
  • 2 型文法，上下文无关文法(CFG)
  • 3 型文法，正规文法

文法的表达能力：0 型 > 1 型 > 2 型 > 3 型

2.3 有限自动机

有限自动机(FA)分为确定型自动机(DFA)和非确定型自动机(NFA)，这里有限表示状态有限

有限自动机的三种表示方式：

  • 状态转换图：用有向图表示 DFA ，用圆圈表示一个结点(状态)，用同心圆表示终态

  • 状态转换矩阵

  • 五元组 $M = (S, \sum, move, s_0, F)$
    • S 是有限状态集合，即自动机中所有的状态的集合
    • $\sum$ 是输入符号集合
    • move 是状态转换函数
    • $s_0$ 是开始状态
    • F 是终态集

DFA 与 NFA 的区别：判断是否属于非确定型有限自动机，根据有限自动机在识别输入单个字符的过程中，其下一个状态是否确定；DFA 不接受 ε 转移

DFA 可以由 NFA 得出，所以我们从 NFA 开始

NFA 可以表示任何正规式

NFA 识别记号的过程，实际上就是从初态开始，根据输入字符不断转换到终态过程。

那我们是不是只需要用 NFA 就可以完成识别了呢？并不是，NFA 识别记号具有不确定性，即在某一状态下，对于同一输入字符，有多个到下一状态的转换，我们无法确定进行哪个转换，或者说，如果尝试所有的可能，代价会非常大。

由此我们引入 DFA ，对于非空的字符，其下一状态转换是唯一确定的。DFA 是 特殊的 NFA

2.4 正规式到词法分析器

(现在词法分析的实现也并不需要从正规式到词法分析器这么完整的过程，比如在 lex 中只要直接写要识别的记号就行了，lex 会自动生成词法分析器)

前面的两节，介绍了我们用于解决词法分析的两个问题所用到的正规式和有限自动机。接下来，我们考虑将两者结合，构造词法分析器。

构造词法分析器的方法和过程：

  • 用正规式对模式进行描述
  • 为每一个正规式构造 NFA
  • 将构造出的 NFA 转换成等价的 DFA
  • 把 DFA 化为最简形式
  • 从简化后的 DFA 构造词法分析器

结合正规式和有限自动机，要解决如由正规式构造有限自动机。这个问题我们可以用Thompson 算法解决。

根据 Thompson 算法，我们解决了由正规式到 NFA 的问题，但是前面提到过 NFA 并不完全适合识别记号，所以我们需要将 NFA 转换为 DFA。

  • NFA 识别记号的“并行”方法

  • 子集构造法

    ε-闭包

有了 DFA 之后，我们仍然不满意，因为等价的两个 DFA 所需的状态数可能差异极大，显然我们希望状态数尽可能少，所以我们需要进行 DFA 化简。

在介绍 DFA 化简的方法前，先介绍一个概念——可区分：

对于任意两个状态 t 和 s ，若对于输入字符 w ，t 可以经由 w 进行状态转换，而 s 不接受 w，则 t 和 s 是可区分。

同样的，我们可以知道，若对于 w ，t 和 s 是不可区分的，则说明从 t 和 s 出发，经由 w 可以得到相同的结果。

理解了可区分的概念，我们就可以讲讲最小化 DFA 的本质了。

DFA 的本质：将 DFA 中的状态划分成不同的组，同一组中的状态不可区分，不同组的状态可区分。

最小化 DFA ：

  1. 初始划分，Ⅱ = {S，S-F}
  2. 对于划分中的每一个子集，尽可能地继续划分
  3. 重复 2 直到划分中的子集数不再增长

(这一步也不考，知道就行)

接下来，我们终于到了最后一步，由 DFA 构造词法分析器。

两种实现词法分析器的方法：

  • 表驱动型的词法分析器

    • 用表(状态转换矩阵)储存 DFA
    • 驱动器模拟 DFA 的状态转换

  • 直接编码的词法分析器

    用程序模拟 DFA 的状态转换

第三章 语法分析

语法分析概述

程序可能出现的错误：

  • 词法错误，非法字符或关键字拼写错误等
  • 语法错误(语法结构错误)，漏分号，括号不匹配等
  • 静态语义错误，类型不一致，参数不匹配等
  • 动态语义错误，数组越界，被除数为零等，编译过程无法发现

文法分类：

  • 0 型文法，短语文法，图灵机识别
  • 1 型文法，上下文有关文法(CSL)，线性界限自动机识别
  • 2 型文法，上下文无关文法(CFG)，下推自动机识别
  • 3 型文法，正规文法，有限自动机识别

3.1 上下文无关文法(CFG)

上下文无关文法(CFG)，用一个四元组表示，G = (N，T，P，S)

  • N 是非终结符的有限集合
  • T 是终结符的有限集合
  • P 是产生式的有限集合
  • S 是非终结符(开始符号)

非终结符，可以出现在产生式左部的符号，用大写字母表示

终结符，不可以出现在产生式左部的符号，用小写字母表示

产生式，如 “ E → E + E ” 可用自然语言表述为 “ 算术表达式定义为两个算术表达式相加 ”

推导：用产生式右部的串代替左部的非终结符，从而由简单的表达式产生复杂的表达式。

  • 直接推导
  • 零步推导
  • 多步推导
  • 至少一步推导

推导具有自反性和传递性。

image-20210414185856801

语言是句子的集合，句子由终结符构成，句型是开始符号推导句子的中间结果，由终结符和非终结符构成。

文法可以唯一确定某一语言，而一个语言可以由多个文法产生

语法树，直接描述句型的语法结构，具有以下性质：

  • 除叶子节点，每个节点用非终结符标记
  • 叶子节点可以被任意符号标记

最左推导和最右推导中间过程的语法树可能不同，但最终语法树相同

用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中

文法二义性：文法对同一句子产生不止一棵语法树

产生二义性的原因：在产生句子的过程中某些直接推导有多于一种选择

语言二义性：产生上下文无关语言的每一个文法都是二义的，则该语言是先天二义的

无法判定上下文无关文法的二义性

二义性例子：悬空 else 问题

二义性的消除：

  • 改写文法为非二义
    • 引入新的非终结符，增加子结构并提高一级优先级
    • 递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性
  • 规定符号优先级和结合性，使其仅产生一棵语法树

二义文法的优点：比非二义文法容易理解；分析效率高（语法树低，直接推导步骤少）。

为什么用正规式而不用 CFG 描述词法

  • 词法规则简单，用正规式描述已足够
  • 正规式的表示比 CFG 更直观、简洁、易于理解
  • 有限自动机的构造比下推自动机简单，且分析效率高
  • 区分词法和语法，为编译器前端的模块划分提供方便

3.2 自上而下的语法分析

概述

自上而下的语法分析，即根据输入串构造语法分析树或对输入串作最左推导。

以一个例子来看自上而下的语法分析是如何进行的：

image-20210506104005677

根据文法逐一匹配符号，如果有多个可能，注意尝试，失败时回溯。

自上而下的语法分析带来的问题及解决措施

左递归

若有 A->Aα ，出现左递归，会无限循环

左递归

直接左递归

先从简单的开始，考虑消除直接左递归：

image-20210506104915434

有了消除直接左递归的基础，考虑消除文法的左递归：

image-20210506105134117

公共左因子

由自上而下的语法分析的过程可知，过程中会不断尝试并进行回溯，这显然效率很低。所以我们考虑尽可能消除回溯，提高效率。

若有 A->αβ1 αβ2 ，既有 α 为公共左因子，可以提取，避免回溯。

image-20210506105239564

既有左递归又含左因子时，先消除左递归，消除左递归后左因子也随之消除

递归下降分析法

递归下降分析与自上而下分析的区别：

自上而下分析的过程时边推导边匹配；递归下降分析的过程是确定的(通过构造程序)，并且因为是确定的，所以要求文法不能出现左递归和公共左因子

递归下降分析的步骤：

  • 根据文法构造状态转换图并化简
  • 用 EBNF 表示状态转换图
  • 根据 EBNF 构造子程序

预测分析法

预测分析器 = 预测分析表 + 表驱动程序 + 分析栈

  • 匹配，栈顶终结符与输入匹配
  • 推导，栈顶是非终结符，将产生式逆序入栈
  • 接收
  • 出错

构造预测分析表：

  • FIRST 集合(可以用什么展开)
  • FOLLOW 集合(往前看一步选择用什么展开)

image-20210607155830495

image-20210607160217951

二义文法的预测分析表 M[A,a] 会有多个条目

image-20210607160741652

image-20210626194016680

根据推论3.2，有左递归的文法不是LL(1)文法，有公共左因子的文法一般也不是LL(1)文法。二义文法也不是LL(1)文法。

3.3 自下而上的语法分析

自下而上的语法分析：从左到右扫描输入序列ω，经过一系列的步骤，最终将ω归约为文法开始符，或发现一个语法错误。

从给定的终结符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。

归约，推导的逆过程，是一个反复用产生式的左部替换产生式的右部、谋求对ω进行匹配的过程。

关键概念：

  • 短语，句型经过至少一次推导

  • 直接短语，句型经过一次推导

  • 句柄，最左直接短语

  • 规范归约，在移进过程中，当发现栈顶呈现句柄时，就用相应产生式的左部符号进行替换。

  • 规范推导

    最左规约(规范归约)的逆过程时最右推导(规范推导)

image-20210607161335730

  • 移进，输入序列中的终结符进栈
  • 规约，将栈顶句柄替换为非终结符
  • 接受
  • 报错

LR 分析

LR 分析器是带符号栈的确定型有限自动机

LR 分析表：动作表 + 状态转移表

image-20210607162026001

LR(0) 分析表的构造：

  • 构造一个可以识别文法 G 中所有活前缀的 DFA
  • 根据DFA构造 LR(0) 分析表

活前缀：规范句型的一个前缀，不含句柄之后的任何符号

构造 DFA ，先构造 NFA ，用一个 LR(0) 项目表示一个 NFA 状态，再将 LR(0) 项目归成项目集

image-20210626200450899

LR(0)项目集规范族的构造

拓广文法，引进新非终结符 S’ 和新产生式 S’->S

其中：S’→.S是识别S的初态， S’→S.是识别S的终态。目的是 使最终构造的DFA状态集中具有唯一的“接受”状态，即唯一的指示语法分析成功结束的状态。

有效项目，若存在最右推导S’=*>αAω=>αβ1β2ω，则称项目A→β1.β2 对活前缀αβ1有效。

项目A→β1.β2对活前缀αβ1有效，作用是： 在当前活前缀αβ1的情况下，该项目可指导下一步分析动作(αAω=>αβ1β2ω)。

LR(0) 分析表构造(这里做做题就懂了，不在此详细描述)

LR(0) 文法：不存在冲突项目(既含移进项目又含归约项目；含多个归约项目)

SLR(1)

SLR(1)文法都是无二义的，但也存在无二义文法不是SLR(1)的

第四章 语法制导翻译与中间代码生成

语法制导翻译

根据翻译的需要设置文法符号的属性，以描述语法结构的语义。例如，一个变量的属性有类型，层次，存储地址等。表达式的属性有类型，值等。属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任务。

语法制导翻译既可以用来产生中间代码，也可用来产生目标指令，甚至可用来对输入串进行解释执行。

属性与语义规则

  • 用属性表示文法符号代表的语言结构的意思
  • 用语义规则规定产生式代表的语言结构之间的关系，即用语义规则实现属性计算

语义规则：对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。

属性文法：在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干相关的“值”

属性

  • 综合属性，值由子节点的属性值决定，自下而上
  • 继承属性，值由父节点和/或兄弟节点的属性值决定，自上而下

终结符只有综合属性，由词法分析器提供；非终结符既可有综合属性也可有继承属性

语义规则的两种表示方式

  • 语法制导定义，用抽象的属性和运算符号表示的语义规则(公式，做什么)
  • 翻译方案，用具体的数据结构和运算表示的语义规则(程序段，如何做)

语法制导定义适用于设计阶段，翻译方案适用于实现阶段

image-20210627105133723

中间代码

中间代码的主要形式

  • 树，语法树，树的优化表示-DAG(有向无环图)

  • 后缀式(逆波兰式)，操作数在前，操作符紧随其后，无需括号限制优先级和结合性

  • 三地址码，类似汇编，最多三个地址(两个操作数，一个结果)

    • 三元式，(i) (op, arg1, arg2)，序号既表示三元式，又表示存放的结果

      缺点：给代码的优化带来困难。因为代码优化常使用的方法是 删除或移动某些代码，而一旦进行了代码的删除或移动， 则表示某些三元式的序号会发生变化，从而使得其他三元式中对原序号的引用失效。

    • 四元式，(op, arg1, arg2, result)

      将表示计算结果的三元式序号 用一个显式的变量表示，从而避免了三元式的值与三元式在三元组中的位置相关的缺点。

    • 两者区别：将由序号所表示的运算结果改为由临时变量来表示。

对树的后序遍历得到的线性序列就是后缀式，每个父子节点结构对应一个三元式或四元式

中间代码的作用：分离编译器前端与后端，便于编译器的开发移植和代码的优化。

中间代码的特性：

  • 便于语法制导翻译
  • 既与机器指令的结构相近，又与具体机器无关

运算符优先级：数值运算 > 比较运算 > 逻辑运算

说明性语句的翻译

语句翻译这块，主要是理解符号表，参数传递，布尔表达式和控制语句的翻译，这块暂时还没整理好。

符号表

连接声明与引用的桥梁。一个名字在声明时，相关信息被填写进符号表；而在引用时，根据符号表中的信息生成相应的可执行语句。有效记录各类符号的信息，以便于在编译的各个阶段对符号表进行快速、有效的查找、插入、修改、删除等操作。

符号表的作用：解决一些不能表示的情况

作用域

  • 并列作用域

  • 嵌套作用域

  • 静态作用域规则

    静态语言与动态语言的区别

  • 最近嵌套作用域规则

过程的定义与声明

左值与右值，左值一般是地址，右值是值

常见的参数传递形式：

  • 值调用，传值

  • 引用调用，传地址

  • 复写—恢复

    解决引用调用的副作用——过程内会改变实参的值

  • 换名调用，用过程体替换过程调用，替换中用实参的文字替换体中的形参，宏定义#define

执行性语句

赋值语句，类型转换，itr，rti

布尔表达式

约定的优先级与结合性：从高到低：not and or ；右结合：not ，左结合：and or

  • 直接计算，模板
  • 短路计算
    • .true 真出口
    • .false 假出口

拉链和回填

  • .tc 真出口链
  • .fc 假出口链

控制语句

CATALOG
    FEATURED TAGS
    Leetcode C++
    FRIENDS