[ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Bisonは、文脈自由文法の仕様を入力として受け取り、 その文法の正しいインスタンスを認識する、 C言語の関数を生成します。
Bison文法ファイルの名前は、通常`.y'で終わります。
3.1 Bison文法の概要 | 文法ファイルの概略. | |
3.2 記号、終端と非終端 | ||
3.3 文法規則の構文 | ||
3.4 再帰的規則 | ||
3.5 言語の意味の定義 | ||
3.6 Bison宣言 | ||
3.7 同一プログラム中の複数の構文解析器 | 一つのプログラムに一つより多くのBison構文解析器を 入れる. |
Bison文法ファイルは4つの主要な部分からなります。 それらを、適切な区切り文字とともに示します。
%{ C宣言部(C declarations) %} Bison宣言部(Bison declarations) %% 文法規則部(Grammar rules) %% 追加のCプログラム部(Additional C code) |
`/* … */'で囲まれたコメントは、どの部分にも書けます。
3.1.1 C宣言部 | ||
3.1.2 Bison宣言部 | ||
3.1.3 文法規則部 | ||
3.1.4 追加のCプログラム部 |
C宣言部(C declarations)には、マクロ定義と、文法定義のアクションで
使うための関数と変数の宣言があります。
これらは、yyparse
の定義に優先するように、構文解析器ファイルの最初に
複写されます。
ヘッダファイルから宣言を得るには`#include'を使います。
C宣言がまったく必要ない場合は、この部分を囲む
`%{'と`%}'を省略できます。
Bison宣言部(Bison declarations)は、終端記号と非終端記号の宣言、 演算子の優先順位の指定などを含みます。 単純な例では、宣言を省略できます。 See section Bison Declarations。
文法規則部(grammar rules)は、1つ以上のBison文法規則を含み、 それ以外は含みません。 See section Syntax of Grammar Rules。
少なくとも1つの文法規則が存在する必要があります。 また、文法規則より先に`%%'が必要で、 もしそれ以前に何も記述されていなくても、省略できません。
追加のCプログラム部(additional C code)は、C宣言部が構文解析器ファイルの先頭に複写
されるのと同じように、構文解析器ファイルの末尾にそのまま複写されます。
構文解析器ファイル中に置く必要があって、
yyparse
の定義よりも前に置く必要のないものを、ここに置くと便利です。
たとえば、yylex
とyyerror
の定義は、
よくここに置かれます。
See section Parser C-Language Interface。
もし直前の部が空ならば、文法規則と区別するための `%%'を省略できます。
Bison構文解析器は、名前が`yy'で始まる多くの静的変数と、 名前が`YY'で始まる多くのマクロを含んでいます。 本書で解説しているものを意図的に使う場合を除いて、 そのような名前を文法ファイルの追加のCプログラム部で使うのは避けるべきです。
Bison文法の記号(symbols)は、 言語の文法的分類を表現します。
終端記号(terminal symbol)
(トークン型(tokens types)ともいいます)は、
構文的に等価なトークンのクラスを表します。
そのクラスのトークンが許されることを表すために、
文法規則の中で記号を使えます。
その記号は、Bison構文解析器の中で番号で表現され、
yylex
関数は、どのような種類のトークンが読み込まれたかを示すために、
トークン番号を返します。
これを表す記号を知っていればよく、その番号を知っている必要はありません。
非終端記号(nonterminal symbol)は、 構文的に等価なグループを表現します。 記号名は文法規則の記述に使われます。 通常、非終端記号名を小文字で書きます。
記号名は、英字、先頭以外での数字、下線記号(`_')とピリオドからなります。 ピリオド記号(`.')は、非終端記号の名前には使えますが、 終端記号の名前には使えません。
文法中で終端記号を記述するには3種類の方法があります。
名前付きトークン型(named token type)を、
C言語における識別子と同様な、識別子とともに書きます。
通常、大文字で書きます。
これらは%token
のようなBison宣言とともに定義する必要があります。
See section Token Type Names。
文字トークン型(character token type)、
すなわちリテラル文字トークン(literal character token)は、
C言語の文字定数と同じ構文で書かれ、
たとえば'+'
は文字トークン型です。
意味値データ型(see section Data Types of Semantic Values)、
結合性、優先順位(see section Operator Precedence)を
指定する必要がなければ、
文字トークン型を宣言する必要はありません。
通常、文字トークン型は、特別な文字(8)から
なるトークンを表すためだけに使います。
たとえば、トークン型'+'
を、
トークンとしての`+'文字を表すために使います。
このようにする義務はありませんが、そうしないと、
あなたが書いたプログラムを読む人が混乱するでしょう。
C言語の文字リテラルで使われる通常のエスケープシーケンス
(9)を、Bisonでも使えます。
しかし、'\0'
だけはASCII符号の0を表し、
yylex
がファイルの終わりを示す符号なので、
文字リテラルとしては使えません
(see section Calling Convention for yylex
)。
リテラル文字列トークン(literal string token)は、
C言語における文字列定数と同様に書きます。
たとえば、"<="
がリテラル文字列トークンです。
意味値(see section データ型と意味値)、
結合性、優先順位(see section Operator Precedence)を
指定する必要がなければ、
リテラル文字列トークンを宣言する必要はありません。
%token
宣言(see section Token Declarations)を使って、
リテラル文字列トークンを、記号名の別名として関連づけられます。
そうしないと、字句解析器は、
yytname
表(see section yylex
を呼び出す方法)を使って、
リテラル文字列トークンからトークン番号を検索する必要があります。
【警告】yacc
ではリテラル文字列トークンを使えません。
通常、特殊文字の列からなるトークンの表現にのみ、
リテラル文字列トークンを使います。
たとえば、トークンとしての`<='を表すために、
トークン型"<="
を使うべきです。
そうする義務はありませんが、そうしないと、
あなたが書いたプログラムを読む人が混乱するでしょう。
C言語で使えるエスケープシーケンスはすべてBisonでも使えます。 リテラル文字列トークンは、2文字以上からなります。 もし、トークンが1文字ならば、前述の1文字トークンを使ってください。
終端記号を書く方法は、終端記号の文法的意味に関係なく、 規則の中に現れる位置と、 構文解析器関数が記号を返す方法に関係します。
yylex
が返す値は、終端記号のどれかを表し、
入力の終わりでは0です。
文法規則の中でどの方法でトークン型を書いても、
yylex
を定義する書き方は同じです。
1文字トークン型に対する符号は、その文字のASCII符号なので、
yylex
は必要な符号を生成するために同一の文字定数を使えます。
名前を付けられたトークン型はそれぞれ、
構文解析器ファイルの中でCのマクロになるので、
yylex
は符号に対するマクロ名を使えます。
これが、終端記号の名前にピリオド記号を使えない理由です。
See section Calling Convention for yylex
。
yylex
が構文解析器と別のソースファイルの中に書かれる場合には、
そこでトークン型マクロ定義を使えるように準備する必要があります。
`-d'オプションを付けてBisonを実行してください。
すると、マクロ定義が`name.tab.h'というファイルに書かれ、
必要に応じて別のソースファイルからインクルードできます。
See section Invoking Bison。
記号error
は、エラー回復用に予約された終端記号(see section エラーからの回復)
で、他の目的に使うべきではありません。
実際に、yylex
がこの値を返すことは決してありません。
Bison文法規則は、一般的に次の書式です。
result: components… ; |
resultは、この規則が記述する非終端記号で、 componentsは、この規則で一緒に置かれるさまざまな 終端および非終端記号です。 例を示します。
exp: exp '+' exp ; |
この例では、`+'トークンを間にはさんで
型exp
の2つのグループ化が行われ、
型exp
のより大きなグループができます。
規則の中の空白(10)は、 記号を分けるだけの意味を持ちます。 必要に応じて、余分な空白を書いてもかまいません。
componentsの周辺にあるものは、 規則の意味を決定するアクション(action)になることができます。 アクションは、次のようになります。
{C statements} |
通常、1つだけのアクションと、それに続くcomponentsがあります。 See section アクション。
同一のresultに対する複数の規則は、 別々に書くこともできますし、 次の例のように縦線記号`|'で区切ってまとめて書くことも可能です。
まとめて書いても、それぞれの規則は別々のものとみなされます。
もし、規則中のcomponentsが空ならば、
resultが空の列にマッチできることを意味します。
例として、カンマで区切られた0個以上のexp
のグループを
定義する方法を示します。
expseq: /* 空 */ | expseq1 ; expseq1: exp | expseq1 ',' exp ; |
空のcomponentを持つ規則には、通常 `/* 空 */'という注釈を書きます。
resultである非終端記号が規則の右側にも現れる場合に、 その規則は再帰的(recursive)であるといいます。 Bison文法の大部分は再帰的規則を使います。 なぜならば、任意の数の並びを定義する唯一の方法が、 再帰的規則だからです。 1つ以上のカンマで区切られた式の並びの定義を考えてみましょう。
expseq1: exp | expseq1 ',' exp ; |
expseq1
で使われている再帰は、規則の右側の中でもっとも左側にあるので、
このような再帰を左再帰(left recursion)と呼びます。
逆に、同じ構造を右再帰(right recursion)を使って書いてみます。
expseq1: exp | exp ',' expseq1 ; |
あらゆる並びを、左再帰を使っても、右再帰を使っても、定義できます。 しかし、限られたスタック容量で任意の数の並びを走査できるので、 つねに左再帰を使うべきです。 右再帰では、規則が適用される前にすべての要素をスタックに積む必要があるので、 要素の数に比例するスタック領域を消費します。 詳細については、See section The Bison Parser Algorithm。
規則の結果が直接その右側には含まれず、 右側にある非終端記号の中に含まれるとき、 間接(indirect)すなわち相互(mutual)再帰が起きます。
例を示します。
expr: primary | primary '+' primary ; primary: constant | '(' expr ')' ; |
この例では、それぞれの規則が互いに参照しているので、 2個の相互再帰が定義されています。
言語に対する文法規則は、文法だけを決めます。 意味は、各種のトークンとグループ化に対応する意味値により、 各種のグループ化が認識されるときに、決定されます。
電卓の例では、式のそれぞれに対応する値が適切な数値なので、 電卓は正確に計算できます。 グループ`x + y'に 対応するアクションが、xとyに関する数値の和を計算します。
3.5.1 データ型と意味値 | ||
3.5.2 複数の値型 | ||
3.5.3 アクション | ||
3.5.4 アクション中の値のデータ型 | ||
3.5.5 規則の途中のアクション |
単純なプログラムでは、言語の要素のすべての意味値に対して同じデータ型を 使えば十分です。 逆ポーランド記法と中間記法電卓の例では、そうでした (see section Reverse Polish Notation Calculator)。
特に指定しないと、Bisonはすべての意味値に対してint
型を使います。
他の型を使うには、次の例のように、マクロYYSTYPE
を定義します。
#define YYSTYPE double |
このマクロ定義は、文法ファイルのC宣言部に置く必要があります (see section Outline of a Bison Grammar)。
多くのプログラムでは、異なる種類のトークンとグループに対して、
異なるデータ型が必要です。
たとえば、数値定数はint
型やlong
型を必要とし、
文字列定数はchar *
型を必要とし、
識別子は記号表の項目へのポインタを必要とするでしょう。
同一の構文解析器内で、意味値に対して2つ以上のデータ型を使うには、 次の2項目が必要です。
Bison宣言の%union
で、考えられるデータ型全体の集合を指定します
(see section The Collection of Value Types)。
終端または非終端記号のそれぞれについて、
その意味値を使うために、上記の型のどれか1つを選びます。
トークンに対する型の指定には、Bison宣言の%token
を使います
(see section Token Type Names)。
グループ化に対する型の指定には、Bison宣言の%type
を使います
(see section Nonterminal Symbols)。
文法規則にともなうアクションは、その規則が認識されるたびに実行される Cのプログラムからなります。 アクションの仕事のほとんどは、関連するトークンまたは小さいグループから 規則にしたがって構成されるグループの、意味値の計算です。
アクションは、Cの複文のように、ブレースで囲まれたCの文からなります。 アクションは、規則のどの場所にも置け、その場所で実行されます。 規則のほとんどは、規則の終わりの構成要素の並びの後に、 1つだけアクションを持ちます。 規則の途中に置かれたアクションは、手の込んだ方法で特別な目的に使われます (see section Actions in Mid-Rule)。
アクションの中のCで書かれたプログラムは、
規則の第n番目の要素に対応する意味値を、
$n
という書式で参照できます。
また、その規則が構成するグループの意味値を、
$$
という書式で参照できます。
アクションが構文解析器ファイルに複写されるときに、Bisonは、
上記の構成要素を配列要素への参照に変換します。
例を示します。
exp: … | exp '+' exp { $$ = $1 + $3; } |
この規則は、加算記号で結び付けられた2つの小さいexp
グループから、
1つのexp
を構成します。
このアクションの中で、$1
と$3
は、
規則の右側の最初と3番目の記号であるexp
グループの
意味値を参照します。
この規則によって認識される加算式の値になるように、
和が$$
に代入されます。
もし、`+'トークンに有用な値があるならば、
それを$2
として参照できるでしょう。
規則に対してアクションを指定しなければ、Bisonは、
省略時アクション$$ = $1
を補います。
したがって、規則の最初の記号の値が規則全体の値になります。
もちろん、両者の型が一致する場合にのみ、省略時アクションは有効です。
空規則に対する省略時アクションは無意味です。
すべての空規則は、その規則の値が必要ならば、
明示的なアクションを持つ必要があります。
$n
のnは0または負が許され、
現在の規則にマッチする前にスタックに積まれていた
トークンとグループの意味値を参照します。
これは非常に危険な手法で、安全に使うためには、
その規則が適用される文脈をあなたが完全に理解している必要があります。
これを安全に使える例を示します。
foo: expr bar '+' expr { … } | expr bar '-' expr { … } ; bar: /* 空 */ { previous_expr = $0; } ; |
bar
がここに書かれた方法でのみ使われるならば、
foo
の定義の中でbar
より前の
expr
の値を$0
が参照します。
すべての意味値に対して同一のデータ型を使っているのならば、
$$
と$n
はそのデータ型を持ちます。
さまざまなデータ型を指定するために%union
を使っているならば、
意味値を持つ終端記号と非終端記号のそれぞれに対して、
データ型の中から適切なものを選ぶように宣言する必要があります。
すると、$$
とn
を使うたびに、
規則の中でそれらがどの記号を参照するかに応じて、
データ型が決められます。
例を示します。
exp: … | exp '+' exp { $$ = $1 + $3; } |
$1
と$3
はexp
という種類の記号を参照するので、
$1
と$3
は、非終端記号exp
に対して宣言された
データ型を持ちます。
もし、$2
が使われるならば、どのような型であれ、
終端記号+
に対して宣言されたデータ型が使われます。
別の方法として、値を参照するときにそのデータ型を指定できます。 そのためには、参照のための`$'記号の後に`<type>'を 挿入します。例を示します。
%union { int itype; double dtype; } |
この場合に、$<itype>1
と書けば、
最初の要素をint
型として参照でき、$<dtype>1
と書けば、
double
型として参照できます。
まれに、アクションを規則の途中に置くと便利な場合があります。 これらのアクションは、通常の規則の終わりに置かれたアクションと同様に 記述されますが、構文解析器が後に続く要素を認識する前に実行されます。
規則の途中のアクションは、そのアクションよりも前にある要素を
$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 section 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の内部では、このようにして、
規則中のアクションという機能が実現されています。
Bison文法ファイルのBison宣言(Bison declarations)部では、 文法の定式化に使う記号を定義し、意味値のデータ型を定義します。 See section 記号、終端と非終端。
'+'
や'*'
のような1文字リテラルトークンを除く
すべてのトークンの型名を宣言する必要があります。
非終端記号については、その意味値に対してどのデータ型を使うか
指定したければ、宣言する必要があります
(see section More Than One Value Type)。
特に指定しないと、文法ファイル中の最初の規則は、 開始記号を特定します。 他の記号を開始記号にしたければ、明示的に宣言する必要があります (see section Languages and Context-Free Grammars)。
3.6.1 トークン型名 | ||
3.6.2 演算子の優先順位 | ||
3.6.3 値型の集合 | ||
3.6.4 非終端記号 | ||
3.6.5 衝突警告の回避 | ||
3.6.6 開始記号 | ||
3.6.7 純粋(再入可能)構文解析器 | ||
3.6.8 Bison宣言の要約 |
トークン型名、すなわち終端記号を、基本的には次のように宣言します。
%token name |
Bisonは、これを、構文解析器の中の#define
ディレクティブに変換します。
したがって、関数yylex
が構文解析器ファイルの中にあれば、
そこで名前nameをこのトークン型を表すために使えます。
優先順位を指定したければ、%token
の代わりに、
%left
、%right
、%nonassoc
のどれかを使います。
See section Operator Precedence。
トークンの名前の直後に整数値を書くことで、 そのトークン型に対応する数値符号を明示的に指定できます。
%token NUM 300 |
しかし、Bisonにすべてのトークン型に対する数値符号の割り当てをまかせる ことがいちばんです。Bisonは、トークン型どうしやASCII文字符号と 衝突が起きないように、自動的に数値符号を割り当てます。
スタック型が共用体である場合には、
%token
あるいは他のトークン宣言に、
小なり記号と大なり記号で区切った型名を追加する必要があります
(see section More Than One Value Type)。
例を示します。
%union { /* スタックのデータ型を定義する */ double val; symrec *tptr; } %token <val> NUM /* トークン「NUM」とその型を定義する */ |
トークン型名を宣言する%token
宣言の末尾に
リテラル文字列を書くことで、リテラル文字列トークンと
トークン型名を関連づけできます。
%token arrow "=>" |
C言語に対する文法では、次の例のように、 等価なリテラル文字列トークンに名前を指定しています。
%token <operator> OR "||" %token <operator> LE 134 "<=" %left OR "<=" |
リテラル文字列とトークン名を等価にすれば、それ以降の文法規則の
宣言の中で、両者を同様に使えます。
yylex
関数は、トークン型の数値符号を得るために、
トークン名とリテラル文字列の両方を使えます
(see section yylex
を呼び出す方法)。
トークンの宣言とトークンの優先順位および結合規則の指定をまとめて行いたいならば、
%left
、%right
、%nonassoc
のどれかを使います。
これらは、優先順位宣言(precedence declarations)と呼ばれます。
演算子の優先順位の詳細については、
See section Operator Precedence。
優先順位宣言の構文は、%token
を使う宣言の構文と同じです。
%left symbols… |
次のようにも書けます。
%left <type> symbols… |
これらの宣言は、%token
を使う宣言が目的とする
すべての機能を持っています。
それに加えて、次のように結合性と、すべてのsymbolsについての優先順位を指定します。
演算子opの結合性は、この演算子が繰り返し使われた場合の
動作を指定します。つまり、`x op y op z'が
構文解析された場合に、最初にxとyがグループ化されるか、
それともyとzがグループ化されるかを指定します。
%left
は、左結合性、つまりxとyが先に結合されることを
指定します。%right
は、右結合性、つまり、
yとzが先に結合されることを指定します。
%nonassoc
は、無結合性を指定し、その場合、
`x op y op z'は
構文エラーとみなされます。
演算子の優先順位は、その演算子が他の演算子とともに使われた場合の 動作を指定します。同一の優先順位宣言で宣言されたすべてのトークンは、 同じ優先順位を持ち、その結合性にしたがって処理されます。 2個のトークンが別々の優先順位宣言で宣言されているならば、 文法ファイルの中で後で宣言されたほうの演算子が強い優先順位を持ちます。
%union
宣言は、意味値に対して可能なデータ型すべての集合を指定します。
キーワード%union
に続いて、C言語における共用体の宣言と同様に、
ブレースで囲んだ宣言の並びを書きます。
例を示します。
%union { double val; symrec *tptr; } |
これは、2つの選択可能な型double
とsymrec *
があると、
宣言しています。
それぞれの型には、名前val
とtptr
が与えられています。
これらの名前は、%token
とtype
宣言の中で、
終端記号あるいは非終端記号に対する型を選ぶために使えます
(see section Nonterminal Symbols)。
C言語での共用体宣言とは異なり、閉じブレースの後にセミコロンを 書いてはいけないことに注意してください。
%union
を複数の値型を指定するために使うならば、
値を持つ各非終端記号の値型を宣言する必要があります。
そのためには、次のように%type
宣言を使います。
%type <type> nonterminal… |
ここで、nonterminalは非終端記号の名前で、
typeは%union
で指定した名前の中からあなたが選んだものです
(see section The Collection of Value Types)。
同じ値型を持つ任意の数の非終端記号を、
1つの%type
宣言の中に記述できます。
その場合、記号名を空白で区切ってください。
同様に終端記号の値型の宣言も可能です。
そのためには、終端記号の宣言の中で、同じ<type>
の
書式を使います。
すべてのトークン宣言で、<type>
が許可されています。
文法の中に衝突(see section Shift/Reduce Conflicts)があると、
Bisonは通常警告を表示します。
しかし、実際の文法のほとんどは、無害なシフト還元衝突を含み、
その衝突は、予測可能な方法で回避できますが、除去は困難です。
衝突の数が変わらないかぎり、このような衝突の警告は
抑制させるべきです。
そのために、%expect
宣言を使います。
次のように宣言します。
%expect n |
ここで、nは10進の整数です。 この宣言によって、n個のシフト還元衝突があって、 還元/還元衝突がなければ、警告が表示されません。 シフト還元衝突の数がnでなかったり、 1つでも還元/還元衝突があった場合は、通常の警告が表示されます。
一般に、次のような手順で%expect
を使います。
%expect
なしで文法ファイルをコンパイルします。
衝突が起こる位置の詳細な目録を得るために、`-v'オプションを指定します。
Bisonは、衝突の数も表示します。
衝突のそれぞれについて、Bisonの省略時の解決方法が、 あなたの望みどおりであるか、確かめます。 もし不都合があれば、文法ファイルを書き直して、最初に戻ります。
Bisonが表示した衝突の数nを書き写して、
%expect
宣言を追加します。
すると、Bisonはチェックした衝突について文句をいわなくなりますが、 文法ファイルを書き換えて衝突の数が変わると、 再び警告を表示します。
Bisonは、文法定義部にある最初の非終端記号を、
省略時の開始記号と仮定します。
次のような%start
宣言で、明示的に開始記号を指定できます。
%start symbol |
再入可能(reentrant)プログラムとは、進路を変えないプログラム、 いいかえれば、完全に純粋な(pure)(読み出し専用)コードからなる プログラムです。 (11) 再入可能性は、非同期実行が可能な場合に重要です。 たとえば、再入可能でないプログラムを、 シグナルハンドラから呼び出すことは危険です。マルチスレッド制御システムでは、 再入不能プログラムはインターロックからしか呼び出せません。
通常は、Bisonは再入可能でない構文解析器を生成します。
これはほとんどの使用に合い、YACCとの互換性も保ちます。
(標準のYACCインターフェースは継続的に非再入可能であります。
というのは、yylex
、yylval
や yylloc
との通信に
静的に確保された変数
(12)
を使うからです。
代わりに、純粋な、再入可能な構文解析器を生成することができます。
次のような%pure_parser
Bison宣言は、
再入可能な構文解析器を生成します。
%pure_parser |
この宣言によって、上記の2個の通信用変数yylval
とyylloc
が、
yyparse
の局所変数になり、
yylex
字句解析関数を呼び出す方法が変わります。
詳細については、See section Calling Conventions for Pure Parsers。
yyparse
の中のyynerrs
変数も局所変数になります
(see section The Error Reporting Function yyerror
)。
yypase
関数自体を呼び出す方法は変わりません。
解析器が純粋かどうかは文法規則には全く関係しません。 全ての有効な文法から、純粋な解析器と非再入可能な解析器の どちらかを生成するこができます。
Bison宣言の要約を示します。
%union
意味値が持ちうるデータ型の集合を宣言します (see section The Collection of Value Types)。
%token
優先順位と結合性を指定せずに、終端記号(トークン型名)を宣言します (see section Token Type Names)。
%right
右結合的な終端記号(トークン型名)を宣言します (see section Operator Precedence)。
%left
左結合的な終端記号(トークン型名)を宣言します (see section Operator Precedence)。
%nonassoc
結合性がない、つまり、結合して使おうとすると構文エラーになる、 終端記号(トークン型名)を宣言します (see section Operator Precedence)。
%type
非終端記号に対する意味値の型を宣言します (see section Nonterminal Symbols)。
%start
文法の開始記号を宣言します (see section The Start-Symbol)。
%expect
予想されるシフト還元衝突の数を宣言します (see section Suppressing Conflict Warnings)。
%pure_parser
純粋な(再入可能な)構文解析器を生成します (see section A Pure (Reentrant) Parser)。
%no_lines
構文解析器ファイルに、#line
プリプロセッサディレクティブを生成しません。
Bisonは、通常、Cコンパイラとデバッガがエラーとあなたのソースファイル
(文法ファイル)を関連づけられるように、構文解析器ファイルに
#line
ディレクティブを書き込みます。
%no_lines
宣言は、エラーを構文解析器ファイルの行数と関連づけ、
構文解析器ファイルをそれ自身で独立したソースファイルと
みなすことを意味します。
%raw
通常、出力ファイル`name.h'は、 Yacc互換トークン番号を定義します。 このオプションが指定されると、代わりに、Bison内部の番号が使われます (Yacc互換番号は、1文字リテラルトークンを除いて、257から始まりますが、 Bison内部のトークン番号は常に3から始まる連番になります)。
%token_table
構文解析器ファイルの中に、トークン名の表を生成します。
その表の名前はyytname
で、yytname[i]
が
Bison内部トークン番号iのトークンの名前です。
最初の3個の要素は常に、"$"
、"error"
、"$illegal"
で、
この後に文法ファイルで定義された記号が続きます。
表の中で、1文字リテラルトークンにはシングルクォート記号が、
文字列リテラルトークンにはダブルクォート記号が含まれます。
たとえば、"'+'"
は1文字リテラルトークンで、
"\"<=\""
は文字列リテラルトークンです。
文字列リテラルトークンのすべての文字はそのまま表に現れ、
ダブルクォート記号もエスケープされません。
たとえば、トークンが3文字`*"*'からなれば、
yytname
中の文字列は`"*"*"'となります
(Cでは"\"*\"*\""
と書きます)。
%token_table
を指定すると、Bisonは、マクロ
YYNTOKENS
、YYNNTS
、YYNRULES
、YYNSTATES
の
定義も生成します。
YYNTOKENS
最大のトークン番号+1。
YYNNTS
非終端記号の数。
YYNRULES
文法規則の数。
YYNSTATES
構文解析器の状態の数(see section 構文解析器の状態)。
Bisonを使うプログラムのほとんどは、言語を1つだけ構文解析し、
したがって、Bison構文解析器を1つだけ含みます。
しかし、1つのプログラムで2種類以上の言語を構文解析したいときは、
どうすればよいでしょうか? そうするためには、yyparse
、yylval
などの2重定義の衝突を防ぐ必要があります。
これを容易にする方法が、オプション`-p prefix'の利用です (see section Invoking Bison)。 これによって、Bison構文解析器のインターフェイス関数と変数の名前が、 `yy'で始まる代わりにprefixで始まります。 これでそれぞれの構文解析器に、衝突しないような異なる名前を与えられます。
変更される名前は、
yyparse
、yylex
、yyerror
、yynerrs
、
yylval
、yychar
、yydebug
で全部です。
たとえば、`-p c'オプションを使えば、これらの名前は、
cparse
、clex
などに変わります。
Bisonに関連する上記以外の変数とマクロのすべての
名前は変わりません。これらは、広域ではないので、
異なる構文解析器で同じ名前が使われても衝突しません。
たとえば、YYSTYPE
の名前は変わりませんが、
この定義は構文解析器ごとに異なる方法で行われるので、問題ありません
(see section Data Types of Semantic Values)。
`-p'オプションは、さらに、構文解析器ソースファイルの始めで、
yyparse
をprefixparse
と定義するように、
マクロを定義します。
この結果、構文解析器ソースファイル全体で、ある名前を別の名前に変えます。
[ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This document was generated by Akihiro Sagawa on June, 1 2005 using texi2html 1.70.