搁置
编译原理， 媒体处理一天都在和字符，二进制位操作， 操作系统这些底层打交道， 学这个获益极大。
笔记大体上就是概括大意,细致的东西以后的自己翻书或者搜索吧~
第1章 引论
1.1 语言处理器
编译器是一个将源语言翻译为目标语言的程序， 如果目标程序是一个可执行的机器语言程序， 它就可以被用户调用。解释器不通过翻译的方式生成目标程序， 它直接利用用户提供的输入执行源程序的操作。
把用户输入映射为输出的过程中，由编译器产生的机器语言目标程序比解释器快很多， 但解释器的错误诊断效果通常比编译器更好。
例如：Java语言处理器结合了编译和解释过程，java源程序首先被编译成字节码， 由虚拟机对字节码加以解释执行。
语言处理系统：
- 预处理器将程序的多个模块聚合在一起，它还负责把宏的缩写形式转换为源语言的语句
- 编译器受到预处理的源程序可能产生一个汇编语言程序， 因为汇编语言比较容易输出和调试
- 汇编器处理这个汇编程序生成可重定位的机器代码
- 由于一个文件中的代码可能指向另一个文件的位置， 链接器解决外部内存地址的问题
- 加载器把所有的可执行目标文件放到内存执行
1.2 一个编译器的结构
编译器将源程序映射为目标程序， 这个映射过程由两部分组成：分析部分（前端）和综合部分（后端）
分析部分将源程序分解为多个组成要素， 在这些要素上加上语法结构， 使用这个结构创建源程序的一个中间表示。如果分析部分检查出源程序没有按照正确的语法构成或者语义不一致就会提供有用信息使得用户按此改正。分析部分还会收集源程序的信息将其存放在一个符号表的数据结构。符号表和中间表示形式一起传送给综合部分。、
综合部分根据中间表示形式和符号表中的信息来构造目标程序。
编译过程步骤：字符流 —(词法分析器)—> 符号流 —(语法分析)–>语法分析—(语义分析)–>语法树 —(中间代码生成器)–> 中间表示形式 —(机器无关代码优化器)–> 中间表示形式—(代码生成器)–>目标机器语言 —(机器相关代码优化器)–> 目标机器语言
优化是可选的。
1.2.1 词法分析
编译器的第1个步骤为词法分析/扫描。
词法分析读入源程序的字符流， 将它们组织为词素的序列。对于每个词素产生形如<token-name, attribute-value>的词法单元作为输出。其中token-name是由下一步语法分析使用的抽象符号。 attribute-value指向符号表中关于这个词法单元的条目。
例如： 语句position = initial + rate * 60
- position: 被映射为词法单元
<id, 1>，（id是表示标识符的抽象符号， 1是符号表中position的下标， 存放着标识符的名字和类型等信息） - =:
< = >，这个词法单元不需要属性值于是省略， 但也可以使用assign抽象符号作为词法单元的名字。 - initial:
< id, 2 > - +:
< + > - rate:
< id , 3> - *:
< * > - 60:
< 60 >，按理应是<number , 4 >， 具体阅读第2， 3章
于是position = initial + rate * 60 —词法分析–> <id,1><=><id,2><+><id,3><*><60>
1.2.2 语法分析
编译器的第2个步骤称为语法分析/解析。
语法分析器使用词法分析器生成的各词法单元的第一个分量来创建树形的中间表示， 它给出了词法单元分析的语法结构。一个常用的表示方法是语法树， 树中每一个内部节点表示一个运算， 该节点的子结点表示运算的分量。
这颗树显示了语句position = initial + rate * 60的运算执行顺序：
1 =
2 / \
3<id,1> +
4 / \
5 <id,2> *
6 / \
7 <id,3> 60
运算顺序和通常的算术规则相同。
1.2.3 语义分析
语义分析器使用语法树和符号表检查源程序是否和语言定义的语义一致， 同时也收集信息存放在语法树和符号表中以便后续中间代码过程使用。
语义分析还执行类型检查， 检查每个运算符是否具有匹配的运算分量。如果类型错误将报告错误。
如果程序设计语言允许自动类型转换， 那么语义分析将进行自动类型转换。
例如：<id,1>，<id,2>，<id,3>为浮点数， 那么60在这种情况下需要转化为浮点数才能相，这时语义分析器输出一个关于运算符inttofloat的额外结点。inttofloat明确地将整数参数转化为浮点数。
1 =
2 / \
3<id,1> +
4 / \
5 <id,2> *
6 / \
7 <id,3> |
8 inttofloat
9 |
10 60
1.2.4 中间代码生成
在语法分析和语义分析完成后， 编译器生成一个低级的类机器语言的中间表示，这种语言具有两个性质：它易于生成，能够轻松地翻译为目标机器上的语言。
第6章会介绍一种叫三地址代码的中间表示形式， 它类似于汇编指令， 每个指令具有三个运算分量， 每个运算分量类似于寄存器。
1t1 = inttofloat(60)
2t2 = id3 * t1
3t3 = id2 + t2
4id1 = t3
关于三地址指令：
- 每个三地址赋值指令的右部最多只有一个运算符
- 编译器应该生成一个临时名字存放三地址指令计算得到的值
- 有些三地址指令运算分量少于三个
1.2.5 代码优化
机器无关的代码优化生成更好的代码， 通常意味着更快， 也可以是更短或者能耗更低。
不同编译器代码优化的工作量相差很大， 有的优化工作做得很多会在优化阶段花相当多的时间；有些优化简单可以极大提高程序运行效率且不会降低很多编译速度。
例如：优化器得出结论，把60转化为浮点数的运算可以在编译时刻一劳永逸地完成， 于是使用浮点数60.0替代整数60可以消除inttofloat运算；t3仅被使用一次， 可以把它的值传递给id1
1t1 = id3 * 60.0
2id1 = id2 + t1
1.2.6 代码生成
代码生成器以中间表示形式输入映射为目标语言， 如果目标语言是机器代码， 它将为程序使用的每个变量选择寄存器或内存位置，然后中间指令被翻译成为机器指令序列。
例如使用寄存器R1和R2：
1#将地址id3的内容加载到寄存器R2中
2LDF R2, id3
3
4#‘#’表示60.0作为一个立即数处理。将60.0乘R2中的内容
5MULF R2, R2, #60.0
6
7LDF R1, id2
8
9#将存放在R2的值加到R1上
10ADDF R1, R1, R2
11
12#将寄存器R1中的值存放到id1中
13STF id1, R1
1.2.7 符号表管理
符号表为每个变量创建条目, 记录名字的各个属性如类型,作用域; 对于过程名字还包括参数数量和类型, 每个参数的传递方法和返回类型.
1.2.8 将多个步骤组合成趟
多个步骤组合成一趟. 我们可以把不同前端和某个目标机的后端结合为不同源语言建立目标机上的编译器; 同样也可以将同一个前端和不同目标机后端结合建立不同目标机的编译器. 这一切通过前端和后端的中间表示形式连接.
1.2.9 编译器构造工具
工具实现编译器的不同阶段, 它们生成的组件易于和编译器的其他部分相集成, 如语法分析器的生成器, 扫描器的生成器, 语法制导的翻译引擎, 代码生成器的生成器, 数据流分析引擎, 编译器构造工具集.
1.3 程序设计语言的发展历程
1.3.1 走向高级程序设计语言
按照代分类:
- 第一代语言:机器语言
- 第二代语言: 汇编语言
- 第三代语言: 高级程序设计语言(Fortran, Cobol, Lisp, C, C++, C#, Java)
- 第四代语言: 为特定应用设计的语言(NOMAD, SQL, Postscript)
- 第五代语言: 基于逻辑和约束的语言(Prolog, OPS5)
另一种分类方式:
- 强制式语言:指明如何完成一个计算任务的语言
- 声明式语言: 指明要进行哪些运算的语言.
冯诺依曼语言: 以冯诺依曼计算机体系结构为计算模型的程序设计语言
面向对象语言, 脚本语言…
1.3.2 对编译器的影响
- 编译器设计者必须设计算法和表示方式来翻译和支持新的语言特征.
- 通过降低用高级语言程序的执行开销, 编译器还可以推动这些高级语言的使用.
- 编译器必须能够正确翻译用源语言书写的所有程序, 但为源程序生成最佳代码的问题一般是不可判定的, 编译器设计者需要折中处理, 以解决高效代码生成问题.
1.4 构建一个编译器的相关科学
1.4.1 编译器设计和实现中的建模
如何设计正确的数学模型和选择正确算法的研究, 在过程中需考虑通用性, 功能, 简单性, 有效性之间的平衡. 如:
- 有穷状态自动机和正则表达式用来描述程序的词法单位(关键字, 标识符等)以及描述被编译器用来识别这些单位的算法
- 上下文无关法用于描述程序设计语言的语法结构
- 树形结构表示程序结构以及程序到目标代码的翻译方法
1.4.2 代码优化的科学
处理器体系结构更加复杂, 这让编译器有了更多改进代码执行方式的机会.
编译器设计目标:
-
优化必须是正确的(不改变编译程序的含义)
-
优化必须能够改善很多程序的性能.
性能通常意味着执行速度, 也希望降低生成代码的大小, 降低代码能耗. 另外错误报告和调试等可用性也很重要.
-
优化所需的时间必须保持在合理范围内
开启优化有时候会暴露源程序中的新问题, 需要对经过优化的代码再次进行测试.
-
所需要的工程方面的工作必须是可管理的