プログラミング言語処理

字句解析の基礎：正規表現によるパターンマッチ

字句解析とは、文字列として入力されるプログラムをtokenの列に分解するフェーズである。前回のプログラムにおいて、字句解析を行う関数getTokenは、文字列を数字(NUM)、演算子(PLUS_OP,MINUS_OP)などのtokenに分けて、返す関数である。

字句解析と正規表現

どのような文字列がどのようなtokenになるかについては、 正規表現 (regular expression) で定義することができる。アルファベットA上の正規表現とは、

ε (空列記号)は正規表現である。
Aの要素aは正規表現である。
RとSが正規表現であれば、M|N、MN,　M*　は正規表現である。M|Nとは、 MもしくはN、MNはMの次にNがくる列、M*とは、Mの0回以上繰り返しを意味する。

なお、（S）は、Sと同等であることを意味する。

例えば、正規表現a(b|c)*は、最初にaがあり、bまたはｃが続く文字列を表現する。abbcもabcbccも、abccもこの正規表現で表現される文字列である。

正規表現は、図のような規則で 非決定性有限オートマトン（NDA: nondeterministic finite automaton） に変換できる。 有限オートマトン (finite automaton) とは、有限の内部状態を持ち、与えられた記号列を読みこみながら状態遷移し、その記号列があるパターンをもつ列であるかを決定するものである。非決定性有限オートマトンとは、入力によらない状態遷移（空列記号に対する状態遷移）をもち、それは非決定的に遷移してもしなくてもよいと状態をもつものである。図にそれぞれの規則に対応するオートマトンを図示する。

先にあげたa(b|c)*について、この規則で、NDAに変換した結果も示す。

NDAでは、空の状態遷移に対して、状態遷移するかしないかの両方の可能性をしらべなくてはならないので、実際にそのまま実装すると効率がわるい。そのため、非決定的な遷移を取り除き、 決定性有限オートマトン(DFA: deterministic finite automaton) に変換する。DFAとは、以下の条件を満たす有限オートマトンである。

ε による遷移がない。
一つの状態から同じ記号による異なった状態への遷移はない。

変換には次の規則を適用し、上の条件にあったオートマトンに変換する。

初期状態から、ε による遷移を一まとめにした集合を初期状態とする。
状態の集合からの遷移は、その集合からの遷移の集合の合併とする。つまり、状態の集合D={x1,x2,...}からのaによる遷移の行き先は、x1からaで遷移した状態yもしくは、yから ε で遷移する状態の集合になる。
２を繰り返し新しい遷移が得られなくなるまで繰り返す。

このアルゴリズムで得られるFDAは必ずしも、最小のオートマトンとはならない。最小にするには、同じ遷移が２つあった場合には、冗長なので１つにまとめることができ、これを繰り返すことにより、最小化ができる。

自動字句解析生成プログラム：lex

正規表現が与えられた時に、その言語（文字のパターン）を認識するDFAを機械的に作り出すことができる。そのアルゴリズムをプログラムにしたものが字句解析器生成系( lexical analyzer generator)である。このプログラムとして、有名なのが、lexである。lexでは、定義ファイルは以下の形式でかく。

%{
任意のCプログラム。定数やCのマクロの宣言をここにかく。
%}
下の定義で使うlexのマクロの定義
%%
正規表現による入力パターンの定義
正規表現パターン　アクション　という形で書く
%%
任意のCプログラム

例えば、a(b|c)*の正規表現を認識する字句解析は、

%{
%}
%%
a(b|c)*  { printf("OK\n"); }  /*このパターンを入力したらOKを出力する*/
. 　{printf("NG\n");}  /*.は以上以外のパターンの場合のアクションを指定 */
%%
/* 　なにもなし　*/

でよい。

これをコンパイルするには、

% lex test.l
% cc lex.yy.c -ll

とする。これでできたa.outを実行すると、abcにたいしてはOK, xxxにはNGと出力される。Linuxのflexのときには、-llの代わりに、-lflをつかうこと。

前回示した数式の字句解析の部分は以下のように書ける。

%{
#include "expr.h"
%}
digit   [0-9]  /* マクロの定義，digitを0-9の数字の集合と定義する　*/
%%
{digit}+  return NUM;    /*0-9の１回以上の繰り返しは、NUMと認識する　*/
"+"     return PLUS_OP; /*+はPLUS_OP +は繰り返しの意味なので、""で囲む*/
"-"     return MINUS_OP, /* -はMINUS_OP */
[ \t]                     　/* 空白は無視　*/
.       printf("error?\n");   /* error */
%%
main(){
    yystdin = stdout;
    ....
    r = yylex(); /* tokenの列はyytextに入る　*/
    printf(" token is %d,'%s'\n",r,yytext); 
}

lexは、字句解析ルーチンとして、yylexを生成する。このルーチンは、action で指定されたreturn分で返された値を返す。

lexの使い方については、

 % man lex

として、マニュアルを参照のこと。