4    入力言語解析プログラムおよびパーサの作成

プログラムが入力を受け取りその入力を処理する場合,処理を行う前にその入力を解析する手段が必要です。 プログラム内の 1 つまたは複数のルーチンを使用して入力の解析を行うことも,入力をメイン・プログラムに渡す前に,フィルタ処理を行う別のプログラムを使用して入力の解析を行うこともできます。 入力の複雑さに合わせて,入力インタフェースも複雑になります。 複雑な入力を解析するには,かなり大量のコードが必要とされます。 解析を行う際には,プログラムにとって有効なかたまりに入力を分割します。

この章では,入力インタフェースを開発するのに有効な次の 2 つのツールについて説明します。

lex および yacc プログラムと,それらのプログラムが生成するプログラムとの混同を避けるため,この章では,lexyacc をツールと呼びます。

この章では,次の事項について説明します。

4.1    字句解析プログラムの動作

lex が生成する字句解析プログラムは,決定性有限状態オートマトンと呼ばれます。 これは,字句解析プログラムが存在可能な状態の数を限定し,また,次の入力文字を読み取り,解析した時点で字句解析プログラムが移行する状態を決定する規則を提供します。

コンパイルされた字句解析プログラムには,次の機能があります。

図 4-1 に,startgood,および bad という,3 つの状態を持つ簡単な字句解析プログラムを示します。 字句解析プログラムは,文字の入力ストリームを読み取ります。 まず,start の状態で開始され,最初の文字を受け取ると,規則と比較します。 文字が英文字である (規則と適合している) 場合,プログラムは good 状態に移行し,英文字でない場合には,bad 状態に移行します。 プログラムは条件に適合しない文字を見つけるまでは,good 状態で,bad 状態に移行すると終了します。

図 4-1:  簡単な有限状態のモデル

オートマトンは,生成された字句解析プログラムによる入力ストリームの 1 つまたは 2 つ以上の文字の先読みを許可します。 たとえば,lex 仕様ファイルが,文字列 ab を見つける規則と,文字列 abcdefg を探す別の規則を定義しているとします。 abcdefh という文字列が入力されると,字句解析プログラムは abcdefg と照合を行うために十分な文字 (abcdef) を読み取ります。 g ではなく h があるために abcdefg との照合が無効になると,字句解析プログラムは,ab を探す規則に戻ります。 入力された最初の 2 文字が ab と照合するので,その規則に指定されたアクションを実行し,cdefh という残りの入力と照合する規則を探します。

4.2    lex による字句解析プログラムの作成

lex ツールを使用して,文字ストリーム入力を受け取りその入力をプログラムアクションに解釈する C 言語字句解析プログラムを作成することができます。lex を使用するには,次の記述が含まれた仕様ファイルを作成しなければなりません。

実際に仕様ファイルに記述するフォーマットと論理については,4.3 節を参照してください。

lex ツールは,仕様ファイル内の情報を使用して字句解析プログラムを生成します。 このツールによって生成された解析プログラムは yy.lex.c という名前になります。 yy.lex.c プログラムには,仕様ファイルから生成される解析コードとともに標準の関数セットが含まれています。 解析コードは,yylex 関数に含まれています。 lex によって生成された字句解析プログラムは,簡単な文法構造と正規表現を認識します。 次のコマンドを使用して,簡単な lex 解析プログラムをコンパイルすることができます。

% cc -ll yy.lex.c
 

-ll オプションは,コンパイラに lex 関数ライブラリを使用するように指定します。 このコマンドにより実行可能な字句解析プログラムが生成されます。 プログラムに複雑な文法規則が使用されているか,または文法規則がまったく使用されていない場合は,入力の適切な処理を確実にするため (lexyacc ツールを併用して) パーサを作成してください。 詳細については,4.6 節を参照してください。

yy.lex.c 出力ファイルは,lex ライブラリ関数をサポートする C コンパイラを持つシステムならどのシステムにでも移植することができます。

4.3    lex 仕様ファイル

lex 仕様ファイルのフォーマットは次のとおりです。

[ { definitions } ] %% [ { rules } ] [ %% { user subroutines } ]

最初の 2 つのパーセント記号 ( %% ) は,規則の始まりを示すものです。 仕様ファイルのそれ以外の部分は,すべてオプションです。 最小の lex 仕様ファイルには,定義,規則,およびユーザ・サブルーチンは含まれていません。 パターン照合のアクションが指定されていない場合は,字句解析プログラムは,入力パターンを変更することなく出力パターンにコピーします。 したがって,この最小の仕様ファイルは,すべての入力をそのまま出力にコピーする解析プログラムを生成します。

この節では,次の事項について説明します。

4.3.1    置換文字列の定義

lex 仕様ファイル中の最初の 2 つのパーセント記号の前に,文字列マクロを定義することができます。lex ツールは,字句解析プログラムを生成する際に,そこで定義されたマクロを展開します。 この部の行の中で,カラム 1 から開始され,かつ %{ デリミタおよび %} デリミタに囲まれていない行は,lex 置換文字列を定義しています。 置換文字列の定義は,一般的に次のようなフォーマットで記されます。

name  translation

nametranslation の要素は,少なくとも 1 つの空白またはタブで区切り,name は英文字で開始します。 仕様ファイルの規則の部分で,中カッコ ( { } ) で囲まれた文字列 name を発見すると,lex は,nametranslation で定義された文字列に変更して,中カッコを削除します。

たとえば,DE の名前を指定するには,仕様ファイルの中で最初の %% デリミタの前に次の定義を指定します。

D           [0-9]
E           [DEde][-+]{D}+
 

上記の定義を規則部で使用して,整数と実数の識別をより簡潔にすることができます。

{D}+           printf("integer");
{D}+"."{D}*({E})?|
{D}*"."{D}+({E})?|
{D}+{E}        printf("real");
 

また,定義部には次の項目を含めることもできます。

4.3.2    規則

仕様ファイルの規則部には,lex が生成する字句解析プログラムの制御を定義する決定が含まれています。 その規則は,2 カラムのテーブルの形になっています。 テーブルの左のカラムには正規表現が,テーブルの右のカラムには正規表現に対応するアクションが記述されています。 アクションは C 言語プログラム・フラグメントで,最も単純なものとしてセミコロンだけ (nul 文) を指定することも,また必要に応じてより複雑なものを指定することもできます。 lex が作成する字句解析プログラムには,正規表現とアクションの両方が含まれています。 正規表現に照合した文字列を検索すると,それに対応するアクションを実行します。

たとえば,integer という文字列を探し,発見した場合はメッセージをプリントする字句解析プログラムを作成するには,次のような規則を定義します。

integer         printf ("found keyword integer");
 

上記の例では,メッセージの文字列をプリントするために,C 言語ライブラリ関数の printf を使用しています。 規則の最初の空白またはタブは,正規表現の終わりを示します。 1 つのアクションに 1 つの文だけを使用する場合は,正規表現 (上記の例では integer) の右に文を記述します。 2 つ以上の文を使用する場合,または文が 2 行以上にわたる場合には,C 言語プログラムと同様に,アクションを中カッコで囲んでください。 たとえば,次のように記述します。

integer         {
           printf ("found keyword integer");
           hits++;
           }
 

ファイル内の単語を英国式スペリングから米国式スペリングに変更する字句解析プログラムには,次のような規則が記述されている仕様ファイルがあります。

colour          printf("color");
 
mechanise       printf("mechanize");
 
petrol          printf("gas");
 

ただし,上記の仕様ファイルは完全なものではありません。 petroleum という単語が,gaseum に変更されるためです。

4.3.2.1    正規表現

標準の拡張正規表現に加えて,lex表 4-1 に示す正規表現を解釈します。

表 4-1:  lex の正規表現演算子

