自作コンパイラの部屋 > yacc入門 > 字句解析
私は、コンパイラの勉強をはじめるまで、コンパイラというものは文字列処理の塊なんだろうと想像していました。コンパイラは、プログラム言語のソース（すなわち文字列）を入力として何やら複雑な処理をした結果、プログラムを生成します。これを見ていると、そんな気がしたのです。しかし、伝統的（教科書的）なコンパイラ作成技法によるならば、コンパイラの中で文字列処理に関わる部分は、実はごくわずかです。
現実のコンパイラは、一種の階層構造になっています。一番下の層は、言語のソース･テキストを扱う部分で、一般に字句解析と呼ばれます。コンパイラの中で文字列処理が多く現れるのは、この字句解析部分です。
一般には、字句解析プログラムは関数（サブルーチン）の形で作られます。この関数は、呼び出すたびに、入力文字列の中から基本単位を一つ読みこみ、その内容を返します。コンパイラの用語では、この基本単位をトークン（token）と呼びます。以下は、C言語のトークンの例です。
+ 加算演算子 ++ インクリメンタル演算子 while 予約語while point 識別子 123 整数リテラル "this is a pen" 文字列リテラル
一般に、字句解析プログラムは空白やコメントを読み飛ばします。このため、次のようなC言語プログラムがあったとすると、
int main()
{
printf("hello world");
}
字句解析プログラムを通すと、以下が次々に返ることになります| 予約語int |
| 識別子(main) |
| ( |
| ) |
| { |
| 識別子(printf) |
| ( |
| 文字列(hello world) |
| ) |
| ; |
| } |
つまり、字句解析関数は、getc()、fgets()、rand()と同じように、呼び出すたびに次の値を返すようなタイプの関数だということになります。一種のイテレータだと言ってもいいかもしれません。
次に、字句解析関数が返す値は何でしょうか？もちろん、文字列でも良いのですが、通常はトークンの種類を示す整数値を返します。コンピュータにとっては整数値の方が高速に扱えるし、メモリ管理なども楽だからです。yaccを使う場合、字句解析関数は整数値を返すように定められています。 どんな整数値を使うかは、基本的には任意で、区別がつきさえすれば可です。しかし、一般的には、一文字のトークン（加算演算子など）は、その文字のアスキーコードを使用し、それ以外はdefineで名前をつけられた一連番号を使います。yaccを使う場合、トークンの名前を定義さえすれば、内部的な数値については考慮する必要はありません。
ここで再び三度、電卓プログラムの中の字句解析関数を調べてみることにします。前述のように、yaccで使用する字句解析関数は、yylex()という名前にすることが決まっています。
| lex.c |
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#ifdef UNIX
#include "parser.tab.h"
#else
#include "parser.h"
#endif
int yylex() /* 字句解析ルーチンはyylexという関数にする */
{
int c = getchar();
if (isdigit(c)) { /* 一文字が数字だったら */
char buff[128]; /* atoi用のバッファ */
char *p = buff;
do {
*p++ = c; /* その一文字を記憶し */
c = getchar(); /* 次の文字を読む */
} while (isdigit(c)); /* まだ数字だったら繰り返し */
ungetc(c, stdin); /* 読み過ぎた文字を返しておく */
*p = '\0'; /* 終端 */
yylval = atoi(buff); /* yylval変数に値を覚える */
return NUM; /* NUMを返す */
} /* 数字でない場合は */
return c; /* 文字そのものを返す */
}
|
電卓の場合、一文字を超えるトークンは整数リテラルしかありません。したがって、一文字を読みこんだら数字かどうかを調べ、数字でない場合はそのアスキーコードをそのままリターンしています。 数字の場合はさらに文字列を読みこんで、数字以外の文字が出現するまで続けます。その後、数字列の部分はatoi()関数により数値化し、一文字読み過ぎた「数字以外の文字」については、ungetc()関数で「読まなかった」ことにしています。
一般に字句解析プログラムは、この「読みすぎ」が頻繁に現れます。これに対する処理方法は大きく分けて二つあります。
一つは、常に一文字を「読み過ぎた状態にしておく」方法です。一文字先を読んだ状態を維持する訳ですから、これを「先読み法」と呼ぶことが出来ます。伝統的にPascalのコンパイラはこの手法で作られるようです。その理由は、Pascalコンパイラの元祖Pascal-P4がこの方法で開発されているからです。
もう一つは、読みすぎた文字を「読まなかったことにする」方法です。C言語には、まさにこのための関数ungetc()があるので、C言語を使う場合（すなわちyaccを使う場合も）は、この方法が便利で、電卓プログラムでもこの方法を使っています。
また、整数リテラルの場合は、リターン値としてNUMを返しています。NUMはyaccの文法定義ファイルで定義された名前です。しかし、これだけだと、整数リテラルの数値がわからなくなるため、yaccで定義されたグローバル変数 yylval に、この値を記憶しています。
|
目次 |