编译与计算机程序设计语言的关系
编译：将高级语言翻译成机器语言或汇编语言的过程
编译器和解释器的区别：
1.编译器整个将源程序翻译成目标程序，而解释器以源程序作为输入，每输入一条语句就执行一条语句，不生产目标程序
2.相比解释器编译器经过一次编译就不需要再编译，直接以目标程序运行即可
编译器在语言处理系统中的位置
翻译过程
一条句子的翻译过程：
1.词法分析
划分词性，如名词、动词、形容词
2.语法分析
划分短语，依靠词法分析，如名词短语、动词短语、介词短语
3.语义分析
最后根据语法分析，总结各短语的关系，得到一条句子的语义（中间表示形式），如某人干了某事，即名词短语和动词短语的练习
语法制导翻译
即编译器过程的逻辑实现，在实际中可能是多个步骤在一起实现，比如语法分析、语义分析、中间代码生成就被放在一起实现，而这个技术也称为语法制导翻译
词法分析
1.这个过程概括来讲就是：高级语言的单词 –> 对应的机内表示（也被称为token），为了区别这些机内表示，token的结构如下：
token：(种别码，属性值)，这很容易理解，种别码表示哪类词性，比如名词或是动词，而属性值就是这具体指哪个名词或是动词，而高级语言具体存在那些token，如下图：
语法分析
文法：短语组合规则，即语法规则，毕竟短语是由各种单词构造的，所以文法指的就是各种token构造成语法的规则，或者说称它为生成语法的函数
语法分析：从词法分析器输出的token序列识别短语并构造语法分析树的过程，语法分析树描述了句子的语法结构
语义分析
高级语言大概分为声明语句和可执行语句，声明语句声明属性和对象，而属性和对象作为可执行语句的操作单元，重新赋值给新的属性或对象，而这些对象就属于token中的标识符，可见表示符是声明语句和可执行语句的重要组成部分
所以语义分析的第一任务是提取这些属性，并且记录它们的种属（比如简单变量、数组、函数或者叫过程）、类型、值、作用域、位置、长度
语义分析的第二任务是语义检查
中间表示形式
1.表现方式：三地址码和语法结构树
三地址码：由三地址指令序列组成，每条指令最多有三个操作数，所以被称为三地址码，三地址指令形如：
三地址指令的数据结构表示分为：四元式（类似汇编语句，前缀表达式）、三元式，间接三元式
四元式形如：
如此可见，中间表示形式已经非常像汇编代码，而目标代码生成器最终的任务就是为变量或对象选择合适的寄存器
2.代码优化，分为机器无关代码优化器和机器相关代码优化器，在语言处理系统中所处的位置如下：
词法语法分析基本概念
字母表：有穷字符集合，这个字符包括大小写字母，数字，标点符号等，用∑表示，其中用ε表示空串
字母表的基本运算：乘积、n次幂、正闭包、克林闭包
正闭包：长度为正数的串的集合，是无穷的，不断的进行递归的幂运算得到的集合
克林闭包与正闭包：克林闭包 equal （正闭包 并 空字母表）
串：克林闭包的每个元素，都被称为一个串
串的长度
串运算：连接，幂运算
文法定义
首先看下图：该图表示的是自然语言中句子的文法
我们可以看到文法是由一条条产生式构成，如果我们把产生式作为函数，那么产生式左端就是函数参数，右端就是函数输出
如果把函数也作为属性，那么它表示就是产生规则，我们丢入原料就会输出产物，而把函数作为参数传给函数，就会形成更大的规则，甚至的递归的
因而上图表示的是句子的产生规则
其中未用尖括号的部分称为语言的基本符号（函数的最终输出），有括号的称为语法成分（函数）
终结符和非终结符
非终结符：表示语法成分的变量
终结符：语言的基本符号，也叫token
以上两者统称文法符号
两者关系：
产生式
产生式左右端均是串，串是由终结符和非终结符组合而成，而产生式左端至少包含一个非终结符
开始符号
文法最终的输出
符号约定
终结符：
非终结符：
文法符号（以上两者均可以表示）、终结符号串、文法符号串：
语言的定义
推导和规约
推导，按照产生式向右推导，最终得到只有终结符的式子，规约相反，向左推导，直至产生式左端是开始符号
通过这两个方法可以判断一个词串是否是该语言的句子
句型和句子
S =>* x，即开始符号经过若干推导步骤得到的产物就可称为句型，而只有终结符的句型才称为句子
短语、直接短语、句柄
看下文：
语言
所有句子构成的集合就被称为语言，即L(G) = {w|S =>* w，w∈VT* }，其中VT* 表示终结符的克林闭包，w表示终结符号串
文法解决了无穷语言的有穷表示，函数的递归表示不也可以实现这样的效果吗，这也是我为什么把文法比作函数的原因，也可以对应到MIT-Scheme流和表的定义，两者都有递归性质
文法的分类
四种文法之间的关系：
正则文法
正如我们用L(G)表示语言，其中G表示文法，同时也可以用L(r)表示，其中r，就是正则表达式
1.正则文法（3型文法）包括右线性文法和左线性文法，即在上下文无关文法的基础上约束产生式右端要么是终结符号串，要么是非终结符和终结符号串的组合（文法符号串），而非终结符的位置则决定了是右线性文法还是左线性文法
2.正则文法示例： 使用正则文法
| 其实正则文法和正则表达式很像，只不过多了空串和表达式引用，其他如*（0个或多个字符）， | （或）等符号的意思是相同的 |
3.正则表达式，是正则文法的更加紧凑易读的写法，其实就是我们平时应用的正则表达式，而且这个*，其实就集合运算中的克林闭包；见下图：
| 4.运算符优先级：* 克林闭包 > 连接 > |
5.正则定义
为了方便我们可以给正则表达式命名，并在其他正则表达式中使用这些标识符，构造一个更加复杂的正则表达式
例子：
6.正则文法转正则表达式
基本思路：
1
2
3
4
1.根据正则文法G构造正则表达式联立方程组
2.解联立方程组，求等价的正则表达式r
3.求得结果
最终结果是 S=r的形式
如何构造方程组：
然后代入消元，解联立方程组，最终得到S=r的形式
CFG（上下文无关文法）的分析树
上下文无关文法相比正则文法使用更多，受到更多的研究并且相比正则文法能更熟练的表达句子，但是程序中的大多数单词可以用正则文法表示，下面是分析树的相关概念：
句型的短语
二义性文法
一个文法可以为一个句子生成多颗分析树，则该句子存在二义性文法，二义性文法是不好的，我们可能需要引入非终结符来消除二义性，以便编译器能准确的翻译句子，或者定义一组规则，避免二义性文法，如：else与离它最近的if组合
二义性文法的判定
给定一个充分条件，满足这个条件则说明该文法无二义性，否则不能说明是否存在二义性
有穷自动机（FA）
它是一个数学模型，模型示意图如下：
用一句话表示这个模型就是，有穷控制器根据读头指向的输入，和当前状态，判断是否进入下一状态
有穷自动机可以通过转换图表示
FA接收的语言
对于串A，如果FA存在对应于串A的从初始状态到某个终止状态的转换序列，则称串A被FA接收，有FA所能接收的所有串组成的集合称为FA接收的语言，记为L(M)
最长子串匹配原则
简单来说就是匹配到最远的终止状态
FA的分类
FA又可以分为DFA、NFA，其中DFA表示确定的有穷自动机，即每读取一次输入，只会有一个输出，而NFA则可能有多个，相比于DFA，NFA更加直观，但程序实现更加复杂，DFA则相对容易
DFA的算法表示：
s = s0; // s0表示初始状态
c = nextChar(); // 读取下个输入
while(c != eof){
s = move(s,c) // ð函数，更新当前状态
c = nextChar();
}
if(s在F中) return "yes"; // F代表终止状态集
else return "no";
如上，s0初始状态和F终止状态集是已知的，句子作为输入
正则文法、正则表达式、NFA、DFA之间的关系
正则文法 <==> 正则表达式 <==> NFA <==> DFA
我们最终需要的是DFA，因为其用程序更容易实现，因而更适合构造我们的词法分析器，而在求DFA时一般按照上面的顺序一步步得到DFA，但其实目前从正则表示式也可以很容易直接构造DFA，例如有如下的正则表达式：
(a b)* abb，我们可以把它分成四个部分，第一部分：(a b)* ，第二部分：a，第三部分：b，第四部分：b，按照从左往右的顺序，每连接一个部分就是一个新的句型，所以把每个句型作为FA模型中的状态，根据输入，判断是否应该转入下一句型，或是回溯到原来的句型，这样就能一步步构造出DFA了
NFA ==> DFA
上例中我们可以发现，DFA中每个状态都是由NFA中的状态构成的集合，而每接收一个输入，会作用到集合中每个状态，从而又形成新的状态集合
词法分析器的错误处理和错误恢复
词法分析器检查单词的步骤：词法错误检测 ==> 调用错误处理程序 ==> 错误处理 ==> 错误恢复策略
1.首先词法错误检测：如果当前状态遇到了不可能的输入，调用调用错误处理程序
2.错误处理程序查找已扫描的字符串中最后一个于某终态对应的字符，如找到，将该字符和前面的字符识别为一个正确的单词，未找到则报错，并启用错误恢复策略
3.错误恢复策略删除输入，知道遇到正确的字符开启下一轮错误检测，直至扫描完整个输入
语法分析
自顶向下的分析概述
从分析树的根节点（文法开始符号）向叶节点（一般时文法终结符）方向构造分析树，其实就是之前判断一个词串是否是文法的句子，从开始符号推导得到终结字符串的过程，也就是S ==>* w的过程
如何构造分析树：给定文法如下
1
2
3
4
5
6
7
8
文法
①E --> E + E
②E --> E * E
③E --> (E)
④E --> id
输入
id + (id + id)
其中我们发现每一步推导我么都需要做两个选择
- 用该非终结符的哪个候选式进行替换
- 替换当前句型中的哪个非终结符
其实以我们上帝视角来看这个词串其实很简单，把最左边的id，作为一个句型，（id+id）作为一个句型，就可发现它符合产生式：E –> E + E，然后（id + id）本身其实就符合产生式 E –> E + E，所以还是很简单的，计算机不像我们可以看到整个输入，计算机只能一个个读入
推导的方式
- 最左推导
- 最右推导
两种推导产生的语法分析树具有唯一性
自顶向下分析法总是采用最左推导
为什么会需要预测分析器
在自顶向下的递归下降分析法（计算机采用的自顶向下分析法）中，计算机根据输入选择候选式，如果该候选式不合适，就有必要回溯选择其他候选式，但回溯使得计算效率降低，所以我们通过预测分析器避免回溯，简单来说如果能够预测正确的候选式，就不会发生回溯了（听起来其实有点扯，什么叫做能够预测出正确式子，总之不急，慢慢来，继续学习下面的内容）
预测分析
我们前面也提到过计算机不像人能提前看到后面的输入，它只能一个个读入输入，而预测分析器中提到的向前看k个输入符号估计就是为了能模仿人类这种分析的方式
文法转换
不是所有文法适合自顶向下分析法，所以就存在文法转换，将不合适的转换成合适的
回溯存在的例子：
即句型存在公共前缀，容器出现回溯，如果前者不合适就需要回溯选择下一个，这种情况的解决办法是提取左公因子 
另外如果有形如：A –> Aα 的文法，对于计算机很容易陷入无限循环，而这种文法被称为左递归文法，如下：
消除直接左递归
基本上是套公式，如图：
消除间接左递归
通过代入消元，将间接左递归转换成直接左递归，如下例：