演算子 名前 解説
{name} 中カッコ 中カッコで囲まれた変数は,仕様ファイルの最初に定義されている文字列を意味します。 たとえば,{digit}digit として定義されている文字列と置き換えられます。 カウント式と混同しないでください。 ともに lex で識別されます。
" " 引用符 引用符でリテラル文字列を囲むとテキスト文字列として解釈します。 たとえば,"$" と指定すると,lex はドル記号を演算子として解釈しません。 引用符は,文字列の中で部分的に使用することもできます。 たとえば,"abc++"abc"++" は,どちらもリテラル文字列 abc++ を照合します。
a/<b スラッシュ 2 番目の文字 (b) が最初の文字 (a) の直後に続く場合のみ,最初の文字 (a) を照合します。 たとえば,dog/cat は,cat が dog の直後に続いている場合にのみ,dog を照合します。
<x> 山カッコ 開始条件を囲みます。 指定された開始条件 <x> に字句解析プログラムが適合する場合にのみ,アクションを実行します。 開始条件 ONE が行頭にあるという条件を意味する場合,<ONE> は山形記号 ( ^ ) 演算子と同じ意味になります。
\n 改行 正規表現の中では実際の改行文字は使用しません。 基本正規表現の \n と混同しないよう注意してください。
\t タブ リテラルのタブ文字 (16 進数の 09) を照合します。
\b バックスペース リテラルのバックスペース文字 (16 進数の 08) を照合します。
\\ バックスラッシュ リテラルのバックスラッシュ文字を照合します。
\digits Digits エンコードが 3 桁の 8 進数で表される文字です。
\xdigits xDigits エンコードが 16 進の整数で表される文字です。

通常,ホワイト・スペース (空白またはタブ) は,正規表現の終わりとそれに関連するアクションの始まりを区切るために使用されます。 式に空白やタブを入れる場合には,それらを引用符 ( " " ) で囲みます。 大カッコ ( [ ] ) で囲まれていない正規表現の中の空白にはすべて引用符を使用してください。

4.3.2.2    照合規則

仕様ファイルの規則部内にある 2 つ以上の正規表現が現在の入力と照合する場合には,字句解析プログラムは次の基準を使用して,適用する規則を決定します。

  1. 一致する文字数が最も多い文字列に適用する。

  2. 一致する文字数が同じ場合は,最初に出現した規則を適用する。

たとえば,次のような規則がある場合を考えてみましょう。

integer         printf("found int keyword");
[a-z]+          printf("found identifier");
 

上記の順に規則が適用され,integers という語が入力された場合,[a-z]+ ワードの中の 8 文字と照合しますが,一方 integer は,7 文字にしか照合しないために,解析プログラムは,入力を "identifier" とみなします。 しかし,入力が integer の場合には,両方の規則とも照合します。 この場合,keyword の規則が先に出現するために,lex はこれを選択します。 int のような短い入力は,integer という文字列には照合しないので,lex では "identifier" の規則を選択します。

4.3.2.2.1    文字列を照合するためのワイルドカード文字の使用

字句解析プログラムでは,照合するもののうち最長の文字列が最初に選択されるために,意図した目的以上の影響をもたらす正規表現を使用しないように注意しなければなりません。 たとえば,ピリオドの後にアスタリスクを指定してアポストロフィで囲んだ ( '.*' ) 正規表現は,アポストロフィで囲まれるすべての文字列を認識するために適切であるように見えますが,字句解析プログラムは,可能な限り長い文字列に照合させようと,さらに先を探し,離れたアポストロフィを検出します。 次は,その例です。

'first' quoted string here, 'second' here
 

このような入力があると,字句解析プログラムは,次の文字列を照合します。

'first' quoted string here, 'second'
 

ピリオド演算子は改行文字を照合しないので,それほど広範囲に影響を与えることはありません。.* のような式は,現在の行で停止します。 次のような式を使用して,このようなアクションを予防しようとしないでください。

[.\n]+
 

このような式を指定すると,字句解析プログラムは,入力ファイルの全体を読み取り,内部バッファのオーバフローが発生します。

次の規則は,前述のテキスト例から引用符で囲まれたより小さな範囲の文字列 `first' および `second' を検索します。

'[^'\n]*'"
 

この規則では,`first' を照合した後,検索を停止します。 検索されるアポストロフィには,別のアポストロフィまたは改行文字を除く任意の文字数が続き,次に,2 番目のアポストロフィが続いているためです。 次に,解析プログラムは再び該当する文字列を探し,`second' を検出します。 また,この文字列は,引用符の付いた空の式 ( ' ' ) も照合します。

4.3.2.2.2    文字列内の文字列の検索

字句解析プログラムは,通常,入力ストリームを区切ります。 それぞれの式と照合する文字列を,可能な限りすべて探すわけではありません。 文字はそれぞれ,1 回だけカウントされます。 たとえば,入力テキストで `she' と `he' と照合するものをカウントするためには,次の規則が考えられます。

she       s++;
he        h++;
\n        ;
.         ;
 

最後の 2 つの規則は検索したい 2 つの文字列を除いたすべてを無視します。 ただし,`she' には `he' が含まれているため,字句解析プログラムは,`she' に含まれる `he' は認識しません。

特殊なアクション REJECT は,この動作を抑止するためのものです。 この指示は解析プログラムに,REJECT を含む規則を実行させ,次の規則を実行する前に,入力ポインタの位置を最初の規則が実行される前に戻します。 たとえば `she' に含まれる `he' と照合するものをカウントするには,次の規則を使用します。

she       {s++; REJECT;}
he        {h++; REJECT;}
\n        ;
.         ;
 

字句解析プログラムは,`she' をカウントした後に,入力ストリームをリジェクトして,`she' に含まれる `he' をカウントします。 この例では,`she' は `he' を含んでいますが,その逆はあり得ないため,`he' での REJECT アクションは省略することができます。 しかし他の場合,たとえば,ワイルドカードの正規表現と照合した場合,両方のクラスに属する入力文字を決定することは,困難になります。

REJECT が有効なのは,通常,入力ストリームを区切ることが目的ではなく,むしろオーバーラップしたり,相互に含み合うことができるような,入力の中の項目のインスタンスをすべて検出することが目的である場合です。

4.3.2.3    アクション

字句解析プログラムが,仕様ファイルの規則部中の正規表現の中の 1 つを照合した場合は,その正規表現に対応するアクションを実行します。 入力ストリームの中の文字列すべてを照合する規則を使用しない限り,字句解析プログラムは,入力を標準出力にコピーします。 したがって,ただ入力を出力にコピーするだけの規則は作成しないでください。 規則に含まれない条件を見つけるために,この省略時の出力を使用してください。

lex で生成された解析プログラムを使用して yacc が生成するパーサのための入力を処理する場合は,入力文字列のすべてを照合する規則を作成してください。 その規則は,yacc が解釈できるような出力を生成しなければなりません。yacc および lex を使用する際の詳細については,4.5 節を参照してください。

4.3.2.3.1    ヌル・アクション

ある正規表現に対応する入力を無視するには,C 言語の空文であるセミコロン ( ; ) をアクションとして使用してください。 たとえば,次のようにします。

[ \t\n]          ;
 

この規則では,3 つのスペーシング文字 (空白,タブ,および改行文字) を無視しています。

4.3.2.3.2    複数の式に対する同一アクションの使用

いくつかの異なった式に対して同じアクションを使用するには,最後の式以外の各式に対して 1 つのアクションが縦線文字 ( | ) のみで構成されている連続した規則を作成します。 それらの規則の最後の式には,通常どおり,そのアクションを指定します。 縦線文字は,それを含む規則に対するアクションが,次の規則に対するアクションと同じであることを示しています。 たとえば,空白,タブ,および改行文字 (4.3.2.3.1 項を参照) を無視するには,次のような規則を使用します。

" "     |
"\t"    |
"\n"    ;
 

この例の特殊文字シーケンス (\n\t) を囲む引用符は必要ではありません。

4.3.2.3.3    一致した文字列のプリント

仕様ファイルの規則部の中の正規表現に,どのテキストが一致するかを検出するには,その式に対するアクションのうちの 1 つとして,C 言語の printf 関数を入力します。 字句解析プログラムが入力ストリーム中から照合する文字列を検出すると,解析プログラムはその照合した文字列を,yytext と呼ばれる外部文字配列に加えます。 照合した文字列をプリントするには,次のような規則を使用します。

[a-z]+          printf("%s", yytext);
 

