プログラムが入力を受け取りその入力を処理する場合,処理を行う前にその入力を解析する手段が必要です。 プログラム内の 1 つまたは複数のルーチンを使用して入力の解析を行うことも,入力をメイン・プログラムに渡す前に,フィルタ処理を行う別のプログラムを使用して入力の解析を行うこともできます。 入力の複雑さに合わせて,入力インタフェースも複雑になります。 複雑な入力を解析するには,かなり大量のコードが必要とされます。 解析を行う際には,プログラムにとって有効なかたまりに入力を分割します。
この章では,入力インタフェースを開発するのに有効な次の 2 つのツールについて説明します。
lex
ツール
lex
ツールは,一連の規則を使用して字句解析プログラムを生成します。
これは,入力を解析し,数字,英字,または演算子などのカテゴリに分割するものです。
yacc
ツール
yacc
ツールは,一連の規則を使用してパーサを生成します。
パーサとは,字句解析プログラムによって識別されたカテゴリを使用して入力を解析し,入力の処理方法を決定するプログラムです。yacc
ツールによって,左結合左復帰 (LALR) パーサが生成されます。
LALR 文法についての詳細は,『Compilers: Principles, Techniques, and Tools』 [脚注 7] などのコンパイラに関する書籍を参照してください。
lex
および
yacc
プログラムと,それらのプログラムが生成するプログラムとの混同を避けるため,この章では,lex
と
yacc
をツールと呼びます。
この章では,次の事項について説明します。
字句解析プログラムの動作 (4.1 節)
lex
による字句解析プログラムの作成 (4.2 節)
lex
仕様ファイル (4.3 節)
字句解析プログラムの生成 (4.4 節)
lex
と
yacc
の併用 (4.5 節)
yacc
によるパーサの作成 (4.6 節)
文法ファイル (4.7 節)
パーサの動作 (4.8 節)
デバッグ・モードの使用 (4.9 節)
簡易計算機プログラムの作成 (4.10 節)
lex
が生成する字句解析プログラムは,決定性有限状態オートマトンと呼ばれます。
これは,字句解析プログラムが存在可能な状態の数を限定し,また,次の入力文字を読み取り,解析した時点で字句解析プログラムが移行する状態を決定する規則を提供します。
コンパイルされた字句解析プログラムには,次の機能があります。
文字の入力ストリームを読み取る。
入力ストリームを出力ストリームにコピーする。
lex
仕様ファイルの正規表現に照合するより小さな文字列に入力ストリームを分割する。
字句解析プログラムが認識した各正規表現にアクションを実行する。
アクションは
lex
仕様ファイル中の C 言語プログラムのフラグメントです。
アクション・フラグメントはそれ自体で完結している必要はなく,サブルーチンまたは他のアクションを呼び出すことができます。
図 4-1
に,start
,good
,および
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
関数ライブラリを使用するように指定します。
このコマンドにより実行可能な字句解析プログラムが生成されます。
プログラムに複雑な文法規則が使用されているか,または文法規則がまったく使用されていない場合は,入力の適切な処理を確実にするため (lex
と
yacc
ツールを併用して) パーサを作成してください。
詳細については,4.6 節を参照してください。
yy.lex.c
出力ファイルは,lex
ライブラリ関数をサポートする C コンパイラを持つシステムならどのシステムにでも移植することができます。
4.3 lex 仕様ファイル
[ { definitions } ]
%%
[ { rules } ]
[ %%
{ user subroutines } ]
最初の 2 つのパーセント記号 ( %%
) は,規則の始まりを示すものです。
仕様ファイルのそれ以外の部分は,すべてオプションです。
最小の
lex
仕様ファイルには,定義,規則,およびユーザ・サブルーチンは含まれていません。
パターン照合のアクションが指定されていない場合は,字句解析プログラムは,入力パターンを変更することなく出力パターンにコピーします。
したがって,この最小の仕様ファイルは,すべての入力をそのまま出力にコピーする解析プログラムを生成します。
この節では,次の事項について説明します。
置換文字列の定義 (4.3.1 項)
規則 (4.3.2 項)
標準の入出力ルーチンの使用または変更 (4.3.3 項)
ファイルの終わりの処理 (4.3.4 項)
生成されたプログラムへのコードの引き渡し (4.3.5 項)
開始条件 (4.3.6 項)
lex
仕様ファイル中の最初の 2 つのパーセント記号の前に,文字列マクロを定義することができます。lex
ツールは,字句解析プログラムを生成する際に,そこで定義されたマクロを展開します。
この部の行の中で,カラム 1 から開始され,かつ
%{
デリミタおよび
%}
デリミタに囲まれていない行は,lex
置換文字列を定義しています。
置換文字列の定義は,一般的に次のようなフォーマットで記されます。
name translation
name
と
translation
の要素は,少なくとも 1 つの空白またはタブで区切り,name
は英文字で開始します。
仕様ファイルの規則の部分で,中カッコ ( { }
) で囲まれた文字列
name
を発見すると,lex
は,name
を
translation
で定義された文字列に変更して,中カッコを削除します。
たとえば,D
と
E
の名前を指定するには,仕様ファイルの中で最初の
%%
デリミタの前に次の定義を指定します。
D [0-9] E [DEde][-+]{D}+
上記の定義を規則部で使用して,整数と実数の識別をより簡潔にすることができます。
{D}+ printf("integer"); {D}+"."{D}*({E})?| {D}*"."{D}+({E})?| {D}+{E} printf("real");
また,定義部には次の項目を含めることもできます。
仕様ファイルの規則部には,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 つ以上の正規表現が現在の入力と照合する場合には,字句解析プログラムは次の基準を使用して,適用する規則を決定します。
一致する文字数が最も多い文字列に適用する。
一致する文字数が同じ場合は,最初に出現した規則を適用する。
たとえば,次のような規則がある場合を考えてみましょう。
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]
字句解析プログラムでは,規則ファイルの中の正規表現と完全に照合する前に,入力が不足することがあります。
この場合,その規則に対するアクションの中に,lex
関数の
yymore
への呼び出しを入力します。
通常は,入力ストリームからの次の文字列が,yytext
の現在のエントリに重ね書きされます。yymore
アクションによって,次の文字列は,入力ストリームから
yytext
の現在のエントリの最後に追加されます。
たとえば,次の構文を含む文字列を考えてみてください。
文字列は,引用符 ( " "
) で囲まれる任意の文字の集合である。
バックスラッシュ ( \
) が次の文字をエスケープすることによって,その文字は文字列の一部とみなされる。
たとえば,バックスラッシュと引用符の組み合わせ ( \
) は,引用符がその文字列の終わりのデリミタではなく,文字列の 1 部になっていることを示している。
次の規則によって,このような字句特性を処理することができます。
\"[^"]* { 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 =-... }
lex
プログラムは,使用する字句解析プログラム用の入出力 (I/O) ルーチンを提供します。
仕様ファイルの中の C コード・フラグメントに,次のようなルーチンへの呼び出しを含めてください。
input
-- 次の入力文字を返す。
output(
c)
-- 出力に文字
c
を書き込む。
unput(
c)
-- 後で
input
によって読み取るために,入力ストリームに文字
c
を戻す。
上記のルーチンは,マクロ定義として実装されています。 サブルーチン部の中で,ユーザ自身のコードを同名のルーチンとして記述することによって,マクロ指定を変更することができます。 これらのルーチンによって,外部ファイルと内部の文字の関係が定義されています。 それらの定義を変更する場合は,すべて同じ方法で変更してください。 変更する際は,次の規則に従ってください。
すべてのルーチンは同じ文字セットを使用する。
入力ルーチンでは,0 の値を返して,ファイルの終端を示す。
ユーザ自身のコードを記述する場合は,仕様ファイルの定義部の中で,ユーザの定義するコードの前に,これらのマクロ定義を削除する必要があります。
%{ #undef input #undef unput #undef output }%
注意
unput
とinput
の関係を変更すると,先読み機能が動作しません。
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
字句解析プログラムがファイルの終わりに到達すると,yywrap
というライブラリ・ルーチンを呼び出します。
このルーチンは,1 の値を返して,字句解析プログラムに通常のラップアップ (処理終了時に行われる動作) を続けるように示します。
しかし,解析プログラムが 2 つ以上のソースから入力を受け取る場合は,yywrap
関数を変更しなければなりません。
新しい関数は,新しい入力を得て,0 の値を字句解析プログラムに返さなければなりません。
0 のリターン値は,プログラムが処理し続けることを示します。
コマンド行で複数ファイルを指定した場合は,ファイルの終端の処理に関しては,1 つの入力ファイルとして扱われます。
また,yywrap
には,特に要約レポートとテーブルをプリントするコードを含めることもできます。yywrap
関数は,yylex
に強制的に入力の終わりを認識させる唯一の方法です。
4.3.5 生成されたプログラムへのコードの引き渡し
仕様ファイルの定義部または規則部のいずれにも変数を定義することができます。
仕様ファイルを処理すると,lex
は,指定ファイル中の文を字句解析プログラムに変更します。lex
が解釈できない仕様ファイルの行はすべて,変更されずに字句解析プログラムに渡されます。
次の 4 つのエントリのタイプは,変更されずに字句解析プログラムに渡されます。
lex
のいずれの規則にも含まれない,空白またはタブで始まる行は,字句解析プログラムにコピーされる。
仕様ファイル中の最初の 2 つのパーセント記号 ( %%
) の前にこのエントリが出現した場合,エントリは,コードの関数に対しても外部的なものとなる。
最初の
%%
の後にエントリが出現する場合には,変数を定義するための C 言語プログラム・フラグメントになる。
仕様ファイル中では,最初の
lex
規則の前に,それらの文を定義しなければならない。
プログラムのコメントであり,空白またはタブで始まる行は,生成された字句解析プログラムでもコメントとして含まれる。 コメントは,C 言語のコメントのフォーマットでなければならない。
%{
と
%}
だけの行の間にある行はすべて,字句解析プログラムにコピーされる。
%{
と
%}
の記号はコピーされない。
カラム 1 で始まらなければならないプリプロセッサ文を入力したり,プログラム文としては認識されない行をコピーする場合には,このフォーマットを使用する。
3 番目の
%%
デリミタの後に出現する行はいずれも,フォーマットの制限条項なしで字句解析プログラムにコピーされる。
どんな規則でも,開始条件に指定することができます。 字句解析プログラムは,開始条件に含まれている場合にのみ,その規則を認識します。 現在の開始条件は,常時変更可能です。
仕様ファイルの定義部の中の開始条件を定義するには,次のフォーマットの行を使用します。
% 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 つの手順で行います。
lex
を実行して仕様ファイルを C 言語プログラムに変更する。
その結果生成されたプログラムは,lex.yy.c
というファイルに存在する。
lex.yy.c
を
cc -ll
コマンドで処理して,プログラムにコンパイルし,それを
lex
サブルーチンのライブラリとリンクする。
結果として生成された実行可能プログラムは,a.out
という名前になる。
たとえば,
lex
仕様ファイルが
lextest
である場合は,次のコマンドを入力します。
% lex lextest % cc lex.yy.c -ll
省略時の設定である
lex
I/O ルーチンは,C 言語標準ライブラリを使用しますが,lex
が生成する字句解析プログラムでは必須ではありません。
I/O ルーチンをライブラリで使用しないようにするには,input
,output
,および
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
を参照してください。lex
や
yacc
によって生成されたプログラムと他のプログラムを併用することも可能です。
図 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
ライブラリの前にロードしなければなりません。lex
と
yacc
プログラムは,どちらを先に生成してもかまいません。
4.6 yacc によるパーサの作成
yacc
を使用してパーサを生成するには,入力データ・ストリーム,およびパーサがそのデータに対して行う処理を指定する文法ファイルを記述する必要があります。
文法ファイルには,入力の構造,規則が認識される際に呼び出されるコード,および基本入力を行うルーチンが含まれています。
yacc
ツールは,文法ファイルの情報を使用することによって,yyparse
を生成します。
このプログラムによって,入力処理が制御されます。
このパーサは,yylex
入力ルーチン (字句解析プログラム) を呼び出して,入力ストリームからトークンを取り出します。
このパーサは,文法ファイルの構造規則に従って,これらのトークンを組織化します。
この構造規則は,文法規則と呼ばれます。
パーサが文法規則を認識すると,パーサは,その規則に与えられたユーザ・コード (アクション) を実行します。
アクションは,値を返し,また,他のアクションによって返された値を使用します。
yacc
が認識および使用する仕様以外に,文法ファイルには次の関数を含めることができます。
main
-- 最小限の
yyparse
関数の呼び出しが含まれる C 言語関数。yyparse
関数は,yacc
によって生成される。
この関数の限定は,yacc
ライブラリに含まれる。
yyerror
-- パーサの動作中に発生するエラーを処理する C 言語関数。
この関数の簡易版は,yacc
ライブラリに含まれる。
yylex
-- 入力ストリームについて字句解析を実行し,必要に応じて値を付けたトークンをパーサに渡す C 言語関数。
この関数では,読み取られたトークンの種類を表す整数が返されなければなりません。
この整数は,トークン番号と呼ばれています。
さらに,値がトークンに対応する場合,字句解析プログラムは,その値を外部変数
yylval
に割り当てなければなりません。
トークン番号についての詳細は,4.7.1.3 項を参照してください。yacc
で生成されたパーサと組み合わせて,正常に動作する字句解析プログラムを作成するには,lex
ツールを使用してください。
詳細は,4.3 節を参照してください。
yacc
ツールは,文法ファイルを処理して
y.tab.c
という,C 言語関数およびデータを含むファイルを生成します。
cc
コマンドを使用してコンパイルすると,この関数は,yyparse
という結合された関数を形成します。
この
yyparse
関数は,入力トークンを得るために,yylex
という字句解析プログラムを呼び出します。
この解析プログラムは,パーサがエラーを検出するか,または解析プログラムが演算の終わりを示す
endmarker
トークンを返すまで入力を与え続けます。
エラーが発生して,yyparse
を復旧できない場合,yyparse
は,main
関数に 1 の値を返します。endmarker
トークンが検出された場合には,yyparse
は
main
関数に 0 の値を返します。
アクション・コードおよび他のサブルーチンを記述するには,C プログラミング言語を使用してください。yacc
プログラムは,文法ファイル内で多くの C 言語構文規約を使用します。
4.6.1 main および yyerror の関数
文法ファイルの中には,main
および
yyerror
という関数ルーチンが含まれていなければなりません。yacc
の初期導入作業を少なくするために,yacc
ライブラリには,main
と
yyerror
ルーチンの簡易版が備えられています。
ローダまたは
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
にパターンを渡す
トークンは,入力ルーチンによって送られたパターンを
yyparse
に通知する記号または名前です。
記号は,次の 2 つのクラスのいずれかにあります。
たとえば,字句解析プログラムが,数字,名前,および演算子のいずれでも認識する場合は,これらの要素が終端記号とみなされます。yacc
文法が認識する非終端記号は,EXPR
,TERM
,および
FACTOR
などの要素です。
入力ルーチンが入力ストリームを
WORD
,NUMBER
,および
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
文法ファイルの宣言部には,次の要素が含まれます。
文法ファイルの他の部分で使用されるすべての変数宣言または定数宣言
文法ファイル (ライブラリ・ヘッダ・ファイルに使用) の一部として他のファイルを呼び出す
#include
文
生成されたパーサの処理条件を定義する文
変数宣言または定数宣言は,次のように,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; %}
パーサは,開始記号と呼ばれる特殊記号を認識します。
開始記号は,文法規則に付けられた名前です。
この文法規則には,解析される言語の中で最も一般的な構造が記述されています。
これが最も一般的な構造であるため,入力ストリームの解析をトップ・ダウンでパーサを開始させる構造になっています。%start
キーワードを使用することによって,宣言部の中で開始記号を宣言します。
開始記号を宣言しない場合には,パーサは,ファイル中の最初の文法規則の名前を使用します。
たとえば,C 言語の手順を解析する際に,パーサが認識する最も一般的な構造は次のようになります。
main() { code_segment }
開始記号は,この構造を記述する規則を示さなければなりません。
ファイル内の残りのすべての規則は,処理の中でより低いレベルの構造体を識別する方法を記述します。
4.7.1.3 トークン番号
トークン番号は,トークン名を表す,負でない整数になります。 字句解析プログラムによって,トークン番号は,実際のトークン名ではなくパーサに渡されるので,プログラムはトークンに同じ番号を割り当てければなりません。
yacc
文法ファイルで使用されるトークンにトークン番号を割り当てることができます。
トークン番号をトークンに割り当てなかった場合,yacc
は,次の規則を使用してトークン番号を割り当てます。
リテラル文字には,ASCII 文字セットの文字の数値が割り当てられる。
他の名前には,257 以降のトークン番号が割り当てられる。
注意
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 ;
空文字列と照合する非終端記号を示すためには,次のように,セミコロンだけを規則の本体に使用してください。
nullstr : ;
字句解析プログラムが入力ストリームの終わりに達すると,パーサに
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; } ;
yacc
文法ファイルのプログラム部には,規則部の中のアクションで使用することができる C 言語関数が含まれています。
また,字句解析プログラム
yylex
を記述する場合は,プログラム部に追記してください。
4.7.4 文法ファイルの使用上のガイドライン
この項では,yacc
文法ファイルを使用する際の一般的なガイドラインを説明します。
次の処理に関して解説しています。
コメントの使用 (4.7.4.1 項)
リテラル文字列の使用 (4.7.4.2 項)
文法ファイルのフォーマット (4.7.4.3 項)
再帰の使用 (4.7.4.4 項)
エラーの訂正 (4.7.4.5 項)
文法ファイルのコメントには,プログラムの実行内容が説明されています。
名前を指定できるファイルであれば文法ファイルのどこにでも,コメントを書くことができます。
ただし,ファイルを読みやすくするために,規則の中の関数ブロックの最初の部分に独立した行としてコメントを記述するようにしてください。yacc
文法ファイルのコメントは,C 言語プログラムのコメントと,まったく同じフォーマットを持っています。
つまり,スラッシュとアスタリスク ( /*
) で始まり,アスタリスクとスラッシュ ( */
) で終わります。
その例を次に示します。
/* This is a comment on a line by itself. */
リテラル文字列は,アポストロフィ,すなわち一重引用符 ( ' '
) で囲まれた,1 つまたは複数の文字です。
バックスラッシュ ( \
) は,C 言語のように,リテラル文字列の中ではエスケープ文字になり,C 言語の特別文字シーケンスは,次のように認識されます。
\n |
改行文字 |
\r |
リターン |
\' |
アポストロフィまたは一重引用符 |
\\ |
バックスラッシュ |
\t |
タブ |
\b |
バックスペース |
\f |
改ページ |
\ nnn |
8進法の値 nnn |
\0
または
0
(空文字) は,絶対に文法規則では使用しないでください。
4.7.4.3 文法ファイルのフォーマットに関するガイドライン
次のガイドラインを使用すると,yacc
文法ファイルをより読みやすくすることができます。
トークン名には大文字を,非終端記号名には小文字を使用する。
文法規則とアクションは,いずれかを変更する場合に片方を変更するだけですむように別の行に置く。
規則はすべて,左側の位置を合わせる。
左側から入力を始め,縦線 ( |
) を使用してその残りの規則を始める。
左側が同じである各規則のセットについては,左の最後の規則の後に,1 行にセミコロン ( ;
) を 1 つだけ入力する。
そうすると,新しい規則が容易に追加できる。
規則本体はタブで 2 つ分字下げし,またアクション本体はタブ 3 つ分字下げする。
再帰とは,規則自身を定義するために関数を使用する処理のことです。 言語定義では,通常,これらの規則は次のフォーマットになります。
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
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 } ;
先読みトークンは,次にパーサによってチェックされるトークンです。
エラーが発生すると,先読みトークンは,エラーが検出された箇所のトークンになります。
しかし,エラー回復アクションに,処理を再開するための正確な位置を検出するコードが含まれている場合は,そのコードの先読みトークンも変更しなければなりません。
先読みトークンを消去するには,yyclearin;
文をエラー回復アクションに含みます。
4.8 パーサの動作
yacc
プログラムによって,文法ファイルは,C 言語プログラムに変更されます。
C 言語プログラムは,コンパイルされて実行されると,文法規則に従って入力を解析します。
パーサは,スタックを持つ,有限状態マシンです。 パーサは次の入力トークン (先読みトークン) を読み取り,記憶することができます。 現在の状態は,常に,スタックの最上部にある状態です。 有限状態マシンの状態は,小さい整数によって表されます。 最初は,マシンは 0 (ゼロ) の状態で,スタックには 0 (ゼロ) のみが含まれています。 先読みトークンはまったく読み取りません。
マシンは,次の 4 つのアクションのうちのいずれかを実行することができます。
shift
n |
パーサは,現在の状態をスタックにプッシュし,n を現在の状態にし,先読みトークンを消去する。 |
reduce
r |
引数
r
は規則の番号。
パーサは,入力ストリームの
r
番の規則に照合するトークン・シーケンスを検出すると,出力ストリームの規則番号を持つシーケンスに置換される。 |
accept |
パーサによってすべての入力がチェックされ,それらの入力は文法指定と照合し,その入力が,最も高いレベルの構造 (開始記号として定義) を満たすように認識される。 このアクションは,先読みトークンがエンド・マーカで,しかもパーサが正常に完了したことを示している場合にのみ有効。 |
error |
パーサは入力ストリームの処理を続行できず,文法指定で定義された規則への正常な照合を続けられない。 パーサが探している入力トークンは,先読みトークンとともに,正当な結果を出力できない。 パーサはエラーを報告し,その状況を回復して,解析を再開しようとする。 |
パーサは,1 つの処理手順の中で,次のアクションを実行します。
パーサは,現在の状態に基づき,次のアクションを決めるのに先読みトークンが必要かどうかを決定する。
パーサに先読みトークンが必要なときに,それがない場合は,パーサは,次のトークンを得るために
yylex
を呼び出す。
現在の状態と,必要であれば先読みトークンを使用して,パーサはその次のアクションを決定し,実行する。 これによって,スタックにプッシュされるか,あるいはスタックからはじき出される状態で終了し,先読みトークンは処理されるか,あるいは処理されずに残される場合もある。
shift
アクションは,パーサの使用する最も一般的なアクションです。
パーサが
shift
を実行すると,常に,先読みトークンがあります。
次のパーサ・アクションの規則を考えてみます。
IF shift 34
パーサが,この規則を含む状態で,しかも先読みトークンが
IF
である場合は,パーサは次の手順を実行します。
現在の状態をスタックにプッシュする。
状態 34 を現在の状態に指定する (スタックの最上部に置く)。
先読みトークンを消去する。
reduce
アクションを使用すると,スタックが肥大化するのを防ぐことができます。
パーサは,入力ストリームに対して規則の右側に照合し,入力ストリームのトークンを規則の左側に置換する準備ができると,縮小アクションを使用します。
パーサは,先読みトークンを使用してパターンが完全に照合したかを決定する必要のあることがあります。
縮小アクションは,個々の文法規則によって関連付けられています。
また,文法規則もまた,小さい整数を持つために,shift
アクションと
reduce
アクションの番号の意味は混乱が生じやすくなっています。
たとえば,次の 2 つのアクションの 1 番目は,文法 18 を表し,2 番目はマシン状態 34 を表しています。
reduce 18 IF shift 34
たとえば,次の規則の縮小を考えてみてください。
A : x y z ;
パーサによって,スタックから一番上の 3 つの状態が取り出されます。
取り出された状態の番号は,規則の右側の記号の番号と等しくなります。
これらの状態は,x
,y
,および
z
を認識している間,スタックに置かれるものです。
上記の状態が取り出されると,パーサは,規則が処理される前 (規則
A
を認識して,その規則を満たすのが必要な状態) のパーサの状態になります。
パーサは,元に戻された状態と規則の左側の記号を使用して,goto
アクションを実行します。
このアクションは,A
の
shift
と似ています。
新しい状態が得られると,スタックにプッシュされて,解析が続きます。
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 - c
を
expr
に縮小します。
このとき,パーサは,次のものを持ちます。
a - expr
再度,式を縮小することによって,右結合の解釈になります。
したがって,パーサによって最初の 3 つの部分が読み取られたところで,2 つの正当なアクション,すなわち,shift
か,reduce
のうちの 1 つを選択することができます。
パーサにアクションを決定する規則がまったくない場合は,shift/reduce
競合が生じます。
パーサが 2 つの有効な
reduce
アクションの中から選択が可能な場合は,同様の状態が発生します。
このような状態を
reduce/reduce
競合といいます。
shift/reduce
競合あるいは
reduce/reduce
競合が発生する場合,yacc
は選択可能な場合は,有効な方法を選んで,パーサを生成します。
選択するための規則がない場合,yacc
は次の規則を使用します。
shift/reduce
競合では,shift を実行する。
reduce/reduce
競合では,入力ストリーム中の最初に出現する文法規則により縮小する。
パーサがどの規則を認識しているか認識する前にアクションを実行しなければならない場合には,規則内のアクションを使用することによって,競合が発生することがあります。
このような場合,前述の規則を使用すると,間違ったパーサが生成されます。
このために,yacc
は,前述の 2 つの規則を適用することによって解決された,shift/reduce
競合と
reduce/reduce
競合の数を報告します。
4.9 デバッグ・モードの使用
通常の操作では,外部整数変数
yydebug
は 0 に設定されています。
しかし,ゼロ以外の値に設定した場合,パーサは,実行記述ファイルを生成します。
この記述ファイルには,パーサが受け取る入力トークン,および各トークンに対して行うアクションが含まれています。
次の 2 つの中のいずれかの方法で,yydebug
変数を設定することができます。
yacc
文法ファイルの宣言部に次の C 言語文を入れることによって
yydebug
関数を使用する。
yydebug = 1;
デバッガを使用して最後のパーサを起動し,デバッガ・コマンドを使用して,yydebug
変数のオンまたはオフを設定する。dbx
などのデバッガの使用についての詳細は,各デバッガのリファレンス・ページを参照。
例 4-1
および例 4-2
に示す
lex
で生成された字句解析プログラムおよび
yacc
で生成されたパーサのプログラムを使用して,加算,減算,乗算,および除算の演算を実行する簡単な卓上計算機のプログラムを作成することができます。
また,この計算機プログラムでは,1 つの小文字で指定した変数に値を代入して,計算することもできます。
プログラムを含むファイルは次のとおりです。
calc.l
- 字句解析規則を定義する
lex
仕様ファイル
calc.y
- 解析規則を定義する
yacc
文法ファイル。
入力を提供するために,lex
によって作成された
yylex
関数を呼び出す。
慣例で,lex
と
yacc
のプログラムには,ファイル名の接尾文字として,それぞれ
.l
と
.y
の英字が使用されます。例 4-1
と
例 4-2
は,実際に入力するためのプログラム・フラグメントの例です。
この項の処理手順は,ファイルが現在のディレクトリにあることを前提としています。
示された順序どおりに,次の手順を実行して,lex
と
yacc
を使用した計算機プログラムを作成してください。
次のコマンドを使用して,yacc
文法ファイルを処理する。
yacc
では,-d
オプションを指定すると,C 言語ソース・コードに加えて,使用するトークンを定義するファイルを作成します。
% yacc -d calc.y
このコマンドで,次のファイルが作成されます。
次のコマンドを使用して
lex
仕様ファイルを処理する。
% lex calc.l
このコマンドは
lex.yy.c
ファイルを作成し,lex
が字句解析プログラム用に作成した C 言語ソース・ファイルを含んでいます。
次のコマンドを使用して 2 つの C 言語ソース・ファイルをコンパイルし,リンクする。
% cc -o calc y.tab.c lex.yy.c
ls
コマンドを使用して次のファイルが作成されたことを確認する。
y.tab.o
-
y.tab.c
から作成されたオブジェクト・ファイル
lex.yy.o
-
lex.yy.c
から作成されたオブジェクト・ファイル
calc
- 実行可能プログラム・ファイル
calc
コマンドを入力すると,プログラムを実行することができます。
その後で,数字と演算子を代数的に入力することができます。
リターンを押すと,このプログラムは演算の結果を表示します。
次のように,変数に値を与えることができます。
m=4
次のように,計算で変数を使用することができます。
m+5 9
例 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); }
宣言部には,次の機能を実行するエントリが含まれています。
標準 I/O ヘッダ・ファイルをインクルードする。 [例に戻る]
グローバル変数を定義する。 [例に戻る]
処理を開始する位置として規則のリストを定義する。 [例に戻る]
パーサで使用されるトークンを定義する。 [例に戻る]
演算子およびその優先順位を定義する。 [例に戻る]
規則部には,入力ストリームを解析する規則が定義されています。
プログラム部には,次のルーチンが含まれています。
これらのルーチンが含まれているため,このファイルの処理には,yacc
ライブラリを使用する必要がありません。
main( )
- プログラムを開始するために
yyparse( )
を呼び出す,必須メイン・プログラム
yyerror(s)
- 構文エラー・メッセージをプリントするエラー処理ルーチン
yywrap( )
- 入力が終了した場合に 1 の値を返す,
ラップアップ・ルーチン
例 4-2
は,calc.l
ファイルの内容です。
このファイルには,y.tab.h
ファイルが使用する,標準入出力用の
#include
文が含まれています。
y.tab.h
ファイルは,calc.l
で
lex
を実行する前に,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); }