2021-03-29 编译原理简介(一词法分析)

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

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

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

下文中用 $L(x)$ 表示正则表达式 $x$ 对应的语言。

定义:
1)给定两个字符串 $s_1,s_2$ 则 $s_1s_2$ 表示两者前后相连所得字符串;
2)如果 $S_1$ 是一个字符串序列的集合, $S_2$ 也是一个字符串序列的集合，则 $S_1S_2$ 表示 $S_1$ 中任意一个字符串后接 $S_2$ 中任意一个字符串所得的集合
3) $S$ 是一个字符串序列组成的集合，则 $S^i:= SSS...$ (共i个S),当i=0时， $S^0$ 定义为 $\epsilon$ （空串）
4) $S^*$ : = $S^0 \cup S \cup S^2 \cup S^3...$

正则表达式官方定义:

$\epsilon$ 是一个正则表达式， $L(\epsilon) = \emptyset$
给定符号集S,则S中每个元素x都是一个正则表达式，其对应语言为 $L(x)= {x}$
3)如果 $a$ 是正则表达式，则 $(a)$ 也是正则表达式，且 $L((a))=L(a)$
如果 $(a),(b)$ 是两个正则表达式；则
$(a)|(b)$ 是一个正则表达式， $L((a)|(b))= L(a)\cup L(b)$
4) $(a)(b)$ 是一个正则表达式， $L((a)(b)) = L(a)L(b)$
5) $(r)^*$ 是一个正则表达式，表示语言 $L(r)^*$

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

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

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

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

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

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

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

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

2,抽象语法树->NFA
给抽象语法树的所有非 $\epsilon$ 叶子节点标上数字（随意标，不重复即可，不过一般从1,递增标）这些数字称为节点的位置，可同时也称为节点上符号的位置（一个符号允许对应多个位置）
计算每个节点的三个参数:
nullable, firstpos, lastpos ,
和每个位置的 followpos
定义：
nullable(n) :是一个bool值，当且仅当以n为根的子树对应的正则表达式的语言中包含 $\epsilon$
firstpos(n): 是一个位置集合，一个位置属于该集合当且仅当以n为根的子树对应正则表达式的语言中存在一个符号串满足其首字母按照这颗树解析时刚好解析到这个位置；
lastpos(n): 位置集合，一个位置属于该集合当且仅当 n为根的子树对应的正则表达式的语言中存在一个符号串满足其尾字母按照这颗树解析时刚好解析到这个位置；
followpos(p): 是一个和位置p相关的位置集合。一个位置q属于该集合当且仅当 L中的某个川 $x=a_1a_2...a_n$ 按照抽象语法树解析时， $p$ 和某个 $a_i$ 匹配而 $q$ 和 $a_{i+1}$ 匹配
算法：
每种类型对应的 nullabel 值和 firstpos值分别为:
$\epsilon$ 叶子节点: true , $\emptyset$
位置为i的叶子节点: false , {i}
or节点 $n=c_1|c_2$ : $nullable(c_1) 或者 nullabel(c_2)$ , $firstpos(c_1) \cup firstpos(c_2)$
cat-节点 $n=c_1c_2$ : $nullable(c_1) \quad and\quad nullable(c_2)$ ,
$if(nullabel(c_1)) firstpos(c_1)\cup firstpos(c_2) else firstpos(c_1)$
start-节点 $n=c^*$ : $true, firstpos(c)$
由对称性容易推出 lastpos的公式，略过;
followpos计算法则如下:
1,如果n是 cat节点，左右子节点为 $c_1,c_2$ ,则 $lastpos(c_1)$ 中每个位置 $i$ , $firstpos(c_2)$ 中所有都位于 $followpos(i)$ 中
2,如果 $n$ 是 $start$ 节点，并且 $i$ 是 $lastpos(n)$ 中的一个位置， $firstpos(n)$ 中的所有位置都位于 $followpos(i)$ 中

按照以上方法，计算出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节点数目，这里略过；

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

2021-03-29 编译原理简介(一 词法分析)

推荐阅读更多精彩内容

2021-03-29 编译原理简介(一词法分析)