可以用最浅显的话告诉我为什么需要 DFA/NFA 吗?

2019-01-13 23:40:56 +08:00
 lastright

我在学着写一个正则表达式引擎,我现在构建好了语法树,接下来要转成 DFA 或 NFA.

但是我觉得基于语法树,好像已经可以实现正则引擎了.(而且我确实已经实现了 concat 和 or 的匹配).

请问 DFA/NFA 的好处是更快吗?这个问题是不是有点儿傻,但我看的教程里都是在讲 DFA/NFA 的原理,没讲为什么需要它.

而且我看不懂原理,好像都是在说从一个状态,转化到另一个状态.请问它这种状态转化,是为了干什么?如果是为了加速匹配,它加速的原理是什么?是不是像 kmp 算法那样,跳过注定失败的位置.

我还在看网上的教程,如果有人点拨两句,就太感谢了.

2112 次点击
所在节点    程序员
4 条回复
chord65
2019-01-14 08:49:48 +08:00
编译原理的东西记不太清了,建议你回头再看看编译原理的教材?
luckyuro
2019-01-14 09:46:57 +08:00
如果我没记错的话,不是根据语法实现状态机,之后使用状态机来构建语法树,之后在进行语义分析么。
还是我记错了😂😂
CRVV
2019-01-14 10:06:32 +08:00
这里不是为什么要构建 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
lastright
2019-01-14 13:24:45 +08:00
@CRVV 非常感谢,耳目一新.

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/526709

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX