(loj118) 正则表达式

题目链接

思路

本题可以看作是一个小型的编译原理实践。由于题目保证正则表达式正确，因此可以不用进行语义检查；同时每个字符可以看作单独的 token，因此也不用做词法分析。所以剩下的步骤就是：

• 语法解析：将正则表达式解析为 AST；
• 代码生成：将 AST 翻译成 DFA。

字符串匹配的部分即为 DFA 上的遍历。

语法解析

为了建立 AST 先定义 AST 节点，rust 中可以使用枚举来定义 AST 节点。在 C++ 中可以使用建立虚基类 Node，然后子类继承的模式。

enum Node {
    CAT {       //conCATenate
        ls: Box<Node>,
        rs: Box<Node>
    },
    LOR {       //Logical OR
        ls: Box<Node>,
        rs: Box<Node>
    },
    CLO {       //CLOsure
        sn: Box<Node>
    },
    PCL {       //Plus CLosure
        sn: Box<Node>
    },
    CHR {       //CHaRacter
        id: usize,  //需要记录id用于后续生成DFA
        ch: char
    }
}
impl Node {
    fn new_cat(ls: Box<Node>, rs: Box<Node>) -> Box<Node> {
        Box::new(Node::CAT {ls, rs})
    }
    fn new_lor(ls: Box<Node>, rs: Box<Node>) -> Box<Node> {
        Box::new(Node::LOR {ls, rs})
    }
    fn new_clo(sn: Box<Node>) -> Box<Node> {
        Box::new(Node::CLO {sn})
    }
    fn new_pcl(sn: Box<Node>) -> Box<Node> {
        Box::new(Node::PCL {sn})
    }
    fn new_chr(id: usize, ch: char) -> Box<Node> {
        Box::new(Node::CHR {id, ch})
    }
    fn build(str: &str) -> Box<Node> {
        Parser::from_str(str).parse()
    }
}

为了进行语法解析需要写出解析的 CFG，根据题意可写出如下所示的 CFG：

Expr    :   Expr '|' Term
        |   Term
Term    :   Term Clos
        |   Clos
Clos    :   Atom '*'
        |   Atom '+'
        |   Atom
Atom    :   [a-z]
        |   '(' Expr ')'

（下面将各非终止符均以大写首字母代替）

然后就是根据 CFG 进行解析，有两种办法：

LL (1) 解析

要使用递归下降算法进行 LL 预测解析，需要对原 CFG 进行左递归消除与左约分，结果如下：

E   :   T Ex
Ex  :   '|' T Ex
    |   /*empty*/
T   :   C Tx
Tx  :   C Tx
    |   /*empty*/
C   :   A Cx
Cx  :   '*'
    |   '+'
    |   /*empty*/
A   :   [a-z]
    |   '(' E ')'

