EDIT (2025-12-09): 添加了算法的生成的NFA节点与转移数量的结论的说明. 简要介绍 正则表达式Regex可以转换到NFA，然后可以直接模拟NFA或将所得NFA转换到DFA再模拟。这样就是一个完整的正则匹配引擎了。 参考博文 本文是词法分析系列第三篇文章，主要介绍从regex转换到NFA的方法。关于如何模拟运行NFA请参考下面两篇文章： 直接模拟NFA：NFA的模拟运行 先将NFA转换到DFA再模拟：NFA到DFA的转换算法 将正则表达式转换到NFA(本文) 算法! 这个算法又被称为McNaughton-Yamada-Thompson Algorithm （好长的名字！） INPUT: 在字符集Σ定义的正则表达式r OUTPUT: 该正则r对应的NFA N , N 能接受 L(r) (L(x): Language of x) 算法流程: 解析(拆分)输入的正则表达式r成多个不包含操作符的子表达式。 按下面的方法逐个转换1)得到的子表达式转换到子NFA： 如果表达式是ϵ：直接生成ϵ转移 graph LR; s(((Start))) --ϵ--> f(((f))) 否则是在字符集Σ有定义的表达式a graph LR; s(((Start))) --a--> f(((f))) 按下面的方法将得到的子NFA根据子表达式之间的操作符连接起来： r = s|t: graph LR; start(((start))) --ϵ--> s{{"N(s)"}} start(((start))) --ϵ--> t{{"N(t)"}} s{{"N(s)"}} --ϵ--> fin(((f))) t{{"N(t)"}} --ϵ--> fin(((f))) r=st: graph LR; start(((start))) --ϵ--> s{{"N(s)"}} s{{"N(s)"}} --ϵ--> t{{"N(t)"}} t{{"N(t)"}} --ϵ--> fin(((f))) r = s*: graph LR; start(((start))) --ϵ--> fin(((f))) start(((start))) --ϵ--> s{{"N(s)"}} --ϵ--> s{{"N(s)"}} s{{"N(s)"}} --ϵ--> fin(((f))) r = (s): N(r) = N(s). 不太能理解为啥流程图能生成出这个样子。。上述图片去就参考Wiki好了 ...
Start to learn ARM64 ASM! - S1E1 - Installing the qemu for aarch64 on x86-64 archlinux
Goal This post shows how to install aarch64 qemu simulator on x86-64 and run a simple program on aarch64. Step 1: Installing prerequisites for qemu-system-aarch64. Basically, you will need to install the following packages into your x86-64-based host system. qemu-system-aarch64: For the emulator itself. qemu-img for creating virtual disk image files. edk2-aarch64 for bios support files for the aarch64 architecture. The qemu for aarch64 needs these BIOS files to boot up. Just run (pacman is my Archlinux package manager, by the way.): ...
NFA的模拟运行
EDIT1：更新原始算法的时间复杂度估计 EDIT2：更新优化后的算法实现 EDIT3: 重写了优化后的代码及代码分析。 EDIT4: 重写代码复杂度分析 NFA的基础 NFA的概念、构成要素可以参考这篇文章. 本文主要讨论如何模拟NFA. 模拟NFA的算法 ALGORITHM: NFA Simulation 的经典算法 算法 INPUT: 输入字符串str NFA nfa. OUTPUT: ACCEPT / REJECT. def sim_nfa(nfa, str): (s0, F) = nfa # NFA的开始状态s0和终结状态F S = ϵ-closure(s0) # 计算ϵ-closure(s), 即开始状态集. for c in str: S = ϵ-closure(move(S, c)) #经过字符c之后,可以看作是状态S发生了转移 (即: S因为c变化了) if (S ∩ F != ∅) return ACCEPT else return REJECT 时间复杂度 注：下面计算的是不带任何优化的情况下的算法最坏情况下时间复杂度。算法优化见下一节。 代码第3行计算ϵ-closure(s0)的过程实际上是要遍历s0中的每一个状态s，再对于遍历的每一个s，去遍历所有的transition。找出所有的ϵ转移。假设一共有n个状态，m个可能的转移，那么ϵ-closure的时间复杂度就是O(nm)。 代码第5行针对于长度为L的输入字符串，遍历其中的字符，对每一个字符都进行ϵ-closure计算。那么第4~5行的循环的时间复杂度是O(L*nm) IMPLEMENT: NFA Simulation 的经典算法的改进实现 仔细观察上述伪代码不难发现，代码第3行和第5行做的事情是源源不断的将新发现的可达节点添加到S中。类似于BFS/DFS算法，我们可以用堆栈来模拟这个过程，不需要重复计算新的S并替换原来的集合。 《Compilers - principles techniques and tools 》这本书提到了这种思想，这里简单介绍一下这种思想的算法实现过程。 ...
NFA到DFA的转换算法
EDIT(2025-12-01): 添加了对ϵ转移的说明。隔了一段时间再看居然有些看不懂ϵ转移了，赶紧复习了下，新增了说明备忘。 EDIT2(2025-12-18): 扩充FA的说明，添加算法优化思路及时间复杂度分析。 EDIT2(2025-12-18): 扩充DFA的说明，添加Dead State. EDIT3(2025-12-29):修改了算法伪代码, 修正了算法时间复杂度分析(原来的分析是错的!). EDIT4(2026-03-13): 扩充文章内容，解释算法的目的。 常见概念的说明 首先需要对本文用到的概念进行说明. 如果你已经对下述概念很熟悉,可以跳过本节. 什么是FA：FA即有限自动机(Finite Automata)，是一种有有限个状态和状态之间转移的有向图。有限自动机也可以成为有限状态机(Finite State Machine). 重点在于有限个状态，以及状态之间的转移。这些转移可以是有条件的，也可以是无条件的；通常一个状态可以绑定一个或多个动作，来表示程序执行到该状态应该执行什么动作。 NFA(Non-deterministic Finite Automaton, 非确定性有限自动机)和DFA(Deterministic Finite Automaton, 确定性有限自动机)的区别: 先来看NFA的五大构成要素： S: 有限状态集合 S. Σ: 输入符号集合(A set of symbols) : (Input Alphabet). move: 状态转移函数. 这个函数计算对于S中的任意一个状态, 经过符号a之后,可以转移到哪些状态的集合. (包括ϵ转移). s0: 起始状态(Start state/Initial state). F: 终结状态集合 (Accepting states/Final states). DFA是NFA的特例: 状态转移函数move中不包括ϵ转移 对于一个状态s, 一个输入符号a, move之后只能抵达一个确定的状态节点. 需要特别注意的是，DFA的状态转移表(move)是针对输入符号集合Σ的任意一个符号c都需要能够找到一条出边。也是DFA的D(Deterministic, adj. 确定的)的由来。 算法简介 这个算法的名称被称为子集构造法，此算法将输入的NFA转换到等价的DFA。在所输出的结果DFA中，每一个DFA状态节点都是原NFA的一个状态子集。 ...
Hello World
💘 博麗 霊夢 💘