TeX で LR(0) DFA のような強そうなオートマトンを描く

6728 ワード
Tikz TeX オートマトン LaTeX LaTeX テキストリンク

レポート等でオートマトンを描きたくなることがあると思います。「TeX オートマトン」でググると、TikZのautomataライブラリでオートマトンを描く方法が様々な記事で解説されています。
それらの例で登場するオートマトンはどれも丸に矢印が生えているだけのシンプルな図です。では、以下のような状態遷移図はautomataライブラリで描くことができるでしょうか？

これは ANDREW W. APPEL, Modern Compiler Implementation in ML という本に出てくる、LR(0) DFA と呼ばれるオートマトンです。このオートマトンは

\begin{align}
S &\rightarrow E \$ \\
E &\rightarrow T \\ 
E &\rightarrow T + E \\
T &\rightarrow x
\end{align}

という言語に対応していて、LR(0) の場合 shift と reduce が衝突して解析できませんが、 SLR (Simple LR(1)) の場合解析できます。

さて、これを描いてみましょう。

\usepackage{tikz}

\usetikzlibrary{automata}

\begin{tikzpicture}
  [>=latex, 
    node distance=3cm, 
    block/.style={state, rectangle, text width=6em}
  ]

  \node [block, label=above right:1] (q_0) 
    {
      \( S \rightarrow . E \$ \) \\
      \( E \rightarrow . T + E \) \\
      \( E \rightarrow . T \) \\
      \( T \rightarrow . x \) 
    };
  \node [block, label=above right:2] (q_1) [right of = q_0]
    {
      \( S \rightarrow E . \$ \)
    };
  \node [block, label=above right:3] (q_2) [below of = q_1] 
    {
      \( E \rightarrow T . + E \) \\
      \( E \rightarrow T . \)
    };
  \node [block, label=above right:4] (q_3) [below of = q_2]
    {
      \( E \rightarrow T + . E \) \\
      \( E \rightarrow . T + E \) \\
      \( E \rightarrow . T \) \\
      \( T \rightarrow . x \) 
    };
  \node [block, label=above right:5] (q_4) [left of = q_3]
    {
      \( T \rightarrow x . \)
    };
  \node [block, label=above right:6] (q_5) [right of = q_3]
    {
      \( E \rightarrow T + E . \)
    };

  \path [->] (q_0) edge [right]      node [above] {\(E\)} (q_1)
                   edge [right]      node [above] {\(T\)} (q_2)
                   edge [right]      node [left]  {\(x\)} (q_4)
             (q_2) edge [bend right] node [left]  {\(+\)} (q_3)
             (q_3) edge [right]      node [above] {\(x\)} (q_4)
                   edge [bend right] node [right] {\(T\)} (q_2)
                   edge [right]      node [above] {\(E\)} (q_5);
\end{tikzpicture}

すると

それらしきものを描くことができました。

いくつかのポイント

  • node の style で rectangle を指定することで、状態の部分を四角形にすることができます。
  • node の style で text width を指定することで、中で改行ができるようになります。
  • 中で複数行の数式を書くとき、普通に align 環境を使うと、数式の上側に余白ができて不恰好になってしまうので、一行ずつ数式を分けて書くのが良いと思います（もしオートマトン以外で数式を使わないのであれば、グローバルなオプションで余白の大きさを変えてしまっても良いとは思いますが）。