完成后可以计算得到如下解析表：

	‘|’	’*’	‘+’	‘(’	‘)’	[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 的生成。

struct Parser {
    rest_char: VecDeque<char>,  //输入字符流
    id_cnt: usize               //id计数器
}
impl Parser {
    fn from_str(str: &str) -> Self {
        let mut queue: VecDeque<char> = VecDeque::new();
        for c in str.chars() {
            queue.push_back(c)
        }
        Self { rest_char: queue, id_cnt: 0 }
    }
    fn parse_expr(&mut self) -> Box<Node> {
        let mut tmp = self.parse_term();    //返回节点
        loop {      //可以认为loop内即为非终止符Ex
            let och = self.rest_char.front();
            if let Some(&ch) = och {
                if ch == '|' {
                    self.rest_char.pop_front();
                    tmp = Node::new_lor(tmp, self.parse_term());
                } else {
                    return tmp;
                }
            } else {
                return tmp;
            }
        }
    }
    fn parse_term(&mut self) -> Box<Node> {
        let mut tmp = self.parse_clos();
        loop {      //同上，可以认为loop内为Tx
            let och = self.rest_char.front();
            if let Some(&ch) = och {
                if ch == '(' || ch == '#' || ch.is_lowercase() {
                    tmp = Node::new_cat(tmp, self.parse_clos())
                } else {
                    return tmp;
                }
            } else {
                return tmp;
            }
        }
    }
    fn parse_clos(&mut self) -> Box<Node> {
        let tmp = self.parse_atom();
        let ch = self.rest_char.front();
        match ch {      //Cx
            Some(&'*') => {
                self.rest_char.pop_front();
                Node::new_clo(tmp)
            }
            Some(&'+') => {
                self.rest_char.pop_front();
                Node::new_pcl(tmp)
            }
            _ => tmp,
        }
    }
    fn parse_atom(&mut self) -> Box<Node> {
        let ch = self.rest_char.front();
        match ch {
            Some(&'(') => {     //( E )
                self.rest_char.pop_front();
                let ret = self.parse_expr();
                assert_eq!(self.rest_char.pop_front(), Some(')'));
                ret
            }
            Some(&t) if t.is_lowercase() || t == '#' => {   //[a-z]
                let ret = Node::new_chr(self.id_cnt, t);
                self.id_cnt += 1;
                self.rest_char.pop_front();
                ret
            }
            _ => {
                panic!("syntax error")
            }
        }
    }
    
    fn parse(mut self) -> Box<Node> {
        self.parse_expr()
    }
}

SLR 解析

使用 LR 进行解析需要添加一条产生式 S -> E，然后画出可行前缀的 DFA，如图所示：

LR_Parse_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 中的枚举。

enum Terminal {
    E, T, C, A,
    OPR, CPR,       //open & close parenthesis
    BAR, STR, PLS,  //'|'
    ALP {ch: char, id: usize},
    PLH             //Placeholder
}

#[derive(Clone,Debug)]
enum State {
    START,
    S1,
    E12, E13,
    E21,
    T12,
    T21,
    C1, C12, C22,
    A11,
    A21, A22, A23,
}
impl State {
//---------------------------------------------------------------
//-----------------------------DFA状态转移------------------------
//---------------------------------------------------------------
    fn trans(&self, t: &Terminal) -> Self {
        match self {
            Self::START => {
                match t {
                    Terminal::E => Self::S1,
                    Terminal::T => Self::E21,
                    Terminal::C => Self::T21,
                    Terminal::A => Self::C1,
                    Terminal::ALP{ch:_, id:_} => Self::A11,
                    Terminal::OPR => Self::A21,
                    _ => panic!()
                }
            }
            Self::S1 => {
                match t {
                    Terminal::BAR => Self::E12,
                    _ => panic!()
                }
            }
            Self::E12 => {
                match t {
                    Terminal::T => Self::E13,
                    Terminal::C => Self::T21,
                    Terminal::A => Self::C1,
                    Terminal::ALP{ch:_, id:_} => Self::A11,
                    Terminal::OPR => Self::A21,
                    _ => panic!()
                }
            }
            Self::E13 => {
                match t {
                    Terminal::C => Self::T12,
                    Terminal::A => Self::C1,
                    Terminal::ALP{ch:_, id:_} => Self::A11,
                    Terminal::OPR => Self::A21,
                    _ => panic!()
                }
            }
            Self::E21 => {
                match t {
                    Terminal::C => Self::T12,
                    Terminal::A => Self::C1,
                    Terminal::ALP{ch:_, id:_} => Self::A11,
                    Terminal::OPR => Self::A21,
                    _ => panic!()
                }
            }
            Self::C1 => {
                match t {
                    Terminal::STR => Self::C12,
                    Terminal::PLS => Self::C22,
                    _ => panic!()
                }
            }
            Self::A21 => {
                match t {
                    Terminal::E => Self::A22,
                    Terminal::T => Self::E21,
                    Terminal::C => Self::T21,
                    Terminal::A => Self::C1,
                    Terminal::ALP{ch:_, id:_} => Self::A11,
                    Terminal::OPR => Self::A21,
                    _ => panic!()
                }
            }
            Self::A22 => {
                match t {
                    Terminal::CPR => Self::A23,
                    Terminal::BAR => Self::E12,
                    _ => panic!()
                }
            }
            _ => panic!()
        }
    }
//---------------------------------------------------------------
//---------------------------------------------------------------
//---------------------------------------------------------------
}

struct StackItem {
    t: Terminal,            //当前符号
    s: State,               //当前DFA状态
    r: Option<Box<Node>>    //返回AST节点
}

struct Parser {
    stack: Vec<StackItem>,          //栈
    rest_term: VecDeque<Terminal>   //队列
}
impl Parser {
    fn from_str(str: &str) -> Self {
        let mut queue: VecDeque<Terminal> = VecDeque::new();
        let mut id_cnt = 0;
        for c in str.chars() {  //所有字符入队
            match c {           //这里可以看作是词法分析
                '(' => queue.push_back(Terminal::OPR),
                ')' => queue.push_back(Terminal::CPR),
                '|' => queue.push_back(Terminal::BAR),
                '*' => queue.push_back(Terminal::STR),
                '+' => queue.push_back(Terminal::PLS),
                ch => {
                    if ch.is_ascii_lowercase() || ch == '#' {
                        queue.push_back(Terminal::ALP{ch, id: id_cnt});
                        id_cnt += 1;
                    } else {
                        panic!()
                    }
                }
            }
        }
        Self {
            stack: Vec::from([StackItem {   //放入一个占位符方便计算状态
                t: Terminal::PLH, s: State::START, r: None
            }]),
            rest_term: queue
        }
    }
    fn trans_top(&self, t: &Terminal) -> State {    //计算状态
        self.stack.last().unwrap().s.trans(t)
    }
//---------------------------------------------------------------
//------------------------Follow set-----------------------------
//---------------------------------------------------------------
    fn try_reduce(&mut self) -> bool {
        let t_next = self.rest_term.front();
        let s = self.stack.last().unwrap().s.clone();
        match s {
            State::E13 => {
                match t_next {
                    None |
                    Some(Terminal::BAR) |
                    Some(Terminal::CPR) => {
                        let si = self.reduce_e1();
                        self.stack.push(si);
                        true
                    }
                    _ => false
                }
            }
            State::E21 => {
                match t_next {
                    None |
                    Some(Terminal::BAR) |
                    Some(Terminal::CPR) => {
                        let si = self.reduce_e2();
                        self.stack.push(si);
                        true
                    }
                    _ => false
                }
            }
            State::T12 => {
                match t_next {
                    None |
                    Some(Terminal::BAR) |
                    Some(Terminal::CPR) |
                    Some(Terminal::OPR) |
                    Some(Terminal::ALP{ch:_, id:_}) => {
                        let si = self.reduce_t1();
                        self.stack.push(si);
                        true
                    }
                    _ => false
                }
            }
            State::T21 => {
                match t_next {
                    None |
                    Some(Terminal::BAR) |
                    Some(Terminal::CPR) |
                    Some(Terminal::OPR) |
                    Some(Terminal::ALP{ch:_, id:_}) => {
                        let si = self.reduce_t2();
                        self.stack.push(si);
                        true
                    }
                    _ => false
                }
            }
            State::C12 => {
                match t_next {
                    None |
                    Some(Terminal::BAR) |
                    Some(Terminal::CPR) |
                    Some(Terminal::OPR) |
                    Some(Terminal::ALP{ch:_, id:_}) => {
                        let si = self.reduce_c1();
                        self.stack.push(si);
                        true
                    }
                    _ => false
                }
            }
            State::C22 => {
                match t_next {
                    None |
                    Some(Terminal::BAR) |
                    Some(Terminal::CPR) |
                    Some(Terminal::OPR) |
                    Some(Terminal::ALP{ch:_, id:_}) => {
                        let si = self.reduce_c2();
                        self.stack.push(si);
                        true
                    }
                    _ => false
                }
            }
            State::C1 => {
                match t_next {
                    None |
                    Some(Terminal::BAR) |
                    Some(Terminal::CPR) |
                    Some(Terminal::OPR) |
                    Some(Terminal::ALP{ch:_, id:_}) => {
                        let si = self.reduce_c3();
                        self.stack.push(si);
                        true
                    }
                    _ => false
                }
            }
            State::A11 => {
                match t_next {
                    None |
                    Some(Terminal::BAR) |
                    Some(Terminal::STR) |
                    Some(Terminal::PLS) |
                    Some(Terminal::CPR) |
                    Some(Terminal::OPR) |
                    Some(Terminal::ALP{ch:_, id:_}) => {
                        let si = self.reduce_a1();
                        self.stack.push(si);
                        true
                    }
                    _ => false
                }
            }
            State::A23 => {
                match t_next {
                    None |
                    Some(Terminal::BAR) |
                    Some(Terminal::STR) |
                    Some(Terminal::PLS) |
                    Some(Terminal::CPR) |
                    Some(Terminal::OPR) |
                    Some(Terminal::ALP{ch:_, id:_}) => {
                        let si = self.reduce_a2();
                        self.stack.push(si);
                        true
                    }
                    _ => false
                }
            }
            _ => false
        }
        
    }
//---------------------------------------------------------------
//---------------------------------------------------------------
//---------------------------------------------------------------
    fn get_reduce_si(&self, t: Terminal, r: Option<Box<Node>>) -> StackItem {
        let s = self.trans_top(&t);
        StackItem { t, s, r }
    }
//---------------------------------------------------------------
//-------------------------规约操作-------------------------------
//---------------------------------------------------------------
    fn reduce_e1(&mut self) -> StackItem {
        let si1 = self.stack.pop().unwrap();
        self.stack.pop();
        let si2 = self.stack.pop().unwrap();
        self.get_reduce_si(
            Terminal::E,
            Some(Node::new_lor(
                si2.r.unwrap(), si1.r.unwrap()
            ))
        )
    }
    fn reduce_e2(&mut self) -> StackItem {
        let si = self.stack.pop().unwrap();
        self.get_reduce_si(
            Terminal::E,
            si.r
        )
    }
    fn reduce_t1(&mut self) -> StackItem {
        let si1 = self.stack.pop().unwrap();
        let si2 = self.stack.pop().unwrap();
        self.get_reduce_si(
            Terminal::T,
            Some(Node::new_cat(
                si2.r.unwrap(), si1.r.unwrap()
            ))
        )
    }
    fn reduce_t2(&mut self) -> StackItem {
        let si = self.stack.pop().unwrap();
        self.get_reduce_si(
            Terminal::T,
            si.r
        )
    }
    fn reduce_c1(&mut self) -> StackItem {
        self.stack.pop();
        let si = self.stack.pop().unwrap();
        self.get_reduce_si(
            Terminal::C,
            Some(Node::new_clo(si.r.unwrap()))
        )
    }
    fn reduce_c2(&mut self) -> StackItem {
        self.stack.pop();
        let si = self.stack.pop().unwrap();
        self.get_reduce_si(
            Terminal::C,
            Some(Node::new_pcl(si.r.unwrap()))
        )
    }
    fn reduce_c3(&mut self) -> StackItem {
        let si = self.stack.pop().unwrap();
        self.get_reduce_si(
            Terminal::C,
            si.r
        )
    }
    fn reduce_a1(&mut self) -> StackItem {
        let si = self.stack.pop().unwrap();
        if let Terminal::ALP{ch, id} = si.t {
            self.get_reduce_si(
                Terminal::A,
                Some(Node::new_chr(id, ch))
            )
        } else {
            panic!()
        }
    }
    fn reduce_a2(&mut self) -> StackItem {
        self.stack.pop();
        let si = self.stack.pop().unwrap();
        self.stack.pop();
        self.get_reduce_si(
            Terminal::A,
            si.r
        )
    }
//---------------------------------------------------------------
//---------------------------------------------------------------
//---------------------------------------------------------------

    fn parse(mut self) -> Box<Node> {
        while !self.rest_term.is_empty() {
            while self.try_reduce() {}      //尝试规约
            /* 移位 */
            let t = self.rest_term.pop_front().unwrap();
            let s = self.trans_top(&t);
            self.stack.push(StackItem {
                t, s, r: None
            });
            /*     */
        }
        while self.try_reduce() {}          //尝试规约
        let si_final = self.stack.last().unwrap();
        if let StackItem{       //接受条件
            t: Terminal::E,
            s: State::S1,
            r
        } = si_final {
            r.clone().unwrap()
        } else {
            panic!()
        }
    }
}

（可以看出这里面的模板代码是又臭又长，所以 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 即可。

#[derive(Hash, PartialEq, Eq, Clone, Copy, Debug)]
struct Bitset {
    st: [u64; 2],
}
impl BitAnd for Bitset {
    type Output = Self;
    #[inline]
    fn bitand(self, rhs: Self) -> Self {
        Self {
            st: [self.st[0] & rhs.st[0], self.st[1] & rhs.st[1]],
        }
    }
}
impl BitOr for Bitset {
    type Output = Self;
    #[inline]
    fn bitor(self, rhs: Self) -> Self {
        Self {
            st: [self.st[0] | rhs.st[0], self.st[1] | rhs.st[1]],
        }
    }
}
impl Bitset {
    fn new() -> Self {
        Self { st: [0; 2] }
    }
    #[inline]
    fn get(&self, idx: usize) -> bool {
        if idx < 64 {
            (self.st[0] & (1 << idx)) != 0
        } else {
            (self.st[1] & (1 << (idx - 64))) != 0
        }
    }
    #[inline]
    fn set(&mut self, idx: usize) {
        if idx < 64 {
            self.st[0] |= 1 << idx
        } else {
            self.st[1] |= 1 << (idx - 64)
        }
    }
    #[inline]
    fn empty(&self) -> bool {
        self.st[0] == 0 && self.st[1] == 0
    }
    fn any(&self) -> bool {
        !self.empty()
    }
}

对于每个 AST 节点的计算规则如下：

• 字符节点 CHR(id, ch)：nu = false，\(f\) 与 \(l\) 为仅包含该节点编号 id 的集合；
• 连接节点 CAT(L, R)：nu = nu(L) && nu(R)，若 nu(L) = true，则 $f = f_L f_R \(，否则 \)f = f_L\(；同理若 `nu (R) = true`，则 \)l = l_L l_R \(，否则 \)l = l_R\(，同时令 \)i l_L\(，\)F_i F_i f_R$；
• 或节点 LOR(L, R)：nu = nu(L) || nu(R)，$f = f_L f_R \(，\)l = l_L 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) 外，其余均与闭包节点一致。

