编译原理
编译原理
龙书第二版读书笔记 + cs143课程记录
引论
语言处理器
简单来说编译器就是一个程序，它可以阅读以某一种语言编写的程序，并把程序翻译成一个等价的、用另一种语言编写的程序
编译器的重要任务之一就是报告它在翻译过程中发现的源程序中的错误
解释器并不通过翻译的方式生成目标程序
由一个编译器产生的机器语言目标程序通常要比一个解释器快很多，但是解释器的错误诊断效果通常要比编译器要好
一个编译器的结构
源程序映射为语义上等价的目标程序
分析 analysis
分析部分把源程序分解成为多个组成要素，并在这些要素之上加上语法结构。然后使用这个结构来创建该源程序的一个中间表示。这里通常会有一个语法语义上的检查，来帮助用户改正
分析部分会收集有关源程序的信息，并把信息存放在一个称为符号表的数据结构，符号表将和中间部分一起传送给综合部分
综合 synthesis
根据中间表示和符号表中的信息来构造用户期待的目标程序
分析部分通常被称为编译器的前端，而综合部分被称为后端
有些编译器在前端和后端之间有一个与机器无关的优化步骤，在中间表达式之上进行转换，以便后端程序能够生成更好的目标代码
字符流 ———-> 符号流 ———-> 语法树 ———-> 语法树 ———-> 中间表示形式 ———-> 中间表示形式 ———-> 目标机器语言 ———-> 目标机器语言
词法分析器 语法分析 语义分析 中间代码生成器 机器无关代码优化器 代码生成器 机器无关代码优化器
词法分析 lexical analysis
词法分析器读入组成源程序的字符流，将它们组织成为有意义的词素 (lexeme) 的序列，对于每个词素，词法分析器产生如下形式的词法单元 (token) 作为输出
< token-name, attribute-value >
e.g.
position = initial + rate * 60
position是一个词素，被映射为<id, 1>，id 是表示标识符的抽象符号，1 指向符号表中position对应的条目=是一个词素，被映射为< = >，这个词法单元不需要属性值initial是一个词素，被映射为<id, 2>+是一个词素，被映射为< + >rate是一个词素，被映射为<id, 3>*是一个词素，被映射为< * >60是一个词素，被映射为< 60 >
分隔词素的空格会被词法分析器忽略掉
<id, 1> < = > <id, 2> < + > <id, 3> < * > < 60 >
语法分析 syntax analysis
一个常用的表示方式就是语法树 (syntax tree)
例子见上图
语义分析 semantic analysis
语义分析器 (semantic analyzer) 使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。它也收集类型信息，并把这些信息存放在语法树或符号表中
语义分析的一个重要部分是类型检查 (type checking)，编译器检查每个运算符是否具有匹配的运算分量
自动类型转换，比如整数和浮点数运算，那么编译器要将整数转换为一个浮点数
例子见上图，我们可以发现60被类型转换了，这是因为在这个例子中rate是一个浮点数
中间代码生成
在把一个源程序翻译成目标代码的过程中，一个编译器可能构造出一个或多个中间表示，这些中间表示可以有多种形式
在源程序的语法分析和语义分析完成之后，很多编译器生成一个明确的低级的或类机器语言的中间表示，我们可以把这个看作是某个抽象机器的程序
( 这种中间表示必须要具有两个重要的性质：易于生成，能够轻松被翻译成目标机器上的语言 )
例子见上图，采用了一种称为三地址代码 (three-address code) 的中间表示形式
代码优化
机器无关的代码优化步骤试图改进中间代码，以便生成更好的目标代码
不同的编译器所做的代码优化工作量相差很大，那些优化工作做的最多的编译器，会在优化阶段花相当多的时间
代码生成
代码生成器以源程序的中间表示形式作为输入，并把它映射到目标语言 (代码生成的一个至关重要的方面是合理分配寄存器以存放变量的值)
符号表管理
编译器的重要功能之一就是记录源程序中的使用的变量的名字，并收集和每个名字的各种属性有关的信息
符号表数据结构为每个变量名字创建了一个记录条目，记录的字段就是名字的各个属性，这个数据结构应该允许编译器迅速查找到每个名字的记录
将多个步骤组合成趟
多个步骤的活动可以被组合成一趟
可以把一个前端和不同的目标机后端结合，建立针对不同目标机的编译器
编译器构造工具
- 语法分析器的生成器：可以根据一个程序设计语言的语法描述自动生成语言分析器
- 扫描器的生成器：可以根据一个语言的语法单元的正则表达式描述生成词法分析器
- 语法制导的翻译引擎：可以生成一组用于遍历分析树并生成中间代码的例程
- 代码生成器的生成器：依据一组关于如何把中间语言的每个运算翻译成为目标机上的机器语言的规则，生成一个代码生成器
- 数据流分析引擎：帮助收集数据流信息，即程序中的值如何从程序的一部分传递到另一部分，数据流分析是代码优化的一个重要部分
- 编译器构造工具集：可用于构造编译器的不同阶段的例程的完整集合
编译技术的应用
针对计算机体系结构的优化
几乎所有的高性能系统都利用了两种技术
- 并行 (parallelism)
- 内存层次结构 (memory hierarchy)
并行性
所有的现代微处理器都采用了指令级并行性，指令级的并行也显式地出现在指令集中，VLIW (Very Long Instruction Word 超长指令字) 机器拥有可并行执行多个运算的指令
人们已经开发了并行技术以便自动地把顺序的科学计算程序翻译成为多处理器代码
内存层次结构
高效使用寄存器可能是优化一个程序时要处理的最重要的问题；和寄存器必须由软件明确管理不同，高速缓存和物理内存必须是对指令集隐藏的，并由硬件管理
硬件实现的高速缓存管理策略有时并不高效，我们可以改变数据的布局或数据的访问代码的顺序来提高内存层次结构的效率，也可以通过改变代码的布局来提高指令高速缓存的效率
新计算机体系结构的设计
决定一个计算机系统性能的不是他的原始速度，还包括编译器能够以何种程度利用其特征
在现代计算机体系结构的开发中，编译器在处理器设计阶段就进行开发，然后编译得到代码并运行于模拟器上，这些代码被用来评价提议的体系结构特征
程序翻译
二进制翻译
编译器技术可以用于把一个机器的二进制代码翻译成另一个机器的二进制代码，使得可以在一个机器上运行原本为另一个指令集编译的程序
二进制翻译也可以被用来提供向后兼容性
硬件合成
大部分硬件设计也是使用高级硬件描述语言描述的，硬件设计通常是在寄存器传输层 (Register Transder Level, RTL) 上描述的
在这个层，变量代表寄存器，而表达式代表组合逻辑；硬件合成工具把RTL描述自动翻译成为门电路，而门电路再被翻译成为晶体管，最后生成一个物理布局
编译然后模拟
对设计进行编译并生成能够在机器上直接模拟特定设计的机器代码，经过编译后模拟比基于解释器的方法快了几个数量级
软件生产率工具
通过数据流分析技术静态地定位错误 (静态分析工具)
- 类型检查
- 边界检查
- 内存管理工具
程序设计语言基础
静态和动态的区别
如果一个语言使用的策略支持编译器静态决定某个问题，那么我们说这个语言使用了一个静态 (static) 策略，或者说这个问题可以在编译时刻 (compile time) 决定
一个只允许在运行程序的时候作出决定的策略被称为动态策略 (dynamic policy)，或者被认为需要在运行时刻 (run time) 做出决定
如果仅通过阅读程序就可以确定一个声明的作用域，那么这个语言使用的是静态作用域 (static scope)，或词法作用域 (lexical scope)
否则，这个语言使用的是动态作用域 (dynamic scope)，
环境与状态
环境 (environment)
一个从名字到存储位置的映射，变量就是指内存位置，我们可以把环境定义为名字到变量的映射
状态 (state)
从内存位置到它们的值的映射，状态即把左值映射为它们的相应右值
- 名字到位置的静态绑定与动态绑定，大部分从名字到位置的绑定是动态的
- 位置到值的静态绑定与动态绑定，一般来说位置到值的绑定也是动态的，因为我们无法在运行一个程序之前指出一个位置上的值
一个简单的语法制导翻译器
引言
分析阶段的工作是围绕着待编译语言的语法展开的，一个程序设计语言的语法 (syntax) 描述了该语言的程序的正确形式
而该语言的语义 (semantics) 则定义了程序的含义，即每个程序在运行时做什么事情
一个广泛使用的表示方法来描述语法，这个方法就是上下文无关文法或BNF (Backus-Naur范式)
上下文无关文法不仅可以描述一个语言的语法，还可以指导程序的翻译过程
词法翻译器使得翻译器可以处理由多个字符组成的构造，比如标识符
标识符由多个字符组成，但是在语法分析阶段被当做一个单元进行处理，这样的单元称作词法单元
语法分析器生成一颗语法树，它又被进一步翻译为三地址代码，有些编译器会将语法分析和中间代码生成合并为一个组件
语法定义
描述程序设计语言语法的表示方法，上下文无关文法，用于组织编译器前端
1 | if (expression) statement else statement |
可以表示为
1 | stmt -> if (expr) stmt else stmt |
这样的规则称为产生式 (production)，像关键字if和括号这样的词法元素称为终结符号 (terminal)，像expr和stmt这样的变量表示终结符号的序列，它们称为非终结符号 (nonterminal)
文法定义
一个上下文无关文法 (context-free grammar) 由四个元素组成：
- 一个终结符号集合，它们有时也称为“词法单元”，终结符号是该文法所定义的语言的基本符号的集合
- 一个非终结符号集合，它们有时被称为“语法变量”，每个非终结符号表示一个终结符号串的集合
- 一个产生式集合，其中每个产生式包括一个称为产生式头部或左部的非终结符号
- 指定一个非终结符号为开始符号
在编译器中，词法分析器读入源程序中的字符序列，将它们组织为具有词法含义的词素，生成并输出代表这些词素的词法单元序列
词法单元由两个部分组成：名字和属性值，词法单元的名字是语法分析器进行语法分析时使用的抽象符号，我们常把这些词法单元名字称为终结符号，
因为它们在描述程序设计语言的文法中是以终结符号的形式出现的，如果词法单元具有属性值，那么这个值就是一个指向符号表的指针，符号表中包含
了该词法单元的附加信息。这些附加信息不是文法的组成部分，因此在我们讨论语法分析时，通常将词法单元和终结符号当做同义词
推导
首先从开始符号出发，不断将某个非终结符号替换为该终结符号的某个产生式的体，可以从开始符号推导得到的所有终结符号串的集合称为该文法定义的语言
语法分析 (parsing) 的任务是：接受一个终结符号串作为输入，找出从文法的开始符号推导出这个串的方法，如果不能从文法的开始符号推导得到该终结符号串，
则报告该终结符号串包含的语法错误
语法分析树
给定一个上下文无关文法，该文法的一棵语法分析树 (parse tree) 是具有以下性质的树：
- 根节点的标号为文法的开始符号
- 每个叶子节点的标点为一个非终结符号
- 每个内部节点的符号为一个非终结符号
- 如果非终结符号A是某个内部节点的符号，并且它的子节点的标号从左到右分别是X1 X2 … Xn，那么必然存在产生式A->X1X2…Xn，其中X1 X2 … Xn既可以是终结符号
也可以是非终结符号，作为一个特殊情况，如果A->e是一个产生式，那么一个标号为A的节点可以只有一个标点为e的子节点
二义性
一个文法可能有多棵语法分析树能够生成同一个给定的终结符号串，这样的文法称为具有二义性 (ambiguous)，要证明一个文法具有二义性，我们只需要找到一个终结符号串
说明它是两棵以上的语法分析树的结果。因为具有两棵以上语法分析树的符号串通常具有多个含义，所有我们需要为编译应用设计出没有二义性的方法，或者在使用二义性文法时
使用附加的规则来消除二义性
运算符的结核性
一些规则来说明哪个运算符是“左结合”还是“右结合”
运算符的优先级
一些规则来定义说明符之间的相对优先关系
语法制导翻译
语法制导翻译是通过一个文法的产生式来附加一些规则或程序片段而得到的
expr -> expr1 + term
此处，expr 是两个子表达式 expr1 和 term 的和
1 | 翻译 exp1; |
首先建立 expr1 和 term 的语法分析树，然后处理 + 运算符并构造一个和次运算符对应的节点
后缀表示
中缀表达式转后缀表达式
综合属性
词法分析
词法分析器的作用
任务：读入源程序的输入字符、将它们组成词素，生成并输出一个词法单元序列，每个词法单元对应于一个词素
这个词法单元序列被输出到语法分析器进行语法分析。词法分析器通常还要和符号表进行交互，当词法分析器发现了一个标识符的词素时，它将这个词素添加到符号表中
在某些情况下，词法分析器会从符号表中读取有关标识符种类的信息，以确定向语法分析器传送哪个词法单元
通常，交互是由语法分析器调用词法分析器来实现的，图中的命令getNextToken所指示的调用使得词法分析器从它的输入中不断读取字符，直到它识别出下一个词素为止
词法分析器根据这个词素生成下一个词法单元并返回给语法分析器
词法分析器在编译器中负责读取源程序，因此他还会完成一些识别词素之外的其他任务
任务之一是过滤掉源程序中的注释和空白
另一个任务是将编译器生成的错误信息与源程序的位置联系起来
有时，词法分析器可以分为两个级联的处理阶段
- 扫描阶段主要负责完成一些不需要生成词法单元的简单处理，比如删除注释和将多个连续的空白字符压缩成一个字符
- 词法分析阶段是较为复杂的部分，它处理扫描阶段的输出并生成词法单元
词法分析及语法分析
把编译过程的分析过程划分为词法分析和语法分析阶段有如下几个原因
- 简化编译器的设计，将词法分析和语法分析分离通常使我们至少可以简化其中的一项任务
- 提高编译器的效率，把词法分析器独立出来使我们能够使用专用于词法分析人物、不进行语法分析的技术
- 增强编译器的可移植性，输入设备相关的特殊性可以被限制在词法分析器中
词法单元、模式和词素
在讨论词法分析时，我们使用三个相关但有区别的术语
- 词法单元由一个词法单元名和一个可选的属性值组成
- 模式描述了一个词法单元的词素可能具有的形式
- 词素是源程序中的一个字符序列，它和某个词法单元的模式匹配，并被词法分析器识别为该词法单元的一个实例
在很多程序设计语言中，下面的类别覆盖了大部分或所有的词法单元
- 每个关键字有一个词法单元，一个关键字的模式就是该关键字本身
- 表示运算符的词法单元，它可以表示单个运算符，也可以表示一类运算符
- 一个表示所有标识符的词法单元
- 一个或多个表示常量的词法单元，比如数字和字面值字符串
- 每一个标点符号由一个词法单元，比如左右括号、逗号和分号