聞き慣れない人にはまったく聞き覚えのない言葉かもしれませんが、上記の２つのソフトはコンパイラ開発を支援する為のツールです。 それぞれYaccが構文解析の部分で、Lexが字句解析の部分でそれを支援します。 具体的にはYacc、Lexの表記法に従って字句解析や構文解析のルールを書いてやり、それをＣのソースにして出力してやるものです。 この時のYaccやLexに書くコードと言うのは実際のＣのコードに対して視覚的にもっかなり分かり易いです。
では具体的にどのような行程を経てコンパイラは完成されるのか、簡単な例を挙げ順を追って説明して行きたいと思います。 今回は入出力、繰り返し制御、条件分岐などの最低限の機能のみを扱えるインタプリタ型の言語を作成します。 それでは大まかな流れを見てみます。
| YaccとLexのコードを記述 |
| ↓ |
| それぞれをＣのソースにコンパイル |
| ↓ |
| そのＣのソースをＣコンパイラでコンパイル |
| ↓ |
| 作成された実行ファイルでオリジナルの言語のソースを読んで実行する。 |
まず字句解析の部分から見て行こうと思います。字句解析とは連続した文字列を一文字ずつ調べていき、トークンと呼ばれるプログラムにとっての言語の最小単位の塊を見つけて行きます。 日本語で言えば、「さかなとうみ」が文字列で、「さかな」「と」「うみ」がトークンになります。要は意味を持つ最小の文字の集まりがトークンと言うわけです。 ここでそのトークンを見つけるために「正規表現」と言うものを用います。正規表現に関する具体的な表記法は下に記して置きます。 それでは一応簡単な例を示します。
トークンが「＜」「＜＝」「＝」「＝＝」「（数字）」である場合、文字列「２＜＝３」はどのように解釈されるでしょう。 最初に「２」が数字として認識されます。次に「＜」を読みこみますがこれは数字ではないので結局数字は「２」だけであるとして認識します。 この時実際は「＜」は読み終わった状態なのですが、次に「＝」の解釈から入ったら「＜」の存在が無視されてしまいます。 そこで数字のトークンを認識した後、文字を読みこんでいる位置を１つ前にずらしてやる必要があります。大概その処理はLex側で勝手に処理を加えてくれるのでこちらが意識する必要はありません。 只そうで無いものもあるので各マニュアルを通読して下さい。本流に戻ると、１つ戻って「＜」を読みこむとこれはトークン「＜」に一致します。 しかし続いて「＝」が来るので「＜＝」トークンとの認識に変わります。続いて「３」を読みこむと「＜＝（数字）」と言うトークンは無いため「＜＝」がトークンと決定します。 そしてまた１つ戻って「３」を読みこみ次には空白なので「３」をトークンとして決定します。見てきたようにトークンの照合は不一致が起こるまで続けられます。 つまり「＜」を読んだからと言ってすぐにそれをトークンとしてしまう訳では無いのです。もしそう言う解釈を行う字句解析ルーチンであったなら「＜＝」を「＜」「＝」と解釈してしまう使い物にならないルーチンになってしまいます。 要は最長マッチですね。
続いて構文解析です。構文とは早い話が文法についてです。例えばＣのｉｆ文なんかは「ｉｆ （ａ ＝＝ ２） ｛ｐｒｉｎｔｆ（”ＴＥＳＴ”）；｝」みたいな感じで書くことが出来ます。 これは次の様に文法的定義を与えることが出来ます。「ｉｆ （＜条件式＞） ｛＜処理＞；｝」。さらに「＜条件式＞」は「＜変数＞＜不等号＞＜数字＞」となります。 このようにして文法をどんどん細分化して行き、これ以上分割出来ない単位まで分割した際に残っている各部品がトークンとなります。Yaccは要は字句解析ルーチンを呼び出して返されたトークンを元に文法を調べて行くものです。 様々な規則を用いて文法を作成して行きますが、その中で注意しなければいけないことが文法の曖昧性です。 曖昧性とは「＜数字＞＝＜数字＞＋＜数字＞」と言う規則があった場合に「１＋２＋３」が与えられた時、「１＋（２＋３）」と解釈するのか「（１＋２）＋３」と解釈するのか曖昧な状態になってしまうようなことです。 こう言った曖昧性の解決法については後に触れます。 以下に視覚的に構文解析の過程を分かりやすく示した構文木を載せて置きます。
さて文法に関しての大体の仕組みは上記のとおりです。次に構文解析の結果としての「処理」を記述します。 和算を解釈しても何も実行しないのでは意味がないですね。ここではその和算を例に構文解析の説明を行って行きたいと思います。 まず和算の文法を書いて見ます。
exp : exp '+' exp {$$ = $1 + $3;}
| NUMBER {$$ = $1;}
;
※expは数式を表すものです。
NUMBERは数字を表すトークンです。
expは疑似変数として数値を持ってます。
|
ここでexpは疑似変数をして「値」を持つことが出来るようになっています。疑似変数を扱うためにはちょっとした記述を加える必要があるのですがそれについては後述します。 上記に出てくる「$$」や「$1」はそのexpらの疑似変数値を表します。$$は$0の意です。右側の数字はその文法規則に出てくる位置です。 $$は一番左側のexp、$1は左から２番目のexp、$2は+、$3は一番右のexpです。ちなみにここでは$2は値を持てません。
簡単な演算等は上記のようなyacc内で擬似変数などを用いて処理することが出来ますが、変数処理や条件分岐、繰り返し文などの制御構造などを実現しようとなるとそれだけでは間に合いません。 そこで外部にそれらの処理をする関数等を用意する必要があります。これらのことについてはいずれ触れて行きたいと思いますが、簡単にそれらの実現方法を書いておきます。 但し以下で述べることはあくまで一例です。
まず様々な命令処理は全てyacc内から関数を呼び出すことで実現させます。YaccやLexはあくまで”構文解析””字句解析”を行う道具であると割り切ってしまいます。 条件分岐に関しては、条件によってflagを立たせそれによって命令を実行させたり飛ばしたりします。条件分岐文が終了したらflagも戻します。 繰り返し文については構文解析の結果得られた命令の実行順序を事前に記録しておき、それを後で呼び出すと言う形で実現します。 最後に変数は線形リストでその名前、型、値等を保存し、必要に応じて呼び出します。