fn analyze_node(proot: &Node, chpos: &mut [char; 128], flpos: &mut [Bitset; 128])
    //AST节点，字符映射，Follow_i (proot -> pointer of root)
    -> (bool, Bitset, Bitset) {     //nullable, first, last
    match proot {
        Node::CAT{ls, rs} => {
            let lret = Self::analyze_node(ls, chpos, flpos);
            let rret = Self::analyze_node(rs, chpos, flpos);
            for i in 0..=127 {
                if lret.2.get(i) {
                    flpos[i] = flpos[i] | rret.1;
                }
            }
            (
                lret.0 && rret.0,
                if lret.0 { lret.1 | rret.1 } else { lret.1 },
                if rret.0 { lret.2 | rret.2 } else { rret.2 },
            )
        }
        Node::LOR{ls, rs} => {
            let lret = Self::analyze_node(ls, chpos, flpos);
            let rret = Self::analyze_node(rs, chpos, flpos);
            (lret.0 || rret.0, lret.1 | rret.1, lret.2 | rret.2)
        }
        Node::CLO{sn} => {
            let sret = Self::analyze_node(sn, chpos, flpos);
            for i in 0..=127 {
                if sret.2.get(i) {
                    flpos[i] = flpos[i] | sret.1;
                }
            }
            (true, sret.1, sret.2)
        }
        Node::PCL{sn} => {
            let sret = Self::analyze_node(sn, chpos, flpos);
            for i in 0..=127 {
                if sret.2.get(i) {
                    flpos[i] = flpos[i] | sret.1;
                }
            }
            sret
        }
        Node::CHR{id, ch} => {
            chpos[*id] = *ch;
            let mut tmp = Bitset::new();
            tmp.set(*id);
            (false, tmp, tmp)
        }
    }
}

