lex(1) ソフトウェアツールを使用して、テキスト処理、コード暗号化、コンパイラ書き込みにおける問題を解決できます。たとえばテキスト処理では、ワードのスペルを検査してエラーを検出できます。コード暗号化では、特定の文字パターンを別のパターンに変換できます。コンパイラ書き込みでは、プログラム内のどのトークン (意味を持った最小の文字列) をコンパイルするかを決定できます。
これらの問題すべてに共通の処理は字句解析で、ある特定の特徴をもったさまざまな文字列を識別します。このツールの名前 lex は、字句解析 (lexical analysys) からきています。lex を使用して、字句解析を扱う必要はありません。C などの標準言語で作成されたプログラムを使用して、字句解析を扱うことができます。lex が行うのはそのような C プログラムを作成することなので、lex はプログラムジェネレータと呼ばれています。
lex を使用すると、上記の処理を実行するプログラムを、短い時間で簡単に作成することができます。lex の短所は、手作業で記述した場合よりも長い C プログラムが作成されたり、実行速度が遅い C プログラムが作成されることがあるという点です。ただし、多くのアプリケーションにとっては、この問題は深刻なものではなく、lex を使用する利点の方が大きいです。
また、lex を使用して、文字数、ワード長、ワードの出現回数などの、入力テキストの特徴に関する統計データを収集することもできます。この章は、以下の節で構成されています。
字句アナライザプログラムの生成
lex ソースの作成
lex ソースの変換
C++ 符号化 (mangle) シンボル
lex と yacc の併用
オートマトン
ソース形式の概要
英語以外の言語でアプリケーションを開発する場合の lex の使用については、lex(1) を参照してください。
lex は、ユーザーが作成したソース仕様から C 言語スキャナを生成します。この仕様には、入力テキスト内で検索される文字列 (式) と、式が見つかったときに実行するアクションが示す、規則のリストが含まれています。lex 仕様の作成方法については、「lex ソースの作成」を参照してください。
字句アナライザの C ソースコードは、以下のコマンドを実行すると生成されます。
$ lex lex.l
lex.1 は、lex 仕様が記述されているファイルです。(慣例的に lex.1 という名前が使用されていますが、この名前は自由に選択できます。ただし接尾辞の .l は、他のシステムツール、特に make によって認識される規約なので、注意してください。) ソースコードは、デフォルトで、lex.yy.c という名前の出力ファイルに書き込まれます。このファイルには、指定した式が入力ファイル内で見つかるごとに 1 を返し、ファイルの終わりを検出すると 0 を返す yylex() という関数の定義が含まれています。yylex() を呼び出すと、トークンが 1 つ構文解析されます (結果は yylex() に返されます)。yylex() を再度呼び出すと、yylex() は最後に構文解析したトークンの次のトークンから構文解析を再開します。
以下の例のように、複数のファイルにまたがった仕様に対して lex を実行しても、 lex.yy.c というファイルが 1 つ生成されます。
$ lex lex1.l lex2.l lex3.l
-t オプションを付けて lex を呼び出すと、lex.yy.c の代わりに stdout へ lex の出力が書き込まれるため、以下のように出力をリダイレクトすることができます。
$ lex -t lex.l > lex.c
lex のオプションは、コマンド名とファイル名の引数の間に入力します。
入力テキストの字句解析を行う実行可能オブジェクトプログラム (スキャナ) を生成するためには、lex.yy.c (または、lex.yy.c のリダイレクト先の .c ファイル) に保存された字句アナライザのコードをコンパイルする必要があります。
lex ライブラリは、関数 yylex() を呼び出すデフォルトの main() を提供します。したがって、ユーザーは独自の main() を用意する必要はありません。このライブラリにアクセスするには、以下のように cc に -ll オプションを付けてコンパイルします。
$ cc lex.yy.c -ll
また、ユーザーは独自のドライバを作成することもできます。lex ライブラリのドライバに類似したコードを以下に示します。
extern int yylex(); int yywrap() { return(1); } main() { while (yylex()); ; }
関数 yywrap() についての詳細は、「lex ソースの作成」を参照してください。以下のように、lex.yy.c と共にドライバファイルをコンパイルすると、lex ライブラリがロードされているかのように、その main() は実行時に yylex() を呼び出します。
$ cc lex.yy.c driver.c
生成された実行可能ファイルは、stdin を読み取り、出力を stdout に書き込みます。lex による処理の流れを図 2-1 に示します。
lex のソースは、3 つまでのセクションで構成されています。その 3 つとは、定義、規則、ユーザー定義ルーチンです。規則セクションは必須です。定義とユーザー定義ルーチンのセクションは省略できますが、使用する場合には、以下に示した順に配置する必要があります。
定義 %% 規則 %% ユーザー定義ルーチン
必須の規則セクションは、区切り記号 %% で開始します。ルーチンのセクションを後に続ける場合は、規則の最後の行に %% を記述して規則のセクションをそこで終了します。区切り記号 %% は、行の先頭に入力する必要があります。%% の前に空白文字は入れないでください。2 つ目の区切り記号がない場合には、規則セクションがプログラムの終わりまで続いているとみなされます。
規則セクション内の最初の規則の前にある空白で始まる行は、関数 yylex() の開始部分の最初の中括弧のすぐ後ろにコピーされます。この機能を利用すれば、yylex() の局所変数を宣言できます。
各規則によって、検索するパターンと、そのパターンが見つかったときに実行するアクションが指定されます。パターン仕様は、行の先頭から入力する必要があります。スキャナは、パターンと一致しない入力を出力ファイルに直接書き込みます。したがって、最も単純な字句アナライザプログラムは、規則セクションの開始を示す区切り記号 %% だけが入っているプログラムです。このプログラムは、すべての入力をまったく変更を加えずにそのまま出力に書き込みます。
検索するパターンは、正規表現と呼ばれる表記法を使用して指定します。正規表現は、文字や演算子をつなぎ合せて形成します。最も単純な正規表現は、以下のような演算子が 1 つも含まれていないテキスト文字の列です。
apple orange pluto
これら 3 つの正規表現は、入力テキストに現われるこれと同じ文字列すべてと一致します。入力テキストに現われる orange をスキャナにすべて削除させたい場合には、以下のように規則を指定することができます。
orange ;
セミコロンの後にアクションが指定されていないため、スキャナは何も行わずに、元の入力テキストからこの正規表現に一致した文字列をすべて削除したテキストを出力します。つまり、出力されるテキストには、文字列 orange はまったく含まれません。
ほとんどの式は、orange のように簡単に指定することはできません。式自体は非常に長いものであったり、あるいは (こちらの方がよくある事例ですが) その式のクラスが非常に大きい可能性があります。実際、無限の大きさである可能性も考えられます。
lex 演算子 (表 2-1 を参照) を使用して、特定のクラスのあらゆる式を表すための正規表現を形成できます。たとえば + 演算子は、直前の式が 1 個以上存在することを表します (つまり、直前の式は省略可能です)。? は、直前の式が 0 個または 1 個存在することを表します。* は、直前の式が 0 個以上存在することを表します。したがって m+ は、1 個以上の m で構成される文字列すべてと一致する正規表現になります。
mmm m mmmmm
また、7* は、0 個以上の 7 で構成される文字列すべてと一致する正規表現となります。
77 77777 777
空白の 3 行目が正規表現に一致したのは、その行に 7 が 1 つも含まれていないためです。
| 演算子は、二者択一を表します。したがって、ab|cd は ab または cd と一致します。演算子 {} は、繰り返しを指定します。したがって a{1,5} は、a が 1 〜 5 個含まれている文字列と一致します。A(B{1,4}) は、ABC、ABBC、ABBBC、ABBBBC と一致します (グループ化するための記号として丸括弧 ()を使用している点に注目してください)。
角括弧 [] は、角括弧内に指定された文字列のいずれかの文字を表します。したがって [dgka] は、1 個の d、g、k、または a と一致します。角括弧内の文字は、間に空白文字や句読点を入れないで隣接して並べてください。
^ 演算子は、左角括弧の直後の文字として使用したときには、角括弧内に指定した文字を除く標準セットのすべての文字を表します。|、{、}、および ^ は、他の目的で使用する場合もあるので注意してください。
標準のアルファベットや数字 (A 〜 Z、a 〜 z、0 〜 9) の範囲は、ハイフンを使用して指定します。たとえば、[a-z] は、任意の小文字を表します。
[A-Za-z0-9*&#]
これは、任意の文字 (大文字または小文字)、任意の数字、アスタリスク、アンパサント、または # と一致する正規表現の式です。
以下に示した入力テキストを与えられると、上記の仕様を規則の 1 つとして持つ字句アナライザは、*、&、r、# を認識して、規則が指定するアクションをその認識した各文字に対して実行し、残りのテキストをそのまま出力します。
$$$$?? ????!!!*$$ $$$$$$&+====r‾‾# ((
ハイフン文字をクラスに加えるには、[-A-Z] または [A-Z-] のように、角括弧内の最初または最後の文字として入力してください。
演算子は、組み合わせて使用すると非常に効果的です。たとえば、複数のプログラミング言語の識別子を認識するための正規表現は、次のようになります。
[a-zA-Z][0-9a-zA-Z]*
これらの言語における識別子は、文字の後にゼロ、文字、または数字が続く文字列として定義されており、上記の正規表現は、その識別子を表しています。 1 組目の角括弧は、任意の文字に一致します。2 組目の角括弧は、その後の * がなければ、任意の数字または文字に一致します。
2 つの角括弧の組とそれに囲まれた文字は、後ろに 1 個の数字または文字が続く任意の文字と一致します。しかし * が付いているため、この例は後ろに任意の数の文字または数字が続く任意の文字と一致します。たとえば、この例は以下の文字列を識別子として認識します。
e not idenTIFIER pH EngineNo99 R2D2
一方、以下の文字列は識別子として認識されません。not_idenTIFIER には下線が含まれており、5times は文字でなく数字で始まっており、$hello は特殊文字で始まっているためです。
not_idenTIFIER 5times $hello
演算子文字に潜在する問題は、検索する文字としてどのようにその演算子文字を検索パターン内で指定するかということです。たとえば、前述の例は * を含むテキストを認識しません。lex では、2 つの方法のいずれかでこの問題を解決します。バックスラッシュの後の演算子文字、二重引用符で囲まれた文字 (バックスラッシュは除く) は、そのまま文字として扱われます。つまり、検索されるテキストの一部となります。
たとえば、バックスラッシュによる方法を使用して、* の後に任意の数の数字が続く文字列を認識するには、以下のパターンを使用できます。
¥*[1-9]*
¥ 自体を認識するには、バックスラッシュを 2 つ並べる必要があります (¥¥)。同様に、"x¥*x" は x*x と一致し、"y¥"z" は y"z と一致します。その他の lex 演算子については、表 2-1 で説明しています。
表 2-1 lex 演算子
式 |
説明 |
---|---|
¥x |
x が lex 演算子の場合は x |
"xy" |
x または y が lex 演算子 (¥ は除く) の場合でも xy |
[xy] |
x または y |
[x-z] |
x、y、または z |
[^x] |
x 以外の文字 |
. |
復帰改行以外の文字 |
^x |
行の先頭の x |
<y>x |
lex が開始状態 y にあるときは x |
x$ |
行の最後の x |
x? |
0 個または 1 個の x |
x* |
0 個以上の x |
x+ |
1 個以上の x |
x{m,n} |
m 〜 n 個の x |
xx|yy |
xx または yy |
x | |
x に対するアクションは、次の規則のアクション |
(x) |
x |
x/y |
x の後に y が続く場合にのみ x |
{xx} |
定義セクションからの xx の変換 |
スキャナは、規則の開始部にある正規表現に一致する文字列を認識すると、その規則の右側を検査してアクションを実行します。ユーザーは、このアクションを指定します。
見つかったトークンの型とその値を記録する、トークンを別のトークンと置換する、トークンまたはトークンの型のインスタンス数 (出現する数) をカウントする、などがアクションとして考えられます。これらのアクションは、C のプログラムとして作成します。
アクションは、任意の数の文を使用して構成できます。何らかの方法でテキストを変更したり、テキストが見つかったことを示すメッセージを出力したい場合があります。たとえば、式 Amelia Earhart を認識して、認識したことを通知するには、以下の規則を適用します。
"Amelia Earhart" printf("found Amelia");
テキスト内の長い医学用語を同義の略語に置換する処理は、以下のような規則で実現できます。
Electroencephalogram printf("EEG");
テキスト内の行数をカウントするには、行の終わりを認識して、行カウンタを増分します。
lex では、復帰改行を表す ¥n などの、標準の C エスケープシーケンスを使用します。たとえば行数をカウントするには、以下のような構文を使用できます。ここで使用している lineno は、他の C 変数と同じようにして、「定義」で宣言されています。
¥n lineno++;
C 言語の NULL 文 (1 個のコロン ;) を指定すると、入力は無視されます。したがって、以下の規則を使用した場合には、空白文字、タブ、復帰改行は無視されます。
[ ¥t¥n] ;
また、択一演算子 | は、ある規則とその次の規則のアクションが同じであることを表す際に使用することもできます。たとえば、前述の例は以下のように記述しても同じ結果になります。
" " | ¥t ¥n ;
スキャナは、式と一致したテキストを yytext[] という文字配列内に格納します。必要に応じて、この配列の内容を出力したり操作できます。実際に、lex は printf ("%s", yytext) と同義の ECHO
というマクロを備えています。
C 言語の長い文または複数の文でアクションを構成する場合には、その文を複数の行に渡って記述できます。アクションが、1 つの規則だけに対するものであることを lex に伝えるには、その C コードを中括弧で囲みます。
たとえば、数字列が見つかるごとにその数字列とそれまでに見つかった数字列の総数を出力しながら、入力テキスト全体の数字列の総数をカウントするには、次のような lex コードを使用します。
¥+?[1-9]+ { digstrngcount++; printf("%d",digstrngcount); printf("%s", yytext); }
? は、その直前の文字が 0 個または 1 個存在することを表しているので、この仕様は 0 個または 1 個のプラス記号が直前に付いた数字列と一致します。また、負の数字列の場合でも、マイナス記号の後の部分はこの仕様に一致するので、同様に数値が捕捉されます。
lex に提供されている一連の機能を使用することによって、複雑なパターンで入力テキストを処理できます。考えられる複数の仕様のうちどの仕様が一番適しているかを決定する規則、一致パターンを別の一致パターンに変換する関数、定義とサブルーチンの使用なども含まれています。
以下の例には、これまで取り上げてきた事項がまとめて記述されています。
%% -[0-9]+ printf("negative integer"); ¥+?[0-9]+ printf("positive integer"); -0.[0-9]+ printf("negative fraction, no whole number part"); rail[ ¥t]+road printf("railroad is one word"); crook printf("Here's a crook"); function subprogcount++; G[a-zA-Z]* { printf("may have a G word here:%s", yytext); Gstringcount++; }
最初の 3 つの規則では、それぞれ負の整数、正の整数、0 〜 -1 の間の負の小数が認識されます。各仕様の終わりには + が付いているので、これらの数字は 1 桁または複数桁の数字で構成されることになります。
その後の規則は、それぞれ以下に示す特定のパターンを認識します。
railroad 用の仕様は、rail と road の 2 つの音節の間に 1 個以上の空白がある場合に一致します。railroad と crook については、メッセージの代わりに同義語を出力させる仕様にすることもできます。
関数を認識する規則は、カウンタを増分します。
この規則には、いくつか重要なポイントがあります。
この規則では、複数行に渡る連続したアクションを中括弧で囲んでいます。
このアクションでは、認識した文字列を格納する lex 配列 yytext[] を使用しています。
この仕様では、* を使用して、G の後に 0 個以上の文字が続くことを表しています。
スキャナは、一致した入力テキストを yytext[] に格納する以外にも、一致した入力テキストの文字数をカウントしてその値を変数 yyleng に自動的に格納します。ユーザーは、この変数を使用して、配列 yytext[] に配置された任意の文字を参照できます。
C 言語の配列インデックスは 0 から始まります。したがって、認識した整数の 3 桁目の数字 (3 桁目の数字がある場合) を出力するには、以下のように記述します。
[1-9]+ {if (yyleng > 2) printf("%c", yytext[2]); }
記述した一連の規則によってあいまいさが生じた場合、lex は上位のルールに従ってそのあまいさを解決します。以下の字句アナライザの例では、「予約語」end は 2 番目の規則と、識別子用の 8 番目の規則に一致します。
begin return(BEGIN); end return(END); while return(WHILE); if return(IF); package return(PACKAGE); reverse return(REVERSE); loop return(LOOP); [a-zA-Z][a-zA-Z0-9]* { tokval = put_in_tabl(); return(IDENTIFIER); } [0-9]+ { tokval = put_in_tabl(); return(INTEGER); } ¥+ { tokval = PLUS; return(ARITHOP); } ¥- { tokval = MINUS; return(ARITHOP); } > { tokval = GREATER; return(RELOP); } >= { tokval = GREATEREQL; return(RELOP); }
lex は、仕様内の 2 個以上の規則と一致する場合には、最初の規則のアクションが実行されるというルールに従います。識別子用の規則の前に end やその他の予約語用の規則を配置すれば、予約語を確実に認識できます。
検索するパターンが別のパターンの接頭辞になっている場合には、また別の問題が発生する可能性があります。たとえば、上記の字句アナライザの例における最後の 2 つの規則は、> と >= を認識するようにデザインされています。
lex は、できる限り長い文字列と照合してその文字列用の規則を実行する、というルールに従います。テキストの一部に文字列 >= が含まれている場合には、スキャナは > で止まって > の規則を実行するのではなく、>= を認識して >= の規則を実行します。このルールによって、C プログラムの + と ++ が区別されます。
字句アナライザが、検索する文字列を超えて読み取る必要がある場合には、後方コンテキストを使用してください。その典型的な例が、FORTRAN の DO 文です。以下の DO 文の最初の 1 は、最初のコンマを読み取るまではインデックス k の初期値のように見えます。
DO 50 k = 1 , 20, 1
つまり、最初のコンマを読み取るまでは、この文は代入文のように見えます。
DO50k = 1
FORTRAN では空白はすべて無視されます。後ろに続く文字列が後方コンテキストであることを示すには、スラッシュ / を使用します。スラッシュはパターンの一部ではないため、この後方コンテキストは yytext[] には格納されません。
FORTRAN の DO 文を認識する規則は、以下のように記述できます。
DO/([ ]*[0-9]+[ ]*[a-zA-Z0-9]+=[a-zA-Z0-9]+,) { printf("found DO"); }
別バージョンの FORTRAN で識別子 (この例ではインデックス名) のサイズが制限されていても、この規則のように任意の長さのインデックス名を受け入れると、記述を簡素化することができます。後方コンテキストと類似した前方コンテキストの取り扱いについては、「開始条件」を参照してください。
lex では、特別な後方コンテキスト (行の終わり) を表す演算子として $ 記号を使用します。例として、行の終わりの空白文字とタブをすべて無視する規則を以下に示します。
[ ¥t]+$ ;
上記の例は、以下のように記述することもできます。
[ ¥t]+/¥n ;
パターンが行またはファイルの先頭にあるときにだけそのパターンと一致させるには、^ 演算子を使用します。たとえば、あるテキスト書式整形プログラムでは、空白文字以外の文字で行を開始する必要があるとします。その場合には、以下の規則を使用して、そのプログラムへの入力を検査できます。
^[ ] printf("error: remove leading blank");
左角括弧の内側に ^ 演算子がある場合との意味の違いに注意してください。
input()
は、文字をもう 1 つ読み取ります。
unput()
は、少し後でもう一度読み取る文字を元へ返します。
output()
は、文字を出力デバイスに書き込みます。
2 つの特殊文字 (たとえば、二重引用符など) の間にある文字をすべて無視する方法の 1 つとして、以下のように input()
を使用する方法があります。
¥" while (input() != '"');
スキャナは、最初の二重引用符を読み取ってから 2 番目の二重引用符を読み取るまでは、照合を行わずに後続の文字をすべて読み取ります。(input()
と unput()
の使い方の詳しい例については、「ユーザールーチン」を参照してください。)
これらデフォルトのマクロでは対応していない特殊な入出力 (複数ファイルへの書き込みなど) が必要な場合には、C の標準入出力ルーチンを使用してマクロ関数を書き直してください。
ただし、これらのルーチンは一貫性をもって変更する必要があります。特に、文字セットはすべてのルーチンで同じものを使用し、input()
によって返される値 0 はファイルの終わりを意味していなければなりません。また、input()
と unput()
との間の関係も維持する必要があります。関係が維持されていないと、lex の先読み処理は機能しなくなります。
独自の input()
、output(c)
、または unput(c)
を作成する場合には、まず初めに #undef input、#undef output、または #undef unput を定義セクションに記述してください。
#undef input #undef output . . . #define input() ... etc. more declarations . . .
標準のルーチンが新しいルーチンへ置換されます。詳しくは、「定義」を参照してください。
ユーザーが再定義できる lex ライブラリルーチンは、スキャナがファイルの終わりに到達すると必ず呼び出される yywrap() です。yywrap() が 1 を返した場合には、スキャナは入力の終わりで通常の後処理を行います。新しいソースから引き続き入力を受け取るようにするには、yywrap() を再定義して、継続して処理が必要なときには 0 を返すようにします。デフォルトの yywrap() は必ず 1 を返します。
ファイルの終わりを認識する標準の規則を記述することはできないので注意してください。yywrap() からのみ、ファイルの終わりを認識する標準の規則を変更することができます。input() によって返される値 0 はファイルの終わりとみなされるので、ユーザーが独自の input() を用意しないかぎり、NULL を含んだファイルを取り扱うことはできません。
複数の方法で処理される文字列を扱うための lex ルーチンとしては、yymore()、yyless(n)、REJECT があります。 与えられた仕様に一致したテキストは配列 yytext[] に格納されることに注意してください。一般に、その仕様のアクションが実行されると、yytext[] 内の文字は、その次に一致した入力ストリーム内の文字に置換されます。
一方、関数 yymore() の場合には、認識された後続の文字は yytext[] 内にすでに格納されている文字の後に追加されます。この関数を使用すれば、ある文字列が有効で、その文字列を含んだ別の文字列も有効なときなどに、処理を連続して行うことができます。
二重引用符で囲まれた文字の集まりとして文字列が定義されている言語において、文字列に二重引用符を含める指定を行うには、その引用符の直前にバックスラッシュを置く必要があります。これに一致する正規表現は多少複雑であるため、次のように記述してください。
¥"[^"]* { if (yytext[yyleng-2] == '¥¥') yymore(); else ... 通常処理 }
スキャナは、文字列 "abc¥"def" に出会うと、まず文字列 "abc¥" と照合します。次に、yymore() を呼び出して、文字列の次の部分 "def を先の文字列の後ろに追加します。文字列の終わりを示す二重引用符は、「通常処理」と記されている部分のコードで取り扱われます。
関数 yyless(n) を使用して、アクションの実行対象となる一致文字の数を指定できます。yytext[] には、式の最初の n 文字だけが保持されます。後続の処理は、nth+1 番目の文字から再開されます。
たとえば、コードの解読を行なっていて、特定の文字 (この例では、小文字または大文字の Z) で終了する文字列の半分だけを処理する場合には、以下のように記述します。
[a-yA-Y]+[Zz] { yyless(yyleng/2); ... 文字列の前半分を処理 ... }
また、REJECT 関数を使用すれば、文字列が重複していたり、文字列の一部に別の文字列が含まれている場合であっても、文字列の処理をさらに容易に行うことができます。REJECT 関数では、yytext[] の内容を変更せずに次の規則とその仕様に直接ジャンプすることによって、この処理を実現しています。たとえば、入力テキスト内の正規表現 snapdragon とその部分式 dragon の両方の出現回数をカウントするには、以下のように記述します。
snapdragon {countflowers++; REJECT;} dragon countmonsters++;
パターンが別のパターンと重複しているときの例を以下に示します。この例では、入力テキストに comediana などの文字列が含まれている場合でも、式 comedian と diana の出現回数をカウントします。
comedian {comiccount++; REJECT;} diana princesscount++;
この例のアクションはカウンタの値を増やしていくことですが、それよりもずっと複雑なアクションを指定しなければならない場合もあります。カウンタやその他必要な変数は、常に lex 仕様の開始部分の定義セクションで宣言してください。
lex の定義セクションには、複数のクラスの項目を入れることができます。最も重要なのは、外部定義、#include などの前処理文、および略語です。正式な lex ソースではこのセクションは省略可能ですが、ほとんどの場合において、これらの項目のいくつかは必要になります。前処理文と C ソースコードは、%{ と %} の行の間に記述します。
この区切り記号の間の行 (空白で始まる行も含む) は、すべて yylex() の定義の直前に lex.yy.c にコピーされます。(区切り記号で囲まれていない定義セクション内の行は、同じ場所にコピーされ、その先頭には空白が入れられます。)
定義セクションは通常、規則セクション内のアクションまたは外部にリンクされたルーチンによってアクセスされるオブジェクトの C 定義を配置する場所です。
たとえば、字句アナライザを呼び出すパーサーを生成する yacc と共に lex を使用するときには、ファイル y.tab.h をインクルードします。このファイル中で、#define を使用してトークン名を定義することができます。
%{ #include "y.tab.h" extern int tokval; int lineno; %}
#include 文と宣言の終わりを示す %} の後には、規則セクション内の正規表現の略語を置いてください。行の左側には略語、行の右側にはその定義または変換後の正規表現を記述して、両者を 1 つ以上の空白文字で区切ります。
規則の中で略語を使用するときには、その略語を中括弧で必ず囲んでください。略語を使用することにより、仕様を繰り返し記述する手間が省け、見た目にも読みやすくなります。
たとえば、「lex の高度な機能」で取り上げた lex ソースについて再検討します。定義を使用することによって、数字、文字、空白文字が後で見た時にわかりやすくなります。
D [0-9] L [a-zA-Z] B [ ¥t]+ %% -{D}+ printf("negative integer"); ¥+?{D}+ printf("positive integer"); -0.{D}+ printf("negative fraction"); G{L}* printf("may have a G word here"); rail{B}road printf("railroad is one word"); crook printf("criminal"); ... ...
開始条件を使用すると、単独の ^ 演算子よりも細かく前方コンテキストを取り扱うことができます。たとえば、行の終わりまたはファイルの始まりよりも複雑な前方コンテキストに従って、異なる規則を式に適用する場合があります。
その場合には、規則の適用条件となるコンテキスト内の変化を示すフラグを設定して、そのフラグをテストするコードを作成できます。あるいは、各規則の適用条件となるさまざまな「開始条件」を lex 用に定義することもできます。
以下の問題について考えます。
入力を出力にコピーする。ただし、文字 a で始まる行にあるワード magic をすべて first に変更する。
b で始まる行にある magic をすべて second に変更する。
c で始まる行にある magic をすべて third に変更する。フラグを使用してこの問題を扱った場合のコード例を以下に示します。
すでに説明したように、ECHO は printf ("%s", yytext) と同義の lex マクロです。
int flag %% ^a {flag = 'a'; ECHO;} ^b {flag = 'b'; ECHO;} ^c {flag = 'c'; ECHO;} ¥n {flag = 0; ECHO;} magic { switch (flag) { case 'a': printf("first"); break; case 'b': printf("second"); break; case 'c': printf("third"); break; default: ECHO; break; } }
開始条件を使用してこれと同じ問題を扱うには、以下のような行を lex の定義セクションに記述する必要があります。定義セクションには、任意の順序で条件を記述することができます。
%Start name1 name2 ...
ワード Start は、S または s と短縮できます。この条件を参照する場合は、規則の先頭で角括弧 <> を使用します。たとえば、スキャナの開始条件が name1 のときにだけ認識される規則は、以下のようになります。
<name1>式
開始条件に入るには、以下のアクションの文を実行します。
BEGIN name1;
上記の文は、開始条件を name1 に変更します。通常の状態に戻す場合は、以下の文を使用します。
BEGIN 0;
この文は、スキャナの初期条件をリセットします。
規則は、複数の開始条件によってアクティブにすることができます。たとえば、以下のような開始条件にすることもできます。
<name1,name2,name3>
前置演算子 <> で開始されていない規則は、すべてアクティブです。
開始条件を使用した場合には、前述の例は以下のように記述できます。
%Start AA BB CC %% ^a {ECHO; BEGIN AA;} ^b {ECHO; BEGIN BB;} ^c {ECHO; BEGIN CC;} ¥n {ECHO; BEGIN 0;} <AA>magic printf("first"); <BB>magic printf("second"); <CC>magic printf("third");
ユーザーは、他のプログラミング言語でルーチンを使用する場合と同じようにして lex ルーチンを使用できます。複数の規則で使用されるアクションのコードは、1 度だけ作成して、必要なときに呼び出すことができます。定義の場合と同様に、このルーチンによってプログラムの記述が簡素化され、コードも読みやすくなります。
「lex と yacc の併用」で説明している put_in_tab1() 関数は、lex 仕様のユーザールーチンのセクションで使用するのに適した関数です。
このセクションにルーチンを配置するもう 1 つの理由は、コードを使用する規則が 1 つしかない場合であっても、重要なコードを強調したり規則セクションを簡素化するためです。例として、/* と */ に挟まれた部分がコメントになっている C のような言語のコメントを無視する以下のルーチンについて説明します。
%{ static skipcmnts(); %} %% "/*" skipcmnts(); ... ... /* 残りの規則 */ %% static skipcmnts() { for(;;) { while (input() != '*') ; if (input() != '/') unput(yytext[yyleng-1]) else return; } }
この例には、重要なポイントが 3 つあります。
マクロ unput(c)
は、読み取った最後の文字を元に返して、コメントが **/ で終わっている場合でも最後の / を読み取ることができるようにします。
その場合、スキャナは、* を読み取った後にその次の文字が終端の / でないことを検知して読み取りを継続します。
式 yytext[yyleng-1] は、読み取った最後の文字を取り出します。
関数名が C++ の符号化 (mangle) シンボルの場合には、lex はそれを復号化された (demangle) 形式で出力します。符号化 C++ シンボルは、すべて復号化シンボルの後で [] でくくられます。通常の符号化 C++ 関数名 (メンバー関数と非メンバー関数を含む) の場合には、関数プロトタイプがその復号化 (demangle) の形式として使用されます。
たとえば、以下の関数名は、
_ct_13Iostream_initFv
以下のように出力されます。
Iostream_init::Iostream_init()
C++ の静的コンストラクタと静的デストラクタは、復号化されて以下の形式で出力されます。
static constructor function for
または、
static destructor function for
たとえば、以下のデストラクタは、
_std_stream_in_c_Fv
以下のように復号化されます。
static destructor function for _stream_in_c
C++ 仮想テーブルシンボルが符号化された時の名前は以下の形式になります。
_vtbl_class
_vtbl_root_class_derived_class
lex の出力では、仮想テーブルシンボルが復号化された時のの名前は以下のように出力されます。
virtual table for class
virtual table for class derived_class derived from root_class
たとえば、以下を復号化すると、
_vtbl_7fstream
以下の形式になります。
virtual table for fstreamH
また、以下を復号化すると、
_vtbl_3ios_18ostream_withassign
以下の形式になります。
virtual table for class ostream_withassign derived from ios
一部の C++ シンボルは、仮想テーブルに対するポインタです。符号化された時の名前は、以下の形式になります。
_ptbl_class_filename
_ptbl_root_class_derived_class_filename
lex の出力では、これらのシンボルが復号化された時の名前は以下のように出力されます。
pointer to virtual table for class in filename
pointer to virtual table for class derived class derived from root_class in filename
たとえば、以下を復号化すると、
_ptbl_3ios_stream_fstream_c
以下の形式になります。
pointer to the virtual table for ios in _stream_fstream_c
また、以下を復号化すると、
_ptbl_3ios_11fstreambase_stream_fstream_c
以下の形式になります。
_stream_fstream_c
pointer to the virtual table for class fstreambase derived from ios in _stream_fstream_c
コンパイラプロジェクトに取り組んでいる場合、または入力言語の妥当性を検査するプログラムを開発する場合には、システムツールの yacc (第 3 章「yacc - コンパイラコンパイラ」を参照) を使用することがあります。yacc は、パーサーを生成します。パーサーは、入力を解析してその入力の構文に誤りがないことを検証するプログラムです。
多くの場合、コンパイラの開発では lex と yacc を併用して作業を行うことができます。
すでに説明したように、プログラムは、関数 yylex() を繰り返し呼び出して、lex が生成したスキャナを使用します。yacc が生成したパーサーはこれと同じ名前を使用して字句アナライザを呼び出すので、lex と yacc を併用する場合にこの名前は好都合です。
lex を使用してコンパイラ用の字句アナライザを作成する場合は、lex の各アクションはトークンを返す文で終了してください。トークンとは、整数値を使用して定義された語句です。
返されるトークンの整数値によって、字句アナライザが何を見つけたかがパーサーに示されます。その後、パーサー (yacc によって呼び出された yyparse()) は制御を再開して、字句アナライザに対して別の呼び出しを行い、次のトークンを取得します。
コンパイラでは、見つかったその言語の予約語 (予約語がある場合) によって、または識別子、定数、算術演算子、関係演算子のどれが見つかったのかによって、トークンの値は異なります。後者の場合は、アナライザはトークンの厳密な値も指定する必要があります。つまり、識別子、定数の値 (9 や 888 など)、算術演算子の種類 (+ や * など)、関係演算子の種類 (= や > など) を指定する必要があります。
以下に、C のような言語のトークンを認識するスキャナの lex ソースの一部を示します。
表 2-2 トークンを認識する lex ソースの例
返されるトークンと、tokval に割り当てられる値は、整数です。プログラムを理解しやすくするために、整数値をそのまま使用するのではなく、BEGIN、END、WHILE などの説明的な語句を使用してパーサーが解釈する整数を表してください。
整数値と語句の関連付けは、C パーサーを呼び出すルーチンの #define 文を使用して定義します。たとえば、以下のように定義します。
#define BEGIN 1 #define END 2 ... #define PLUS 7 ...
また、いずれかのトークン型の整数を変更する場合は、その特定の整数が現われる個所をすべて変更するのではなく、パーサーの #define 文を変更してください。
yacc を使用してパーサーを生成するには、lex ソースの定義セクションに以下の文を挿入します。
#include "y.tab.h"
-d オプションを付けて yacc を呼び出したときに作成されるファイル y.tab.h は、BEGIN や END などのトークン名を有効な整数に関連付ける #define 文を、生成されたパーサーに提供します。
表 2-2 の予約語は、返される整数値だけで十分表すことができます。他のトークン型については、変数 tokval にその整数値が保存されます。
この変数は広域的に定義されているので、パーサーと字句アナライザはその変数にアクセスできます。yacc も、同じ用途の変数 yylval を提供します。
表 2-2 には tokval に値を割り当てる方法が 2 種類示されている点に注目してください。
1 つは、関数 put_in_tabl() による方法です。関数 put_in_tabl() は、識別子または定数の名前と型をシンボルテーブルに配置するので、コンパイラはその名前と型を参照できます。
put_in_tabl() は、現在位置に加えて型の値も tokval に割り当てるので、パーサーはその情報をすぐに使用して入力テキストの構文上の正当性を判定できます。関数 put_in_tabl() は、コンパイラの作成者がパーサーのユーザールーチンセクションに配置するルーチンです。
もう 1 つは、特定の整数を tokval に割り当てる方法です。tokval には、スキャナが認識した算術演算子または関係演算子を表す特定の整数が割り当てられます。
たとえば、#define 文によって変数 PLUS が整数 7 に関連付けられている場合には、+ が認識されると、そのアクションは + を表す値 7 を tokval に割り当てます。
スキャナは、演算子の一般クラス (つまり、ARITHOP または RELOP で表される整数) を、パーサーに返す値で示します。
lex と yacc を併用するときには、どちらを先に実行しても構いません。以下のコマンドを実行すると、ファイル y.tab.c にパーサーが生成されます。
$ yacc d grammar.y
すでに説明したように、-d オプションを使用すると、ファイル y.tab.h が作成されます。このファイルには、yacc によって割り当てられた整数のトークン値とユーザー定義のトークン名を関連付ける #define 文が含まれています。lex は以下のコマンドで呼び出すことができます。
$ lex lex.l
次に、以下のコマンドを使用して出力ファイルのコンパイルとリンクを行うことができます。
$ cc lex.yy.c y.tab.c -ly -ll
-ll オプションで lex ライブラリをロードする前に、-ly オプションで yacc ライブラリをロードして、提供されている main() が yacc パーサーを呼び出すようにしています。
また、CC と共に yacc を使用するには (特に、.l ファイル内の yyback()、yywrap()、yylook()() などのルーチンが外部 C 関数になる場合)、コマンド行に以下のコマンドを入力する必要があります。
$ CC -D__EXTERN_C__ ... ファイル名
入力テキスト内の式の認識は、lex が生成する決定性有限オートマトンによって実行されます。-v オプション を使用すると、有限オートマトンを表す少量の統計情報が出力されます。(有限オートマトンの詳細な説明と、lex における有限オートマトンの重要性については、『Aho, Sethi, and Ullman text, Compilers: Principles, Techniques, and Tools』(Addison-Wesley, 1986) を参照してください。)
lex は、テーブルを使用してその lex の有限オートマトンを表します。有限オートマトンで使用できる状態の最大数は、デフォルトで 500 に設定されています。多数の規則または非常に複雑な規則が lex ソースに含まれている場合には、lex ソース の定義セクションに以下のようなエントリをもう 1 つ置くことによって、そのデフォルト値を大きくすることができます。
%n 700
このエントリは、700 個の状態を扱うことができる大きさのテーブルを作成するように lex に指示します。-v オプションを使用すると、選択する必要のある状態の数が表示されます。
状態遷移の最大数を 2000 よりも多くするには、指定パラメータを a にします。
%a 2800
lex コマンドで使用できるオプションの一覧については、lex(1) を参照してください。
lex ソースファイルの一般形式を以下に示します。
定義 % 規則 % ユーザールーチン
定義セクションでは、以下の項目を自由に組み合わせて使用できます。
以下の形式による略語の定義
name space translation
以下の形式で取り込まれたコード
% { C code % }
以下の形式による開始条件
Start name1 name2 ...
以下の形式による内部配列サイズの変更
%x nnn
nnn は配列サイズを表す 10 進整数で、x はそのパラメータを選択します。
内部配列サイズの変更は、以下のように表すことができます。
表 2-3 内部配列サイズp |
位置 |
n |
状態 |
e |
ツリーノード |
a |
遷移 |
k |
パック文字クラス |
o |
出力配列サイズ |
規則セクションの行は以下の形式になります。
式 アクション
アクションは、中括弧で囲むことによって、次の行まで続けることができます。
lex 演算子用の文字を以下に示します。
" ¥ [] ^ - ? . * | () $ / {} <> +
重要な lex 変数、関数、マクロを以下に示します。
表 2-4 lex 変数、関数、およびマクロyytext[] |
char の配列 |
yyleng |
int |
yylex() |
関数 |
yywrap() |
関数 |
yymore() |
関数 |
yyless(n) |
関数 |
REJECT |
マクロ |
ECHO |
マクロ |
input() |
マクロ |
unput(c) |
マクロ |
output(c) |
マクロ |