[elixir! #0084] 关于 DFA(确定性有限自动机)的那些事儿

最近在看 编译原理 这本书,感觉是很棒的入门书(指难度由浅入深深深深)。前两章主要是一些概念性的东西,第三章就开始动真格的,上代码上公式了。不自己实现一下,根本就是看得云里雾里的。所以接下来一段时间可能会不定期地更新一些关于我在 编译原理 这本书里看到的东西的实现的文章。
书本的第三章介绍了 DFA 是如何对字符串进行匹配的,例如,正则表达式 (a|b)*abb 可以转换为以下的 DFA 代码。通过状态机的机制在读取字符时切换当前状态,并根据最后的状态来确定匹配是否成功。

defmodule DFA dodef init(string) do %{ s: 0, chars: String.to_charlist(string) } enddef run(%{s: s, chars: [h | t]}) do s = move(s, h) run(%{s: s, chars: t}) end def run(%{s: s, chars: []}) do if s in f() do :yes else :no end enddefp move(0, ?a), do: 1 defp move(0, ?b), do: 0 defp move(1, ?a), do: 1 defp move(1, ?b), do: 2 defp move(2, ?a), do: 1 defp move(2, ?b), do: 3 defp move(3, ?a), do: 1 defp move(3, ?b), do: 0defp f(), do: [3]end

这个 DFA 只会匹配到以 "abb" 结尾的字符串:
DFA.init("ababb") |> DFA.run()# :yesDFA.init("ababa") |> DFA.run()# :no

【[elixir! #0084] 关于 DFA(确定性有限自动机)的那些事儿】是不是很神奇呢

    推荐阅读