この方法で出力をプリントすることはよくあります。 仕様ファイルの定義部にマクロとして,この printf 文などの式を定義することもできます。 このアクションが ECHO として定義されている場合には,規則部のエントリは,次のようになります。

[a-z]+            ECHO;
 

マクロの定義についての詳細は,4.3.1 項を参照してください。

4.3.2.3.4    一致した文字列の長さの検出

字句解析プログラムに特定の正規表現に一致する文字数を検出させるには,外部変数 yyleng を使用します。 たとえば,次の規則は,入力ワード中のワード数および文字数の両方をカウントします。

[a-zA-Z]+       {words++; chars += yyleng;}
 

このアクションによって,一致したワードの中の文字数が合計され,その値を chars 変数に与えます。

次の式では,一致した文字列の中から,最後の文字を検出します。

yytext[yyleng-1]
 

4.3.2.3.5    入力の追加

字句解析プログラムでは,規則ファイルの中の正規表現と完全に照合する前に,入力が不足することがあります。 この場合,その規則に対するアクションの中に,lex 関数の yymore への呼び出しを入力します。 通常は,入力ストリームからの次の文字列が,yytext の現在のエントリに重ね書きされます。yymore アクションによって,次の文字列は,入力ストリームから yytext の現在のエントリの最後に追加されます。 たとえば,次の構文を含む文字列を考えてみてください。

次の規則によって,このような字句特性を処理することができます。

\"[^"]* {
        if (yytext[yyleng-l] == '\\')
          yymore();
        else
          ... normal user processing
      }
 

この字句解析プログラムによって,"abc\"def" 文字列 (引用符はこのとおり) が検索されると,まず,最初の 5 文字 "abc\ を照合します。 バックスラッシュによって,yymore の呼び出しが行われ,文字列の "def の部分が "abc の後に追加されます。 "normal user processing" というラベルの付いたアクション・コードの部分では,文字列を終了する引用符を処理しなければなりません。

4.3.2.3.6    入力へ文字を戻す

字句解析プログラムは,正規表現との照合が完了している文字すべてを必要としない場合があります。 または,再び別の照合をチェックするために,照合した文字を入力ストリームに戻す必要が生じる場合もあります。 文字を入力ストリームに戻すには,yyless(n) 呼び出しを使用します。 変数 n には,現在の文字列で戻さない文字数を入れます。 ストリームの中の n 番目を超えた文字は,入力ストリームに戻ります。 この関数によって,スラッシュ演算子 ( / ) と同様に先読みを行いますが,yyless には先読みに対してより強い制御機能があります。yyless(0) を使用した場合,REJECT と同じ機能を持ちます。

2 回以上テキストを処理するには,yyless 関数を使用してください。 たとえば,x=-a などの C 言語の式は複数の意味に解釈されあいまいです。x = -a であるとも,または x -= a として計算される,一般的には使用されない x = x - a という式とも解釈されます。 このあいまいな式を x = -a として扱い,警告メッセージをプリントするには,次のような規則を使用してください。

=-[a-zA-Z]     {
          printf("Operator (=-) ambiguous\n");
          yyless(yyleng-1);
          ... action for =-...
          }
 

4.3.3    標準の入出力ルーチンの使用または変更

lex プログラムは,使用する字句解析プログラム用の入出力 (I/O) ルーチンを提供します。 仕様ファイルの中の C コード・フラグメントに,次のようなルーチンへの呼び出しを含めてください。

上記のルーチンは,マクロ定義として実装されています。 サブルーチン部の中で,ユーザ自身のコードを同名のルーチンとして記述することによって,マクロ指定を変更することができます。 これらのルーチンによって,外部ファイルと内部の文字の関係が定義されています。 それらの定義を変更する場合は,すべて同じ方法で変更してください。 変更する際は,次の規則に従ってください。

ユーザ自身のコードを記述する場合は,仕様ファイルの定義部の中で,ユーザの定義するコードの前に,これらのマクロ定義を削除する必要があります。

%{
#undef    input
#undef    unput
#undef    output
}%
 

注意

unputinput の関係を変更すると,先読み機能が動作しません。

lex で生成した字句解析プログラムを,標準入力から標準出力に引き渡すための簡易変換プログラムおよびまたは認識プログラムとして使用している場合は,lex ライブラリ (libl.a) を使用すれば,フレームワークに書き込まないですみます。 このライブラリには,main ルーチンがあり,yylex 関数の呼び出しを行います。 標準の lex ライブラリによって,字句解析プログラムは,最大 100 までの文字をバックアップできます。

空文字 (16 進の 00) を含む入力ファイルを読み取る必要がある場合は,input ルーチンの別のバージョンを作成しなければなりません。input の標準のバージョンでは,空を読み取ると 0 の値が返され,この値はファイルの最後を示すものとして解釈されます。

lex が生成する字句解析プログラムは,input ルーチン,output ルーチン,および unput ルーチンを使用して,文字 I/O を処理します。 したがって,yytext で値を返すため,解析プログラムでは,これらのルーチンが使用する文字表現を使用します。 ところが,各文字は,内部では小さい整数で表されています。 標準ライブラリについては,この整数は,コンピュータが文字を表すために使用するビット・パターンの値です。

通常,a という文字は,文字定数 a と同じ形式で表されます。 別の I/O ルーチンによって,この解釈を変更する場合は,仕様ファイルの定義部に変換テーブルを含めなければなりません。 変換テーブルでは,始めの行と終わりの行が %T キーワードのみで,次のような書式の行が含まれます。

[{integer } {characterstring }]

次の例では,英字の A および数字の 0 (ゼロ) と,それらの標準の値を関連づけるテーブル・エントリを示しています。

%T
{65} {A}
{48} {0}
%T
 

4.3.4    ファイルの終わりの処理

字句解析プログラムがファイルの終わりに到達すると,yywrap というライブラリ・ルーチンを呼び出します。 このルーチンは,1 の値を返して,字句解析プログラムに通常のラップアップ (処理終了時に行われる動作) を続けるように示します。 しかし,解析プログラムが 2 つ以上のソースから入力を受け取る場合は,yywrap 関数を変更しなければなりません。 新しい関数は,新しい入力を得て,0 の値を字句解析プログラムに返さなければなりません。 0 のリターン値は,プログラムが処理し続けることを示します。

コマンド行で複数ファイルを指定した場合は,ファイルの終端の処理に関しては,1 つの入力ファイルとして扱われます。

また,yywrap には,特に要約レポートとテーブルをプリントするコードを含めることもできます。yywrap 関数は,yylex に強制的に入力の終わりを認識させる唯一の方法です。

4.3.5    生成されたプログラムへのコードの引き渡し

仕様ファイルの定義部または規則部のいずれにも変数を定義することができます。 仕様ファイルを処理すると,lex は,指定ファイル中の文を字句解析プログラムに変更します。lex が解釈できない仕様ファイルの行はすべて,変更されずに字句解析プログラムに渡されます。 次の 4 つのエントリのタイプは,変更されずに字句解析プログラムに渡されます。

4.3.6    開始条件

どんな規則でも,開始条件に指定することができます。 字句解析プログラムは,開始条件に含まれている場合にのみ,その規則を認識します。 現在の開始条件は,常時変更可能です。

仕様ファイルの定義部の中の開始条件を定義するには,次のフォーマットの行を使用します。

% Start [name1] [ [name2 ...] ]

name1 記号および name2 記号は,条件を表します。 条件の数には制限がなく,どのような順番でもかまいません。Start は,S または s のいずれかに省略することができます。 開始条件の名前には,C の予約語や,変数,フィールドなどの名前として定義されたものを使用することはできません。

仕様ファイルの規則部の中で開始条件を使用する場合は,その規則の最初に,山カッコ ( < > ) で開始条件の名前を囲みます。 次のフォーマットで開始条件を含む規則を定義します。

[<name1] [ [,name2 ...] ] [> expression]

字句解析プログラムは,名前のうちのいずれかと対応する条件にある場合にのみ,expression を認識します。 特定の開始条件に lex を移行させるには,次のアクション文を規則のアクション部分で実行してください。

BEGIN name;
 

