实验四:语法分析树转 ε-NFA¶
背景¶
我们学习过了正规表达式转为 ε-NFA 的方法(Thompson 构造法)。在本课程的实验中,我们将正规表达式转为 ε-NFA 的过程拆为两个阶段:基于正规表达式转化成的波兰式得到语法分析树;根据正规表达式的语法分析树构造等价的 ε-NFA。
回顾一下我们语法分析树基于的文法:
S → +SS
S → -SS
S → *S
∀a∈{ε}∪Σ, S → a (注意此处的ε应当是一个常量而不是空串)
这四种语法分析树上的结构对应的就是 Thompson 构造法的四种构造方法:E+F,EF,E*,a或ε。我们可以通过查看每个阶段的最左孩子来确定应当采用哪种构造方法,在剩余的孩子节点上进行递归构造,直至递归到每一个终结符节点。例如节点 x 的最左孩子如果使 x->children[0]->label_value == regex_union<T> ,则要将nd->children[1]和nd->children[2]转为的 ε-NFA 使用 Thompson 构造法中 E+F 的构造,而且我们可以通过递归将nd->children[1]和nd->children[2]转为 ε-NFA。
任务¶
你需要将homework/lib_char.h中的
// #include "ParseTree-to-eNFA/converter.h"
取消注释,然后完成homework/ParseTree-to-eNFA/converter.h中的TODO,将传入的正规表达式语法分析树转为对应的 NFA,使项目通过CI/CD。
提示:std::set_union可能对 ε-NFA 的合并有所帮助。
作者: