test

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

基本仕様

名前とは、トークンまたは非終端記号のことを指します。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 の宣言は宣言セクションに置くことができます。字句アナライザのコードは、以下のようにして、別にコンパイル済みファイルに置くこともできます。