開始条件はこの文によって name に移行します。 通常の状態に戻すには,次のアクションを使用してください。

BEGIN 0;
 

前述の構文ダイアグラムに示したように,複数の開始条件で,1 つの規則がアクティブになります。 たとえば,次のようにします。

<start1,start2,start3>  [0-9]+  printf("integer");
 

この規則では,3 つの名前の開始条件のうちいずれかで,整数を検出した場合にのみ,integer をプリントします。 開始条件で始まらない規則は常にアクティブです。

4.4    字句解析プログラムの生成

lex に基づく字句解析プログラムの生成は,次の 2 つの手順で行います。

  1. lex を実行して仕様ファイルを C 言語プログラムに変更する。 その結果生成されたプログラムは,lex.yy.c というファイルに存在する。

  2. lex.yy.ccc -ll コマンドで処理して,プログラムにコンパイルし,それを lex サブルーチンのライブラリとリンクする。 結果として生成された実行可能プログラムは,a.out という名前になる。

たとえば, lex 仕様ファイルが lextest である場合は,次のコマンドを入力します。

% lex lextest
% cc lex.yy.c -ll
 

省略時の設定である lex I/O ルーチンは,C 言語標準ライブラリを使用しますが,lex が生成する字句解析プログラムでは必須ではありません。 I/O ルーチンをライブラリで使用しないようにするには,inputoutput,および unput のルーチンの別のコピーをいれます。 詳細については,4.3.3 項を参照してください。

lex コマンドのオプションについては,表 4-2 を参照してください。

表 4-2:  lex コマンドのオプション

オプション 説明
-n 有限状態マシン用にユーザがテーブル・サイズを設定した場合に,省略時の値として生成される統計値の要約を出力しない。 状態マシンの指定についての詳細は, lex(1) を参照。
-t 生成された字句解析プログラム・コードを lex.yy.c ファイルではなく,標準出力に書き込む。
-v 有限状態マシンの一般的な統計値の要約を 1 行表示する。

lex は,中間ファイルおよび出力ファイルに決まった名前を使用するため,所定のディレクトリ内には,lex で生成されたプログラムが 1 つしか存在できません。 ただし,-t オプションを使用して代わりのファイル名を指定した場合は,この限りではありません。

4.5    yacc と lex の併用

lex ツールは,単独で使用された場合,簡単な 1 ワードの入力を認識するか,または統計の入力を受け取る字句解析プログラムを作成します。 また,yacc などのパーサ生成プログラムとあわせて lex を使用することもできます。yacc ツールは,パーサという,複数ワードの入力の構造を解析するプログラムを生成します。 このパーサ・プログラムは,lex が生成する字句解析プログラムと組み合わせても効率よく動作します。 字句解析プログラムは,正規表現だけを認識し,それらをトークンと呼ばれる文字パッケージの形式に分離します。

トークンは,パーサまたは字句解析プログラムのいずれかで定義される,最小の独立した意味単位のことです。 トークンには,データ,言語キーワード,識別子,または他の言語構文のパーツが含まれます。 トークンは,どのような文字列でもかまいません。 トークンは,ワードの 1 部分またはそのワード全体,あるいは連続した複数のワードでもかまいません。yacc ツールによって,分脈に関係なく多種多様な文法を認識するパーサが生成されます。 このようなパーサが入力トークンを認識するために,lex で生成された字句解析プログラムなどのプリプロセッサが必要になります。

lex で生成された字句解析プログラムが,yacc で生成されたパーサ用のプリプロセッサとして使用される場合は,字句解析プログラムが入力ストリームを区切ります。 パーサは,その結果として生成された断片に構造を割り当てます。lex および yacc がプログラムを生成する方式,および,そのプログラムが組み合わされて動作する方式については図 4-2 を参照してください。lexyacc によって生成されたプログラムと他のプログラムを併用することも可能です。

図 4-2:  lex および yacc による入力パーサの生成

パーサ・プログラムは,そのプログラム用のプリプロセッサ (字句解析機能) に yylex という名前を付けなければなりません。 この名前は,生成する字句解析プログラムの解析コードに lex が指定する名前です。 字句解析プログラムを単独で使用する場合には,lex ライブラリの省略時の設定である main プログラムが,yylex ルーチンを呼び出します。 しかし,yacc が生成するパーサがロードされてそのパーサの main プログラムが使用される場合は,パーサによって yylex が呼び出されます。 この場合,各 lex の規則は,次に示した行で終わらなければなりません。 ここでは,該当するトークン値が返されます。

return(token);
 

yacc で使用されるトークン名を検出するためには,yacc 文法ファイルの最後の部分に,次の行を入れることによって,パーサの一部 (yacc 出力ファイル) として字句解析プログラム (lex 出力ファイル) をコンパイルします。

#include lex.yy.c
 

別の方法として,yacc 出力 (y.tab.h ファイル) を lex プログラム仕様ファイルに含めることができます。 これによって,y.tab.h で定義されているトークン名を使用することもできます。 たとえば,文法ファイルが good という名前で,仕様ファイルが better という名前の場合は,次のコマンド・シーケンスによって,最終プログラムが作成されます。

% yacc good
% lex better
% cc y.tab.c -ly -ll
 

yacc パーサを呼び出す main プログラムを作成するには,yacc ライブラリ (上記の例の -ly) を,lex ライブラリの前にロードしなければなりません。lexyacc プログラムは,どちらを先に生成してもかまいません。

4.6    yacc によるパーサの作成

yacc を使用してパーサを生成するには,入力データ・ストリーム,およびパーサがそのデータに対して行う処理を指定する文法ファイルを記述する必要があります。 文法ファイルには,入力の構造,規則が認識される際に呼び出されるコード,および基本入力を行うルーチンが含まれています。

yacc ツールは,文法ファイルの情報を使用することによって,yyparse を生成します。 このプログラムによって,入力処理が制御されます。 このパーサは,yylex 入力ルーチン (字句解析プログラム) を呼び出して,入力ストリームからトークンを取り出します。 このパーサは,文法ファイルの構造規則に従って,これらのトークンを組織化します。 この構造規則は,文法規則と呼ばれます。 パーサが文法規則を認識すると,パーサは,その規則に与えられたユーザ・コード (アクション) を実行します。 アクションは,値を返し,また,他のアクションによって返された値を使用します。

yacc が認識および使用する仕様以外に,文法ファイルには次の関数を含めることができます。

yacc ツールは,文法ファイルを処理して y.tab.c という,C 言語関数およびデータを含むファイルを生成します。 cc コマンドを使用してコンパイルすると,この関数は,yyparse という結合された関数を形成します。 この yyparse 関数は,入力トークンを得るために,yylex という字句解析プログラムを呼び出します。 この解析プログラムは,パーサがエラーを検出するか,または解析プログラムが演算の終わりを示す endmarker トークンを返すまで入力を与え続けます。 エラーが発生して,yyparse を復旧できない場合,yyparse は,main 関数に 1 の値を返します。endmarker トークンが検出された場合には,yyparsemain 関数に 0 の値を返します。

アクション・コードおよび他のサブルーチンを記述するには,C プログラミング言語を使用してください。yacc プログラムは,文法ファイル内で多くの C 言語構文規約を使用します。

4.6.1    main および yyerror の関数

文法ファイルの中には,main および yyerror という関数ルーチンが含まれていなければなりません。yacc の初期導入作業を少なくするために,yacc ライブラリには,mainyyerror ルーチンの簡易版が備えられています。 ローダまたは cc コマンドで -ly オプションを使用することによって,これらのルーチンをインクルードすることができます。 main ライブラリ関数のソース・コードは次のとおりです。

main()
{
     yyparse();
}
 

yyerror ライブラリ関数のソース・コードは,次のとおりです。

#include <stdio.h>
 
void yyerror(s)
        char *s;
{
        fprintf( stderr, " %s\n" ,s);
}
 

yyerror の引数には,通常,文字列構文エラーなどのエラー・メッセージを含む文字列を指定します。

これらは,かなり制約のあるプログラムです。 入力行番号を保持しておき,構文エラーの検出時にエラー・メッセージとともにそれをプリントするなど,これらのルーチンをより精巧なものにしてください。 また,外部整数変数 yychar の値も使用することができます。 この変数には,エラーが検出されたときの,先読みトークン番号が含まれます。

4.6.2    yylex 関数

指定する yylex プログラムの入力ルーチンは,次の処理が実行できなければなりません。

トークンは,入力ルーチンによって送られたパターンを yyparse に通知する記号または名前です。 記号は,次の 2 つのクラスのいずれかにあります。

たとえば,字句解析プログラムが,数字,名前,および演算子のいずれでも認識する場合は,これらの要素が終端記号とみなされます。yacc 文法が認識する非終端記号は,EXPRTERM,および FACTOR などの要素です。 入力ルーチンが入力ストリームを WORDNUMBER,および PUNCTUATION のトークンに分ける例を,"I have 9 turkeys." という入力文の例で考えてみましょう。 解析プログラムは,次の文字列とトークンをパーサに渡します。

文字列 トークン
I WORD
have WORD
9 NUMBER
turkeys WORD
. PUNCTUATION

yyparse 関数には,入力ルーチンが渡すトークンの定義が含まれてなければなりません。yacc コマンドの -d オプションを使用することによって,プログラムが y.tab.h というファイル名のトークンのリストを生成します。 このリストは,#define 文のセットで,これによって,yylex で,パーサと同じトークンが使用可能になります。

パーサとの競合を回避するために,yy の英字で始まる名前は使用しないでください。lex を使用して入力ルーチンを生成しても,C 言語で記述してもかまいません。lex の使用方法についての詳細は,4.3 節を参照してください。

4.7    文法ファイル

yacc 文法ファイルは,次の 3 つの部で構成されています。

2 つのパーセント記号 ( %% ) は,文法ファイルの部を分けます。 ファイルを読みやすくするために,パーセント記号は,単独で 1 行に書きます。 文法ファイルのフォーマットは,次のとおりです。

declarations ] %% rules [ %% programs ]

規則の始まりと規則それ自体を示す ( %% ) 以外の,文法ファイルの各部分は,すべてオプションです。 最小の yacc 文法ファイルには,次に示すように,定義およびプログラムはまったく含まれていません。

%%
rules
 

yacc プログラムでは,名前または予約記号の中を除いて,文法ファイルの中の空白,タブ,および改行文字は無視されます。 これらの文字を使用することによって,文法ファイルを読みやすくすることができます。 名前または予約記号の中では,空白,タブ,改行文字は,いずれも使用しないでください。

4.7.1    宣言

yacc 文法ファイルの宣言部には,次の要素が含まれます。

変数宣言または定数宣言は,次のように,C プログラミング言語の構文に準拠します。

type-specifier  declarator;

この構文では,type-specifier はデータ型キーワードで,declarator は変数または定数の名前です。 名前の長さに制限はなく,英字,ドット,下線,および数字で構成されています。 名前を数字で始めることはできません。 大文字と小文字は区別されます。 文法規則の本体で使用される名前は,トークンまたは非終端記号を表します。

宣言部で名前を宣言しない場合は,非終端記号としてのみその名前を使用することができます。 それぞれの非終端記号は,規則部中で,少なくとも 1 つの規則の左側にその名前を使用して定義してください。#include 文は C 言語構文の場合と同じで,同じ機能を持ちます。

yacc ツールには,表 4-3 にリストしたような,キーワードのセットがあります。 これらのキーワードは,生成されたパーサの処理条件を定義しています。 各キーワードは,パーセント記号 ( % ) で始まり,その後にトークンのリストがあります。

表 4-3:  yacc の処理条件の定義キーワード

キーワード 機能
%left 他のトークンと左結合するトークンを識別する。
%nonassoc 他のトークンと結合しないトークンを識別する。
%right 他のトークンと右結合するトークンを識別する。
%start 開始記号の名前を識別する。
%token yacc が受け入れるトークン名を識別する。 宣言部ですべてのトークン名を宣言すること。

同じ行でリストされたすべてのトークンは,同じ優先順位のレベルと結合性を持っています。 ファイルの中の行は後に宣言されたものほど優先順位,または結合力が高くなります。 たとえば,次のようになります。

%left     '+'  '-'
%left     '*'  '/'
 

この例は,4 つの算術演算子の優先順位と結合性を説明しています。 加算 ( + ),減算 ( - ) の演算子は,左結合であり,同じく左結合である乗算 ( * ),除算 ( / ) の演算子よりも,優先順位が低いことを表しています。

4.7.1.1    グローバル変数の定義

字句解析プログラムだけでなく,一部またはすべてのパーサ・アクションで使用されるグローバル変数も定義することができます。 パーセント記号と中カッコ (%{%}) からなる 2 つの照合した記号で変数に対する宣言を囲むことによって,定義します。 たとえば,プログラム全体のすべての部分で var 変数を使用可能にするためには,文法ファイルの宣言部の中に次のエントリを含んでください。

%{ int var = 0; %}
 

4.7.1.2    開始記号

パーサは,開始記号と呼ばれる特殊記号を認識します。 開始記号は,文法規則に付けられた名前です。 この文法規則には,解析される言語の中で最も一般的な構造が記述されています。 これが最も一般的な構造であるため,入力ストリームの解析をトップ・ダウンでパーサを開始させる構造になっています。%start キーワードを使用することによって,宣言部の中で開始記号を宣言します。 開始記号を宣言しない場合には,パーサは,ファイル中の最初の文法規則の名前を使用します。

たとえば,C 言語の手順を解析する際に,パーサが認識する最も一般的な構造は次のようになります。

main()
{
   code_segment
}
 

開始記号は,この構造を記述する規則を示さなければなりません。 ファイル内の残りのすべての規則は,処理の中でより低いレベルの構造体を識別する方法を記述します。

4.7.1.3    トークン番号

トークン番号は,トークン名を表す,負でない整数になります。 字句解析プログラムによって,トークン番号は,実際のトークン名ではなくパーサに渡されるので,プログラムはトークンに同じ番号を割り当てければなりません。

yacc 文法ファイルで使用されるトークンにトークン番号を割り当てることができます。 トークン番号をトークンに割り当てなかった場合,yacc は,次の規則を使用してトークン番号を割り当てます。

注意

0 (ゼロ) のトークン番号は使用できません。 この番号は endmarker トークンに割り当てられます。 この番号を再定義することはできません。

文法ファイルの宣言部の中のトークン (リテラル文字を含む) に番号を割り当てるためには,%token 行のトークン名の直後にゼロを含まない正の整数をいれます。 この整数は,名前か,またはリテラル文字のトークン番号です。 各番号は,ユニークでなければなりません。yacc と一緒に使用される字句解析プログラムは,入力の終わりに到達する際のトークンに,0 (ゼロ) または負の値を返さなくてはなりません。

4.7.2    文法規則

yacc 文法ファイルの規則には,1 つまたは複数の文法規則が含まれます。 各規則には,構造が記述され,名前が付けられます。 文法規則のフォーマットは,次のとおりです。

[nonterminal-name : BODY ;]

この構文では,BODY は 0 以上の名前とリテラルのシーケンスになります。 コロンとセミコロンは,yacc の句読点として必要です。

同じ非終端名を伴う文法規則がいくつかある場合は,( | ) 縦線を使用すれば,左の非終端名を何度も入力する必要がなくなります。 また,縦線で結合されたすべての規則の最後にだけ,セミコロン ( ; ) を使用してください。 次の文法規則の 2 つの例は,ともに同じ意味になります。

例 1

A  :  B  C  D  ;
A  :  E  F  ;
A  :  G  ;
 

例 2

A  :  B  C  D
   |  E  F
   |  G
   ;
 

4.7.2.1    空文字列

空文字列と照合する非終端記号を示すためには,次のように,セミコロンだけを規則の本体に使用してください。

nullstr  :  ;
 

4.7.2.2    入力の終わりマーカ

