最近在看 编译原理 这本书,感觉是很棒的入门书(指难度由浅入深深深深)。前两章主要是一些概念性的东西,第三章就开始动真格的,上代码上公式了。不自己实现一下,根本就是看得云里雾里的。所以接下来一段时间可能会不定期地更新一些关于我在 编译原理 这本书里看到的东西的实现的文章。
书本的第三章介绍了 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(确定性有限自动机)的那些事儿】是不是很神奇呢