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

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

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

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

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

定义:
1)给定两个字符串s_1,s_2s_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...

正则表达式官方定义:

  1. \epsilon是一个正则表达式,L(\epsilon) = \emptyset
  2. 给定符号集S,则S中每个元素x都是一个正则表达式,其对应语言为L(x)= {x}
    3)如果a是正则表达式,则(a)也是正则表达式,且L((a))=L(a)
  3. 如果(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匹配而 qa_{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,如果nstart节点,并且ilastpos(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节点数目,这里略过;

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容