字句解析プログラムが入力ストリームの終わりに達すると,パーサに endmarker と呼ばれる特別なトークンを送ります。 このトークンは 0 のトークン値を持ち,入力の終わりをシグナル通知します。 パーサが endmarker トークンを受け取ると,すべての入力が定義された文法規則に割り当てられているかどうか,また,処理された入力が yacc 文法ファイルに定義されているとおり完全な単位を形成しているかどうかを,パーサがチェックをします。 入力が完全な単位である場合は,パーサは停止します。 入力が完全な単位ではない場合は,パーサによってエラーと停止がシグナル通知されます。

字句解析プログラムでは,ファイルやレコードなどが終わる時点で,endmarker トークンを送らなければなりません。

4.7.2.3    yacc パーサのアクション

それぞれの文法規則に,パーサが入力ストリームの中でその規則を認識するたびに,実行するアクションを指定することができます。 アクションが値を返し,次に,前のアクションによって返された値を得ます。 また,字句解析プログラムは,トークンのための値を返すこともできます。

アクションは,C 言語文で入出力を行ったり,サブプログラムを呼び出したり,外部ベクトルと変数の変更を行ったりします。 文法ファイルのアクションは,中カッコ ( { } ) で囲んだ 1 つ以上の文を使用して,指定します。 次の例は,アクションが含まれている文法規則です。

A  :  '('B')'
   {
     hello(1, "abc" );
   };
XXX  :  YYY  ZZZ
     {
     printf("a message\n");
     flag = 25;
     }
 

アクションは,番号の付いた yacc パラメータ・キーワード ($1, $2 など) を使用することによって,他のアクションで生成された値を受け取ることができます。 これらのキーワードは,左から右に読み,規則の右側の構成要素によって返された値を表示します。 たとえば,次のようになります。

A  :  B  C  D  ;
 

このコードが実行された場合,$1 は,B を認識した規則によって返される値を持ち,$2 は,C を認識した規則によって返される値を持ち,また,$3 は,D を認識した規則によって返された値を持ちます。

値を返すためには,アクションで擬似変数 $$ をある値に設定します。 たとえば,次のアクションでは,1 の値を返します。

{ $$ = 1;}
 

省略時の設定では,ある規則の値は,$1 の最初の要素の値になります。 そのため,次のようなフォーマットの規則には,アクションは必要ありません。

A : B ;
 

規則が終了する前に解析処理を制御するには,規則の中央にアクションを記述します。 この規則で,$n パラメータを使用して値が返された場合は,その後のアクションで,その値を使用することができます。 したがって,次の規則は,x を 1 に設定し,y を,C によって返された値に設定します。

A  :  B
         {
            $$ =1;
         }
      C
         {
            x = $2;
            y = $3;
         }
    ;
 

内部的には,yacc は,中央にあるアクションの新しい非終端記号名を作成して,この名前と空文字列を照合させる新しい規則を作成します。 したがって yacc は,前述のプログラムを,次のフォーマットで記述されているかのように処理します。 ここでは,$ACT は,空のアクションになります。

$ACT :    /* null string */
     {
      $$ = 1;
     }
     ;
A    :    B  $ACT  C
     {
       x = $2;
       y = $3;
     }
     ;
 

4.7.3    プログラム

yacc 文法ファイルのプログラム部には,規則部の中のアクションで使用することができる C 言語関数が含まれています。 また,字句解析プログラム yylex を記述する場合は,プログラム部に追記してください。

4.7.4    文法ファイルの使用上のガイドライン

この項では,yacc 文法ファイルを使用する際の一般的なガイドラインを説明します。 次の処理に関して解説しています。

4.7.4.1    コメントの使用

文法ファイルのコメントには,プログラムの実行内容が説明されています。 名前を指定できるファイルであれば文法ファイルのどこにでも,コメントを書くことができます。 ただし,ファイルを読みやすくするために,規則の中の関数ブロックの最初の部分に独立した行としてコメントを記述するようにしてください。yacc 文法ファイルのコメントは,C 言語プログラムのコメントと,まったく同じフォーマットを持っています。 つまり,スラッシュとアスタリスク ( /* ) で始まり,アスタリスクとスラッシュ ( */ ) で終わります。 その例を次に示します。

/* This is a comment on a line by itself. */
 

4.7.4.2    リテラル文字列の使用

リテラル文字列は,アポストロフィ,すなわち一重引用符 ( ' ' ) で囲まれた,1 つまたは複数の文字です。 バックスラッシュ ( \ ) は,C 言語のように,リテラル文字列の中ではエスケープ文字になり,C 言語の特別文字シーケンスは,次のように認識されます。

\n 改行文字
\r リターン
\' アポストロフィまたは一重引用符
\\ バックスラッシュ
\t タブ
\b バックスペース
\f 改ページ
\nnn 8進法の値 nnn

\0 または 0 (空文字) は,絶対に文法規則では使用しないでください。

4.7.4.3    文法ファイルのフォーマットに関するガイドライン

次のガイドラインを使用すると,yacc 文法ファイルをより読みやすくすることができます。

4.7.4.4    文法ファイル中の再帰の使用

再帰とは,規則自身を定義するために関数を使用する処理のことです。 言語定義では,通常,これらの規則は次のフォーマットになります。

rule      :    end case
          |    rule, end case
 

rule の最も簡単な例は,end case で,rule は,2 つ以上の end case で構成することもできます。rule の定義に rule を使用する 2 行目のエントリが,再帰です。 この規則が与えらると,パーサは,ストリームが最終の end case に減少するまで入力を繰り返します。

yacc ツールでは,左再帰の文法をサポートしています。 右再帰はサポートしていません。 規則中に再帰を使用する場合は,常にその規則の一番左のエントリとして (例に示したように),規則名への呼び出しを含めてください。 次の例で示すように,規則名の呼び出しが行の後方に出現した場合,パーサの内部のスタック・スペースが不足し,クラッシュすることがあります。

rule      :    end case
          |    end case, rule
 

4.7.4.5    文法ファイルのエラー

yacc ツールは,すべての文法指定のセットに対応するパーサを生成することはできません。 文法規則自身が矛盾している場合,または yacc が持つ方法とは別の方法で照合させる必要がある場合は,yacc は,パーサを生成しません。 通常,yacc は,エラーを示すメッセージを表示します。 これらのエラーを訂正するためには,文法ファイルの規則を設計し直すか,または yacc では処理できないパターンを認識する字句解析プログラムを生成してください。

4.7.5    パーサによるエラー処理

パーサが,入力ストリームを読み取る場合には,その入力ストリームが,文法ファイルの規則に一致しないことがあります。 文法ファイルにエラー処理ルーチンがある場合,パーサは,データを再入力させたり,不正データをスキップしたりすることができます。 または,データの削除および回復のアクションを行うことができます。 たとえば,パーサがエラーを検出した場合には,構文解析ツリー記憶を再生したり,シンボル・テーブル・エントリのクリーンアップあるいは変更を行ったり,またはこれ以上の出力を生成しないようにスイッチの設定を行ったりする必要があります。

エラーが発生すると,エラー処理ルーチンを使用するまでパーサは停止しています。 さらにエラーを検出するために入力の処理を続けるには,パーサがさらに入力を認識できるような入力ストリームのある場所からパーサを再起動してください。 エラーの発生後にパーサを再起動する方法としては,エラーに続くトークンのうちのいくつかを破棄して,入力ストリームのその場所からパーサを再起動する方法があります。

yacc ツールには,error という,特殊なトークン名があります。 これはエラー処理のために使用されます。 文法ファイルの入力エラーが発生する可能性があるところにこのトークンを置いてください。 そうすれば,回復ルーチン error を使用することができます。 入力エラーが,error トークンによって保護された位置に発生した場合は,パーサは,正常なアクションではなく,error トークンのアクションを実行します。

1 つのエラーで多数のエラー・メッセージが生成されないように,パーサは,エラーの後の 3 つのトークンが正常に処理されるまで,エラー状態を保持します。 パーサがこのエラー状態の間に,別のエラーが発生した場合には,パーサは入力トークンを破棄し,メッセージを表示しません。 また,error アクションで引数を使用すると,パーサが処理を再開する時点を指定することができます。 たとえば,次のように入力します。

stat  :  error ';'
 

