# 编译原理
# 名词
预处理器： 将称为宏的缩写形式转换成源语言的程序
编译器： 将程序源语言转换成机器或汇编语言的程序
汇编器： 将汇编语言转换成机器语言的程序
链接器： 解释出语句中的外部内存地址
加载器： 将可执行目标文件放到内存中执行
解释器： 通过翻译机器语言的指令，让机器按语言程序执行的程序
# 编译器
# 组成部分
由两个部分组成：
分析部分： 俗称编译器的前端。将源程序分解成多个组成要素，结合语法结构，利用该语法结构创建源程序的一个中间表示。收集有关源程序的信息，存储到一个称为符号表的数据结构中。编译器将中间表示形式和符号表一起传送给综合部分。
综合部分： 俗称编译器的后端。通过中间表示和符号表生成目标程序。
- 符号表： 用于存储键的名称与变量映射关系
# 步骤
将源语言解析成语法树，转换并优化为汇编语言或机器语言，具体如下：
字符流 ---词法分析器---> 符号流 ---语法分析---> 语法树 ---语义分析---> 语法树 ---中间代码生成器---> 中间表示形式 ---机器无关代码优化器---> 中间表示形式 ---代码生成器---> 目标机器语言 ---机器相关代码优化器---> 目标机器语言
# 词法分析
词法单元（token）由两部分组成： <token-name, attribute-value>
- token-name： 抽象符合，如：id、assign 或 =、+、-
- attribute-value： 词法单元的条目，如：空、123、456
词素： 源语言编写的语句的组成部分
# 语法分析
将词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。该中间表示给出了词法分析产生的词法单元流的语法结构。
- 语法树： 一种表示方法，树的每个结点表示一个运算，而该节点的子节点为运算的分量
# 语义分析
使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。如：静态类型检查
# 中间代码生成
两个重要性质：易于生成，易于翻译为目标机器上的语言，如：语法树
# 代码优化
改进中间代码，改进方向为：更快、更短或能耗更低的目标。
# 代码生成
将中间表示形式映射到目标语言，为程序中使用的每个变量分配寄存器或内存位置
# 符号表管理
记录程序中使用的变量名字、并收集和每个名字的各个属性有关信息，如：参数数量和类型、参数传递方式等
# 内存
寄存器： 存储二进制代码，它由具有存储功能的触发器组合起来构成的。
触发器： 数字电路中的一个存储单元，一个触发器可以存储一位二进制代码
缓存命中： CPU在缓存中找到所需数据称为命中，未命中才会访问内存
高速缓存： 高速缓冲存储器，具有容量小速度快的特性，大小一般在1K~nM bytes
物理寄存器： 即内存条，大小一般在1M~nG bytes
外部存储器： 如u盘，nG bytes
内存寻址： 将 逻辑地址 -> 线性地址 -> 物理地址 转化的过程
精简指令计算机： RISC（Reduced Instruction Set Computing），具有指令少，计算快的特点
复杂指令集计算机： CISC（Complex Instruction Set Computing），具有复杂指令，计算慢的特点
超长指令集： VLIW（Very Long Instruction Word），将多个指令连在一起，增加了运算的速度
SIMD处理器阵列： SIMD（Single Instruction Multi Data），一条指令同时控制多条并行的数据通道进行运算
共享内存的多处理器：
分布式内存的多处理器：
# 程序设计语言基础
软件开发领域相关术语
静态策略： 编译时决定
动态策略： 运行时决定
静态作用域： 又称词法作用域，词法解析时确定的作用域，具有阅读性
动态作用域： 会在重复声明时改变作用域
环境： 名字到存储位置的映射，他的改变遵循作用域规则
状态： 内存位置到值的映射
定义： 不同于声明，是一个定值的操作
BNF： 巴科斯范式，是一个上下文无关文法
# 翻译器
终结符号： 像if和括号这样的词法元素
非终结符号： 像表达式、语句这样的变量表示终结符号的序列
产生式： 形式表达式，如： stmt -> if (expr) stmt else stmt
ε： 读音依普西隆，零个终结符号组成的
上下文无关文法： 简称“文法”，由四个元素组成：
- 一个终结符号的集合，也称“词法单元”
- 一个非终结符号集合，也称“语法变量”
- 一个产生式集合
- 指定一个非终结符号为开始符号
二义性： 一个文法可能有多棵语法分析树能够生成同一个给定的终结符号串
左结合： 从左向右执行运算
右结合： 从右向左执行运算
因子： factor，不可被任何运算符分开的表达式
项： term，可能被优先级高的运算符 * 和 / 分开，不能被低优先级运算符分开的表达式
翻译方案： 即语法制导的翻译方案，将程序片段附加到一个文法的各个产生式上的表示法
后缀表示法： 运算量放前面，运算符放后面，虽然不符合人的习惯，但对计算机来说，可以很容易地使用一个栈来计算它的值或转换成另一种代码
注释语法分析树： 又称注释分析树，在各个节点上标记了相应的属性值
综合属性： 语法树结点N上的值是由N的子节点以及N本身的属性值确定的。只需要以深度优先的方式遍历语法树，对语法树进行自底而上的遍历求值，就可以计算出属性的值
语义动作： 被嵌入到产生体中的程序片段，用花括号括起来，并写入到产生体的体中，执行位置由此指定
自底向上分析方法： 先构造叶子，逐步构造出根结点，可以处理更多种文法和翻译方案，是语法分析器常用的方法
向前看符号： lookahead符号，即输入串的第一个（最左的）终结符号