test

プログラミングユーティリティ

パーサーの操作

yacc を使用して、仕様ファイルを C 言語の手続きに変換します。この手続きは、与えられた仕様に従って入力を構文解析します。仕様からパーサーへの変換で使用されるアルゴリズムは非常に複雑なので、ここでは説明しません。ただし、パーサー自体は比較的シンプルであり、その使い方を理解すればエラー回復やあいまいさの取扱いが容易になります。

yacc によって生成されたパーサーは、スタックを持った有限状態マシンで構成されています。パーサーは、lookahead トークンと呼ばれる次の入力トークンを読み取ってそれを記憶することもできます。現在の状態は常にスタックの 1 番上にあります。有限状態マシンの状態には、小さい整数のラベルが付けられます。初期状態では、マシンは状態 0 (スタックには状態 0 しか入っていません) になっており、lookahead トークンもまだ読み取られていません。

マシンで実行できるアクションは、shift (シフト)、reduce (還元)、accept (受理)、error (エラー) の 4 つだけです。パーサーの動作手順を以下に示します。

  1. パーサーは、実行するアクションを選択するためには lookahead トークンが必要かどうかを現在の状態に基づいて判断します。lookahead トークンが必要で、まだそのトークンを持っていない場合には、パーサーは yylex() を呼び出して次のトークンを取得します。

  2. パーサーは、必要であれば現在の状態と 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 が再度取り出されます。