编译原理-学习记录2
编译程序的工作步骤（续）
中间代码生成
通常和语义分析在同一步
代码优化
保持等价变换，提高目标程序的质量
代码生成
如果在语义分析时已经得到目标指令，则不需要进行代码生成
目标指令可能是绝对指令代码、可重新定位的指令代码或汇编指令代码
从编译实现的角度，有表格管理和出错处理，这两个步骤贯穿整个编译过程
表格管理
使用符号表，登记源程序中出现的每个名字及其各种属性，有些名字的属性需在各个阶段才能填入
出错处理
错误分为语法错误和语义错误。语法错误指源程序中不符合语法或词法的错误，可以在词法或语法分析时被检测；语义错误指源程序中不符合语义规则的错误，一般在语义分析时被检测出，也有的要在运行时才能检测出
无法查出动态语义错误。动态语义错误是在使用中出现的
编译程序的结构
按阶段来看，有词法分析、语法分析、语义分析、代码优化和代码生成。而表格处理与出错处理则与每一阶段都有关联
此为逻辑结构，并非执行顺序
分析-综合模型
此模型将编译拆分为两个部分：分析部分和综合阶段
分析部分包括词法分析、语法分析和语义分析
综合阶段包括中间代码生成、代码优化和代码生成
编译程序的组织方式
遍（pass）
指一个程序在编译时把源程序或中间程序从头到尾扫描一遍并转换成另一紧邻的等价物的全过程。例如：对源程序进行词法分析得到单词（串）的过程算作一遍。
根据扫描的遍数，可以将编译程序分为单遍扫描程序和多遍扫描程序
单遍扫描
编译速度快、效率高，但运行时占用空间大，目标程序质量低（https://wenku.baidu.com/view/a69684a3a55177232f60ddccda38376bae1fe0d9.html）
多遍扫描
每遍都从外存获取前一遍的结果作为开始，工作结果仍然记入外存，占内存小，但运行效率低
分工明确，便于多人合作开发
前端/后端
前端主要由与源语言有关但与目标机器无关的部分组成，例如：词法分析、语法分析、语义分析、中间代码生成及部分代码优化
后端主要包括与目标机器有关的部分，例如：与目标机器有关的代码优化、目标代码生成。后端仅依赖于中间语言
通过改变编译程序的后端可以实现编译程序移植
编译程序的构造
高级语言的自编译性
一个语言可以用来编写自己的编译程序
编译的自展技术
先对核心部分构造编译程序（核心部分使用机器语言或汇编语言），随后经过一系列自展途径而形成更大的编译程序
先对源语言 L 0 L_0 L0构造编译器 T L 0 M T_{L_0M} TL0M，将 L 0 L_0 L0扩充为 L 1 L_1 L1语言（ L 0 ⊂ L 1 L_0\subset L_1 L0⊂L1），再用 L 0 L_0 L0编写 L 1 L_1 L1的编译程序 T L 1 M T_{L_1M} TL1M。同样地，再将 L 1 L_1 L1扩充为 L 2 L_2 L2语言，用 L 1 L_1 L1编写 T L 2 M T_{L_2M} TL2M……以此类推，即可将编译程序扩充的越来越大
编译的移植
移植：将宿主机上的具有自编译性的高级语言编译程序移植到目标机上
将A机器上的高级语言L的编译程序移植到B机器上的过程：
(1)“L语言编写的A机器上运行的、产生B代码的L语言编译程序”的源程序，经过“在A机器上运行的、产生A代码的编译程序”，得到“在A机器上运行的、产生B代码”的编译程序
(2)使用(1)中得到的“在A机器上运行的、产生B代码”的编译程序，对“L语言编写的A机器上运行的、产生B代码的L语言编译程序”的源程序进行编译，得到“在B机器上运行的、产生B代码”的编译程序
理解（图例参考：https://blog.****.net/yihaolovem/article/details/39101349）：
(1)：如图1（左）所示，现有两种编译器，一种是使用L语言，将L语言变换为B机器语言，而另一种则是使用A机器语言，将L语言变换为A机器语言，以供A机器运行。而图1（右）将这两个编译器结合起来，使用后者编译前者，即可等效于用A机器语言，将L语言编译为B机器语言。值得注意的是，这个编译过程还是基于A机器语言的，与B机器无关。
(2)：如图2所示，使用(1)中得到的编译器，在A机器上对“使用L语言，将L语言变换为B机器语言”的编译器进行编译，编译出的结果便是在B机器上使用的编译器，能够将B机器上将L语言转换为B语言（相当于将左侧编译器的下方的L换成B）。
编译程序自动化
使用词法分析程序生成器、语法分析程序生成器等可以快速构造编译器，但并不能全自动化
ch2.文法和语言的形式定义
语法
由程序设计语言的基本符号组成程序中各个语法成分(包括最大的语法成分“程序”)的一组规则，其中：
词法规则：由基本符号构成符号(单词)的书写规则
语法规则：由符号(单词)构成语法成分的规则
例如：赋值语句的语法为：
<赋值语句>::=<变量><赋值号><表达式>
语义
程序设计语言中按语法规则构成的各个语法成分的意义，也就是各语法成分在运行阶段被计算机执行时所做的工作及其结果，其中：
静态语义：编译时刻可确定的语法成分含义
动态语义：运行时刻才能确定的语法成分含义
例如：赋值语句的语义为：
先对语句的右部表达式求值，再把所得结果与语句左部的变量相结合，并取代该变量原有的值
语用
表示语言符号及其使用者之间的关系
例如：赋值语句的语用为：
计算和保存表达式的值
使用自然语言时，无法让使用者与实现者达成共识，因此需要使用形式化的方式：形式语言
字母表与字符串
字母表
元素有穷非空的集合，字母表的元素称为符号
元素不仅局限于字母，也可以是数字等。常用大写英文字母或希腊字母表表示元素
{a, b, …, y, z}，{0, 1}等都算是字母表
一个程序设计语言只使用有限符号集作为字母表
符号串与符号串集合
符号串：字母表中符号组成的任何有穷序列，通常用小写字母表示
空串不包含任何符号，记为
ϵ
\epsilon
ϵ
符号串的长度：符号串中符号的个数（表示形式：x的长度为|x|）
空串长度为0，与空集
∅
\empty
∅不同
符号串的连接：假定有同一字母表上的两个符号串x,y，把y的各个符号写在x的符号之后得到的符号串，称为x与y的连接，记作xy。例如：x=ab，y=ba，则xy=abba
符号串的方幂：设x是符号串，把x自身连接n次得到的符号串，即z=xx…x(n个x)，称为x的n次方幂，记作 x n x^n xn。例如：x=ab，则 x 3 x^3 x3=ababab
符号串集合：若集合中所有元素都是某字母表上的符号串，则称其为该字母表上的符号串集合。用大写英文字母表示。
符号串集合的乘积：定义为
A
B
=
{
x
y
∣
x
∈
A
,
y
∈
B
}
AB=\{xy|x\in A,\ y\in B\}
AB={xy∣x∈A, y∈B}
例如：A={a, b}，B={0, 1}，则AB={a0, a1, b0, b1}
符号串集合的方幂：定义为 A n = A n − 1 A = A n − 2 A 2 = ⋯ = A A n − 1 A^n=A^{n-1}A=A^{n-2}A^2=\cdots=AA^{n-1} An=An−1A=An−2A2=⋯=AAn−1，与符号串方幂不同的是，此处为符号串集合之间的运算
符号串集合的闭包
A
∗
A^*
A∗与正闭包
A
+
A^+
A+：
A
A
A的闭包
A
∗
A^*
A∗：A上所有有穷长的串的集合——
A
∗
=
{
ϵ
}
∪
A
∪
A
2
∪
⋯
A^*=\{\epsilon\}\cup A\cup A^2\cup \cdots
A∗={ϵ}∪A∪A2∪⋯
A
A
A的正闭包
A
+
A^+
A+：
A
+
=
A
∗
−
{
ϵ
}
A^+=A^*-\{\epsilon\}
A+=A∗−{ϵ}
串s的各部分：
（1）前缀：从s尾部删除0或多个符号后得到的串
（2）后缀：从s的开始处删除0个或多个符号后得到的串
（3）子串：删除s的某个前缀和后缀后得到的串
（4）真前缀，真后缀，真子串：s的既不等于
ϵ
\epsilon
ϵ，也不等于s本身的前缀、后缀和子串
（5）子序列：从s中删除0个或多个符号后得到的串，这些被删除的符号可能不相邻
形式语言
字母表上的符号串的任意集合
例如：若字母表
Σ
=
{
a
,
b
}
\Sigma=\{a,\ b\}
Σ={a, b}，则定义在
Σ
\Sigma
Σ上的语言可以有
L
1
=
{
a
b
,
b
a
}
L_1=\{ab,\ ba\}
L1={ab, ba}，
L
2
=
{
a
b
,
a
b
a
b
,
a
b
a
b
a
b
,
…
}
L_2=\{ab,\ abab,\ ababab,\ \dots\}
L2={ab, abab, ababab, …}等
文法的形式定义
文法
终结符号：组成语言的基本符号，如保留字、运算符、界限符等。终结符号是语言的不可再分的基本符号。终结符号形成的集合记为
V
T
V_T
VT
非终结符号：用来表示语言的语法成分（或语法范畴、语法单位），例如“赋值语句”。非终结符号所形成的集合记为
V
N
V_N
VN
终结符号和非终结符号不能有交集