エラーが発生すると,この規則によりパーサは,そのトークンおよびそれに続くトークンをすべて飛ばして,次のセミコロンを探すように指示されます。 そのエラーの後のトークンおよび次のセミコロンまでのトークンは,すべて破棄されます。 パーサがセミコロンを検出すると,この規則を修正してこの規則に関連したクリーンアップ・アクションをすべて実行します。

4.7.5.1    エラーの訂正

対話型の環境で入力ストリームを入力した場合,データ・ストリームの行を再入力することによって,入力エラーを訂正することができます。 たとえば,次のように入力します。

input   :    error '\n'
        {
          printf(" Reenter last line: " );
        }
        input
       {
         $$ = $4;
       }
       ;
 

この例では,パーサは,エラーの後の 3 つの入力トークンに対してエラー状態のままになっています。 最初の 3 つのトークンでエラーが検出された場合は,パーサはトークンを削除して,メッセージを表示しません。 回復するには,yyerrok; 文を使用してください。 パーサは yyerrok; 文を検出すると,エラー状態をそのままにして通常の処理を開始します。 回復の例は次のとおりです。

input   :    error     '\n'
        {
          yyerrok;
          printf( "Reenter last line: " );
        }
        input
       {
         $$ = $4
       }
       ;
 

4.7.5.2    先読みトークンの消去

先読みトークンは,次にパーサによってチェックされるトークンです。 エラーが発生すると,先読みトークンは,エラーが検出された箇所のトークンになります。 しかし,エラー回復アクションに,処理を再開するための正確な位置を検出するコードが含まれている場合は,そのコードの先読みトークンも変更しなければなりません。 先読みトークンを消去するには,yyclearin; 文をエラー回復アクションに含みます。

4.8    パーサの動作

yacc プログラムによって,文法ファイルは,C 言語プログラムに変更されます。 C 言語プログラムは,コンパイルされて実行されると,文法規則に従って入力を解析します。

パーサは,スタックを持つ,有限状態マシンです。 パーサは次の入力トークン (先読みトークン) を読み取り,記憶することができます。 現在の状態は,常に,スタックの最上部にある状態です。 有限状態マシンの状態は,小さい整数によって表されます。 最初は,マシンは 0 (ゼロ) の状態で,スタックには 0 (ゼロ) のみが含まれています。 先読みトークンはまったく読み取りません。

マシンは,次の 4 つのアクションのうちのいずれかを実行することができます。

shift n パーサは,現在の状態をスタックにプッシュし,n を現在の状態にし,先読みトークンを消去する。
reduce r 引数 r は規則の番号。 パーサは,入力ストリームの r 番の規則に照合するトークン・シーケンスを検出すると,出力ストリームの規則番号を持つシーケンスに置換される。
accept パーサによってすべての入力がチェックされ,それらの入力は文法指定と照合し,その入力が,最も高いレベルの構造 (開始記号として定義) を満たすように認識される。 このアクションは,先読みトークンがエンド・マーカで,しかもパーサが正常に完了したことを示している場合にのみ有効。
error パーサは入力ストリームの処理を続行できず,文法指定で定義された規則への正常な照合を続けられない。 パーサが探している入力トークンは,先読みトークンとともに,正当な結果を出力できない。 パーサはエラーを報告し,その状況を回復して,解析を再開しようとする。

パーサは,1 つの処理手順の中で,次のアクションを実行します。

  1. パーサは,現在の状態に基づき,次のアクションを決めるのに先読みトークンが必要かどうかを決定する。 パーサに先読みトークンが必要なときに,それがない場合は,パーサは,次のトークンを得るために yylex を呼び出す。

  2. 現在の状態と,必要であれば先読みトークンを使用して,パーサはその次のアクションを決定し,実行する。 これによって,スタックにプッシュされるか,あるいはスタックからはじき出される状態で終了し,先読みトークンは処理されるか,あるいは処理されずに残される場合もある。

4.8.1    shift アクション

shift アクションは,パーサの使用する最も一般的なアクションです。 パーサが shift を実行すると,常に,先読みトークンがあります。 次のパーサ・アクションの規則を考えてみます。

IF shift 34
 

パーサが,この規則を含む状態で,しかも先読みトークンが IF である場合は,パーサは次の手順を実行します。

  1. 現在の状態をスタックにプッシュする。

  2. 状態 34 を現在の状態に指定する (スタックの最上部に置く)。

  3. 先読みトークンを消去する。

4.8.2    reduce アクション

reduce アクションを使用すると,スタックが肥大化するのを防ぐことができます。 パーサは,入力ストリームに対して規則の右側に照合し,入力ストリームのトークンを規則の左側に置換する準備ができると,縮小アクションを使用します。 パーサは,先読みトークンを使用してパターンが完全に照合したかを決定する必要のあることがあります。

縮小アクションは,個々の文法規則によって関連付けられています。 また,文法規則もまた,小さい整数を持つために,shift アクションと reduce アクションの番号の意味は混乱が生じやすくなっています。 たとえば,次の 2 つのアクションの 1 番目は,文法 18 を表し,2 番目はマシン状態 34 を表しています。

reduce 18
IF shift 34
 

たとえば,次の規則の縮小を考えてみてください。

A  :  x y z ;
 

パーサによって,スタックから一番上の 3 つの状態が取り出されます。 取り出された状態の番号は,規則の右側の記号の番号と等しくなります。 これらの状態は,xy,および z を認識している間,スタックに置かれるものです。 上記の状態が取り出されると,パーサは,規則が処理される前 (規則 A を認識して,その規則を満たすのが必要な状態) のパーサの状態になります。 パーサは,元に戻された状態と規則の左側の記号を使用して,goto アクションを実行します。 このアクションは,Ashift と似ています。 新しい状態が得られると,スタックにプッシュされて,解析が続きます。

goto アクションは,トークンの通常の shift とは異なります。 先読みトークンは shift で消去されますが,goto によっては作用されません。 上記の例で 3 つの状態が取り出されると,元に戻された状態には,次のようなエントリが含まれています。

A  goto 20
 

このエントリによって,状態 20 がスタックにプッシュされて,現在の状態となります。

また,reduce アクションは,ユーザが指定するアクションや値の取り扱いにおいても重要です。 規則が縮小されると,パーサは,スタックを調整する前にユーザが規則に入れたコードを実行します。 状態を保持するスタックだけでなく,そのスタックと平行して実行される別のスタックによって,字句解析プログラムとアクションから返された値が保持されます。shift が実行されると,外部変数 yylval は値スタックにコピーされます。 ユーザが指定するコードを実行した後,パーサが縮小を行います。 パーサによって goto アクションが実行されると,外部変数 yylval は,値スタックにコピーされます。 名前がドル記号 ( $ ) で始まる yacc 変数は,値スタックを表します。

4.8.3    あいまいな規則およびパーサの競合

入力文字列を 2 つ以上の違った方法で構造化できる場合は,文法規則はあいまいになります。 次は,その例です。

expr : expr '-' expr
 

上記の規則では,2 つの式の間に - (マイナス) 符号が入っているので,算術式になりますが,この文法規則では,すべての複雑な入力をどのように構成するかは指定されません。 たとえば,次のような場合です。

expr - expr - expr
 

上記の規則を使用すると,プログラムは,この入力を左結合にするか,または右結合にするのかのどちらかで構成します。

(  expr - expr ) - expr
 

または

expr - ( expr - expr )
 

上記の 2 つの数式を評価すると,別の結果が生じます。

パーサがあいまいな規則を処理する場合は,入力を処理する際に 4 つのアクションのうち,いずれを実行するかを混同することがあります。 次の 2 種類の競合が生じる可能性があります。

Shift/reduce 競合 ある規則が,shift アクションまたは reduce アクションのいずれを使用しても正しく評価できる,別の結果を出力する。
Reduce/reduce 競合 ある規則が,2 つの異った reduce アクションのいずれを使用しても正確に評価できる,2 つの異ったアクションを生成する。

shift/shift 競合はあり得ません。

このような競合は,規則があまり完全でない場合に生じます。 たとえば,次の入力と前述のあいまいな規則を考えてみてください。

a - b - c
 

