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

[lastright]

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

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

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

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

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

[chord65]

编译原理的东西记不太清了，建议你回头再看看编译原理的教材？

[luckyuro]

如果我没记错的话，不是根据语法实现状态机，之后使用状态机来构建语法树，之后在进行语义分析么。
还是我记错了😂😂

[CRVV]

这里不是为什么要构建 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]

@CRVV 非常感谢,耳目一新.