关于编译原理:elixir-0084-关于-DFA确定性有限自动机的那些事儿

最近在看 编译原理 这本书，感觉是很棒的入门书（指难度由浅入深深深深）。前两章次要是一些概念性的货色，第三章就开始动真格的，上代码上公式了。不本人实现一下，根本就是看得云里雾里的。所以接下来一段时间可能会不定期地更新一些对于我在 编译原理 这本书里看到的货色的实现的文章。

书本的第三章介绍了 DFA 是如何对字符串进行匹配的，例如，正则表达式 (a|b)*abb 能够转换为以下的 DFA 代码。通过状态机的机制在读取字符时切换以后状态，并依据最初的状态来确定匹配是否胜利。

defmodule DFA do    def init(string) do    %{      s: 0,      chars: String.to_charlist(string)    }  end  def 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  end  defp 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: 0  defp f(), do: [3]end

这个 DFA 只会匹配到以 "abb" 结尾的字符串：

DFA.init("ababb")|> DFA.run()# :yesDFA.init("ababa")|> DFA.run()# :no

是不是很神奇呢