入力の最初の 3 つの部分を読み取った後,パーサは,次の部分を持ちます。

a - b
 

この入力は,文法規則の右側に照合します。 パーサは,この規則を適用して,入力を縮小させることができます。 この規則を適用した後に,入力は次のようになります。

expr
 

これは規則の左側です。 次に,パーサは入力の最後の部分を次のように読み取ります。

- c
 

この時点で,パーサは次の部分を持ちます。

expr - c
 

この入力を縮小することによって,左結合の解釈が生まれます。

ただし,パーサは入力ストリームで先読みを行うこともできます。 入力の最初の 3 つの部分を受け取った後に,入力ストリームの読み取りを続行して,次の 2 つの部分を得た場合は,パーサは,次の入力を持ちます。

a - b - c
 

この規則を一番右の 3 つの部分に適用することによって,b - cexpr に縮小します。 このとき,パーサは,次のものを持ちます。

a - expr
 

再度,式を縮小することによって,右結合の解釈になります。

したがって,パーサによって最初の 3 つの部分が読み取られたところで,2 つの正当なアクション,すなわち,shift か,reduce のうちの 1 つを選択することができます。 パーサにアクションを決定する規則がまったくない場合は,shift/reduce 競合が生じます。

パーサが 2 つの有効な reduce アクションの中から選択が可能な場合は,同様の状態が発生します。 このような状態を reduce/reduce 競合といいます。

shift/reduce 競合あるいは reduce/reduce 競合が発生する場合,yacc は選択可能な場合は,有効な方法を選んで,パーサを生成します。 選択するための規則がない場合,yacc は次の規則を使用します。

パーサがどの規則を認識しているか認識する前にアクションを実行しなければならない場合には,規則内のアクションを使用することによって,競合が発生することがあります。 このような場合,前述の規則を使用すると,間違ったパーサが生成されます。 このために,yacc は,前述の 2 つの規則を適用することによって解決された,shift/reduce 競合と reduce/reduce 競合の数を報告します。

4.9    デバッグ・モードの使用

通常の操作では,外部整数変数 yydebug は 0 に設定されています。 しかし,ゼロ以外の値に設定した場合,パーサは,実行記述ファイルを生成します。 この記述ファイルには,パーサが受け取る入力トークン,および各トークンに対して行うアクションが含まれています。 次の 2 つの中のいずれかの方法で,yydebug 変数を設定することができます。

4.10    簡易計算機プログラムの作成

例 4-1 および例 4-2 に示す lex で生成された字句解析プログラムおよび yacc で生成されたパーサのプログラムを使用して,加算,減算,乗算,および除算の演算を実行する簡単な卓上計算機のプログラムを作成することができます。 また,この計算機プログラムでは,1 つの小文字で指定した変数に値を代入して,計算することもできます。 プログラムを含むファイルは次のとおりです。

慣例で,lexyacc のプログラムには,ファイル名の接尾文字として,それぞれ .l.y の英字が使用されます。例 4-1例 4-2 は,実際に入力するためのプログラム・フラグメントの例です。 この項の処理手順は,ファイルが現在のディレクトリにあることを前提としています。

示された順序どおりに,次の手順を実行して,lexyacc を使用した計算機プログラムを作成してください。

  1. 次のコマンドを使用して,yacc 文法ファイルを処理する。

    yacc では,-d オプションを指定すると,C 言語ソース・コードに加えて,使用するトークンを定義するファイルを作成します。

    % yacc -d calc.y
     
    

    このコマンドで,次のファイルが作成されます。

  2. 次のコマンドを使用して lex 仕様ファイルを処理する。

    % lex calc.l
     
    

    このコマンドは lex.yy.c ファイルを作成し,lex が字句解析プログラム用に作成した C 言語ソース・ファイルを含んでいます。

  3. 次のコマンドを使用して 2 つの C 言語ソース・ファイルをコンパイルし,リンクする。

    % cc -o calc y.tab.c lex.yy.c
     
    

  4. ls コマンドを使用して次のファイルが作成されたことを確認する。

calc コマンドを入力すると,プログラムを実行することができます。 その後で,数字と演算子を代数的に入力することができます。 リターンを押すと,このプログラムは演算の結果を表示します。 次のように,変数に値を与えることができます。

m=4
 

次のように,計算で変数を使用することができます。

m+5
9
 

4.10.1    パーサのソース・コード

例 4-1 は,calc.y ファイルの内容です。 このファイルには,yacc 文法ファイルの 3 つの部である,宣言,規則,およびプログラムのエントリが入っています。 このファイルで定義された文法には,演算子の優先順位による通常の代数学の階層がサポートされています。

ファイルのさまざまな要素の記述とそれらの関数は,例の後に示されています。

例 4-1:  計算機のパーサ・ソース・コード

%{
#include <stdio.h>    [1]
 
int regs[26];    [2]
int base;
 
%}
 
%start list    [3]
 
%token DIGIT LETTER    [4]
 
%left '|'    [5]
%left '&'
%left '+' '-'
%left '*' '/' '%'
%left UMINUS  /*supplies precedence for unary minus */
 
%%                   /* beginning of rules section */
 
list:                       /*empty */
         | list stat'\n'
         | list error'\n'
         {
           yyerrok;
         }
         ;
stat:    expr
         {
           printf("%d\n",$1);
         }
         |
         LETTER '=' expr
         {
           regs[$1] = $3;
         }
         ;
expr:    '(' expr ')'
         {
           $$ = $2;
         }
         |
         expr '*' expr
         {
           $$ = $1 * $3;
         }
         |
         expr '/' expr
         {
           $$ = $1 / $3;
         }
         |
         expr '%' expr
         {
           $$ = $1 % $3;
         }
         |
         expr '+' expr
         {
           $$ = $1 + $3;
         }
         |
         expr '-' expr
         {
           $$ = $1 - $3;
         }
         |
         expr '&' expr
         {
           $$ = $1 & $3;
         }
         |
         expr '|' expr
         {
           $$ = $1 | $3;
         }
         |
         '-' expr %prec UMINUS
         {
           $$ = -$2;
         }
         |
         LETTER
         {
           $$ = regs[$1];
         }
         |
         number
         ;
number:  DIGIT
         {
           $$ = $1;
           base = ($1==0) ? 8:10;
         }
         |
         number DIGIT
         {
           $$ = base * $1 + $2;
         }
         ;
%%
main()
{
 return(yyparse());
}
 
yyerror(s)
char *s;
{
  fprintf(stderr," %s\n",s);
}
 
yywrap()
{
  return(1);
}

宣言部には,次の機能を実行するエントリが含まれています。

  1. 標準 I/O ヘッダ・ファイルをインクルードする。 [例に戻る]

  2. グローバル変数を定義する。 [例に戻る]

  3. 処理を開始する位置として規則のリストを定義する。 [例に戻る]

  4. パーサで使用されるトークンを定義する。 [例に戻る]

  5. 演算子およびその優先順位を定義する。 [例に戻る]

規則部には,入力ストリームを解析する規則が定義されています。

プログラム部には,次のルーチンが含まれています。 これらのルーチンが含まれているため,このファイルの処理には,yacc ライブラリを使用する必要がありません。

4.10.2    字句解析プログラムのソース・コード

例 4-2 は,calc.l ファイルの内容です。 このファイルには,y.tab.h ファイルが使用する,標準入出力用の #include 文が含まれています。 y.tab.h ファイルは,calc.llex を実行する前に,yacc によって生成されたファイルです。y.tab.h ファイルは,パーサ・プログラムで使用されるトークンを定義します。 また,calc.l は,入力ストリームからトークンを生成する規則を定義します。

例 4-2:  計算機の字句解析プログラム・ソース・コード

%{
 
#include <stdio.h>
#include "y.tab.h"
int c;
extern int yylval;
%}
%%
" "       ;
[a-z]     {
            c = yytext[0];
            yylval = c - 'a';
            return(LETTER);
          }
[0-9]     {
            c = yytext[0];
            yylval = c - '0';
            return(DIGIT);
          }
[^a-z0-9\b]    {
                 c = yytext[0];
                 return(c);
               }