Posts Tagged ‘编译原理’

简单的基于DFA的正则表达式引擎

最近做了一个很简单的正则表达式引擎,能支持*,|和字符连接,目的是动手写点东西熟悉一下编译里面的一些原理.

龙书中将解析正则表达式库分为两种办法:
1)将正则转换为NFA,然后NFA再转换成对应的DFA
2)将正则转换为抽象语法树,再将抽象语法书转换成DFA.

我这里用的第2种方式,第1种等我有空了再补上吧.

大体说一下流程,分为以下几步:
1)自下而上的构建抽象语法树