本文主要记录一下编译原理的学习路径，由于龙书等著作已近给出了详细介绍，本文只给出算法介绍；本文不会写的特别严谨，主要是介绍算法。

词法分析器的实现主要有几个核心概念：
1，正则表达式
2，抽象语法树
3，NFA(不确定有穷状态机)
4, DFA(确定有穷状态机)

1，正则表达式:
通俗理解：
可以看成一个符号序列，中间含若干确定运算符；最基础的正则表达式就是字符；每个正则表达式唯一对应一个该正则表达式表达的语言，语言指的是以字符串序列为元素的确定集合；正则表达式的复合对应的语言集合的复合。
因此正则表达式在数学上可以看成是一系列集合运算；每个正则表达式就对应唯一一个集合，正则表达式的运算对应集合的运算，集合运算的结果仍然是集合

下文中用表示正则表达式对应的语言。

定义:
1)给定两个字符串则表示两者前后相连所得字符串;
2)如果是一个字符串序列的集合,也是一个字符串序列的集合，则 表示中任意一个字符串后接中任意一个字符串所得的集合
3)是一个字符串序列组成的集合，则(共i个S),当i=0时，定义为（空串）
4) : =

正则表达式官方定义:

1. 是一个正则表达式，
2. 给定符号集S,则S中每个元素x都是一个正则表达式，其对应语言为
   3)如果是正则表达式，则也是正则表达式，且
3. 如果是两个正则表达式；则
   是一个正则表达式，
   4)是一个正则表达式，
   5)是一个正则表达式，表示语言

可以用以正则表达式定义的语言叫做正则集合

2,正则表达式的抽象语法树
通俗解释: 由于正则表达式只包含2元和1元运算符，因此正则表达式可以表示为一棵树的形状
举例: (a|b)*abb 的抽象语法树为:

                _
             /       \         
           _         b
         /    \
       _      b
     /    \
    *     a
    |
    (|)
   /   \
 a      b

其中用 _ 表示两个正则表达式连接

3,NFA:
通俗解释：可以看成一个不含重边的有向图，图的有向边上关联着符号，同一个节点发出的多条边上可能关联相同的符号；
4，DFA:
基本同上，不过同一个节点发出的多条边上的符号都不相同

下面基于以上概念快速实现词法分析器:
一个DFA基本上等价于一个词法分析器了，而输入的词法单元可以对应为一门语言，也就对应到一个正则表达式；

因此，实现词法分析器的过程，也就是：
根据正则表达式 构建 DFA的过程，方法为:
正则表达式-> 抽象语法树-> NFA->DFA

1,正则表达式 -> 抽象语法树
这一步基本没什么难度，手写都可以，略去

2,抽象语法树->NFA
给抽象语法树的所有非叶子节点标上数字（随意标，不重复即可，不过一般从1,递增标）这些数字称为节点的位置，可同时也 称为节点上符号的位置（一个符号允许对应多个位置）
计算 每个节点的三个参数:
nullable, firstpos, lastpos ,
和每个位置 的 followpos
定义：
nullable(n) :是一个bool值，当且仅当 以n为根的子树对应的正则表达式的语言中 包含
firstpos(n): 是一个位置集合，一个位置属于该集合 当且仅当 以n为根的子树对应正则表达式的语言中存在一个符号串满足其首字母 按照这颗树解析时 刚好解析到这个位置；
lastpos(n): 位置集合 ，一个位置属于该集合 当且仅当 n为根的子树对应的正则表达式的语言中存在一个符号串 满足其尾字母 按照这颗树解析时 刚好解析到这个位置；
followpos(p): 是一个和位置p相关的位置集合。 一个位置q属于该集合当且仅当 L中的某个川 按照抽象语法树解析时，和某个匹配而 和匹配
算法：
每种类型对应的 nullabel 值 和 firstpos值 分别为:
叶子节点: true ,
位置为i的叶子节点: false , {i}
or节点: ,
cat-节点 : ,

start-节点:
由对称性容易推出 lastpos的公式，略过;
followpos计算法则如下:
1,如果n是 cat节点，左右子节点为,则中每个位置 ,中所有都位于 中
2,如果是节点，并且是中的一个位置，中的所有位置都位于 中

按照以上方法，计算出nullabel,firstpos,lastpos,followpos之后，可以用一个有向图 来表示 followpos, 每个位置对应图中一个节点，位置i到位置j 存在一条有限边当且仅当 j在followpos(i)中，
然后做三件事:
1把该图firstpos所有位置设为 开始状态
2每条i到j的有向边上添加位置i上的符号
3 把和结尾#关联的位置作为接受状态
至此，得到 NFA

3，NFA -> DFA
之后利用以下伪代码算法就可以计算出 DFA了：
初始化Dstates, 使之只包含未标记状态 firstpos(n_0)$ n_0为抽象语法树根节点
while( Dstates 中存在未标记的状态S){
标记S,
for( 每个输入符号a){
U :=S中和a对应的所有位置p的followpos(p)的并集 （和a对应的意思NFA中该位置的节点有一个用a标记的发出边）
if(U不在Dstates中）将U作为未标记态加入Dstates;
Dtran[S,a] = U;
}
}
注：其中Dran的就是待求DFA的状态边转移关系，也就是状态S通过标记了a的有向边转换到 U;

之后，还有一些优化减少DFA节点数目，这里略过；

至此，我们快速的实现了一个词法分析器。