我在学着写一个正则表达式引擎,我现在构建好了语法树,接下来要转成 DFA 或 NFA.
但是我觉得基于语法树,好像已经可以实现正则引擎了.(而且我确实已经实现了 concat 和 or 的匹配).
请问 DFA/NFA 的好处是更快吗?这个问题是不是有点儿傻,但我看的教程里都是在讲 DFA/NFA 的原理,没讲为什么需要它.
而且我看不懂原理,好像都是在说从一个状态,转化到另一个状态.请问它这种状态转化,是为了干什么?如果是为了加速匹配,它加速的原理是什么?是不是像 kmp 算法那样,跳过注定失败的位置.
我还在看网上的教程,如果有人点拨两句,就太感谢了.
 |
1
chord65 Jan 14, 2019 via Android
编译原理的东西记不太清了，建议你回头再看看编译原理的教材？
|
 |
2
luckyuro Jan 14, 2019 via iPhone  1
如果我没记错的话，不是根据语法实现状态机，之后使用状态机来构建语法树，之后在进行语义分析么。
还是我记错了😂😂 |
 |
3
CRVV Jan 14, 2019 via Android 2
这里不是为什么要构建 FA 的问题
正则表达式不是专门为了做字符串匹配设计出来的东西，这玩意是从学术研究那边来的 Finite Automata 是某门课讲 Turing Machine 之前要讲的东西，这课要讲它和正则表达式是等价的，还有证明 从这个角度来考虑，用 Finite Automata 来实现正则表达式是最普通的做法，所以他们不给你解释为什么要用 至于能不能不用，当然可以。现代的正则表达式为了做字符串匹配加了其它功能，用 Finite Automata 已经不能实现了，其实通常都没用 https://math.stackexchange.com/questions/2705692/regular-expression-vs-finite-automata https://swtch.com/~rsc/regexp/regexp1.html |
Select Language