遍历完整个 AST 后即得到了当前 NFA 的起始节点集合，后继数组 \(F_i\) 即为一个不包含 \(\epsilon\) 转移的 NFA，依次以 NFA 节点的集合为节点即可将 NFA 转化为 DFA：

至于接受状态，可以在原表达式后以连接形式添加一个字符，则返回的结束节点集合即为仅包含该字符的集合，可视为原表达式的接受节点。该代码中添加的即为'#'。

struct DFA {
    start_state: Bitset,    //起始状态
    receive_chk: Bitset,    //接受状态
    trans_gph: HashMap<Bitset, [Bitset; 27]>,   //DFA转移
}
impl DFA {
    fn enc(ch: char) -> usize {     //字符编码
        if ch == '#' {
            26
        } else {
            ch as usize - 97
        }
    }
    fn from_pnode(proot: Box<Node>) -> Self {   //pnode -> pointer of node
        let mut chpos = [' '; 128];     //字符映射
        let mut flpos = [Bitset::new(); 128];   //Follow_i
        let (_, start_state, receive_chk) = Self::analyze_node(proot.as_ref(), &mut chpos, &mut flpos);
        let mut trans_gph: HashMap<Bitset, [Bitset; 27]> = HashMap::new();      //DFA转移
        let mut q = VecDeque::from([start_state]);
        while !q.is_empty() {       //BFS
            let nst = q.front().unwrap().clone();
            q.pop_front();
            let mut stvec = [Bitset::new(); 27];
            for i in 0..=127 {
                if nst.get(i) {
                    let encp = Self::enc(chpos[i]);
                    stvec[encp] = stvec[encp] | flpos[i];
                }
            }
            trans_gph.insert(nst, stvec);
            for i in 0..27 {
                if !trans_gph.contains_key(&stvec[i]) {
                    q.push_back(stvec[i]);
                }
            }
        }
        Self {
            start_state,
            receive_chk,
            trans_gph,
        }
    }
    fn from_string(str: &str) -> Self {
        let pr = Node::build(str);  //生成 AST
        Self::from_pnode(pr)        //生成 DFA
    }
}

匹配

正则匹配的过程就是在 DFA 上转移的过程：

impl DFA {
    fn reg_match(&self, str: &str) -> bool {
        let mut cur = self.start_state;
        for ch in str.chars() {
            cur = self.trans_gph[&cur][Self::enc(ch)];
            if cur.empty() {
                return false;
            }
        }
        (cur & self.receive_chk).any()
    }
}
fn reg_match(str: &str, reg: &str) -> bool {
    DFA::from_string(format!("({reg})#").as_str()).reg_match(str)
}   //添加特殊字符

主函数循环调用即可。

fn get_line() -> Option<String> {
    let mut line = String::new();
    match std::io::stdin().read_line(&mut line) {
        Ok(0) => None,
        Ok(_) => Some(line.trim().to_string()),
        Err(_) => None
    }
}
fn main() {
    loop {
        let str_reg = get_line();
        if let None = str_reg { break }
        let str_chk = get_line().unwrap();
        println!("{}", if reg_match(&str_chk, &(str_reg.unwrap())) { "Yes" } else { "No" });
    }
}

后记

因为这道题看了几个月的编译原理……

再也不手写 LR 解析了……