GNU Bison

GNU Bison は文脈自由文法からパーサーを生成します。Yacc 互換の記法でトークン、非終端記号、意味値、アクションを定義し、生成されたパーサーは慣例に従ってスキャナーからトークンを取得します。スケルトンや言語固有のインターフェースについては GNU Bison マニュアルを参照してください。

文法セクション、値、アクション #

文法は %% で区切られた宣言、生成規則、任意のエピローグコードから成ります。宣言ではトークン、値の型、優先順位、パーサー設定、必要なコードを定義します。生成規則では非終端記号とアクションを定義します。

bison

%define api.value.type {int}
%token NUMBER
%left '+' '-'
%%
expression:
    NUMBER                 { $$ = $1; }
  | expression '+' expression { $$ = $1 + $3; }
  ;
%%

アクションは対応する生成規則が還元されたときに実行されます。$$ は結果の意味値を表し、$1、$2 などは右辺の値を表します。記号が異なる値型を持つ場合は、%union とともに %type および型付き %token 宣言を使うか、適切な %define api.value.type 設定を使います。エラー回復中に破棄される値を、デストラクターと所有権規則が確実に処理するようにしてください。

名前とパーサーインターフェース #

C パーサーは既定で yyparse、yylex、yyerror を使います。%define api.prefix {project_} により生成される外部名に固有の接頭辞を付けられるため、1 つのプログラムに複数の生成パーサーをリンクできます。対応する接頭辞とヘッダー契約でスキャナーを設定します。

既定のプルパーサーは自らレクサーを呼び出します。%define api.push-pull push はトークンを供給する呼び出し側向けのプッシュインターフェースを生成し、both はプルとプッシュの両方を提供します。%define api.pure full は再入可能インターフェースからパーサーのグローバル状態を除去しますが、並行設計には再入可能なスキャナーと明示的なコンテキスト受け渡しも必要です。 %parse-param と %lex-param を使って、そのコンテキストをパーサーとレクサーの呼び出しに渡します。

位置情報、優先順位、競合 #

診断でソース範囲が必要な場合は %locations を有効にします。アクションは左辺と右辺の位置情報を @$ と @1 で参照できます。レクサーは無視される空白を含むすべての入力について、位置フィールドを一貫して設定する必要があります。

%left、%right、%nonassoc、%precedence、%prec は、宣言された優先順位と結合規則に従って選択したシフト/還元競合を解決します。それ以外では、Bison はシフト/還元競合ではシフトを優先し、還元/還元競合では先にある規則を使います。どちらの既定動作も、意図した言語意味論を保証しません。すべての競合を調査し、利用可能なら -Wcounterexamples で例を取得し、 %expect は確認済みの競合数を表明する場合にだけ残してください。

エラー回復 #

Bison は回復用生成規則のために error トークンを予約しています。構文エラーが発生すると、 statement: error ';' のような生成規則で同期トークンまで入力を破棄し、後続の文を解析できます。アクションが意図的に回復を終了するときだけ yyerrok を使い、先読みトークンが不適切だと分かっているときだけ yyclearin を使います。

回復処理では破棄した意味値を解放し、処理を前進させ、連鎖したエラーを独立した根本原因として報告しないようにします。回復点は式の内部で任意のトークンを受け入れるのではなく、文、宣言、閉じ区切り文字など安定した文法境界に置きます。