概念

词法分析

词法分析是编译的第一阶段.词法分析主要任务是读入输入字符,产生记号(token)序列,提交给语法分析使用.
由于这种交互模式,词法分析器可以作为语法分析器的子程序或协作程序.语法分析器每次调用词法分析器持续读入字符,直到识别出下一个记号.

词法分析除了产生记号,也收集记号相关的信息作为记号的属性(比如数字的值,标识符对应的字符串).记号影响语法分析,记号的属性影响记号的翻译.属性一般存储在符号表中.

记号、模式、词素

词素是源程序的字符序列

模式是描述源程序中表示特定记号的词素集合的规则.

每个符合某模式的词素经词法分析后产生对应的记号.

记号的描述

字母表: 有限符号的集合
语言是给定字母表上任意字符串的集合.

正规表达式 Regular Expressions

正规表达式表示的语言叫做正规集.

非正规集

正规表达式描述能力有限,其不能描述均衡或嵌套结构,如具有配对括号的符号串集合.
正规表达式只能表示固定次数的重复或给定结构的没有指定次数的重复.

实现

接下来我们要完成对一个给定的正规表达式r的识别器的构造.

有穷自动机

概念

语言的识别器是一个程序,它以字符串x作为输入,输出true(接受)或false来表示x是否是语言的句子.

不确定的有穷自动机(NFA):

NFA可以由带标记的有向图(状态转换图),转换表表示.
F(T,a)=S:在T状态时,如果当前输入字符是a,可以转换到S状态(对于NFA来说,这里的S可能是一个状态集合)
当且仅当对应的转换图中存在从开始状态到某个接受状态的路径,使得该路径的边上的标记恰好连成字符串x时,NFA接受字符串x.

确定的有穷自动机(DFA)是特殊的NFA:

也就是对于当前正在识别的字符a,当前状态有唯一的转换,这非常适合计算机的模拟.

模拟DFA

算法: 持续读入字符并根据当前输入字符进行状态转换(“对于当前正在识别的字符a,当前状态有唯一的转换”),当输入结束,检查当前状态是否为一个接受状态.

有了DFA的模拟算法,现在只需要构造r的DFA表示.

从正规表达式到NFA

然而更容易的方式是从正规表达式r先构造出一个NFA.

Thompson构造法

对于字符表中的每个符号a(包括ε),构造一个如下的NFA.

接下来要做的便是根据正规表达式r来”组合”之前产生的NFA.
实际就是改变之前各NFA初始状态和接受状态,并增加一些结点和有向边,从而”组合”成r的NFA.

这样产生的NFA有以下的性质:

从NFA到DFA

其实就是消除ε转换(目标1)和对同一输入符号的多种转换(目标2).

子集构造算法

分析一下这个算法是怎么实现这两个目标的.

通过ε-closure()来合并只通过ε转换可以达到的状态为一个状态集,这个状态集是该算法操作的基本单位(目标1).
对于某个状态T对某个特定字符a的一种或多种(对于转换的结果而言)转换关系F(T,a),产生一个新的状态(这个状态是NFA中F(T,a)的所有输出状态的集合).之后再根据该状态集合里的每个状态在NFA中的转换关系得到状态集合之间的转换关系(目标2).

其实,两个目标都是通过将状态合并为状态集合的方式来实现的.

NFA的双堆栈模拟

至此我们已经完成了对正规表达式r的识别器的构造.而实际上,NFA也是可以直接模拟的.

算法描述

回想一下我们是怎么实现NFA到DFA转换的那两个目标,可以发现该模拟算法实质上是在运行中构造DFA.

算法实现

我们要实现的结构有两个,当前状态集合,要转换到的状态集合.注意这里与DFA模拟时不同,DFA中状态集合是实现为一个新的状态,有状态集合之间独立的转换关系(新的转换表),而模拟NFA时我们只具有单个状态之间的转换关系.

这两个结构可以以两个栈的形式实现.一个栈表示当前状态集合,一个栈表示要转换到的状态集合.压入所有在ε-closure(当前状态)的输出状态.转换时遍历当前状态集合的每一个状态并进行状态转换,压入结果到另一个栈中.清空当前状态集合,两个栈交换身份.

最长词素匹配

常见有如下的实现:如果有多个模式匹配成功,选择最长词素匹配的模式.
当当前状态集合中含有接受状态时,记录当前输入指针的位置和该接受状态后继续识别,直到NFA进入终止(无法状态转换或输入结束),恢复到最近一次保存的输入指针位置,以该接受状态为结果.

基于DFA的模式匹配器的优化

NFA的重要状态

如果一个NFA的状态有一个标记为非ε的出边,那么该状态为重要状态.
如果两个子集的重要状态相同且两者同时包含或不包含NFA的接受状态,那么这两个子集可被认为是等同的.

The constructed NFA has only one accepting state, but this state, having
no out-transitions, is not an imp ortant state. By concatenating a unique right
endmarker # to a regular expression r , we give the accepting state for r a
transition on #, making it an imp ortant state of the NFA for (r )#. In other
words, by using the augmented regular expression (r )#, we can forget ab out
accepting states as the subset construction pro ceeds; when the construction is
complete, any state with a transition on # must b e an accepting state.

Functions Computed From the Syntax Tree

Compute

为了直接从正规表达式r构造DFA,需要从语法树中计算这四个函数.Each denition refers to the syntax tree for a particular augmented regular expression (r )#

直白点说,nullable就是该位置代表的字符串是否可以为空(ε).
firstpos就是该节点所代表的字符串可能的开始位置集合.
lastpos就是该节点所代表的字符串可能的结束位置集合.
followpos就是可能的紧跟着该位置的位置集合.

最后我们需要的其实只有follow集,根据求出的follow集可以得到这样一个没有ε的NFA

TO DFA

其实感觉和之前的思想是差不多的,状态->状态集合.
使用根节点的first集合并初始状态,以是否有#转换来合并接受状态.其他状态由followpos来合并.
差别就在于之前是通过NFA的转换关系来合并的,这里是直接通过计算follow集来合并的(其实感觉是一回事).

最小化DFA的状态数

每一个正规集都可以由一个状态最少的DFA识别,这个DFA是唯一的.

表压缩算法