yacc コマンドで生成されるパーサー操作

yacc コマンドは、文法ファイルを C 言語プログラムに変換します。

そのプログラムは、コンパイルして実行すると、指定された文法仕様に従って入力を構文解析します。

パーサーは、スタックのある有限状態マシンです。パーサーは、ルック・アヘッド・トークンを読み取って覚えることができます。現在の状態は、常にスタックの一番上にある状態です。有限状態マシンの状態は、短整数によって表されます。最初のマシンの状態は 0 で、スタックには 0 しか入っておらず、ルック・アヘッド・トークンをまだ読み取っていません。

マシンは、次のアクションの中の 1 つを実行できます。

アクション	説明
shift State	パーサーは、現在の状態をスタックにプッシュし、 State を現在の状態にし、ルック・アヘッド・トークンをクリアします。
reduce Rule	入力ストリーム中に Rule (規則番号) で定義された文字列を発見すると、パーサーはその文字列を出力ストリームで Rule に置き換えます。
accept	パーサーはすべての入力を見て、それを文法仕様に対して突き合わせ、入力を最高レベルの構造 (開始記号によって定義される) を満たすものとして認識します。このアクションは、ルック・アヘッド・トークンが終了マーカーであり、パーサーがそのジョブを正常に実行したことが示されている場合だけ現れます。
error	パーサーは入力ストリームの処理を継続できませんが、それを文法仕様で定義されている任意の規則と正常に突き合わせることはできます。パーサーが見る入力トークンは、ルック・アヘッド・トークンとともに、その後に有効な入力になるようなものを続けることができません。パーサーは、エラーを報告して状況のリカバリーを試み、構文解析を再開します。

パーサーは、1 つのプロセス・ステップの間に次に示すアクションを実行します。

現在の状態に基づいて、パーサーはとるべきアクションを判断するためにルック・アヘッド・トークンが必要かどうかを決定します。ルック・アヘッド・トークンが必要なのにそれを持っていない場合、パーサーは yylex サブルーチンを呼び出して次のトークンを取得します。
現在の状態、および必要ならばルック・アヘッド・トークンを使用して、パーサーは次のアクションを決定し、実行します。その結果、状態がスタックにプッシュされるかまたはスタックからはじき出されて、ルック・アヘッド・トークンが処理されるかまたはそのままの状態にされます。

シフト・アクション

シフト・アクションは、パーサーが行う最も一般的なアクションです。パーサーがシフトするときは、常にルック・アヘッド・トークンが存在します。例えば、次の文法仕様規則を考えてみましょう。

IF shift 34

パーサーがこの規則を収めた状態にあり、ルック・アヘッド・トークンが IF である場合、パーサーは以下のように稼働します。

スタックの現在の状態をプッシュする。
状態 34 を現在の状態にする (状態 34 をスタックの一番上に書き込む)。
ルック・アヘッド・トークンをクリアする。

縮小アクション

縮小アクションは、スタックが大きくなりすぎるのを防ぎます。パーサーは、規則の右側を入力ストリームと突き合わせた後で、縮小アクションを使用します。そうすると、パーサーは入力ストリーム内の文字を規則の左側で置き換える態勢ができます。パーサーは、ルック・アヘッド・トークンを使用して、パターンが完全な一致かどうかを決定する必要がある場合があります。

縮小アクションは、個々の文法規則と関連しています。文法規則には短整数もあるので、shift と reduce の 2 つのアクションの数字の意味を混同しがちです。例えば、次のアクションは文法規則 18 を参照します。


. reduce 18

次のアクションは、状態 34 を参照します。


IF shift 34

例えば、次の規則を縮小するために、パーサーは一番上から 3 つの状態をスタックからはじき出します。

A  :  x y z ;

はじき出された状態の数は、規則の右側の記号の数と同じです。これらの状態は、 x、y、および z を認識しているときに、スタックに置かれるものです。これらの状態をポップした後には状態は保護されません。これはパーサーが規則の処理を開始する前の状態、つまり、規則 A を認識して、その規則を満足させる必要のある状態です。この保護されていない状態と規則の左側の記号を使用して、パーサーは goto と呼ばれるアクションを実行します。これは、A のシフトと似ています。新しい状態が取得され、スタック上にプッシュされ、構文解析が継続します。

goto アクションは、通常のトークンのシフトとは異なります。ルック・アヘッド・トークンはシフトによってクリアされますが、 goto アクションの影響は受けません。 3 つの状態がはじき出されると、この保護されていない状態には、次のような項目があります。

A  goto 20

この項目によって、状態 20 がスタックにプッシュされ、現在の状態の状態になります。

ユーザーが指定したアクションと値を扱うときには、縮小アクションも重要です。規則を縮小すると、パーサーは、スタックの調整の前にユーザーが規則に組み込んだコードを実行します。状態を保持しているスタックと並行して実行している別のスタックは、字句解析プログラムとアクションによって戻された値を保持します。シフトが行われると、yylval 外部変数が値を保持しているスタック上にコピーされます。ユーザーが指定したコードの実行後に、パーサーが縮小を実行します。パーサーが goto アクションを実行すると、yylval 外部変数は値のスタックへコピーされます。 $ で始まる yacc キーワードは、値のスタックを参照します。