第 3 章 yacc - コンパイラコンパイラ
yacc (yet another compiler compiler) ユーティリティは、コンピュータプログラムに対する入力の構造を指定するための汎用ツールで構成されています。yacc を使用する場合は、以下の内容が含まれている仕様をあらかじめ用意する必要があります。
-
入力の要素を表す規則
-
規則が認識されたときに呼び出されるコード
-
入力を調べるための低レベルのスキャナの定義もしくは宣言
yacc は、この仕様を、入力ストリームを調べる C 言語の関数に変換します。パーサーと呼ばれるこの関数は、低レベルスキャナを呼び出すことによって機能します。
字句アナライザと呼ばれるスキャナは、入力ストリームから項目を拾い上げます。選択されたこの項目はトークンと呼ばれます。トークンは、構文規則と比較検査されます。
規則として認識されると、その規則に対して設定したコードが呼び出されます。このコードはアクションと呼ばれます。このアクションは、C 言語のコードです。アクションは、値を返したり、他のアクションが返す値を使用できます。
yacc 仕様の核となるのは、構文規則の集まりです。各規則には構成を記述し、その構成に名前が付けられます。構文規則の例を以下に示します。
date: month_name day ',' year ; |
date、month_name、day、year がこの構文規則の構成になります。month_name、day、year は別の場所で詳細に定義されているものと仮定します。
この例では、コンマを単一引用符で囲んでいます。これは、コンマがそのまま入力に現われるということを意味しています。コロンとセミコロンは規則内では句読点で、入力の評価では無視されます。正しく定義されると、以下の入力はその規則によって照合されます。
July 4, 1776
字句アナライザは、構文解析関数の重要な要素です。ユーザーが作成するこのルーチンは、入力ストリームを読み取り、低レベルの構成を認識して、その構成をトークンとしてパーサーに伝えます。字句アナライザは、入力ストリームの構成を終端記号として認識します。一方、パーサーは、構成を非終端記号として認識します。混乱を避けるため、終端記号をトークンとして読み進めてください。
字句アナライザと構文規則のどちらを使用して構成を認識するかは、かなり自由に選択できます。たとえば、上記の例では以下のような規則を使用することもできます。
month_name : 'J' 'a' 'n' ; month_name : 'F' 'e' 'b' ; ... month_name : 'D' 'e' 'c' ;
字句アナライザは個々の文字を単純に認識するだけですが、このような低レベルの規則は、時間や空間を浪費する傾向があり、また yacc では扱えないほど仕様を複雑化する可能性があります。
通常、字句アナライザは、月の名前を認識して、month_name が見つかったことを示す通知を返します。この場合は、month_name がトークンであり、詳細な規則は不要です。
字句アナライザを通り過ぎる必要があるコンマなどのリテラル文字も、同様にトークンとみなされます。
仕様ファイルには柔軟性があります。前述の例には、比較的簡単に以下の規則を加えることができます。
date : month '/' day '/' year ;
この規則により、入力では
7/4/1776
の同義語として
July 4, 1776
も使用できるようになります。ほとんどの場合、この新しい規則は、既存の記述を変更せずに最低限の労力でシステムに取り入れることができます。
読み取られた入力は、仕様と一致していない場合もあります。左から右に検査することによって、入力エラーは理論上可能な最も早い段階で検出されます。したがって、無効な入力データの読み取りや計算の回数が実際に減少するだけでなく、通常は無効なデータも瞬時に見つけることができます。
入力仕様の一部として用意されているエラー処理では、無効データを再入力したり、無効データを読み飛ばした後に入力処理を再開できます。複数の仕様を一度に指定すると、yacc はパーサーの生成に失敗することがあります。たとえば、仕様どうしが矛盾している場合や、yacc の認識メカニズムよりも強力な認識メカニズムを必要とする仕様などの場合に失敗します。
前者の場合は、設計エラーであることを表しています。後者の場合は、さらに機能が豊富な字句アナライザを作成するか、または構文規則の一部を書き直すことによって、問題を解決することができます。
yacc は、どんな仕様でも扱えるわけではありませんが、他の類似したシステムよりも優れています。また、yacc で扱うのが難しい構成は、ほとんどの場合、人間でも扱うのが難しい構成です。入力を検査する有効な yacc 仕様によって、プログラム開発の初期で概念や設計のエラーが明らかになったという、ユーザーからの報告があります。
この章の残りの部分では、以下の主題について説明します。
-
yacc 仕様を準備するための基本処理
-
パーサーの操作
-
あいまいさの取り扱い
-
算術式における演算子の優先度の取り扱い
-
エラー検出と回復
-
yacc が生成したパーサーの操作環境と特殊機能
-
仕様のスタイルと有効性を改善するためのヒント
-
高度なトピック
また、yacc 入力構文のまとめと 2 つの例を記載しています。
国際化
英語以外の言語でのアプリケーション開発における yacc の使用についての詳細は、yacc(1) を参照してください。
基本仕様
名前とは、トークンまたは非終端記号のことを指します。yacc では、トークン名をトークンとして宣言する必要があります。字句アナライザは、仕様ファイルの一部として取り込むこともできますが、モジュール化し独立したファイルとして保存する場合の方が多くあります。字句アナライザと同様に、他のサブルーチンを取り込むこともできます。
すべての仕様ファイルは、理論上は 3 つのセクションで構成されます。その 3 つのセクションとは、宣言、(構文) 規則、サブルーチンです。これらのセクションは、2 つのパーセント記号 %% (パーセント記号は、yacc 仕様では通常はエスケープ文字として使用されます) で区切られます。
すべてのセクションを使用したときの仕様全体は以下のようになります。
宣言 %% 規則 %% サブルーチン
宣言とサブルーチンのセクションは省略可能です。最も短い正当な yacc 仕様の例を以下に示します。
%% S:;
空白文字、タブ、復帰改行は無視されますが、名前や複数文字から成る予約シンボルでこれらを使用することはできません。コメントは、名前が正当である任意の場所で使用できます。C 言語の場合と同じように、コメントは /* と */ で囲みます。
規則セクションは、1 つ以上の構文規則で構成されます。構文規則は以下の形式になっています。
A: BODY ;
A は非終端記号を表しており、BODY はゼロ、または 1 つ以上の名前やリテラルを表しています。コロンとセミコロンは、yacc の句読点です。
名前は、任意の長さにすることが可能で、文字、ピリオド、下線、および数字で構成できます。ただし、数字を名前の先頭の文字に使用することはできません。大文字と小文字は区別されます。構文規則の本体で使用される名前では、トークンまたは非終端記号を表すことができます。
リテラルは、単一引用符で囲まれた文字で構成されます。C 言語の場合と同じように、リテラル内では、バックスラッシュはエスケープ文字です。yacc は、C 言語のエスケープシーケンスをすべて認識します。技術的ないくつかの理由により、NULL 文字を構文規則の中で使用することはできません。
左側の記述が同じ構文規則が複数ある場合には、縦棒を使用して左側の部分を繰り返し記述しなくても済むようにできます。また、規則の終わりにあるセミコロンは、縦棒の前方にあるものについては消去します。
したがって、以下の構文規則は、
A : B C D ; A : E F ; A : G ;
縦棒を使用した以下の形式で yacc に与えることができます。
A : B C D
| E F
| G
;
左側の部分が同一の構文規則を、すべてまとめて構文規則セクションに記述する必要はありません。ただし、そうした方が入力は読みやすくなり、変更するのも容易になります。
非終端記号が空の文字列に一致させたい場合には、以下の規則によってそれを示すことができます。
epsilon : ;
コロンの後の空白は、yacc によって非終端記号 epsilon の構成として認識されます。
トークンを表す名前は宣言する必要があります。宣言セクションに以下のように記述するのが、最も簡単な方法です。
$token name1 name2 name3
宣言セクションで定義されていない名前は、すべて非終端記号を表しているとみなされます。非終端記号は、少なくとも 1 つの規則の左側に記述する必要があります。
すべての非終端記号において、開始シンボルは非常に重要な意味を持っています。このシンボルは、デフォルトでは、規則セクションの最初の構文規則の左側にあるとみなされます。開始シンボルは、宣言セクションで %start キーワードを使用して明示的に宣言できます。また、このように宣言することをお勧めします。
%start シンボル
パーサーに対する入力の終わりは、エンドマーカーと呼ばれる特殊なトークンで示されます。エンドマーカーは、ゼロまたは負の数値で表されます。
エンドマーカーまでのトークン (ただし、エンドマーカーは含まない) が開始シンボルと一致する構成を形成している場合には、パーサー関数はエンドマーカーを認識して、その入力を受け取った後に呼び出し元に戻ります。それ以外のコンテキストでエンドマーカーが認識された場合は、そのエンドマーカーはエラーです。
適切なときにエンドマーカーを返すことは、ユーザーが作成した字句アナライザの役割です。エンドマーカーは、通常はファイルの終わりやレコードの終わりなどの論理的に明白ないくつかの入出力状態を表します。
アクション
ユーザーは、規則が認識されたときに実行するアクションを各構文規則に関連付けることができます。アクションは、値を返したり、他のアクションによって返された値を取得できます。また、字句アナライザは、必要であれば、トークンの値を返すことができます。
アクションは、C 言語の文として入力および出力を行なったり、サブルーチンを呼び出したり、配列や変数を変更できます。アクションは、{ と } で囲まれた 1 つ以上の文によって指定されます。アクションを持った構文規則の例を以下に 2 つ示します。
A : '(' B ')'
{
hello( 1, "abc" );
}
XXX : YYY ZZZ
{
(void) printf("a message¥n");
flag = 25;
}
$ 記号は、アクションとパーサーの間の伝達を容易にするために使用されます。擬似変数 $$ は、完了したアクションによって返される値を表します。
たとえば、以下のアクションは値 1 を返します。実際、このアクションが行うことはそれだけです。
{ $$ = 1; }
アクションは擬似変数 $1、$2、... $n を使用して、他のアクションと字句アナライザによって返された値を取得できます。これらの擬似変数は、規則の右側にある要素 1 〜 n によって返された値を参照します。要素には、左から右の順に番号が割り当てられます。以下のような規則の場合には、$2 は C によって返された値、$3 は D によって返された値を持つことになります。
A : B C D ;
以下の規則で、一般的な例を示します。
expr : '(' expr ')' ;
この規則で値は、括弧内の expr の値に意味があります。アクションの最初の要素はリテラルの左括弧なので、目的の論理的な結果は以下の記述によって表すことができます。
expr : '(' expr ')'
{
$$ = $2 ;
}
デフォルトでは、規則の値はその規則内の最初の要素の値 ($1) になります。したがって、以下の形式の構文規則では、明示的なアクションを持つ必要性はほとんどありません。
A : B ;
前述の例では、アクションは規則の終わりにすべて記述されています。場合によっては、規則が完全に構文解析される前に制御を行う必要があります。yacc では、規則の終了部だけでなく、規則の途中にもアクションを記述できます。
このアクションは、通常の $ メカニズムでアクセスできる値がこのアクションの中の記述によって返されると仮定しています。同様に、このアクションは、その左側のシンボルによって返された値にアクセスできます。したがって、以下の規則の場合には、x は 1 に設定され、y は C によって返される値に設定されます。
A : B
{
$$ = 1;
}
C
{
x = $2;
y = $3;
}
;
規則を終端していないアクションは、yacc によって扱われます。yacc は、新しい非終端記号の名前と、その名前を空の文字列に一致させる新しい規則を作成します。内部のアクションは、この追加された規則を認識することによって起動されるアクションです。
yacc は、以下のように記述されているかのように上記の例を取り扱います。
$ACT : /* 空 */
{
$$ = 1;
}
;
A : B $ACT C
{
x = $2;
y = $3;
}
;
$ACT は空のアクションです。
多くのアプリケーションでは、出力はアクションの直接的な結果ではありません。構文解析ツリーなどのデータ構造がメモリー内で構築され、そのデータ構造に変換処理が適用されてから出力が生成されます。ツリー構造の作成と保守を行うために必要なルーチンは用意されているので、構文解析ツリーは非常に簡単に構築できます。
たとえば、以下のようにして呼び出した場合に、ラベル L とその派生 n1 および n2 を持ったノードを作成し、その新しく作成したノードのインデックスを返す node という C 関数があると仮定します。
node( L, n1, n2 )
その場合、構文解析ツリーは、以下のような仕様のアクションを用意することによって構築できます。
expr : expr '+' expr
{
$$ = node( '+', $1, $3 );
}
ユーザーは、アクションで使用する他の変数を定義できます。宣言と定義は、宣言セクションで %{ と %} の間に記述します。これらの宣言と定義の適用範囲はグローバルスコープであるため、アクション文に認識されます。また、字句アナライザにも認識されるようにすることも可能です。たとえば、以下の定義を宣言セクションに配置すれば、すべてのアクションで変数 (variable) にアクセスできるようになります。
%{ int variable = 0; %}
yacc パーサーは yy で始まる名前だけを使用しているので、yy で始まる名前は避ける必要があります。また、これまでに示した例では値がすべて整数であることに注意してください。
値については、「高度なトピック」で説明しています。最後に、以下のように定義した場合には、yacc は %{ の後からコピーを開始して、最初に検出した %}、つまり printf() の中の %}でコピーを終了するので注意してください。逆に、printf() の中で %{ を検出した場合には、その %{ からコピーが開始されます。
%{
int i;
printf("%}");
%}
字句解析
ユーザーは、字句アナライザを用意して、入力ストリームを読み取った後にトークン (必要であれば、値も共に) をパーサーに伝達する必要があります。字句アナライザは、yylex() と呼ばれる整数値の関数です。この関数は、読み取ったトークンの種類を表す整数値のトークン番号を返します。値がそのトークンに関連付けられている場合には、その値を外部変数 yylval に割り当てる必要があります。
パーサーと字句アナライザの間で伝達を行うためには、これらのトークン番号が両者で共通の番号でなければなりません。この番号は、yacc で選択することも、ユーザーが選択することもできます。いずれの場合でも、C 言語の #define メカニズムを使用して、字句アナライザがこれらの番号をシンボルとして返せるようにします。
たとえば、yacc 仕様ファイルの宣言セクションにトークン名 DIGIT が定義されているとします。適切なトークンを返すための字句アナライザの関連部分は、以下のように記述できます。
int yylex()
{
extern int yylval;
int c;
...
c = getchar();
...
switch (c)
{
...
case '0':
case '1':
...
case '9':
yylval = c - '0';
return (DIGIT);
...
}
...
}
このコードは、DIGIT のトークン番号を返します。字句アナライザのコードはサブルーチンセクションに、DIGIT の宣言は宣言セクションに置くことができます。字句アナライザのコードは、以下のようにして、別にコンパイル済みファイルに置くこともできます。
-
-d オプションを付けて yacc を実行します。これにより、トークンの #define 文を含んだ y.tab.h というファイルが生成されます。
-
独立したコンパイル済み字句アナライザに #include y.tab.h を追加します。
このメカニズムによって、明示的で変更が容易にできる字句アナライザが作成されます。ただし、C 言語またはパーサーで予約済みのトークン名や重要なトークン名を使用しないでください。
たとえば、トークン名 if または while を使用すると、字句アナライザのコンパイル時に深刻な問題が必ず発生します。トークン名 error はエラー処理用に予約されているので、安易に使用しないでください。
デフォルトの状態では、トークン番号は yacc によって選択されます。リテラル文字のデフォルトのトークン番号は、文字セットの文字の数値です。他の名前には、257 以降のトークン番号が割り当てられます。
自分でトークン番号を割り当てたい場合には、宣言セクションで最初に現われるトークン名またはリテラルの直後に負でない整数を置く必要があります。この整数は、名前またはリテラルのトークン番号とみなされます。この方法で定義されていない名前とリテラルには、yacc によってデフォルトの定義が割り当てられます。その場合には、トークン番号が重複する可能性があります。トークン番号が重複していないことを必ず確認してください。
エンドマーカーは 0 または負のトークン番号を持つ必要があります。このトークン番号を再定義することはできません。したがって、字句アナライザは、入力の終わりに達したときに必ず 0 または 負の数字をトークンとして返すようになっていなければなりません。
第 2 章「字句解析」で説明したように、lex によって生成された字句アナライザは、yacc と協調して動作するように設計されています。これらの字句アナライザの仕様では、構文規則の代わりに正規表現が使用されます。lex を使用して非常に複雑な字句アナライザを生成できますが、理論上仕様が適合しない言語がいくつかあります。そのような言語の場合には、手作業で字句アナライザを作成する必要があります。
パーサーの操作
yacc を使用して、仕様ファイルを C 言語の手続きに変換します。この手続きは、与えられた仕様に従って入力を構文解析します。仕様からパーサーへの変換で使用されるアルゴリズムは非常に複雑なので、ここでは説明しません。ただし、パーサー自体は比較的シンプルであり、その使い方を理解すればエラー回復やあいまいさの取扱いが容易になります。
yacc によって生成されたパーサーは、スタックを持った有限状態マシンで構成されています。パーサーは、lookahead トークンと呼ばれる次の入力トークンを読み取ってそれを記憶することもできます。現在の状態は常にスタックの 1 番上にあります。有限状態マシンの状態には、小さい整数のラベルが付けられます。初期状態では、マシンは状態 0 (スタックには状態 0 しか入っていません) になっており、lookahead トークンもまだ読み取られていません。
マシンで実行できるアクションは、shift (シフト)、reduce (還元)、accept (受理)、error (エラー) の 4 つだけです。パーサーの動作手順を以下に示します。
-
パーサーは、実行するアクションを選択するためには lookahead トークンが必要かどうかを現在の状態に基づいて判断します。lookahead トークンが必要で、まだそのトークンを持っていない場合には、パーサーは yylex() を呼び出して次のトークンを取得します。
-
パーサーは、必要であれば現在の状態と lookahead トークンを使用して、次のアクションを決定し、それを実行します。この処理が行われると、状態はスタックにプッシュされたり、スタックからポップされることがあります。lookahead トークンは、処理されたり、処理されずにそのまま残されたりすることがあります。
shift アクションは、パーサーで最も頻繁に使用されるアクションです。shift アクションを行うときには、必ず lookahead トークンが伴います。たとえば、状態 56 で以下のようなアクションを行なったとします。
IF shift 34
これは、状態 56 で lookahead トークンが IF の場合には、現在の状態 (56) がスタックにプッシュされ、状態 34 が現在の状態 (スタックの一番上の状態) になるということを意味しています。lookahead トークンは消去されます。
reduce アクションは、スタックが際限なく大きくなるのを防ぎます。reduce アクションは、パーサーが構文規則の右側を認識し、右側を左側で置換して、規則のインスタンスを認識したことを通知する準備ができたときに適用できます。lookahead トークンを調べて reduce を実行するかどうかを判断しなければならない場合もあります。実際には、ほとんどのデフォルトアクション (. で表されます) が reduce アクションです。
reduce アクションは、個々の構文規則に関連付けられます。構文規則にも小さい整数の番号が付けられるため、多少の混乱が生じます。以下のアクションは、構文規則 18 を参照します。
. reduce 18
一方、以下のアクションの場合には、状態 34 を参照します。
IF shift 34
たとえば、以下の規則を還元すると仮定します。
A : x y z ;
reduce アクションは、左側のシンボル (この場合は A) と右側のシンボルの数 (この場合は 3) に依存します。reduce を実行するには、まずスタックの上位 3 つの状態をポップします (通常は、ポップされる状態の数は規則の右側のシンボルの数と一致します)。
これらの状態は、x、y、z を認識するときにスタックに置かれたものなので、すでにその必要性はなくなっています。これらの状態がポップされると、規則を処理する前のパーサーの状態が取り出されます。
この取り出された状態と、規則の左側のシンボルを使用して、結果的に A がシフトされます。新しい状態が取得され、スタックにプッシュされると、構文解析が再開されます。ただし、左側のシンボルの処理と通常のトークンのシフト処理はかなり異なっています。そのため、このアクションは goto アクションと呼ばれています。特に、lookahead トークンは goto アクションでは何の影響も受けませんが、shift アクションでは消去されので、注意してください。取り出された状態には、必ず以下のようなエントリが含まれています。この例の場合には、状態 20 がスタックにプッシュされて現在の状態になります。
A goto 20
実際には、reduce アクションは、状態をスタックからポップすることによって構文解析を逆戻しして、規則の左側を最初に認識したときの状態に戻します。そして、パーサーはその時点で左側を認識したかのように動作します。規則の右側が空の場合は、スタックから状態はポップされません。取り出された状態は実際の現在の状態です。
reduce アクションは、ユーザーが作成したアクションと値を扱う場合にも重要になります。規則を還元すると、スタックが調整される前に、規則と共に用意されたコードが実行されます。状態を保持するスタックのほかに、そのスタックと並行して動作する別のスタックが用意されています。このスタックは、字句アナライザとアクションから返された値を保持します。
shift アクションが実行されると、外部変数 yylval は、値スタックにコピーされます。還元は、ユーザーコードから戻った後に実行されます。goto アクションが実行されると、外部変数 yyval が値スタックにコピーされます。擬似変数 $1、$2 等は、その値スタックを参照します。
他の 2 つのパーサーアクションは、概念的にはさらに単純なアクションになっています。accept アクションは、入力全体が認識され、その入力が仕様と一致していることを示します。このアクションは、lookahead トークンがエンドマーカーのときにだけ使用されて、パーサーが作業を正常に終了したことを示します。
一方、error アクションは、パーサーが仕様に従って構文解析を続けられなくなった場所を表します。パーサーが (lookahead トークンと共に) 認識した入力トークンの後に、不正となる可能性がある入力を続けることはできません。パーサーは、エラーを報告し、その状態を回復してから構文解析を再開します。
エラー回復 (エラー検出との対応) については、「エラー処理」で説明しています。
以下の yacc 仕様について考えます。
$token DING DONG DELL
%%
rhyme : sound place
;
sound : DING DONG
;
place : DELL
;
-v (冗長) オプションを付けて yacc を呼び出すと、パーサーが記述された y.output というファイルが生成されます。
上記の文法に対応した y.output ファイルは以下のようになります (ただし、ファイルの後ろの統計情報は一部省略されています)。
state 0
$accept : _rhyme $end
DING shift 3
. error
rhyme goto 1
sound goto 2
state 1
$accept : rhyme_$end
$end accept
. error
state 2
rhyme : sound_place
DELL shift 5
. error
place goto 4
state 3
sound : DING_DONG
DONG shift 6
. error
state 4
rhyme : sound place_ (1)
. reduce 1
state 5
place : DELL_ (3)
. reduce 3
state 6
sound : DING DONG_ (2)
. reduce 2
このファイルでは、各状態のアクションが指定されており、各状態で処理される構文解析規則も記述されています。下線 (_) は、各規則において何が認識され、何がまだ認識されていないかを示すために使用されています。以下のように入力をすると、パーサーの動作を追跡できます。
DING DONG DELL
初期状態での現在状態は state 0 です。
パーサーは、入力を参照して、state 0 で使用可能なアクションのいずれかを選択します。したがって、最初のトークン DING が読み取られて、lookahead トークンになります。DING に対する state 0 のアクションは shift 3 です。このstate 3 はスタックにプッシュされ、lookahead トークンは消去されます。これにより、state 3 が現在の状態になります。そして、その次のトークン DONG が読み取られて、lookahead トークンになります。
DONG に対するstate 3 のアクションは、shift 6 です。state 6 はスタックにプッシュされ、lookahead トークンは消去されます。この時点で、スタックには 0、3、6 が含まれています。state 6 では、パーサーは、lookahead を調べることなく、以下の規則 2 によって還元を行います。
sound : DING DONG
state 6 と state 3 がスタックからポップされ、state 0 が取り出されます。そして、state 0 の記述を参照して (sound に対する goto を探して)、以下の記述を見つけ出します。
sound goto 2
state 2 は、スタックにプッシュされて、現在の状態になります。
state 2 では、次のトークン DELL を読み取る必要があります。DELL に対するアクションは shift 5 なので、state 5 がスタックにプッシュされ、lookahead トークンはクリアされます。この時点のスタックには、0、2、5 が入っています。state 5 には、規則 3 によって還元するアクションしかありません。この規則の右側には 1 つのシンボルしかないので、state 5 だけがポップされ、state 2 が取り出されます。
place (規則 3 の左側) に対するstate 2 の goto はstate 4 です。この時点のスタックには、0、2、4 が含まれています。state 4 には、規則 1 によって還元するアクションしかありません。規則 1 の右側にはシンボルが 2 つあるので、上位 2 つの状態がポップされ、state 0 が再度取り出されます。
-
state 0 には rhyme に対する goto があるので、パーサーはstate 1 に移行します。
-
state 1 では、入力が読み取られ、y.output ファイルの $end によって示されているエンドマーカーが取得されます。エンドマーカーを取得した場合には、state 1 のアクションによって構文解析は正常に終了します。
あいまいさと衝突
入力文字列が 2 種類以上の方法で構成できる場合には、構文規則のセットはあいまいになります。たとえば、2 つの式の間にマイナス記号を置いたものが算術式の 1 つであることを表す場合は、普通は以下の構文規則を使用します。
expr : expr '-' expr
この構文規則では、複雑な入力のすべてを構成する方法は完全には指定されていないので注意してください。たとえば、以下のような入力の場合には、
expr - expr - expr
この規則では以下のいずれかでその入力を構成できます。
( expr - expr ) - expr
expr - ( expr - expr )
最初のものは左結合、2 番目のものは右結合と呼ばれています。
yacc は、パーサーを構築する際にこのようなあいまいさを検出します。以下のような入力を与えられたときにパーサーが直面する問題について考えます。
expr - expr - expr
パーサーが 2 番目の expr を読み取ったときには、この入力は以下のように認識されます。
expr - expr
これは、前述の構文規則の右側と一致します。パーサーは、この規則を適用することによって入力を還元 (reduce) できます。この規則を適用すると、入力は還元されて expr (規則の左側) になります。その後、パーサーは入力の最後の部分 (その部分を以下に示します) を読み取って、再度 reduce を実行します。
- expr
この結果、入力は左結合であるとみなされます。
あるいは、以下の入力を認識した場合に、
expr - expr
パーサーは、すぐにその規則を適用しないで、以下の入力を認識するまで読み取りを継続することもできます。
expr - expr - expr
この入力を認識した後で、パーサーは右端の 3 つのシンボルに対して規則を適用し、それを expr に還元できます。その結果、以下の入力が残ります。
expr - expr
これで、この規則をもう一度還元することが可能になります。この結果、入力は右結合であるとみなされます。したがって、以下の入力を読み取ったパーサーは、shift または reduce のいずれかの正当なアクションを実行できます。
expr - expr
shift と reduce を選択する方法はありません。これは、shift-reduce 衝突と呼ばれています。また、正当な 2 つの還元の選択肢をパーサーが持っている可能性もあります。これは、reduce-reduce 衝突と呼ばれています。shift-shift 衝突というものは存在しません。
shift-reduce 衝突や reduce-reduce 衝突が生じた場合でも、yacc はパーサーを生成します。yacc は、選択肢がある場所で有効なステップの 1 つを選択することによって、パーサーの生成を行います。所定の状況において行う選択を表した規則は、あいまいさ解決規則と呼ばれます。
yacc は、デフォルトの 2 つのあいまいさ解決規則を呼び出します。
-
shift-reduce 衝突の場合は、デフォルトは shift になります。
-
reduce-reduce 衝突の場合は、デフォルトは、読み込まれた yacc 仕様中で先に定義された文法規則による reduce になります。
規則 1 は、選択肢があるところでは還元はシフトの方に従うことを意味しています。規則 2 では、ユーザーがこの状況において行えるパーサーの動作の制御は多少おおまかなものになりますが、reduce-reduce 衝突は可能なかぎり避ける必要があります。
衝突は、入力や論理に誤りがあるとき、または yacc では構築できない複雑なパーサーが (矛盾のない) 構文規則で必要になったときに発生します。また、どの規則を認識しているのかをパーサーが確認する前にアクションを実行する必要がある場合には、規則内のアクションを使用すると衝突が発生することがあります。
これらの場合にあいまいさ解決規則を適用するのは不適切であり、パーサーも不正なものになります。そのため、yacc は上記の規則 1 と規則 2 によって解決された shift-reduce 衝突と reduce-reduce 衝突の数を常に報告します。
一般に、あいまいさ解決規則を適用して正しいパーサーを生成できるときには、構文規則を書き直して同じ入力を読み取るようにすることもできます。構文規則を書き直した場合には、衝突は発生しません。そのため、初期のパーサージェネレータでは、衝突は重大なエラーとして扱われていました。
このような書き直しは、やや不自然である上に、低速のパーサーが生成されることになります。そのため、yacc は衝突が存在している場合であってもパーサーを生成します。
あいまいさ解決規則の効果を表した例を以下に示します。
stat : IF '(' cond ')' stat
| IF '(' cond ')' stat ELSE stat
;
これは、if-then-else 文を含んだプログラミング言語のコードの一部です。これらの規則では、IF と ELSE はトークン、cond は条件 (論理) 式を表す非終端記号、stat は文を表す非終端記号になっています。最初の規則は単純 if 規則、2 番目の規則は if-else 規則と呼ばれます。
この 2 つの規則は、あいまいな構造を生じます。その理由は、以下のような形式の入力は、
IF ( C1 ) IF ( C2 ) S1 ELSE S2
その 2 つの規則に従った場合に以下の 2 つの方法で構成できるからです。
IF ( C1 )
{
IF ( C2 )
S1
}
ELSE
S2
IF ( C1 )
{
IF ( C2 )
S1
ELSE
S2
}
後者の解釈は、この構造を持った大部分のプログラミング言語で用いられる解釈です。つまり、各 ELSE は、ELSE に関連付けられていない直前の IF と関連付けられます。この例で、パーサーが以下の入力を認識してから ELSE を探す場合について考えます。
IF ( C1 ) IF ( C2 ) S1
この入力は、単純 if 規則によってすぐに以下のように還元されます。
IF ( C1 ) stat
そして、以下に示す残りの入力が読み取られます。
ELSE S2
次に、if-else 規則によって以下の入力が還元されます。
IF ( C1 ) stat ELSE S2
この結果、前述した前者の方の入力のグループ化が行われます。
一方、ELSE をシフトして、S2 を読み取ってから、以下の右側の部分に if-else 規則を適用すると、
IF ( C1 ) IF ( C2 ) S1 ELSE S2
以下のように還元できます。
IF ( C1 ) stat
これは、単純 if 規則で還元できます。
この結果、前述した後者の方の入力のグループ化が行われます。通常はこちらが望ましい方法です。
パーサーが行うことができる有効な処理が 2 つあるので、shift-reduce 衝突が存在します。この場合にあいまいさ解決規則 1 を適用すると、パーサーは shift を実行し、その結果目的のグループ化が行われます。この shift-reduce 衝突は、現在の入力シンボルが ELSE で、以下のような特定の入力が認識済みのときにだけ発生します。
IF ( C1 ) IF ( C2 ) S1
一般に、衝突は多数発生する可能性があり、各衝突は入力シンボルと以前に読み取った入力のセットに関連付けられます。以前に読み取った入力は、パーサーの状態によって特徴づけられます。
yacc の衝突メッセージの内容は、-v を指定した場合の出力を検討するとよくわかります。例として、上記の衝突状態に相当する出力を以下に示します。
23: shift-reduce conflict (shift 45, reduce 18) on ELSE
state 23
stat : IF ( cond ) stat_ (18)
stat : IF ( cond ) stat_ELSE stat
ELSE shift 45
. reduce 18
最初の行は、衝突に関する説明で、状態と入力シンボルが表示されています。通常の状態の場合には、その状態でアクティブな構文規則とパーサーのアクションが表示されます。下線記号はすでに認識されている構文規則の一部を表しています。
したがって、state 23 のこの例では、パーサーは以下に対応する入力をすでに認識しています。
IF ( cond ) stat
また、この時点では、表示されている 2 つの構文規則はアクティブです。パーサーは 2 通りの処理を行うことができます。入力シンボルが ELSE の場合には、state 45 にシフトできます。
ELSE は state 45 においてすでにシフトされているので、state 45 にはその記述の一部として以下の行が含まれています。
stat : IF ( cond ) stat ELSE_stat
state 23 では、入力シンボルがアクションの中に明示的に記述されていない場合には、代替アクション (. によって指定されたアクション) が実行されます。つまり、入力シンボルが ELSE 以外の場合には、パーサーは構文規則 18 によって以下のように還元を行います。
stat : IF '(' cond ')' stat
shift コマンドの後の数字は別の状態を参照しており、reduce コマンドの後の数字は構文規則番号を参照しています。y.output ファイルでは、規則番号は還元可能な規則の後の括弧内に出力されます。大部分の状態では、reduce が使用可能であり、reduce がデフォルトのコマンドになっています。予期しない shift-reduce が発生した場合には、-v オプションによる出力を調べて、デフォルトのアクションが適切かどうかを判断してください。
優先度
衝突を解決する規則が不十分である状況が 1 つあります。それは、算術式の構文解析における状況です。一般に使用される算術式の構成のほとんどは、演算子の優先度の概念と、左または右の結合規則に関する情報によって自然に表現できます。適切なあいまいさ解決規則を伴ったあいまいな文法を使用すれば、あいまいでない文法で構築されたパーサーよりも高速かつ容易に書き込めるパーサーを作成できます。基本的な概念は、必要なすべての二項演算子と単項演算子について、以下の形式で構文規則を作成するということです。
expr : expr OP expr
次に :
expr : UNARY expr
これにより、構文解析の衝突を多数伴った、非常にあいまいな文法が作成されます。
あいまいさ解決規則として、すべての演算子の優先度または結合の強さ、および二項演算子の結合規則を指定します。この情報によって、yacc がこれらの規則に従って構文解析の衝突を解決し、必要な優先度と結合規則を認識するパーサーを構築することができます。
優先度と結合規則は、宣言セクションでトークンに関連付けられます。この処理は、yacc キーワードの %left、%right、または %nonassoc の後にトークンのリストが続く一連の行によって行われます。同じ行にあるトークンは、すべて同じ優先度レベルと結合規則を持っているとみなされます。各行は、優先度または結合が強いものから順に記述されます。以下にその例を示します。
%left '+' '-' %left '*' '/'
この例では、4 つの算術演算子の優先度と結合規則が記述されています。+ と - は、左結合で、* と / よりも低い優先度を持っています。* と / も左結合です。キーワード %right は、右結合の演算子を表すために使用します。キーワード %nonassoc は、FORTRAN の演算子 .LT. などのような、互いに結合できない演算子を表すために使用します。つまり、以下の記述は FORTRAN では無効なので、.LT. は yacc ではキーワード %nonassoc を使用して表すことになります。
A .LT. B .LT. C
これらの宣言の例を以下に示します。
%right '='
%left '+' '-
%left '*' '/'
%%
expr : expr '=' expr
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| NAME
;
この記述を以下の入力に対して使用すると、
a = b = c * d - e - f * g
演算子の正しい優先度を実現するために、以下のように構成されます。
a = ( b = ( ((c * d) - e) - (f * g) ) )
このメカニズムを使用するときには、通常は単項演算子にも優先度を与える必要があります。単項演算子と二項演算子は、記号表現が同一の場合がありますが、優先度は必ず異なります。たとえば、単項演算子の - と二項演算子の - とでは、優先度が異なります。
単項演算子の - には、* (乗算) と同じか、それよりも高い優先度を与えることができますが、二項演算子の - は * よりも低い優先度になります。キーワード %prec は、特定の構文規則に関連付けられている優先度を変更します。この %prec は、構文規則の本体の直後の、アクションや終端のセミコロンの前に記述します。%prec の後にはトークン名またはリテラルを記述します。これにより、その構文規則の優先度は、後続のトークン名またはリテラルと同じ優先度になります。たとえば、以下の規則を使用すれば、単項演算子の - を * と同じ優先度にできます。
%left '+' '-'
%left '*' '/'
%%
expr : expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| '-' expr %prec '*'
| NAME
;
%left、%right、%nonassoc によって宣言されたトークンは、再度 %token によって宣言する必要はありません。ただし、宣言しても構いません。
優先度と結合規則は、構文解析の衝突を解決する際に yacc によって使用されます。優先度と結合規則によって、以下のようなあいまいさ解決規則が生成されます。
-
優先度と結合規則を持ったトークンやリテラルの優先度と結合規則が記録されます。
-
ある 1 組の優先度と結合規則が、各構文規則に関連付けられます。これらは、規則の本体にある最終的なトークンまたはリテラルの優先度と結合規則です。%prec 構文を使用した場合には、このデフォルト値はその構文の値に置換されます。その構文規則に関連付けられた優先度と結合規則を持っていない構文規則もあります。
-
reduce-reduce または shift-reduce 衝突が生じていて、入力シンボルまたは構文規則が優先度と結合規則を持っていない場合には、前節で示した 2 つのデフォルトのあいまいさ解決規則が使用され、その衝突が報告されます。
-
shift-reduce 衝突が生じていて、構文規則と入力文字の両方が共にそれぞれに関連付けられた優先度と結合規則を持っている場合には、さらに高い優先度に関連付けられたアクション (shift または reduce) を選択して、その衝突を解決します。優先度が等しい場合には、結合規則が使用されます。左結合は reduce、右結合は shift、非結合は error を意味します。
優先度によって解決された衝突は、yacc が報告する shift-reduce と reduce-reduce 衝突の数には加えられません。これは、優先度の仕様が間違っていると、入力構文のエラーを検出できなくなる可能性があることを意味しています。ある程度慣れるまでは優先度の使用を控えることも 1 つの方法です。y.output ファイルは、実際にパーサーが指定通りに動作しているかどうかを判定する際に利用できます。
優先度キーワードを使用して shift-reduce 衝突を解決する方法をさらに詳しく説明するため、前節の例と類似した例を取り上げます。以下の C 言語の文について考えます。
if (flag) if (anotherflag) x = 1;
else x = 2;
パーサーにとっての問題は、else に対応するのは最初の if なのか、それとも 2 番目の if なのかということです。C プログラマであれば、この字下げに惑わされることなく、else は 2 番目の if に対応していると判断するでしょう。if-then-else 構成の以下の yacc 文法では、この問題を抽象化しています。つまり、入力 iises (if-if.statement.else-statment) によってこれらの C の文を形成します。
%{
#include <stdio.h>
%}
%token SIMPLE IF ELSE
%%
S ; stmnt
;
stmnt : SIMPLE
| if_stmnt
;
if_stmnt : IF stmnt
{ printf("simple if¥n");}
| IF stmnt ELSE stmnt
{ printf("if_then_else¥n");}
;
%%
int
yylex() {
int c;
c=getchar();
if (c= =EOF) return 0;
else switch(c) {
case 'i': return IF;
case 's': return SIMPLE;
case 'e': return ELSE;
default: return c;
}
}
この仕様が yacc に渡されると、以下のメッセージが表示されます。
conflicts: 1 shift/reduce
問題なのは、yacc が iises と照合するために iis を読み取ったときに、選択肢が 2 つあるということです。つまり、is を文として認識する (reduce) 場合と、さらに入力を読み取って (shift)、最終的に ises を文として認識する場合があります。
この問題を解決する方法の 1 つとして、新しいトークン REDUCE を作成して解決する方法があります。この REDUCE の用途は、正しい優先度を規則に与えることです。
%{
#include <stdio.h>
%}
%token SIMPLE IF
%nonassoc REDUCE
%nonassoc ELSE
%%
S : stmnt '¥n'
;
stmnt : SIMPLE
| if_stmnt
;
if_stmnt : IF stmnt %prec REDUCE
{ printf("simple if");}
| IF stmnt ELSE stmnt
{ printf("if_then_else");}
;
%%
if_stmnt の 2 番目の形式に関連付けられている優先度が高くなっているので、yacc は最初にその規則との照合を試み、衝突も報告されません。
この単純な例では、実際には新しいトークンは必要ありません。
%nonassoc IF %nonassoc ELSE
上記の 2 つも機能します。また、shift-reduce 衝突では yacc はデフォルトで shift を行うので、実際には上記のような方法で衝突を解決する必要はありません。ただし、正しい仕様ならば診断メッセージは表示されないという点では、衝突を解決するのも良い方法です。
エラー処理
エラー処理には、意味上の問題がいくつか含まれています。たとえば、エラーが見つかったときに、構文解析ツリーの記憶領域の再生、シンボルテーブルのエントリの削除や変更、スイッチを設定して出力の生成を止めたりしなければならない場合があります。
エラーが見つかったときに処理をすべて停止するのは、あまり好ましくありません。入力の検査を継続してその先の構文エラーを見つける方が便利です。その場合には、エラーの後でパーサーを再始動させるという問題が持ち上がります。再始動を行う一般的な部類のアルゴリズムには、入力文字列からトークンをいくつか破棄する処理や、入力を継続するためにパーサーを調整しようとする、という処理が含まれています。
この処理の一部をユーザーが制御できるようにするため、yacc はエラーにトークン名 error を設定します。この名前は、構文規則の中で使用できます。結果的に、この名前は、エラーの発生する箇所と、エラー回復を行うことができる箇所を示します。
パーサーは、トークンエラーが有効な状態に入るまで、そのパーサーのスタックをポップします。そして、トークンエラーが現在の lookahead トークンであるかのようにふるまって、次のアクションを実行します。その後、lookahead トークンはエラーを引き起こしたトークンにリセットされます。エラー規則が特に指定されていない場合は、エラーの検出時に処理は停止します。
エラーメッセージが連続して出力されるのを避けるため、パーサーは、エラー検出後に 3 つのトークンを正常に読み取ってシフトするまではエラー状態を継続します。すでにパーサーがエラー状態にあるときにエラーを検出した場合には、メッセージは表示されず、入力トークンが削除されます。
たとえば、以下の形式の規則は、構文エラー時にパーサーはエラーが見つかった文を読み飛ばそうとすることを表しています。
stat : error
正確に言うと、パーサーは前方を検査し、正当に文の後に続いていると考えられる 3 つのトークンを探して、その 3 つの内の最初のトークンの処理を開始します。文の開始部分が明確でない場合は、誤って文の途中から処理を開始して、実際にはエラーではないところで 2 つ目のエラーを報告することがあります。
アクションは、これらの特別なエラー規則と共に使用できます。これらのアクションは、テーブルの再初期化、シンボルテーブル空間の修正などを試みます。上記のようなエラー規則は、非常に一般的な規則ですが、制御するのは困難です。
以下のような規則であれば、制御は多少容易になります。
stat : error ';'
この規則の場合は、エラーが見つかるとパーサーは文を次のセミコロンまで読み飛ばします。エラー後の次のセミコロンより前のトークンは、シフトできず、すべて破棄されます。セミコロンが見つかると、この規則は還元されてそれに関連するアクションが実行されます。
もう 1 つの形式は、エラーの後に行を再入力できるようにした方が望ましい対話型アプリケーションで用いられます。それを行う方法の 1 つを以下に示します。
input : error '¥n'
{
(void) printf("Reenter last line: " );
}
input
{
$$ = $4;
}
;
この方法には、潜在的な問題が 1 つあります。パーサーは、エラーの後で正しく再同期したことを確認する前に 3 つの入力トークンを正しく処理しなければなりません。再入力された行の最初の 2 つのトークンにエラーが含まれている場合には、パーサーはその不正なトークンを削除し、何もメッセージは表示しません。これは、好ましくない状態です。
そのために、エラーが回復されたことをパーサーに認識させるメカニズムが用意されています。アクションの中に以下の文があると、パーサーは通常のモードにリセットされます。
yyerrok ;
したがって、前述の例は、以下のように書き直すことができます。
input : error '¥n'
{
yyerrok;
(void) printf("Reenter last line: " );
}
input
{
$$ = $4;
}
;
エラーシンボルの直後に認識されたトークンは、エラーが発見された入力トークンです。場合によっては、このことが不適切になることがあります。たとえば、エラー回復アクションは、入力を再開する正しい位置を探すジョブを実行する必要があるとします。その場合には、1 つ前の lookahead トークンを消去する必要があります。アクションに以下の文を記述すれば、そのトークンは消去されます。
yyclearin ;
たとえば、次の有効な文の先頭まで入力を進める (ユーザーが作成した) 複雑な再同期化ルーチンの呼び出しが、エラー後のアクションであると仮定します。このルーチンを呼び出した後は、yylex() によって返された次のトークンは、有効な文の最初のトークンであるとみなされます。古い無効なトークンは破棄し、エラー状態をリセットする必要があります。これを実行する規則の例を以下に示します。
stat : error
{
resynch();
yyerrok ;
yyclearin;
}
;
これらのメカニズムは、確かに不完全ですが、簡単かつ効果的にパーサーを多くのエラーから回復できます。また、ユーザーは、プログラムの他の部分で必要なエラーアクションの処理を制御することもできます。
yacc 環境
$ yacc grammar.y
上記の grammar.y は yacc 仕様が含まれているファイルです (接尾辞 .y は、他のオペレーティングシステムによって認識される表記です。必ずこの表記にする必要はありません) 。 出力は、y.tab.c という C 言語サブルーチンのファイルになります。yacc が提供する関数は、yyparse() という整数値型の関数です。
yyparse() を呼び出すと、この関数は yylex() を繰り返し呼び出します。yylex() は、ユーザーが作成する、入力トークンを取得するための字句アナライザです (「字句解析」を参照)。エラーが検出されると、yyparse() は値 1 を返しますが、エラー回復を行うことはできません。または、字句アナライザがエンドマーカートークンを返して、パーサーがそれを受け取ります。その場合には、yyparse() は値 0 を返します。
実用的なプログラムを作成するためには、ある程度の環境をこのパーサーに提供する必要があります。たとえば、C 言語のプログラムの場合は、yyparse() を呼び出す main() というルーチンを必ず定義しなければなりません。また、構文エラーを検出したときにメッセージを出力するためには、yyerror() というルーチンが必要になります。
この 2 つのルーチンは、ユーザーがいずれかの形式で提供する必要があります。yacc をすぐに使えるようにするため、デフォルトの main() と yyerror() を備えたライブラリが用意されています。ライブラリには、cc コマンドに対する引数 -ly によってアクセスできます。これらのデフォルトプログラムのソースコードを以下に示します。
main()
{
return (yyparse());
}
# include <stdio.h>
yyerror(s)
char *s;
{
(void) fprintf(stderr, "%s¥n", s);
}
このように、デフォルトプログラムは非常に単純な構造になっています。yyerror() に対する引数は、エラーメッセージ (通常は、構文エラーのメッセージ) を含んだ文字列です。平均的なアプリケーションでは、これよりも複雑な処理が求められます。通常は、プログラムは入力の行番号を監視して、構文エラーを検出したときにメッセージと共にその行番号を出力する必要があります。外部整数変数 yychar には、エラーが検出されたときの lookahead トークンの番号が含まれています (これは診断に役立つ機能です)。ほとんどの場合、main() ルーチン (たとえば引数を読み取るなど) はユーザーによって提供されるので、yacc ライブラリは小規模プロジェクトや大規模プロジェクトの初期段階でしか役に立ちません。
外部整数変数 yydebug は、通常は 0 に設定されます。これを 0 以外の値に設定した場合には、パーサーは、読み取った入力シンボルやパーサーのアクションなどを含む、アクションの詳しい説明を出力します。
仕様の準備に関するヒント
この節では、効果的および明瞭で、変更が容易な仕様を準備するためのさまざまなヒントについて説明します。
入力スタイル
規則に実際のアクションを与え、同時に仕様ファイルも読みやすくするのは簡単なことではありません。スタイルに関するヒントをいくつか以下に示します。
-
トークン名にはすべて大文字、非終端名にはすべて小文字を使用してください。このように表記しておくと、デバッグの際に役立ちます。
-
構文規則とアクションを別々の行に置けば、編集が容易になります。
-
左側が同一の規則をまとめて置きます。1 つの規則の左側だけを残して、後の規則はすべて縦棒で始めてください。
-
左側の規則の最後の定義の後にだけセミコロンを置きます。そのセミコロンは別の行に置いてください。これにより、新しい規則を容易に追加できるようになります。
-
規則の本体は 1 個のタブ、アクションの本体は 2 個のタブを使用して字下げしてください。
-
複雑なアクションは、別のファイルで定義されたサブルーチンに入れてください。
この節の例は、このスタイルに従って書かれています。要点は、アクションのコードの中から規則を認識しやすいように記述することです。
左再帰
yacc パーサーによって使用されるアルゴリズムには、いわゆる左再帰構文規則が頻繁に利用されます。以下の形式の規則はこのアルゴリズムに一致します。
name : name rest_of_rule ;
シーケンスとリストの仕様を作成するときには、以下のような規則を頻繁に使用します。
list : item
| list ',' item
;
次に :
seq : item
| seq item
;
どちらの場合でも、最初の規則は最初の項目についてだけ還元され、2 番目の規則は 2 番目とそれ以降のすべての項目について還元されます。
以下のような右再帰規則を使用した場合には、パーサーのサイズが多少大きくなります。認識された項目は、右から左に向かって還元されます。
seq : item
| item seq
;
問題点は、非常に長いシーケンスを読み取った場合に、パーサーの内部スタックがオーバーフローを起こす可能性があることです (ただし、現在の yacc は、かなり大きなスタックを処理できるようになっています)。したがって、なるべく左再帰の方を使用するようにしてください。
ゼロのシーケンスに意味があるかどうかについて考えてみましょう。たとえば、空の規則を使用して以下のシーケンス仕様を作成した場合について考えます。
seq : /* 空 */
| seq item
;
最初の規則は最初の項目が読み取られる前に必ず 1 回だけ還元されます。2 番目の規則は、読み取られた各項目ごとに 1 回還元されます。空のシーケンスを許可すると、一般性が高くなることがよくあります。ただし、どの空シーケンスを認識したのかを、まだ十分に認識していない段階で yacc が判断するように要求された場合には、衝突が発生する可能性があります。
C++ 符号化シンボル
この節の内容は、第 2 章「字句解析」の 「C++ 符号化シンボル」と全く同じ内容です。lex を yacc に置き換えて読んでください。
字句連結
一部の字句の判断はコンテキストに依存します。たとえば、字句アナライザは通常は空白文字を削除しますが、引用符で囲まれた文字列の空白文字は削除しません。また、名前は宣言の中のシンボルテーブルに入力できますが、式の中のシンボルテーブルには入力できません。これらの状況に対処する方法の 1 つは、字句アナライザによって検査され、アクションによって設定される広域フラグを作成することです。以下にその例を示します。
%{
int dflag;
%}
... その他の宣言 ...
%%
prog : decls stats
;
decls : /* 空 */
{
dflag = 1;
}
| decls declaration
;
stats : /* 空 */
{
dflag = 0;
}
| stats statement
;
. . . その他の規則 . . .
この例では、0 個以上の宣言とそれに続く 0 個以上の文で構成されるプログラムが指定されています。文を読み取ると dflag は 0 になり、宣言を読み取ると dflag は 1 になります。ただし、最初の文の最初のトークンは除きます。
パーサーは、宣言セクションが終了して文が始まったことを認識する前に、このトークンを読み取る必要があります。多くの場合、この 1 つのトークン例外は、字句の検査には影響しません。この考え方は、難しい構造を表現する場合の手がかりになります。
予約語
一部のプログラミング言語では、通常はラベル名や変数名として予約されている if などのワードを使用できます。これらのプログラミング言語では、そのような使い方をしても本来の意味で使用されている名前とは衝突しません。しかし、これを yacc で実現するのは非常に困難です。
if のあるインスタンスがキーワードであるか変数であるかを伝える情報を字句アナライザに渡すのは容易ではありません。前節の情報を読むと、「字句連結」がここで役に立つことがわかります。
高度なトピック
この節では、yacc の高度な機能についていくつか説明します。
アクションにおける error と accept のシミュレーション
error と accept の構文解析アクションは、マクロ YYACCEPT と YYERROR を使用してアクションのなかでシミュレーションを行うことができます。YYACCEPT マクロを使用すると、yyparse() は値 0 を返します。YYERROR を使用すると、パーサーは現在の入力シンボルが構文エラーであるかのように動作します。つまり、yyerror() を呼び出して、エラー回復を実行します。
これらのメカニズムは、複数のエンドマーカーを持つパーサーのシミュレーションや、コンテキスト文法の検査に使用できます。
囲み規則の中の値へのアクセス
あるアクションは、左側に記述された規則のアクションによって返された値を参照できます。メカニズムは通常のアクションと同じで、$ の後に数字が 1 つ続きます。
sent : adj noun verb adj noun
{
look at the sentence ...
}
;
adj : THE
{
$$ = THE;
}
| YOUNG
{
$$ = YOUNG;
}
...
;
noun : DOG
{
$$ = DOG;
}
| CRONE
{
if ( $0 = = YOUNG )
{
(void) printf( "what?¥n" );
}
$$ = CRONE;
}
;
...
この例では、その数字は 0 または 負の値にできます。ワード CRONE の後のアクションでは、シフトされた前のトークンが YOUNG かどうかを検査します。ただし、この検査は、入力内のシンボル noun の前のシンボルについて詳しい情報が得られている場合にのみ可能です。場合によっては、このメカニズムによって多くの問題が回避できます。特に、他の標準構造から結合をいくつか除外するときに役立ちます。
任意値型のサポート
デフォルトでは、アクションと字句アナライザによって返される値は整数です。yacc は、構造体などの他の型の値もサポートできます。また、生成されるパーサーの型を厳密に検査するために、yacc は型を監視して、適切な共用体のメンバー名を挿入します。yacc の値スタックは、必要なさまざまな型の値の共用体として宣言されます。共用体を宣言したら、値を持った各トークンと非終端記号に共用体のメンバー名を関連付けます。$$ または $n 構成によって値が参照されると、yacc は、不要な変換が起きないように、適切な共用体の名前を自動的に挿入します。
これには 3 つのメカニズムが用意されています。1 つ目は、共用体を定義する方法です。他のサブルーチン (特に、字句アナライザ) は共用体のメンバー名を知る必要があるので、この定義はユーザーが行わなければなりません。2 つ目は、共用体のメンバー名をトークンと非終端記号に関連づける方法です。3 つ目は、yacc が容易に型を判定できないごく少数の値の型を表すメカニズムです。
共用体を宣言するには、以下の記述を宣言セクションに加えます。
%union
{
共用体の本体
}
これにより、yacc の値スタックと外部変数 yylval および yyval は、この共用体と同じ型で宣言されます。-d オプションを付けて yacc を呼び出した場合には、共用体の宣言は y.tab.h ファイルに YYSTYPE としてコピーされます。
YYSTYPE を定義したら、共用体のメンバー名を各種の終端および非終端の名前に関連づける必要があります。以下の構文を使用して、共用体のメンバー名を指定します。
<name>
%token、%left、%right、%nonassoc のいずれかのキーワードの後に上記の指定が続いている場合は、共用体の名前は記述されているトークンに関連付けられます。
したがって、以下のように記述すると、これら 2 つのトークンによって返された値に対する参照には、すべて共用体のメンバー名 optype がタグとして付けられます。
%left <optype> '+' '-'
もう 1 つのキーワード %type は、共用体のメンバー名を非終端記号に関連づける際に使用します。たとえば、以下の規則を使用すれば、共用体メンバー nodetype を非終端記号 expr と stat に関連づけることができます。
%type <nodetype> expr stat
これらのメカニズムでは対応しきれないケースもいくつかあります。規則のなかにアクションがある場合には、そのアクションによって返される値には型がありません。同様に、左側のコンテキスト値 (たとえば、$0 など) を参照した場合は、yacc はその型を容易に知ることができなくなります。この場合には、最初の $ の直後の < と > の間に共用体のメンバー名を挿入することによって、型を強制的に参照できます。その例を以下に示します。
rule : aaa
{
$<intval>$ = 3;
}
bbb
{
fun( $<intval>2, $<other>0 );
}
;
この構文には特に説明することはありませんが、このような状況は頻繁に発生します。
任意値型のサポート機能は、実際に使用されるまでは起動されません。特に %type の使用によって、これらのメカニズムは有効になります。これらの機能を使用するときには、非常に厳密な検査が行われます。
たとえば、型が定義されていないものを $n または $$ を使用して参照すると、型の診断が行われます。これらの機能を起動しない場合は、yacc の値スタックは int を保持するために使用されます。
yacc 入力構文
この節では、yacc 仕様としての yacc 入力構文について説明します。コンテキスト依存性などについては考慮していません。yacc では LALR(1) 文法を使用することもできますが、yacc 入力仕様言語は、LR(2) 文法として指定されています。この文法では、規則内のアクションの直後に識別子があると、問題が発生します。
この識別子の後にコロンが続いている場合には、次の規則の開始を表しています。コロンが続いていない場合は、現在の規則の続きであり、その規則のなかに偶然アクションが埋め込まれていただけに過ぎません。字句アナライザは、識別子を認識した後にその先を読み取り、次のトークン (空白文字、復帰改行、コメントなどは読み飛ばします) がコロンかどうかを判定します。コロンの場合には、トークン C_IDENTIFIER を返します。
コロンでない場合には、IDENTIFIER を返します。リテラル (引用符で囲んだ文字列) も C_IDENTIFIER としてではなく、必ず IDENTIFIER として返されます。
/* yacc に対する入力の文法 */
/* 基本エントリ */
%token IDENTIFIER /* 識別子とリテラルの取り込み */
%token C_IDENTIFIER /* 識別子 (リテラル以外) */
/* 後に a : が続く */
%token NUMBER /* [0-9]+ */
/* 予約語: %type=>TYPE %left=>LEFT、等 */
%token LEFT RIGHT NONASSOC TOKEN PREC TYPE START UNION
%token MARK /* %% 記号 */
%token LCURL /* %{ 記号 */
%token RCURL /* %) 記号 */
/* 自分自身を表す ASCII 文字リテラル*/
%token spec t
%%
spec : defs MARK rules tail
;
tail : MARK
{
In this action,read in the rest of the file
}
| /* 空: 2 番目の MARK は省略可 */
;
defs : /* 空 */
| defs def
;
def : START IDENTIFIER
| UNION
{
Copy union definition to output
}
| LCURL
{
Copy C code to output file
}
RCURL
| rword tag nlist
;
rword : TOKEN
| LEFT
| RIGHT
| NONASSOC
| TYPE
;
tag : /* 空: 共用体タグは省略可 */
| '<' IDENTIFIER '>'
;
nlist : nmno
| nlist nmno
| nlist ',' nmno
;
nmno : IDENTIFIER /* 注: リテラル % type では無効 */
| IDENTIFIER NUMBER /* 注: % type では無効 */
;
/* 規則セクション */
rules : C_IDENTIFIER rbody prec
| rules rule
;
rule : C_IDENTIFIER rbody prec
| '|' rbody prec
;
rbody : /* 空 */
| rbody IDENTIFIER
| rbody act
;
act : '{'
{
Copy action translate $$ etc.
}
'}'
;
prec : /* 空 */
| PREC IDENTIFIER
| PREC IDENTIFIER act
| prec ';'
;
例
簡単な例
以下のコード例では、小型電卓に対して yacc を完全に適用する例を示します。この電卓は、a 〜 z の名前が付いた 26 個のレジスタを持っており、演算子 +、-、*、/、%、&、| と代入演算子で構成された算術式を使用できます。
最上位レベルの式が代入の場合は、その代入だけが行われます。それ以外の場合は、式が出力されます。C 言語の場合と同じように、0 で始まる整数は 8 進数とみなされます。それ以外は、10 進数とみなされます。
yacc 仕様の例として、この電卓プログラムでは、優先度とあいまいさの使い方を示し、簡単な回復処理も含まれています。大幅に簡略化されているのは字句アナライザの部分で、大部分のアプリケーションよりもかなり単純なものになっています。また出力は行ごとにすぐ生成されます。
構文規則によって 8 進 と 10 進の整数を読み取る方法に注目してください。このジョブは、字句アナライザで実行することもできます。
%{
# include <stdio.h>
# include <ctype.h>
int regs[26];
int base;
%}
%start list
%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' %'
%left UMINUS /* 単項演算子 - の優先度を指定 */
%% /* 規則セクションの開始 */
list : /* 空 */
| list stat '¥n'
| list error '¥n'
{
yyerrok;
}
;
stat : expr
{
(void) 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;
}
| exp '%' expr
{
$$ = $1 % $3;
}
| expr '&' expr
{
$$ = $1 & $3;
}
| expr '|' expr
{
$$ = $1 | $3;
}
| '-' expr %prec UMINUS
{
$$ = -$2;
}
| LETTER
{
$$ = reg[$1];
}
| number
;
number : DIGIT
{
$$ = $1; base = ($1= =0) ? 8 ; 10;
}
| number DIGIT
{
$$ = base * $1 + $2;
}
;
%% /* サブルーチンセクションの開始 */
int yylex( ) /* 字句解析ルーチン */
{ /* 小文字の場合は LETTER を返す */
/* yylval = 0 〜 25、DIGIT を返す */
/* 数字の場合、yylval = 0 〜 9 */
/* その他の文字はすぐに返される */
int c; /* 空白は読み飛ばす */
while ((c = getchar()) = = ' ')
;
/* c は空白以外の文字 */
if (islower(c)) {
yylval = c - 'a';
return (LETTER);
}
if (isdigit(c)) {
yylval = c - '0';
return (DIGIT);
}
return (c);
}
|
高度な例
この節では、高度な機能をいくつか使用した文法の例を示します。例 1 の電卓を変更して、浮動小数点区間演算を実行できる電卓にしています。この電卓は、浮動小数点定数、算術演算子 +、-、*、/ 、および単項演算子 - を認識します。また、この電卓は、a 〜 z のレジスタを使用します。さらに、次のような X が Y より小さいまたは等しい区間演算も理解できます。
(X、Y)
A 〜 Z の 26 個の区間値変数を使用することもできます。使い方は例 1 の電卓と同様で、代入は値を返さず何も出力しませんが、式は (浮動小数点または区間) 値を出力します。
この例では、yacc と C の多数の機能を利用しています。区間は、double として保存されている左終点と右終点の値で構成される構造体で表されます。この構造体には、typedef によって型名 INTERVAL が与えられます。
また、yacc の値スタックは、浮動小数点のスカラーと整数 (変数の値を格納する配列を指し示すために使用されます) を含むことができます。このプログラム全体の設計は、C 言語の構造体と共用体を割り当てることが可能ということに強く依存しているので注意してください。実際に、多くのアクションは構造体を返す関数を呼び出しています。
YYERROR を使用して、0 を含んだ区間による除算や、誤った順序で表された区間などのエラー状態を処理している点に注目してください。また、yacc のエラー回復メカニズムを使用して、残りの不正な行を無視しています。
値スタックでの型の混在に加え、この文法では、中間式の型 (スカラーや区間など) を監視する構文を使用することもできます。また、コンテキストで区間値が必要になった場合には、スカラー値を自動的に区間値に昇格できます。ただしその場合には、yacc によって文法が実行されたときに多数の衝突 (18 個の shift-reduce、26 個の reduce-reduce) が発生することになります。
この問題は、以下の 2 つの入力行で確認できます。
2.5 + (3.5 - 4.)
次に :
2.5 + (3.5, 4)
2 番目の例では区間値の式で 2.5 が使用されていますが、区間値であることはコンマを読み取るまでわからないということに注意してください。2.5 を読み取ったパーサーは、後戻りすることはできず、別の処理を行うことになります。一般的に、任意の数のトークンを先読みし、スカラーを区間に変換するかどうかを判断する必要があります。
この問題は、2 項区間値の演算子の規則を 2 つ用意することによって回避できます。1 つは、左側のオペランドがスカラーのときの規則、もう 1 つは、左側のオペランドが区間のときの規則です。後者の場合には、右側のオペランドを区間にする必要があります。それにより、変換は自動的に適用されます。
この問題回避を行なっても、変換するかどうかを判断しなければならないために、上記の衝突が発生する場合が多数あります。これらの問題は、スカラーを先に生成する規則を仕様ファイルに記述することによって解決されます。これにより、スカラー値の式は強制的に区間に変換されるまではスカラー値のまま維持されるため、衝突は解決されます。
複数の型を扱うこの方法は、参考になります。2 つだけでなくさまざまな型の式がある場合には、必要になる規則の数は大幅に増加し、衝突の数もさらに増加します。したがって、この例は確かに有益ですが、もっと普通のプログラミング言語環境における実践で、文法の一部ではなく値の一部として型の情報を扱うことをお勧めします。
最後に、字句解析に関する事項を説明します。このプログラムの唯一の特殊な機能は、浮動小数点定数の処理です。C 言語のライブラリルーチン atof() を使用して、文字列から倍精度の値への実際の変換を行なっています。字句アナライザは、エラーを検出すると、文法内の無効なトークンを返すことで応答します。これにより、パーサー内で構文エラーが発生し、エラー回復が行われます。yacc 仕様のコード例を以下に示します。
%{
#include <stdio.h>
#include <ctype.h>
typedef struct interval {
double lo, hi;
} INTERVAL;
INTERVAL vmul(), vdiv();
double atof();
double dreg[26];
INTERVAL vreg[26];
%}
%start lines
%union {
int ival;
double dval;
INTERVAL vval;
}
%token <ival> DREG VREG /* dreg と vreg 配列へのインデックス */
%token <dval> CONST /* 浮動小数点定数 */
%type <dval> dexp /* 式 */
%type <vval> vexp /* 区間式 */
/* 演算子に関する優先順位の情報 */
%left '+' '/-'
%left '*' '/'
%% /* 規則セクションの開始 */
lines : /* 空 */
| lines line
;
line : dexp '¥n'
{
(void)printf("%15.8f¥n", $1);
}
| vexp '¥n'
{
(void)printf("(%15.8f, %15.8f)¥n", $1.lo, $1.hi);
}
| DREG '=' dexp '¥n'
{
dreg[$1] = $3;
}
| VREG '=' vexp '¥n'
{
vreg[$1] = $3;
}
| error '¥n'
{
yyerrok;
}
;
dexp : CONST
| DREG
{
$$ = dreg[$1];
}
| dexp '+' dexp
{
$$ = $1 + $3;
}
| dexp '-' dexp
{
$$ = $1 - $3;
}
| dexp '*' dexp
{
$$ = $1 * $3;
}
| dexp '/' dexp
{
$$ = $1 / $3;
}
| '-' dexp
{
$$ = -$2;
}
| '(' dexp ')'
{
$$ = $2;
}
;
vexp : dexp
{
$$.hi = $$.lo = $1;
}
| '(' dexp ',' dexp ')'
{
$$.lo = $2;
$$.hi = $4;
if($$.lo > $$.hi) {
(void) printf("interval out of order¥n");
YYERROR;
}
}
| VREG
{
$$ = vreg[$1];
}
| vexp '+' vexp
{
$$.hi = $1.hi + $3.hi;
$$.lo = $1.lo + $3.lo;
}
| dexp '+' vexp
{
$$.hi = $1 + $3.hi;
$$.lo = $1 + $3.lo;
}
| vexp '-' vexp
{
$$.hi = $1.hi - $3.lo;
$$.lo = $1.lo - $3.hi;
}
| dexp '-' vexp
{
$$.hi = $1 - $3.lo;
$$.lo = $1 - $3.hi;
}
| vexp '*' vexp
{
$$ = vmul($1.lo, $1.hi, $3);
}
| dexp '*' vexp
{
$$ = vmul($1, $1, $3);
}
| vexp '/' vexp
{
if (dcheck($3)) YYERROR;
$$ = vdiv($1.lo, $1.hi, $3);
}
| dexp '/' vexp
{
if (dcheck($3)) YYERROR;
$$ = vdiv($1, $1, $3);
}
| '-' vexp
{
$$.hi = -$2.lo;
$$.lo = -$2.hi;
}
| '(' vexp ')'
{
$$ = $2;
}
;
%% /* サブルーチンセクションの開始 */
# define BSZ 50 /* 浮動小数点数値のバッファーサイズ */
/* 字句解析 */
int yylex()
{
register int c;
/* 空白文字は読み飛ばす */
while ((c=getchar()) = = ' ')
;
if (isupper(c)) {
yylval.ival = c - 'A';
return(VREG);
}
if (islower(c)) {
yylval.ival = c - 'a';
return(DREG);
}
/* 数字、小数点、指数 */
if (isdigit(c) || c = = '.') {
char buf[BSZ + 1], *cp = buf;
int dot = 0, exp = 0;
for (;(cp - buf) < BSZ; ++cp, c = getchar()) {
*cp = c;
if (isdigit(c))
continue;
if (c = = '.') {
if (dot++ || exp)
return('.'); /* 構文エラーが発生する */
continue;
}
if (c = = 'e') {
if (exp++)
return('e'); /* 構文エラーが発生する */
continue;
}
/* 数字の終わり */
break;
}
*cp = '¥0';
if (cp - buf >= BSZ)
(void)printf("constant too long -- truncated¥n");
else
ungetc(c, stdin); /* 最後に読み取った char を元に戻す */
yylval.dval = atof(buf);
return(CONST);
}
return(c);
}
INTERVAL
hilo(a, b, c, d)
double a, b, c, d;
/* vmul と vdiv ルーチンで使用した a、b、c、d を含む最小区間を返す */
INTERVAL v;
if (a > b) {
v.hi = a;
v.lo = b;
}
else {
v.hi = b;
v.lo = a;
}
if (c > d) {
if (c > v.hi)
v.hi = c;
if (d < v.lo)
v.lo = d;
}
else {
if (d > v.hi)
v.hi = d;
if (c < v.lo)
v.lo = c;:
}
return(v);
}
INTERVAL
vmul(a, b, v)
double a, b;
INTERVAL v;
{
return(hilo(a * v.hi, a * v.lo, b * v.hi, b * v.lo));
}
dcheck(v)
INTERVAL v;
{
if (v.hi >= 0. && v.lo <= 0.) {
(void) printf("divisor interval contains 0.¥n");
return(1);
}
return(0);
}
INTERVAL
vdiv(a, b, v)
double a, b;
INTERVAL v;
{
return(hilo(a / v.hi, a / v.lo, b / v.hi, b / v.lo));
}
|
- © 2010, Oracle Corporation and/or its affiliates