1-1 字句解析１

言語処理系の基本構成

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

1. 字句解析

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

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

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

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

中間言語を元に、インタプリタなら計算を実行、コンパイラなら機械語を出力する。

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

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

Lex による字句解析

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

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

%{

任意のC言語プログラム。型や定数の定義を、ここに書く。
#include や #define もここに含める。

%}

下の定義部で使うマクロの定義

%%

正規表現による token の定義

%%

任意のC言語のプログラム。main 関数の定義など。

[0-9]+ 　　　　　　　return 1;
"+"　　　　　　　　　return 2;

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

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

digit　　　　　　　[0-9]

{digit}+ 　　　　　　　return 1;

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

#define NUMBER　　　　1

{digit}+ 　　　　　　　return NUMBER;

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

% lex calc.l
% gcc lex.yy.c -ll

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

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

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

課題1

% 1 + 2 - 3 改行

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

Copyright (C) 1999-2000 Shigeru Chiba