1-1 字句解析1


言語処理系の基本構成

プログラミング言語の処理系は大きく、コンパイラとインタプリタに分けられる。 インタプリタはプログラムを読みこんで即座に実行するが、コンパイラは読みこんだプログラムを機械語に翻訳する。しかし内部構造は、コンパイラもインタプリタも大きく異なるわけではない。特に前半部分はまったく同じである。

言語処理系の一般的な内部構成は次のように5段からなる。

  1. 字句解析

  2. 文字列を token 列に分解。
  3. 構文解析

  4. token 列を抽象構文木 (abstract syntax tree) に変換。
  5. 意味解析

  6. 抽象構文木を元に、変数の型など意味情報を計算して、構文木を中間言語(中間表現とも言う。やはり木構造。)に変換する。
  7. 最適化

  8. 中間言語を変形して、効率のよいプログラムに変換する。
  9. 実行またはコード生成

  10. 中間言語を元に、インタプリタなら計算を実行、コンパイラなら機械語を出力する。
字句解析と構文解析は、人間が読みやすい形(文字列)を、計算機が扱いやすい形(構文木)に変換するためのステージ。それ以降のステージが、言語処理系の本質的な部分。

コンパイラの性能のよしあしは、最適化ステージで決まる。最適化ステージのよしあしは、どのような中間言語を採用しているかに大きく依存する。単純な中間言語は、構文木に意味解析の結果を付加したものだが、商用のコンパイラでは、理想化された機械語を用いる。

中間言語として、理想化された機械語を用いると、各言語からその中間言語への変換プログラムと、中間言語から各計算機の機械語への変換プログラムを作ることで、多言語・多機種に対応したコンパイラを作ることができる。
 
 

Lex による字句解析

字句解析の役目は、ファイルの中に文字列として格納されているプログラムを token (単語) の列に変換して、次の構文解析をやりやすくすることである。余白やコメントを調べて、単語の切れ目を決めなければならない。

lex というプログラムを使うと、簡単に字句解析部を作ることができる。lex は、正規表現による token の定義から、字句解析をおこなうC言語プログラムを生成する、ある種のコンパイラである。

Token の定義ファイルの構成は次のようである。

正規表現による token の定義は具体的には以下のようになる。 Lex は、このような定義にしたがって、字句解析をおこなう関数 yylex() を生成する。この関数は、左側の正規表現に一致した token を見つけたとき、右側の文を実行する。また同時に見つけた token のを文字型配列 yytext にコピーする。通常、右側の文は、token の識別番号を返す return 文にする。上の例では、数が来たら 1 を、+ 記号が来たら 2 を返す。

なお + 記号は、正規表現では1つ以上の繰りかえしを意味するので、"" (引用符)でくくって、通常の + 記号を意味するようにしてある。

lex では正規表現にマクロを使うこともできる。例えば

とマクロ digit を定義したら、 のように token を定義することもできる。

正規表現にマクロを使えるのと同様、右側の return 文でもマクロが使用できる。こちらは通常のC言語のマクロを使う。

と定義しておけば、 とできる。

最後に例として電卓用の字句解析器 calc.l を見てみよう(コピー&ペーストでファイルに落とすときは、最終行に改行を入れることを忘れない。lexのバグ?で、そうでないと正しくプログラムが認識されない)。これは次のようにしてコンパイルする。

Lex は calc.l から lex.yy.c というC言語のソースファイルを出力する。この中には、calc.l に書かれていたC言語のプログラムと、lex が作成した関数 yylex() が含まれる。lex.yy.c は -ll オプションをつけてコンパイルする。

Lex が生成する関数 yylex() は、1回呼ぶごとに標準入力から token をひとつ取り出し、識別番号を返す。同時に取り出した token を文字配列 yytext にコピーする。

calc.l は main 関数を含んでいるので、コンパイルすると実行可能である。現在は、yylex() を呼び、10進数、+ 記号、- 記号、そして改行文字 (return) の4種類の token を表示する。

注: lex が利用できない場合は flex コマンドが利用できるかもしれない。 その場合、gcc のオプションは -ll ではなく -lfl かもしれない。
 
 

課題1

calc.l の main() 関数を改造して、電卓プログラムを作れ。例えば、 と入力したとき、0 を表示すればよい。

さらにかけ算や割り算もできるようにせよ。だたし演算子間の優先順位は考えなくてよい。普通の電卓同様、すべての演算子を同じ優先順位にしてよい。



目次へ戻る

Copyright (C) 1999-2000 Shigeru Chiba

Email: chiba@is.tsukuba.ac.jp