编译流程

词法分析(生成token流)->语法分析（生成AST）→语义分析(AST)→生成字节码(生成IR ，可跳过)->编译器优化（可跳过）->生成汇编代码或机器码 →封装成可执行文件

一些概念

符号、标识符(identifier): 一般是用空格分开的字符串（非数字）

产生式（production）： 形如 A->a 这种表示方式，意思是A可以用a来替换，其中A和a都是文法符号

文法： 多个产生式构成的一组表示方法

句型：开始符经过若干步推导后得到的串。

终结符： 不可以继续用文法展开的符号
非终结符： 可以用文法继续展开的符号，一般是变量或者语句

正则表达式与一般文法的区别： 正则表达式比较简洁， 多用于词法分析，文法比较复杂，多用于语法分析（正则表达式不能表示嵌套结构）

符号表：保存标识符(函数、变量等)有关的信息（出现在哪个文件中、第几行等），编译过程中不涉及函数和变量的内存地址 （是在后续链接过程中重定位时加入的）

词法分析：
记号（token）：词法分析的输出物，一般是通过正则表达式来匹配的字符串集

词法分析的过程：前向指针从头到尾扫描一遍字符串，找到匹配的记号，如果匹配错误有可能需要回溯。从状态转换图的角度来说就是从开始状态到接受状态的一个转换过程。

开始状态：读入第一个字符。
接受状态：匹配模式的字符串。

状态转换图： 扫描过程的记录，每一步都是一个状态。当读取一个字符时，进入一个状态，每个状态可能有多个转换方向（找到下一个匹配的字符）。当字符串全部读入，到达接收状态（找到完全匹配的字符串）后，便结束。如果转换过程中遇到错误，还需要回溯。
状态转换图也可以用于语法分析。

有穷状态机：指状态数量是有限的

image.png

转换表：状态图的表格形式

image.png

NFA（不确定有穷状态机）：状态转换的方向不确定（有多个方向）

image.png

DFA（确定有穷状态机）：状态转换的方向确定（只有一个）

image.png

NFA是比较普遍的情况，但对于计算机来说，实现的成本（时间复杂度）太高，一般都要转换成DFA

语法分析：
分析树：推导过程的图形表示

image.png

左递归： 形如A→Aa这种的产生式，可以无限循环展开下去（类似的还有右递归），在程序设计中要尽量避免。有一些通用的方法可以消除递归。

二义性：对一个文法，存在两个或两个以上的分析树（推导过程）。

递归下降语法分析：从根节点（文法开始符号）开始，从上至下，从左至右的为输入字符串建立一个分析树，并以预先确定的顺序创建分析树的节点

自底向上语法分析：从叶节点开始，向根节点前进的分析过程。

预测语法分析：通过观察候选式所推导出的第一个符号，确定正确的表达时。一般用于分析if..then…else这样具有不同关键字的控制流结构。这种方法用栈来替代递归调用，是无回溯的，需要用到预测分析表。

image.png

FIRST(A)：从A推导出的串的开始符号的终结符集合。对于F->(E)|id, FIRST(F)={(,id}

FOLLOW(A)：包含所有在句型中紧跟在A后面的终结符的集合。

预测分析表：根据FIRST函数和FOLLOW函数构造出的用于预测分析的表格。该表格跟踪的是输入符号的最左推导。空白项是出错信息

image.png

LL(1)：预测分析表中没有多重定义表项的文法。从左到右扫描符号（第一个L），基于最左推导（第二个L），语法分析器每步动作向前扫描一个输入符（1）。

算符优先分析法：用来分析表达式

image.png image.png

句柄：和一个产生式右部匹配的子串，而且把他归约到该产生式左部的非终结符代表了最右推导逆过程的一步

归约：自底向上构造分析树的过程中，把子串和某个产生式的右部进行匹配，用该产生式的左部替代子串的步骤

移动归约分析：用一个栈保存文法符号，用输出缓冲区来保存要分析的串，不停的移动或者归约，直到发现错误或者栈中只含有开始符号并且输入串为空。
移动：把下一个输入符号移动到栈顶。
归约：语法分析器知道句柄的右端已在栈顶的情况下，在栈中确定句柄的左端，并选择正确的非终结符替代句柄。

LR语法分析： 从左至右扫描输入字符串（L），构造最右推导的逆过程（R）。

image.png

LR语法分析表：包含action函数和goto函数，action(sm,ai)根据栈顶状态sm和当前输入ai，确定下一步是进行移动、归约、接受或者是产生错误。 goto(sm, G)根据栈顶状态sm和文法符号G 来进行状态的转移。