前: Action Types, 上: Semantics


3.5.5 規則の途中のアクション

まれに、アクションを規則の途中に置くと便利な場合があります。 これらのアクションは、通常の規則の終わりに置かれたアクションと同様に 記述されますが、構文解析器が後に続く要素を認識する前に実行されます。

規則の途中のアクションは、そのアクションよりも前にある要素を $nを使って参照できますが、後に続く要素は まだ構文解析されていないので参照できません。

規則の途中のアクション自身は、規則の要素の1つとして数えられます。 同じ規則の中に別のアクションが続く場合(通常は最後)に問題が起きます。 $nに使う番号nに 規則の途中のアクションを数えるのを忘れないように注意してください。

規則の途中のアクションは、意味値を持てます。 そのアクションは、$$への代入で値を定め、 後に続くアクションの中で、$nで値を参照できます。 アクションに記号名を対応させる方法がないので、 アクションのデータ型を宣言できません。 そこで、アクションの意味を参照するときに、 `$<...>'を使ってデータ型を指定する必要があります。

規則の途中のアクションでは、$$への代入が規則の値に関係しないので、 規則全体の値を設定する方法はありません。 規則全体の値を設定する唯一の方法は、 規則の最後に置かれた通常のアクションです。

架空のコンパイラの例を示します。 ここでは、`let (variable) statement'のような書式の let文を使え、statementの持続期間中に一時的に variableという名前の変数を作ります。 これを構文解析するために、statementを解析している間、 variableを記号表に置いておき、 後で記号表から削除する必要があります。 これを実現する方法を示します。

     stmt:   LET '(' var ')'
                     { $<context>$ = push_context ();
                       declare_variable ($3); }
             stmt    { $$ = $6;
                       pop_context ($<context>5); }

`let (variable)'が認識されるとすぐに、 最初のアクションが実行されます。 そのアクションは、現在の意味文脈、すなわち参照可能な変数の表の複製を、 データ型共用体の中のcontext型で、 アクションの意味値として保存します。 そして、declare_variableを呼び出して、 新しい変数を記号表に追加します。 最初のアクションが終わると、後続するstmtの解析が可能になります。 規則の途中のアクションが5番目の要素であることに注意してください。 したがって、`stmt'は6番目の要素になります。

後続する文が解析されると、その意味値がlet文全体の意味値になります。 そして、最初のアクションの意味値は、 変数の表を元に戻すために使われます。 そこで、let文中での一時変数が表から削除され、 構文解析されるプログラムの残りの部分では一時変数が存在しません。

構文解析器は、アクションを実行する順序を決めるために、 構文解析する必要があるので、 規則が完全に認識される前にアクションを実行することは、 しばしば不整合を起こします。 たとえば、後述の2個の規則は、規則の途中のアクションを持たないので、 実行可能な構文解析器の中で共存できます。 それは、構文解析器は開きブレーストークンをシフトでき、 宣言があるかどうか調べるために後に続くものを先読みできるからです。

     compound: '{' declarations statements '}'
             | '{' statements '}'
             ;

しかし、次の例のように、規則の途中のアクションを加えると、 この規則は働かなくなります。

     compound: { prepare_for_local_variables (); }
               '{' declarations statements '}'
             | '{' statements '}'
             ;

ここでは、開きブレースを見つけた時点で、 規則の途中のアクションを実行する必要があるかどうかの決定を迫られます。 言い換えれば、正しく判断するための十分な情報なしに、 ある規則か別の規則のどちらかにゆだねる必要があります。 開きブレーストークンは、これを読んだ時点では構文解析器が 何をすべきか決定する途中なので、先読み(look-ahead)トークンと 呼ばれます。See Look-Ahead Tokens

次のように同一のアクションを置くことで、 この問題を解決できるように思えるかもしれません。

     compound: { prepare_for_local_variables (); }
               '{' declarations statements '}'
             | { prepare_for_local_variables (); }
               '{' statements '}'
             ;

しかし、Bisonには2つのアクションが同一であるかどうかわからないので、 問題は解決しません。 Bisonは、アクションの中のCで書かれたプログラムを、 決して解釈しようとしません。

C言語のように、最初のトークンによって文と宣言を区別できるような 文法ならば、実現可能な解決方法の1つは、次の例のように、 開きブレースの後にアクションを置くことです。

     compound: '{' { prepare_for_local_variables (); }
               declarations statements '}'
             | '{' statements '}'
             ;

これで、続く宣言または文の最初のトークンによって、 Bisonがどちらの規則を使うべきかわかります。

別の解決方法は、サブルーチンとして働く非終端記号の内側に、 アクションを埋め込むことです。

     subroutine: /* 空 */
               { prepare_for_local_variables (); }
             ;
     
     compound: subroutine
               '{' declarations statements '}'
             | subroutine
               '{' statements '}'
             ;

これで、Bisonはcompoundに対してどちらの規則を使うべきか決めずに、 subroutineに対する規則中のアクションを実行できます。 任意の規則中のアクションは、この方法によって、 規則の最後のアクションに変換できます。 実際に、Bisonの内部では、このようにして、 規則中のアクションという機能が実現されています。