このシリーズは自分の勉強の形跡のために残したメモとなります。間違いを正すことも目的の一つなので間違いや違和感があれば何でも指定してください。
今回は前回紹介した字句解析フェーズでどのように入力を処理してトークン列にしているか解説していく。ただここではLexの使い方などは紹介しないつもり。
勉強のために参考にしているもの
- 「最新コンパイラ構成技法」Andrew W. Appel (著), 神林 靖 (監修, 編集, 監修), 滝本 宗宏 (編集)
- 「実践コンパイラ構成法 (電子通信情報系コアテキストシリーズ)」滝本 宗宏 (著)
言語処理系入門シリーズ目次
字句解析の流れ
最初に入力をトークン列に変換するのは字句解析器（Lexical analyzer）に入力を食わせて吐き出しているだけです。構文解析と同時に行うこともありますが、字句解析だけで見ると結果が実行可能か正しい意味かはチェックしません。。このトークンは言語ごとにいろいろな表現がされるので一概には言えませんが大抵DEFINEやINTEGER(12)のように意味値を持った形で表現されます。トークンには数値やユーザー変数名などの識別子とifやintなどの予約語があります。
字句解析器とは
字句解析とは入力文字列の頭から順に調べ正規表現にマッチするかどうか調べてマッチしたらトークンとして返すという動作を繰り返し、トークンの列つまりトークン列を返しています。
この字句解析器は正規表現から自動的に生成できるのでその方法を説明していきます。簡単に説明すると
- 正規表現を有限グラフで表現する。
- グラフを最適化する。
- そのグラフをプログラムが利用できるように埋め込む。
この最後はグラフさえできればどうにかなるのでここでは説明を省略します。
ただしここで出てくるグラフとは有限オートマトン（finite automaton, FA）のことです。有限オートマトンは正規表現の表現として計算機理論にはよく使用されます。
有限オートマトン（FA）とは
有限オートマトンとは点に状態、辺に記号を持つ有限有向グラフのことです。状態遷移図とも。
ここでいう状態(State)とは単なる点の別名です。状態を区別するために数字や記号でラベリングします。表記は〇で書く。
そして記号(Symbol)は解析したい言語で使用可能な文字や記号のことです。ちなみにこの記事では辺の根元にある状態を始点、指す先にある状態を終点と表現していきます。表記は有向辺の上下左右に記号をそのまま書く。
まず状態について詳しく説明します。状態には大きく分けて4種類の状態があるので表でまとめて説明していきます。複数あるのは複数存在するということです。ただ一番下は便宜上の分類です。
| 状態の分類 | 表記 | 説明 |
|---|---|---|
| 初期状態(Initial State) 開始状態(Start State) |
・ラベルを持たない辺とその終点 ・ Sでラベリングされたどの辺の終点にならない状態 |
一つのFAがただ一つ持つFAの開始点 |
| 受理状態(Accept State) 最終状態(Finish State) |
・〇の代わりに◎ ・ Fでラベリングする |
一つのFAに複数存在する。この状態で解析が止まればそれまで読み込んだ文字をその最終状態に応じたトークンにして返す。単に辺の始点とならない状態のことではない。 |
| 通常の状態 | 〇 | 0個以上の辺の始点と0個以上の終点のこと。 |
| 遷移不可の状態 | 〇 | 今与えられている入力において遷移できない状態のこと。始点にならない状態としても使うことがある。 |
次に記号について説明する。記号は簡単な正規表現のように表記されます。ただ正規表現の表記とは必ずしも一致しません。例えば正規表現で改行を除く任意の一文字を表す"."はそのまま文字で扱います。この記号もまた表でまとめて説明します。
| 記号の表記 | 例 | 説明 |
|---|---|---|
| 単一記号 | ・i ・f |
一つの記号を認識する。 |
| "で挟まれた記号列 | ・"if" ・"a.*" |
その記号列を文字としてまとめて認識する。 |
| 記号-記号 | ・0-9 ・a-z |
連続的に表記できる記号について最初と最後だけで全部を表現する。辺をその数だけ用意してそれぞれ単一記号でラベリングするのと同じ。 |
| ε（空記号） | ・ε | 入力なしで遷移できる。別に遷移しなくても構わない。 |
ちなみにFAといっても実は種類があります。FAには入力によって一意に決定できる決定性有限オートマトン（Deteminisitic FA, DFA）と入力によって一意には決まらない非決定性有限オートマトン（non-DFA, NDA）の二つです。そして実はNFAからDFAに変換するアルゴリズムがある。このアルゴリズムは後で簡単に説明する。
これまで説明したFAのついての表記などは有限オートマトンも参考になる。
正規表現から最適化されたDFAへの変換
次に正規表現から最適化されたDFAを作る方法を説明します。簡単な流れは
- 正規表現からNFA
- NFAからDFA
- DFAからDFA（最適化）
の順に行われます。Lexはこれらを自動で行い実行できるプログラムを吐き出します。
ここも参考になります。ちなみにこれらの変換方法は"正規表現からDFA"などで調べれば結構出てくるが大体が1から3全てを一つのサイトにまとめて記述しているため情報が浅いことが多い。
ただこの記事ではFAを描画するのが面倒くさいのでFAの描画はしません。
正規表現からNFA
まず最初に一つの記号や複数の記号、文字列を認識するFAを考えるのは簡単にできると思います。そしてそのFAには入力の遷移を表すただ一つの辺とそのFAの最終状態のような扱いができる状態がただ一つあると思います。その辺を尾部、その状態を頭部とします。その頭部と尾部をつなげ正規表現の選択、連接、反復を表すFAを帰納的に定義することができます。
そして受理したい言語を表す正規表現は帰納的に定義してつなぎ合わせる（このようにある言語を定義するときに使う正規表現の集まりを字句仕様という）ので、同様にFAを帰納的に生成してからつなぎ合わせてやることで正規表現からFAを生成することができます。ただこのFAは普通正規表現の選択や0回以上の反復が存在するために、εでラベリングされた辺が存在してしまうことから入力によって一意に決定することができない為NFAであることがわかります。
NFAからDFA
簡単にアルゴリズムのアイデアを説明していく。ここで入力文字は解析対象の言語で使用可能な文字や記号のことを意味している。
- 任意の状態について次の1.~を計算する。
1.1 取ってきた状態を始点に任意の入力それぞれにおいて遷移する可能性のある状態を求める。(εラベルで遷移可能な辺で遷移、入力文字でラベリングされた辺で遷移を繰り返し行って状態をまとめるのを繰り返す。) - 先ほどの計算でまとめた状態の集まりを一つの状態としてまとめ、入力文字に対するふるまいはそのままにする。（状態をまとめた時点で同じ入力文字に対するふるまいは同じはず。）
一番最初に各状態で任意の入力文字に対するふるまいを計算しておくと毎回計算しなくて済むので幾分早くなる。
DFAからDFA（最適化）
先ほどのアルゴリズムでNFAから変換されたDFAは実は無駄があることがある。例えば入力文字bやcで別々の状態に遷移したもののその後は入力文字aで同様に動作するという状況である。そういったことをなくすために状態数が少ないDFAに生成されたDFAを最小化（最適化）していく。
まず最初に状態AとBが等しいということを「AとBがともに最終状態か非最終状態であり、任意の入力文字cに対してある状態Cが存在してAおよびBからそれぞれCに向かう辺が存在する。」ということで定義します。すると「状態AとBが等しいときにBに向かう辺をすべてAを指すようにしたあとでBを削除する」ことでAとBをまとめることができることがわかる。
この方法を繰り返しおこなう方法を方法1とします。この方法1によってある程度最適化できるが、この方法では最後に同じ状態に辺が向かわない状態をまとめることはできないからです。それをまとめるのが次の方法2です。（この方法がちょっとよくわからない）
- 受理状態の集合G_1、非受理状態の集合G_2に分ける。
- 各グループG_iについて、任意の入力文字aによって異なるグループに遷移するとき、遷移先が同じ状態の要素が同じ副グループになるように分割する。
- 分割されたグループが存在すれば2へ。なければ4へ。
- 各グループをそれぞれ一つにまとめる。
この方法1と方法2を繰り返しおこない（繰り返す必要はない？）DFAが変化しなければそれが最適なDFAということになる。
以上で正規表現から最適化されたDFAが得られる。