首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  程序员

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

  •  
  •   lastright · 102 天前 · 588 次点击
    这是一个创建于 102 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

        1
    chord65   101 天前 via Android
    编译原理的东西记不太清了,建议你回头再看看编译原理的教材?
        2
    luckyuro   101 天前 via iPhone   ♥ 1
    如果我没记错的话,不是根据语法实现状态机,之后使用状态机来构建语法树,之后在进行语义分析么。
    还是我记错了😂😂
        3
    CRVV   101 天前 via Android   ♥ 1
    这里不是为什么要构建 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
        4
    lastright   101 天前
    @CRVV 非常感谢,耳目一新.
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1872 人在线   最高记录 5043   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 18ms · UTC 16:27 · PVG 00:27 · LAX 09:27 · JFK 12:27
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1