本文章仅供博主自己复习编译原理回忆之用，由于是速成的所以难免会存在谬误，如有误请在评论区指出。

1.编译器的总体结构

词法分析-语法分析-语义分析-中间代码生成-机器无关代码优化-机器代码生成-机器相关代码优化

（这也是整本书接下来逐个叙述的一个结构）

那么编译器读取到源代码，要做的第一件事就是要从里面的代码识别出词素(lexeme)，然后将他们转化为词法单元(token)。这部分可以参照龙书上的示例。

词素就是有意义的，可转化为一个词法单元的字符串，而词法单元就是描述这个词素本身的类别以及其含有的意义的一个单元。

将源代码中的一个个词素转化为相应的词法单元后，我们就要考虑这些词法单元如何相互配合，来形成一条条语句，表达式，或是一个执行逻辑，乃至一条程序。所以我们就要约定好一些语法规则（以确定优先级以及它们的语法地位等），然后生成出一棵语法树（语法解析的顺序）。

语义分析等todo

2.词法分析

正则文法与上下文无关文法的区别：

正则文法不允许递归文法。即：当前定义的文法的右侧中的非终结字符必须是已经被定义过的非终结字符。

如A -> Aa|b

这是一个上下文无关文法，但不是正则文法。

从正则表达式到NFA的构造很简单，就不说了。

从NFA到DFA：

epsilon-closure（T）是从一个状态集T沿着epsilon可以走到的状态集（实际上，这样的状态集可以作为DFA上的一个状态结点，因为DFA是没有epsilon边的，epsilon在从NFA转化为DFA时已经被化入了新生成的状态集中，由此我们可以再探究从这个状态集中的每一个状态对于不同的字符又会到达哪些状态来构造DFA）。

那么我们按照上面的方法就可以开始构造DFA，方法是求开始结点的epsilon-closure，然后对于每一个字符能转移到的状态集，新的我们就再来看看这些新的状态集对于每一个字符能转移到的状态集...直到没有新的状态集产生。

最小化DFA：

用上面的方法得出的DFA有可能不是最小的，于是我们还得对其再进行一个最小化的操作。

方法是首先将所有状态分成终结状态和非终结状态两组，然后看看每个组里面的状态，看看它们对于相同的输入字符是否会到达相同的组，如果有某些成员到达了不同的组，就将它们划分开来形成一个新组，继续观察每个组的状态对于相同的输入字符的转移情况来观察，直到不能再划分出新的组。最后我们合并处在相同组的状态的转移边，即实现了DFA的最小化。

3.语法分析

最左推导与最右推导：每次替换最左（最右）的非终结字符。

消除立即左递归：其实就是把终结符号先放在前头，再另外设一个文法来生成递归的非终结符号旁边的终结符号。

消除左递归：

其实就是将之前已经消除过左递归的式子带进去现在的这个式子，然后再消除这个式子本身的立即左递归。

之前说过语法分析其实就是将词法单元组拿去匹配语法规则，那么这种匹配实际上是有（至少）两种方法的：自顶向下法与自底向上法。

自顶向下法：

就是根据源代码来匹配出语法规则，也就是说一开始是一组文法的开始非终结字符，然后通过一系列改变转为相应的语法规则。这样的改变是需要回溯的，也就是遇到错误，就需要回到上一次的选择枝来选择另一个语法规则。（相当于DFS穷举匹配）这样做无疑是十分低效的。于是我们可以通过看现在还没被匹配的栈中的词法单元来直接判断我们能否转变，以及怎样转变，也就是直接选择出翻译的分支。但是这样做很明显，我们对于同一个CFG，翻译的分支不能有相同的前缀，而且当有可能是空时，还要将CFG左侧有可能跟着的下一个字符也算进去我们的与栈中词匹配的序列里面...其实说了这么多，要达到这个需求，只要符合LL（1）文法就可以了，因为LL(1)文法就是需要我们符合这个需求。

那么需要做到这样的预先匹配，我们就需要让我们的文法符合LL(1)，然后算出FIRST(X)和FOLLOW(A)就可以算出预测分析表了，然后我们就可以根据这个表来进行自顶向下的分析。

自底向上法：

自底向上法比较复杂。