思路
本题可以看作是一个小型的编译原理实践。由于题目保证正则表达式正确,因此可以不用进行语义检查;同时每个字符可以看作单独的token,因此也不用做词法分析。所以剩下的步骤就是:
- 语法解析:将正则表达式解析为AST;
- 代码生成:将AST翻译成DFA。
字符串匹配的部分即为DFA上的遍历。
语法解析
为了建立 AST 先定义 AST 节点,rust 中可以使用枚举来定义 AST 节点。在 C++ 中可以使用建立虚基类Node
,然后子类继承的模式。
1 | enum Node { |
为了进行语法解析需要写出解析的 CFG,根据题意可写出如下所示的 CFG:
1 | Expr : Expr '|' Term |
(下面将各非终止符均以大写首字母代替)
然后就是根据 CFG 进行解析,有两种办法:
LL(1)解析
要使用递归下降算法进行 LL 预测解析,需要对原 CFG 进行左递归消除与左约分,结果如下:
1 | E : T Ex |
完成后可以计算得到如下解析表:
‘|’ | ‘*’ | ‘+’ | ‘(‘ | ‘)’ | [a-z] | $ | |
---|---|---|---|---|---|---|---|
E | T Ex |
T Ex |
|||||
Ex | OR T Ex |
eps | eps | ||||
T | C Tx |
C Tx |
|||||
Tx | eps | C Tx |
eps | C Tx |
eps | ||
C | A Cx |
A Cx |
|||||
Cx | eps | * |
+ |
eps | eps | eps | eps |
A | ( E ) |
[a-z] |
表中行头为当前待解析的非终止符;列头为预测字符,其中$
代表输入结束;格内即为应当使用的产生式,其中 eps 代表此时应使用空产生式。
通过解析表可以发现每对非终止符与预测字符最多仅预测一个产生式,因此该语法为 LL(1) 语法,可以通过递归下降算法进行 LL(1) 预测解析。
根据解析表可以使用语法制导翻译对表达式进行解析并翻译成 AST,即每次对非终止符解析完成后处理并返回其所代表的 AST 节点。
由于Ex
, Tx
, Cx
较为特殊,可以将其与E
, T
, C
的解析合并,以减少递归。
代码中的'#'
字符当作小写字母,加入该字符的目的是方便后面 DFA 的生成。
1 | struct Parser { |
SLR解析
使用LR进行解析需要添加一条产生式S -> E
,然后画出可行前缀的 DFA,如图所示:
其中的小写a
为小写字母。然后需要计算各个非终止符的 first set 与 follow set,如下所示:
first | follow | |
---|---|---|
S | a ( |
$ |
E | a ( |
$ OR ) |
T | a ( |
$ OR ( a ) |
C | a ( |
$ OR ( a ) |
A | a ( |
$ OR ( a ) * + |
可以看出,若根据SLR解析的规则,即若预测符为a
:
- 移位:当前状态中含有
X -> Y.aZ
项时; - 规约:当前状态中含有
X -> Y.
项,且a
属于X
的 follow set 时。
当前规则不会产生冲突,因此该语法为 SLR 语法。
进行 SLR 解析时,需要一个栈和一个队列。移位时队列出队向栈中入栈,并计算当前栈顶所在的 DFA 节点;规约时将元素出栈,进行语义动作生成 AST 节点,并将其保存到新的入栈元素当中,同时计算当前栈顶所在的 DFA 节点。
使用 rust 编写时 DFA 节点与 CFG 符号均可使用枚举实现,C++ 中可以使用数字代替或使用 C 中的枚举。
1 | enum Terminal { |
(可以看出这里面的模板代码是又臭又长,所以LR解析的代码还是交给程序去生成罢)
生成 DFA
在生成 DFA 之前需要先生成一个 NFA,然后再将 NFA 转化为 DFA。
生成 NFA 的过程相当于在 AST 上做树上 DP,对于每类 AST 节点有如下的生成规则:
- 字符节点:对于单个字符
a
,生成如下的 NFA : - 连接节点:对于表达式
XY
,生成如下的 NFA : - 或节点:对于表达式
X | Y
,生成如下的 NFA : - 闭包节点:对于表达式
X*
,生成如下的 NFA(eps 表示接受空串): - 正闭包节点:对于表达式
X+
,生成如下的 NFA :
从中可以看出,生成的 NFA 节点个数为 AST 的叶子数量,也即字符节点的数量,加上一个接受节点。所以字符节点的编号即代表了其 NFA 节点。
生成 NFA 时,对于每个节点,需要计算如下参数:
nullable
:当前的 NFA 是否接受空串(下面简写为nu
);- $\mathrm{first}$:当前 NFA 的起始节点集合(下面简写为小写$f$);
- $\mathrm{last}$:当前 NFA 的结束节点集合,即连接到接受节点的节点集合(下面简写为小写$l$)。
同时每次需要更新一个全局数组$\mathrm{Follow}_i$,即每个 NFA 节点的后继节点集合(下面简写为大写$F$),并记录下节点编号对应的字符节点代表的字符。
对于集合的表示,由于题目中说明了长度不会超过100,因此可以直接使用 bitset 实现。
rust 需要手写 bitset,C++ 直接使用 STL 即可。
1 |
|
对于每个 AST 节点的计算规则如下:
- 字符节点
CHR(id, ch)
:nu = false
,$f$与$l$为仅包含该节点编号id
的集合; - 连接节点
CAT(L, R)
:nu = nu(L) && nu(R)
,若nu(L) = true
,则$f = f_L \cup f_R $,否则$f = f_L$;同理若nu(R) = true
,则$l = l_L \cup l_R $,否则$l = l_R$,同时令$\forall i \in l_L$,$F_i \leftarrow F_i \cup f_R$; - 或节点
LOR(L, R)
:nu = nu(L) || nu(R)
,$f = f_L \cup f_R $,$l = l_L \cup l_R $; - 闭包节点
CLO(S)
:nu = true
,$f = f_S$,$l = l_S$,同时令$\forall i \in l_S$,$F_i \leftarrow F_i \cup f_S$; - 正闭包节点
PCL(S)
:除了nu = nu(S)
外,其余均与闭包节点一致。
1 | fn analyze_node(proot: &Node, chpos: &mut [char; 128], flpos: &mut [Bitset; 128]) |
遍历完整个 AST 后即得到了当前 NFA 的起始节点集合,后继数组$F_i$即为一个不包含$\epsilon$转移的 NFA,依次以 NFA 节点的集合为节点即可将 NFA 转化为 DFA:
至于接受状态,可以在原表达式后以连接形式添加一个字符,则返回的结束节点集合即为仅包含该字符的集合,可视为原表达式的接受节点。该代码中添加的即为'#'
。
1 | struct DFA { |
匹配
正则匹配的过程就是在 DFA 上转移的过程:
1 | impl DFA { |
主函数循环调用即可。
1 | fn get_line() -> Option<String> { |
后记
因为这道题看了几个月的编译原理……
再也不手写 LR 解析了……