本章では、Bison文法を使って書いた例を3つ示します。 逆ポーランド記法電卓、算術(中置)記法電卓、多機能電卓です。 すべてBSD UNIX 4.3上でテストしました。 限定的ではありますが、対話的な電卓として利用可能です。
これらの例は単純ですが、現実のプログラミング言語に対する Bison文法も、書き方は同じです。
最初の例は、逆ポーランド記法(reverse polish notation)を使う 倍精度の電卓で、演算子を後に書きます。 この例は、演算子の優先順位の問題がないので、入門には適しています。 第2の例では、演算子の優先順位をどのように扱うかを示します。
この電卓のソースファイルを`rpcalc.y'とします。 Bisonの入力ファイルには、通常`.y'という拡張子を付けます。
rpcalc
のための宣言逆ポーランド記法電卓のためのCとBisonの宣言を示します。 Cと同様に`/*...*/'はコメントです。
/* 逆ポーランド記法電卓 */ %{ #define YYSTYPE double #include <math.h> %} %token NUM %% /* 文法規則とアクションが続く */
C宣言部(see section C宣言部)には、 2つのプリプロセッサディレクティブがあります。
#define
ディレクティブで、トークンとグループの意味値に対する
Cのデータ型を指定するために、マクロYYSTYPE
を定義します
(see section データ型と意味値)。
Bison構文解析器は、YYSTYPE
に定義された型を使います。
定義しないと、int
型が使用されます。
各トークンと式は、浮動小数点数である記録値を持つので、
ここではdouble
を指定します。
べき乗関数pow
の宣言を使うために、
#include
ディレクティブを使っています。
第2の部、Bison宣言は、Bisonのためにトークン型についての情報を用意します
(see section Bison宣言部)。
1文字リテラルでない終端記号は、ここで宣言する必要があります
(通常、1文字のリテラルを宣言する必要はありません)。
この例では、すべての算術演算子が1文字リテラルなので、
数値定数に対するトークン型NUM
だけを、
終端記号として宣言します。
rpcalc
のための文法規則逆ポーランド記法電卓のための文法規則を示します。
input: /* 空 */ | input line ; line: '\n' | exp '\n' { printf ("\t%.10g\n", $1); } ; exp: NUM { $$ = $1; } | exp exp '+' { $$ = $1 + $2; } | exp exp '-' { $$ = $1 - $2; } | exp exp '*' { $$ = $1 * $2; } | exp exp '/' { $$ = $1 / $2; } /* べき乗関数 */ | exp exp '^' { $$ = pow ($1, $2); } /* 単項のマイナス */ | exp 'n' { $$ = -$1; } ; %%
ここで定義されるrpcalc「言語」のグループは、
式(exp
)と、入力行(line
)と、
完全な入力の写し(input
)です。
これらの非終端記号には、「論理和」という`|'記号で区切られた、
いくつかの規則があります。
以下の項で、これらの規則の意味を説明します。
言語の意味は、グループが認識されたときのアクションによって決まります。 アクションとは、ブレースで囲まれたCのプログラムです。 See section アクション。
これらのアクションをCで書く必要がありますが、
Bisonには規則の間で意味値を受け渡しする方法があります。
それぞれのアクションで、擬似変数$$
は、
その規則が構成しようとしているグループの意味値を示します。
$$
に値を代入することが、アクションの主な仕事です。
規則の部品の意味値は、$1
、$2
などの
名前で参照されます。
input
の説明
input
の定義について考えます。
input: /* 空 */ | input line ;
この定義の意味は、「完全な入力とは、空文字列であるか、あるいは、
完全な入力に入力行が続いたものである」ということです。
「完全な入力」が、それ自身を使って定義されていることに注意してください。
列の中でinput
が常に左端の記号なので、
このような定義を左再帰(left recursive)と呼びます。
See section 再帰的規則。
最初の選択肢は、`:'と`|'の間に記号がないので空です。 これは、(トークンを含まない)空の入力文字列にマッチします。 電卓を起動した直後にCtrl-d (3)を 押しても、正しい入力と扱われるように、この規則を入れました。 通常、空に対応する選択肢を最初に置き、そこに`/* 空 */'と 書きます。
2つめの選択肢である規則(input line
)は、
自明(空)でないすべての入力を扱います。
その意味は、「任意の数の行を読み込んだ後で、もし可能ならば、
もう1行読み込む」ということです。
左再帰が、この規則を繰り返しにします。
最初の選択肢が空の入力にマッチするので、
0回以上任意の回数の繰り返しになります。
構文解析器関数yyparse
は、文法エラーが発生するか、あるいは、
字句解析器がもうトークンがないと判定するまで、
入力の処理を続けます。
ファイルの終わりで起きることについては、後で考慮します。
line
の説明
次に、line
の定義について考えます。
line: '\n' | exp '\n' { printf ("\t%.10g\n", $1); } ;
最初の選択肢は、改行文字であるトークンです。
これは、rpcalcが空行を受け入れ、それに対応するアクションがないので、
無視することを示します。
第2の選択肢は、式の後に改行が続いたものです。
これが、rpcalcを有用にする選択肢です。
問い合わせの中のexp
が、この選択肢に現れる最初の記号なので、
exp
グループの意味値は、$1
の値です。
アクションは、問い合わされた計算の結果である、
この値を表示します。
このアクションは、値を$$
に代入しないので、例外的です。
したがって、line
に対応する意味値は、初期化されず、
その値は予想できなくなります。
もし、その値が使われると、この仕様はバグになりますが、われわれはこの値を使い
ません。ユーザーが入力した行に対する値を表示したら、
その値はもはや必要ありません。
expr
の説明
exp
グループは、いくつかの規則を持ち、
それぞれが式の種類に対応しています。
最初の規則は、数値そのものであるもっとも単純な式を処理します。
第2の規則は、2個の式に加算記号が続くような、加算式を処理します。
第3の規則は、減算式を処理する、といった具合です。
exp: NUM | exp exp '+' { $$ = $1 + $2; } | exp exp '-' { $$ = $1 - $2; } ... ;
すべてのexp
規則をまとめるために`|'を使っていますが、
次のように別々に書くことも可能です。
exp: NUM ; exp: exp exp '+' { $$ = $1 + $2; } ; exp: exp exp '-' { $$ = $1 - $2; } ; ...
規則のほとんどは、式の部品の値から式の値を計算するための、
アクションを持っています。
たとえば、加算のための規則では、$1
は式の第1の部品を、
$2
は式の第2の部品を表します。
第3の部品'+'
は、意味値には関連する情報を持ちませんが、
もし値を持っていれば、$3
として参照できます。
yyparse
がこの規則を使って加算式を認識すると、
式全体の値として、2個の部分式の値の和が生成されます。
See section アクション。
すべての規則に対してアクションを書く必要はありません。
アクションを省略すると、Bisonは$1
の値を$$
に複写します。
第1の規則では、NUM
の値をそのまま複写するために、
このようになっています。
ここで示したリストは、望ましい書式ですが、 Bisonがこのように要求するわけではありません。 必要に応じて、空白、タブ、改行を置けます。 次のような書き方も可能です。
exp : NUM | exp exp '+' {$$ = $1 + $2; } | ...
これは、次のリストと等価です。
exp: NUM | exp exp '+' { $$ = $1 + $2; } | ...
しかし、後者のほうが可読性が優れています。
rpcalc
字句解析器
字句解析器の仕事は、低水準の構文解析で、文字または文字列を
トークンに変換します。
Bison構文解析器は、字句解析器を呼び出してトークンを得ます。
See section 字句解析器関数yylex
。
RPN(逆ポーランド記法)電卓には、簡単な字句解析器のみが必要です。
この字句解析器は、空白とタブを読み飛ばし、
数値を読み込んでdouble
型のNUM
トークンとして返します。
数値の一部分ではないその他の文字は、独立のトークンです。
1文字トークンのトークン符号はその文字自身であることに注意してください。
字句解析関数の戻り値は、トークン型を表す数値です。
Bison規則の中でトークン型を表すために使われる文字列と同じものが、
その型の数値符号を表すCの式でもあります。
これには、2種類の働きがあります。
もし、トークン型が文字リテラルならば、
その数値符号は文字のASCII符号であり、
数値を表すために字句解析器の中と同じ文字リテラルを使えます。
もし、トークン型が識別子ならば、適切な番号を定義するCのマクロとして、
その識別子がBisonによって定義されます。
したがって、この例では、NUM
は、yylex
のために使える
マクロにもなります。
トークンの意味値は、もし存在すれば、大域変数yylval
に記憶され、
Bison構文解析器はそこを見にいきます
(yylval
のCデータ型は、文法の最初で定義されるYYSTYPE
です。
see section rpcalc
のための宣言)。
ファイルの終わりに達すると、トークン型のコード0が返されます (Bisonは、正でない任意の値を入力の終わりと認識します)。
字句解析器のプログラムの例を示します。
/* * 字句解析器は、数値を読めば、double型の値をスタックに積んで * トークン「NUM」を返し、数値以外を読めば、その文字のアスキー符号を返す。 * 空白とタブは読み飛ばされる。ファイルが終わると0を返す。 */ #include <ctype.h> yylex () { int c; /* 空白類を読み飛ばす */ while ((c = getchar ()) == ' ' || c == '\t') ; /* 数値を処理する */ if (c == '.' || isdigit (c)) { ungetc (c, stdin); scanf ("%lf", &yylval); return NUM; } /* ファイルの終わりを処理する */ if (c == EOF) return 0; /* 1文字を返す */ return c; }
この例の精神に則って、制御関数は、飾りのない最小限のものです。
唯一必要なことは、構文解析の処理を始めるために、
yyparse
関数を呼び出すことです。
main () { yyparse (); }
yyparse
は、構文エラーを検出すると、エラーメッセージ
(必ずそうとはかぎりませんが、通常は"parse error"
)を
表示するために、エラー報告関数yyerror
を呼び出します。
#include <stdio.h> yyerror (s) /* エラーが起きるとyyparseから呼び出される */ char *s; { printf ("%s\n", s); }
yyerror
から戻った後に、Bison構文解析器は、
文法に適切なエラー規則(see section エラーからの回復)があれば、
エラーから回復し、解析を継続できます。
そうでない場合には、yyparse
が0でない値を返します。
この例では、エラー規則を書いていないので、
不正な入力はすべて電卓プログラムを終了させます。
これは、実際の電卓としてはきれいな動作ではありませんが、
最初の例としては十分です。
構文解析器を生成するためにBisonを実行する前に、
1つ以上のソースファイルのすべてをどのように整えるか、
決める必要があります。
このような単純な例では、すべてを1個のファイルに詰め込む方法が
いちばん簡単です。
yylex
、yyerror
、main
の定義を、
ファイルの「追加のCコード」部の最後に置きます
(see section Bison文法の全体像)。
大きなプロジェクトでは、ソースコードを複数のファイルに分け、
まとめてリコンパイルするためにmake
を使うでしょう。
1つのファイルにすべてのソースが入っているならば、 次のコマンドで、それを構文解析器ファイルに変換できます。
bison file_name.y
この例では、ファイルは`rpcalc.y'(逆ポーランド記法電卓)と
呼ばれています。Bisonは、元のファイル名から`.y'を取り除いて、
`file_name.tab.c'というファイルを生成します。
Bisonが出力したファイルには、yyparse
のソースコードが含まれています。
入力ファイル中の追加の関数(yylex
、yyerror
、main
)は、
出力にそのまま複写されます。
構文解析器ファイルをコンパイルする方法を示します。 (5)
# カレントディレクトリのファイルの一覧を見る。
% ls
rpcalc.tab.c rpcalc.y
# Bison構文解析器をコンパイルする。
# 数学ライブラリ内のpow
関数をリンクするために`-lm'を指定する。
% cc rpcalc.tab.c -lm -o rpcalc
# 再び、ファイルの一覧を見る。
% ls
rpcalc rpcalc.tab.c rpcalc.y
できた`rpcalc'ファイルは、実行可能プログラムです。
rpcalc
を実行させる例を示します。
% rpcalc 4 9 + 13 3 7 + 3 4 5 *+- -13 3 7 + 3 4 5 * + - n 単項マイナスを示す`n'に注意 13 5 6 / 4 n + -3.166666667 3 4 ^ べき乗関数 81 ^D 入力の終わり %
calc
後置記法演算子に代わって中間記法演算子を扱うように rpcalcを変更します。 中間記法には、演算子の優先順位の概念と、 適切な深さに入れ子できるかっこが必要です。 中間記法電卓を作るためのBisonソースファイル `calc.y'を示します。
/* 中間記法電卓 -- calc */ %{ #define YYSTYPE double #include <math.h> %} /* BISON宣言 */ %token NUM %left '-' '+' %left '*' '/' %left NEG /* negation--単項マイナス */ %right '^' /* べき乗関数 */ /* 文法規則が続く */ %% input: /* 空文字列 */ | input line ; line: '\n' | exp '\n' { printf ("\t%.10g\n", $1); } ; exp: NUM { $$ = $1; } | exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | exp '*' exp { $$ = $1 * $3; } | exp '/' exp { $$ = $1 / $3; } | '-' exp %prec NEG { $$ = -$2; } | exp '^' exp { $$ = pow ($1, $3); } | '(' exp ')' { $$ = $2; } ; %%
yylex
、yyerror
、main
関数は、
前の例のものと同じです。
このプログラムには、2つの重要な特徴があります。
第2の部分(Bison宣言部)では、
%left
がトークンの型とそれが左結合演算子であると宣言します。
宣言%left
と%right
(右結合演算子)は、
結合性を持たないトークン型名を宣言するために使われる%token
の代わりに
なります
(1文字のリテラルであるトークンは、通常、宣言する必要がありません。
ここでは、結合性を宣言します)。
演算子の優先順位は、宣言が書かれる行の順序で決まります。
後から宣言された演算子ほど、高い優先順位を持ちます。
したがって、べき乗の優先順位がもっとも高く、
単項の負(NEG
)、「`*'」と「`/'」と続きます。
See section 演算子の優先順位。
もう1つの重要な特徴は、単項の負の演算子のために文法部分にある
%prec
です。
%prec
は、単純にBisonに対して、規則`| '-' exp'は
NEG
と同じ優先順位を持つように指示し、
この例ではどちらも2番目に高い優先順位を持ちます。
以下は`calc.y'の実行例です。
% calc 4 + 4.5 - (34/(8*3+-3)) 6.880952381 -56 + 2 -54 3 ^ 2 9
今まで、本書では、エラー回復(error recovery)、
つまり、構文エラーを検出した後で構文解析を続ける方法については
言及していませんでした。
今までに扱ったことは、yyerror
を使ってエラーを報告することだけでした。
yyerror
を呼び出した後で、特に指定しないとyyparse
は
処理を終わることを思い出してください。
つまり、エラーを含む入力行が、電卓プログラムを終了させます。
この欠陥をどのように改善するか示しましょう。
Bison言語の文法規則には、予約語error
があります。
次の例では、line
に対する選択肢群にerror
を追加する
方法を示します。
line: '\n' | exp '\n' { printf ("\t%.10g\n", $1); } | error '\n' { yyerrok; } ;
文法へのこの追加によって、構文解析エラーが発生した場合に、
簡単なエラー回復が可能になります。
評価不可能な式が読み込まれると、
line
に対する第3の規則によってエラーが認識され、
構文解析が続けられます。
この場合にも、関数yyerror
は呼び出され、
メッセージを表示します。
アクションは、
Bisonによって自動的に定義されるマクロであるyyerrok
文を実行します。
これはエラー回復の完了を意味します(see section エラーからの回復)。
yyerrok
とyyerror
の違いに注意してください。
この形式のエラー回復は、構文エラーを扱います。
他の種類のエラーもあります。
たとえば、0による除算は、例外シグナルを発生し、通常は致命的です。
実際の電卓プログラムは、このシグナルをつかまえて、longjmp
を使って
main
に戻り、入力行の構文解析を続ける必要があります。
さらに、現在の入力行の残りは破棄されるべきです。
しかし、これらの問題は、Bisonのプログラムに固有の問題ではないので、
本書では解説しません。
mfcalc
Bisonの基礎についての説明が終わったので、より高度な話題に移りましょう。
前述の電卓は、5種類の機能、`+'、`-'、`*'、`/'、
`^'を持っています。
この電卓に、その他の数学関数、たとえば、sin
、cos
などを
追加するとよいでしょう。
中間記法電卓への新しい演算子の追加は、
その演算子が1文字リテラルならば簡単です。
字句解析器yylex
は、数値以外のすべての文字をトークンとして渡すので、
追加の演算子に対応する文法規則を追加するだけです。
しかし、次のような表記方法の、より柔軟な組み込み関数が必要です。
関数名 (引数)
さらに、電卓にメモリを追加し、名前付き変数を作り、そこに値を記憶し、 後で使えるようにしましょう。 以下に多機能電卓を使う作業の例を示します。
% mfcalc pi = 3.141592653589 3.1415926536 sin(pi) 0.0000000000 alpha = beta1 = 2.3 2.3000000000 alpha 2.3000000000 ln(alpha) 0.8329091229 exp(ln(beta1)) 2.3000000000 %
複数の代入(6)と 関数の入れ子(7)が 許されることに注意してください。
mfcalc
のための定義以下には、多機能電卓のための、CとBisonの宣言があります。
%{ #include <math.h> /* cos(), sin()などの数学関数のため */ #include "calc.h" /* `symrec'の定義を含む */ %} %union { double val; /* 数値を返すため */ symrec *tptr; /* 記号表へのポインタを返すため */ } %token <val> NUM /* 単純な倍精度数値 */ %token <tptr> VAR FNCT /* 変数と関数 */ %type <val> exp %right '=' %left '-' '+' %left '*' '/' %left NEG /* 否定 -- 単項の負 */ %right '^' /* べき乗 */ /* 文法が続く */ %%
この文法の導入部分では、Bison言語の新しい2つの機能を使っています。 これらの機能によって、意味値がいろいろなデータ型を持てます (see section 複数の値型)。
%union
宣言は、YYSTYPE
の定義の代わりで、
可能な型の一覧を指定します。
ここで許される型は、(exp
とNUM
のための)倍精度浮動小数点型と、
記号表の項目へのポインタです。
See section 値型の集合。
値がいろいろな型を持つことができるので、
意味値を使うそれぞれの文法記号に対して、
型を関連づける必要があります。
これらの記号はNUM
、VAR
、FNCT
、exp
です。
それらの宣言は、不等号で囲まれた(`<...>')データ型に関する
情報を付加されています。
Bisonは、ちょうど%token
がトークン型の宣言に使われるのと同じように、
%type
が非終端記号の宣言に使われるようにします。
非終端記号は通常それらを定義する規則によって暗黙に宣言されるので、
%type
をその規則よりも先に使ってはいけません。
しかし、exp
は、その値の型を指定するので、
明示的に宣言する必要があります。
See section 非終端記号。
mfcalc
のための文法規則
多機能電卓のための文法規則を示します。
大部分は、calc
の文法規則からの複写です。
VAR
、FUNCT
に関連する3つの規則が新しいものです。
input: /* 空 */ | input line ; line: '\n' | exp '\n' { printf ("\t%.10g\n", $1); } | error '\n' { yyerrok; } ; exp: NUM { $$ = $1; } | VAR { $$ = $1->value.var; } | VAR '=' exp { $$ = $3; $1->value.var = $3; } | FNCT '(' exp ')' { $$ = (*($1->value.fnctptr))($3); } | exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | exp '*' exp { $$ = $1 * $3; } | exp '/' exp { $$ = $1 / $3; } | '-' exp %prec NEG { $$ = -$2; } | exp '^' exp { $$ = pow ($1, $3); } | '(' exp ')' { $$ = $2; } ; /* 文法の終わり */ %%
mfcalc
の記号表変数と関数の名前と意味を保持するために、 多機能電卓は記号表を必要とします。 これは、アクションを除く文法規則とBison宣言には影響しませんが、 追加のCの関数がいくつか必要です。
記号表は、レコードのリンクリストからなります。 その定義は、後述の、ヘッダファイル`calc.h'にあります。 関数と変数の両方を表に置くことができます。
/* 記号表のリンクを表すデータ型 */ struct symrec { char *name; /* 記号の名前 */ int type; /* 記号の種類:VARまたはFNCT */ union { double var; /* VARの値 */ double (*fnctptr)(); /* FNCTの値 */ } value; struct symrec *next; /* 次の項目へのリンク */ }; typedef struct symrec symrec; /* `struct symrec'のリンクである記号表 */ extern symrec *sym_table; symrec *putsym (); symrec *getsym ();
新しいmain
関数は、記号表を初期化する関数である
init_table
を呼びます。
main
とinit_table
を以下に示します。
#include <stdio.h> main () { init_table (); yyparse (); } yyerror (s) /* エラーがあるとyyparseから呼び出される */ char *s; { printf ("%s\n", s); } struct init { char *fname; double (*fnct)(); }; struct init arith_fncts[] = { "sin", sin, "cos", cos, "atan", atan, "ln", log, "exp", exp, "sqrt", sqrt, 0, 0 }; /* 記号表:`struct symrec'のリスト */ symrec *sym_table = (symrec *)0; init_table () /* 数学関数を表に登録する */ { int i; symrec *ptr; for (i = 0; arith_fncts[i].fname != 0; i++) { ptr = putsym (arith_fncts[i].fname, FNCT); ptr->value.fnctptr = arith_fncts[i].fnct; } }
単純に初期化リストを編集して、必要なインクルードファイルを追加するだけで、 電卓に関数を追加できます。
記号表に記号を登録して検索するために、2個の重要な関数があります。
関数putsym
は、登録すべきオブジェクトの
名前と型(VAR
やFNCT
)を渡されます。
オブジェクトはリストの先頭にリンクされ、
オブジェクトへのポインタが返されます。
関数getsym
は、検索すべき記号の名前を渡されます。
もし見つかれば記号へのポインタが返され、
見つからなければ0が返されます。
symrec * putsym (sym_name,sym_type) char *sym_name; int sym_type; { symrec *ptr; ptr = (symrec *) malloc (sizeof (symrec)); ptr->name = (char *) malloc (strlen (sym_name) + 1); strcpy (ptr->name,sym_name); ptr->type = sym_type; ptr->value.var = 0; /* 関数の場合にも値を0にする */ ptr->next = (struct symrec *)sym_table; sym_table = ptr; return ptr; } symrec * getsym (sym_name) char *sym_name; { symrec *ptr; for (ptr = sym_table; ptr != (symrec *) 0; ptr = (symrec *)ptr->next) if (strcmp (ptr->name,sym_name) == 0) return ptr; return 0; }
今度の関数yylex
は、変数、数値、1文字の算術演算子を
認識する必要があります。
英字で始まり英数字からなる文字列は、記号表にどう書かれているかに応じて、
変数と関数のどちらとも認識されます。
文字列は、記号表を検索するためにgetsym
に渡されます。
もし名前が表にあれば、その場所へのポインタと
名前の型(VAR
またはFNCT
)が、
yyparse
に返されます。
名前がまだ表になければ、putsym
を使って、
VAR
として登録されます。
そして、ポインタと型(この場合には必ずVAR
)が
yyparse
に返されます。
yylex
の中で、数値と算術演算子の扱いに関する部分は、
変更する必要がありません。
#include <ctype.h> yylex () { int c; /* 空白を読み飛ばし、空白以外を得る */ while ((c = getchar ()) == ' ' || c == '\t'); if (c == EOF) return 0; /* 数値を読む */ if (c == '.' || isdigit (c)) { ungetc (c, stdin); scanf ("%lf", &yylval.val); return NUM; } /* 識別子を読む */ if (isalpha (c)) { symrec *s; static char *symbuf = 0; static int length = 0; int i; /* バッファの長さの初期値は40文字 */ if (length == 0) length = 40, symbuf = (char *)malloc (length + 1); i = 0; do { /* あふれたのでバッファを大きくする */ if (i == length) { length *= 2; symbuf = (char *)realloc (symbuf, length + 1); } /* 文字をバッファに変える */ symbuf[i++] = c; /* 次の文字を読む */ c = getchar (); } while (c != EOF && isalnum (c)); ungetc (c, stdin); symbuf[i] = '\0'; s = getsym (symbuf); if (s == 0) s = putsym (symbuf, VAR); yylval.tptr = s; return s->type; } /* その他の文字は文字リテラルトークン */ return c; }
このプログラムは、強力かつ柔軟です。
新しい関数の追加は簡単です。
pi
やe
のようにあらかじめ定義された変数を追加するために
プログラムを変更することは、簡単な仕事でしょう。
init_table
を変更し、定数を記号表に追加しなさい。
定数に型VAR
を与えれば簡単でしょう。
Go to the first, previous, next, last section, table of contents.