Tutorial sections:
Reference sections:
yyparse.
--- The Detailed Node Listing ---
Bisonの概念
例
逆ポーランド記法電卓
rpcalcのための文法規則
多機能電卓：mfcalc
Bison文法ファイル
Bison文法の概要
言語の意味の定義
Bison宣言
構文解析器のC言語インターフェイス
yyparse and what it returns.
yylex
which reads tokens.
yyerror.
字句解析器関数yylex
yyparse calls yylex.
yylex must return the semantic value
of the token it has read.
yylex must return the text position
(line number, etc.) of the token, if the
actions want that.
Bison構文解析器のアルゴリズム
演算子の優先順位
文脈依存性の処理
Bisonの実行
Bisonは、LALR(1)文脈自由文法の文法定義を、 その文法を解析するためのCで書かれたプログラムに変換する、 汎用の構文解析器生成ツールです。 あなたがBisonに熟練すれば、 簡単な電卓から複雑なプログラミング言語まで、 広い範囲の言語解析器を開発できるようになるでしょう。
BisonはYaccの上位互換です。 正しく書かれたすべてのYacc文法を、変更なくBisonで処理できます。 Yaccに親しんでいるすべての人は、ちょっと考えるだけで、 Bisonを使えるようになるでしょう。 Bisonを使い、本書を理解するためには、 C言語に精通している必要があります。
1章と2章は入門の章です。1章では、Bisonを使うための基本的な概念を説明し、 2章では3つの具体例を示します。 BisonやYaccを知らない方は、 1章から読みはじめてください。 3章以降では、Bisonの仕様を詳細に解説します。
Bisonは、最初にRobert Corbettによって開発され、 Richard StallmanがYacc互換にしました。 カーネギーメロン大学のWilfred Hansenが、 文字列リテラル1といくつかの機能を追加しました。
本書は、Bisonのバージョン1.25に基づいています。
本書は、株式会社アスキーの
支援を受けて、慶應義塾の石川直太
（naota@sfc.keio.ac.jp、http://www.sfc.keio.ac.jp/~naota/）
が翻訳しました。
なお、「GNU一般公有使用許諾書」の日本語訳については、 引地さんのところの日本語訳を使わせていただいたことを ここに記して感謝いたします。
日本語訳したtexinfoファイルは、
http://www.ascii.co.jp/pub/GNU/bison-1.25-man-jp.tgz
にあります。コマンドtexi2dviなどでdviファイルを生成したり、GNU Emacsでinfoファイルへ変換したりできます。
Bisonバージョン1.24において、フリーでないプログラムへのBisonの出力の
利用を許可するために、yyparseの配布条件を変えました。
それまでは、Bisonによって生成された構文解析器は、
フリーソフトウェアのプログラム中でのみ、利用可能でした。
GNU Cコンパイラなど他のGNUプログランミングツールには、 このような制限がありません。 それらは、いつでも、フリーでないソフトウェアの開発に利用できます。 Bisonの利用条件が異なっていた理由は、特別な政治的判断によるものではありません。 BisonのすべてのソースコードにGPLを適用した結果です。
Bisonの出力であるBison構文解析器ファイルには、
yyparse関数のためのコードである、
かなりの量のBisonのソースコードの一部分が、そのまま含まれます
（あなたが定義した文法によるアクションは、
この関数の1か所に挿入されるだけで、残りの関数は変わりません）。
われわれFSFがyyparseのコードにGPLを適用した結果、
Bisonの出力をフリーソフトウェアのみに利用するという制約ができたのです。
ソフトウェアを専売しようとする人々への思いやりによって、 われわれが条件を変えることはありませんでした。 ソフトウェアはフリーであるべきです。 しかし、われわれは、Bisonの利用をフリーソフトウェアに限定したことは、 他のソフトウェアをフリーにしようとする人々を勇気づけるために、 少なからず役立っただろうと、結論を下しました。 そこで、われわれは、その他のGNUツールの現実的な利用条件に合わせて、 Bisonの現実的な利用条件を決定することにしました。
1991年6月 バージョン2.0
Copyright © 1989, 1991 Free Software Foundation, Inc. 675 Mass Ave, Cambridge, MA 02139, USA 2 何人も、以下の内容を変更しないでそのまま複写する場合に限り、 本使用許諾書を複製したり頒布することができます。
ほとんどのソフトウェアの使用許諾は、ソフトウェアを共有し、 変更するユーザの自由を奪うことを意図しています。 それに対して、我々のGNU一般公有使用許諾は、 フリー・ソフトウェアを共有したり変更する自由をユーザに保証するためのもの、 即ちフリー・ソフトウェアがそのユーザ全てにとって フリーであることを保証するためのものです。 本使用許諾は、Free Software Foundationのほとんど全てのソフトウェアに 適用されるだけでなく、 プログラムの作成者が本使用許諾に依るとした場合のそのプログラムにも 適用することができます。 （その他の Free Software Foundation のソフトウェアのいくつかは、 本許諾書ではなく、GNUライブラリ一般公有使用許諾で保護されます。） あなたは自分のプログラムにもこれを適用できます。
我々がフリー・ソフトウェアについて言う場合は 自由のことに言及しているのであって、価格のことではありません。 我々の一般公有使用許諾の各条項は、次の事柄を確実に実現することを 目的として立案されています。
このようなユーザの権利を守るために、我々は、 何人もこれらの権利を否定したり、あるいは放棄するように ユーザに求めることはできないという制限条項を設ける必要があります。 これらの制限条項は、ユーザが、フリー・ソフトウェアの複製物を 頒布したり変更しようとする場合には、そのユーザ自身が守るべき義務ともなります。
例えば、あなたがフリー・ソフトウェアの複製物を頒布する場合、 有償か無償かにかかわらず、 あなたは自分の持っている権利を全て相手に与えなければなりません。 あなたは、相手もまたソース・コードを受け取ったり入手できるということを 認めなければなりません。 さらにあなたは、彼らが自分たちの権利を知るように、 これらの条項を知らしめなければなりません。
我々は次の２つの方法でユーザの権利を守ります。 （１）ソフトウェアに著作権を主張し、 （２）本使用許諾の条項の下で ソフトウェアを複製・頒布・変更する権利をユーザに与えます。
また、各作成者や我々自身を守るために、 本フリー・ソフトウェアが無保証であることを 全ての人々が了解している必要があります。 さらに、他の誰かによって変更されたソフトウェアが頒布された場合、 受領者はそのソフトウェアがオリジナル・バージョンではないということを 知らされる必要があります。 それは、他人の関与によって原開発者に対する評価が 影響されないようにするためです。
最後に、どのフリー・プログラムもソフトウェア特許に絶えず脅かされています。 我々は、フリー・プログラムの再頒布者が個人的に特許権を取得し、 事実上そのプログラムを自分の財産にしてしまうという危険を 避けたいと願っています。 これを防ぐために我々は、いずれの特許も、 誰でも自由に使用できるように使用許諾されるべきか、 あるいは何人に対しても全く使用させないかの、 いずれかにすべきであることを明らかにしてきました。
複写・頒布・変更に対する正確な条項と条件を次に示します。
複製、頒布、変更以外の行為は本使用許諾の対象としません。 それらは本使用許諾の範囲外です。 「プログラム」を実行させる行為に関して制約はありません。 「プログラム」の出力は、 （「プログラム」を実行させて作成させたかどうかとは無関係に） その内容が「プログラム生成物」である場合に限り本使用許諾の対象となります。 これが当てはまるかどうかは、「プログラム」が何をするものかに依ります。
複製物の引き渡しに要する実費は請求することができます。 また、あなた独自の保証を行なう場合はそれを有償とすることができます。
これらの要件は変更された作成物にも全て適用されます。 その変更版の或る部分が「プログラム」の派生物ではなく、 しかもそれ自体独立で異なる作成物だと合理的に考えられる場合、 あなたがそれらを別の作成物として頒布した時は、 本使用許諾とその条項はそれらの部分には適用されません。 しかし、それらを「プログラム生成物」の一部として頒布する場合は、 全体が本使用許諾の条項に従って頒布されなければならず、 使用許諾を受ける他の全ての者に対する許諾も プログラム全体にわたって与えられなければならず、 結果として、誰が書いたかにかかわらず、 全ての部分に本使用許諾が適用されなければなりません。
このように、本条項の意図するところは、 完全にあなたによって書かれた作成物について、権利を要求したり、 あなたと権利関係を争うことではありません。 むしろその目的は、作成物が「プログラム生成物」 である場合にその派生物や集合物の頒布を規制することにあります。
さらに、「プログラム」（又は「プログラム生成物」）と 「プログラム生成物」とはならない他のプログラムとを、 単に保管や頒布のために同一の媒体上にまとめて記録したとしても、 本使用許諾は他のプログラムには適用されません。
なお、ソース・コードとは、変更作業に適した記述形式を指します。 また、実行可能形式のファイルに対応するソース・コード一式とは、 それに含まれる全モジュールに対応する全てのソース・コード、 及びあらゆる関連のインタフェース定義ファイル、 及び実行を可能にするコンパイルとインストールの制御に関する記述を指します。 特別な例外として、実行可能なファイルが動作するオペレーティング・システムの 主要な構成要素（コンパイラ、カーネルなど）と共に （ソース・コード又はバイナリのどちらかで）頒布されているものについては、 その構成要素自体が実行形式に付随していない場合に限り、 頒布されるソース・コードに含める必要はありません。
実行可能形式またはオブジェクト・コードの頒布が、 指示された場所からの複製のためのアクセス権の賦与である場合、 同じ場所からのソース・コードの複製のための同等なアクセス権を賦与すれば、 たとえ第三者にオブジェクト・コードと共にソースの複製を強いなくとも、 ソース・コードを頒布したものとみなします。
本条項の或る部分が何らかの特別な状況下で無効または適用不可能になった場合、 本条項のその他の残りの部分が適用されるように意図されており、また、 本条項は全体としてその他の状況に当てはまるように意図されています。
本条項の目的は、特許やその他の財産権を侵害したり、 そのような権利に基づく主張の妥当性を争うようにあなたに 勧めることではありません。 本条項の唯一の目的は、フリー・ソフトウェアの頒布システムの完全性を守ることで、 それは公有使用許諾の実践によって履行されます。 多くの人々が、このシステムの一貫した適用を信頼して、 このシステムを通じて頒布されている幅広い範囲のソフトウェアに惜しみない貢献を してくれました。 作成者や寄贈者が他の何らかのシステムを通じてソフトウェアを 頒布したいと決めることは彼らの自由意志であり、 使用許諾を受ける者はその選択を強いることはできません。
本条項は、本使用許諾の他の条項の意味内容が何であるかを 完全に明らかにすることを意図しています。
各バージョンは、バージョン番号によって区別します。 「プログラム」中に本使用許諾のバージョン番号の指定がある場合は、 その指定されたバージョンか、又はその後にFree Software Foundationから 公表されているいずれかのバージョンから１つを選択して、 その条項と条件に従ってください。 「プログラム」中に本使用許諾のバージョン番号の指定がない場合は、 Free Software Foundation が公表したどのバージョンでも選択することができます。
英文文書（GNU General Public License）を正式文書とする。 この和文文書は弁護士の意見を採り入れて、 できるだけ正確に英文文書を翻訳したものであるが、 法律的に有効な契約書ではない。
いかなる媒体でも次の条件がすべて満たされている場合に限り、 本和文文書をそのまま複写し配布することを許可する。 また、あなたは第三者に対して本許可告知と同一の許可を与える場合に限り、 再配布することが許可されています。
あなたが新しくプログラムを作成し、それを公用に供したい場合は、 プログラムをフリー・ソフトウェアにして、 全ての人々が以上の各条項に従ってこれを再頒布や変更をすることが できるようにするのが最良の方法です。
そうするためには、プログラムに以下の表示をしてください。 その場合、無保証であるということを最も効果的に伝えるために、 ソース・ファイルの冒頭にその全文を表示すれば最も安全ですが、 その他の方法で表示する場合でも、「著作権表示」と全文を読み出す為の アドレスへのポインタだけはファイル上に表示しておいてください。
プログラム名とどんな動作をするものかについての簡単な説明の行 Ｃｏｐｙｒｉｇｈｔ（Ｃ） １９○○年、著作権者名 本プログラムはフリー・ソフトウェアです。 あなたは、Free Software Foundationが公表したGNU 一般公有使用許諾の 「バージョン２」或いはそれ以降の各バージョンの中からいずれかを選択し、 そのバージョンが定める条項に従って本プログラムを 再頒布または変更することができます。 本プログラムは有用とは思いますが、頒布にあたっては、 市場性及び特定目的適合性についての暗黙の保証を含めて、 いかなる保証も行ないません。 詳細についてはGNU 一般公有使用許諾書をお読みください。 あなたは、本プログラムと一緒にGNU一般公有使用許諾の写しを 受け取っているはずです。 そうでない場合は、
Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA 3 へ手紙を書いてください。
また、ユーザが電子メイルや書信であなたと連絡をとる方法についての情報も 書き添えてください。
プログラムが対話的に動作する場合は、 対話モードで起動した時に次のような短い告知文が表示されるようにしてください。
Ｇｎｏｍｏｖｉｓｉｏｎ バージョン６９、Ｃｏｐｙｒｉｇｈｔ（Ｃ）１９○○年 著作権者名 Gnomovision は完全に無保証です。詳細は show w とタイプしてください。 これはフリー・ソフトウェアなので、特定の条件の下でこれを再頒布する ことができます。詳細は show c とタイプしてください。
上記のshow wやshow cは各々、
本一般公有使用許諾の関連する部分を表示するコマンドを指します。
もちろん、あなたが使うこれらのコマンドはshow wやshow cといった
呼び名でなくても構いません。
さらに、それらのコマンドはあなたのプログラムに合わせる為に、
マウスでクリックしたりメニュー形式にすることもできます。
また、必要と認めた場合には、あなたの雇い主 （あなたがプログラマとして働いている場合）や在籍する学校から、 そのプログラムに対する「著作権放棄」を認めた署名入りの書面を入手してください。 ここにその文例を載せます。名前は変えてください。
Yoyodyne, Inc. は、James Hacker が開発したプログラム`Gnomovision' （コンパイラにつなげるプログラム）についての著作権法上の全ての権利を放棄する。 Ｔｙ Ｃｏｏｎ の署名， １ Ａｐｒｉｌ １９８９ Ｔｙ Ｃｏｏｎ， 副社長
本一般公有使用許諾は、あなたのプログラムを財産権の対象となっている 他のプログラムに組み込むことは認めていません。 あなたのプログラムがサブルーチン・ライブラリであって、 あなたがそのライブラリを財産権の対象となっている他のアプリケーションと リンクさせることによって、さらに有用なものにしようとする場合には、 本使用許諾書の代わりに、GNUライブラリ一般公有使用許諾書に従ってください。
この章では、Bisonの詳細を理解するのに欠くことのできない、 多くの基礎概念を説明します。 まだBisonやyaccの使い方を知らない方は、 この章を注意深く読むことから始めてください。
Bisonが言語を解析するためには、その言語が 文脈自由文法（context-free grammar）で記述されている必要があります。 すなわち、1個以上の文法グループ（syntactic groupings）を定め、 その文法グループを部品から組み立てる規則を与える必要があります。 たとえば、C言語では、ある種のグループは「式」と呼ばれます。 式を作る規則の1つは、 「1つの式とは、別の式にマイナス記号を付けたものでもよい」かもしれません。 別の規則は、「1つの式とは、整数でもよい」かもしれません。 ここから解るように、規則はしばしば再帰的になりますが、 再帰を始めるための少なくとも1個の規則が必要です。
このような規則を人間が読めるように表現する、もっとも一般的な形式的な方法は、 バッカス-ナウア記法（Backus-Naur form）略して"BNF"です。 これは、Algol 60言語を定義するために開発されました。 BNFで表現された任意の言語は、文脈自由言語です。 Bisonへの入力は、本質的には、機械可読なBNFです。
すべての文脈自由言語をBisonで扱えるわけではありません。 LALR(1)だけを扱えます。 簡単に説明すると、ちょうど1個のトークンを先読みすることによって、 入力文字列の任意の部分を解析できる必要があるということです。 厳密に説明すると、これはLR(1)文法の説明で、 LALR(1)には簡単に説明できない追加の制限があります。 しかし、LALR(1)になれないLR(1)文法は、現実にはまれです。 より詳しい説明は See Mysterious Reduce/Reduce Conflicts。
ある言語についての形式文法的な規則では、 文法的な単位またはグループを記号（symbol）と呼びます。 文法規則に従って小さい部分から組み立てられた記号を 非終端記号（nonterminal symbol）といい、 終端記号（terminal symbol）またはトークン型（token type）と呼ばれる ものに分解できます。 本書では、1個の終端記号に対応する入力の一部分をトークン（token）、 1個の非終端記号に対応する入力の一部分をグループ（grouping）と呼びます。
何が終端記号で何が非終端記号かを示すために、 例としてC言語を使います。 Cのトークンは、識別子、定数（数値または文字列）、さまざまな予約語、 算術演算子、区切り記号です。 C言語の終端記号には、「識別子」、「数値」、「文字列」、そして、 予約語、演算子、区切り記号のそれぞれに対する記号、 すなわち、「if」、「return」、「const」、「static」、「int」、「char」、 「プラス記号」、「開きブレース」、「閉じブレース」、「カンマ」、 などが含まれます （これらのトークンは文字に分解できますが、 それは文法の問題ではなく、字句解析の問題です）。
次の例は、トークンに分解されたCの関数です。
int /* 予約語 `int' */
square (x) /* 識別子, 開きかっこ, */
/* 識別子, 閉じかっこ */
int x; /* 予約語 `int', 識別子, セミコロン */
{ /* 開きブレース */
return x * x; /* 予約語 `return', 識別子, */
/* アスタリスク, 識別子, セミコロン */
} /* 閉じブレース */
Cの文法的なグループには、式、文、宣言、関数定義が含まれます。
これらは、Cの文法で、非終端記号、「式」、「文」、「宣言」、
「関数定義」として表されます。
完全な文法では、上記の4つの意味を表現するために、
それぞれの非終端記号について、数十個の追加の言語構築が必要です。
上記の例で、関数定義は、宣言と文を含みます。
文の中で、それぞれのxは式であり、
x * xも式です。
それぞれの非終端記号には、それがより単純な構成要素からどのように作られるか
示すために、文法規則が必要です。
たとえば、Cの文の1つであるreturn文について、
文法規則を形式ばらずに書くと、次のようになります。
「文」は、キーワード「return」、「式」、「セミコロン」から
作ることができる。
Cの各種の文について、「文」には多くの他の規則があるでしょう。
1つの非終端記号が、言語の全体を表現するように、 特別なものとして識別される必要があります。 これを開始記号（start symbol）と呼びます。 コンパイラでは、これは完全な入力プログラムを意味します。 C言語では、非終端記号「定義と宣言の並び」が、この働きをします。
たとえば、1 + 2は有効なCの式で、
Cのプログラムの有効な一部分ですが、
Cプログラム全体としては無効です。
したがって、Cの文脈自由文法では、「式」は開始記号でないとわかります。
Bison構文解析器は、入力としてトークンの列を読み、 文法規則を使ってトークンをグループにします。 もし入力が有効であれば、最終的な結果として、トークンの列全体が 文法の開始記号である1つのグループの記号に還元されます。 もしわれわれがCの文法を使うならば、入力全体は 「定義と宣言の列」の必要があります。 もしそうでなければ、構文解析器が文法エラーを報告します。
形式文法（formal grammer）は、数学的な構成です。 Bisonのために言語を定義するためには、Bisonの書式で文法を記述した Bison文法（Bison grammer）ファイルを書く必要があります。 See Bison Grammar Files。
形式文法の中での1つの非終端記号は、Bisonの入力の中で、
Cの識別子のような、1つの識別子として表現されます。
expr、stmt、declarationのように、
通常、非終端記号は小文字で書きます。
終端記号に対するBisonの表現は、
トークン型（token type）ともいいます。
トークン型は、C言語で使われるような識別子であるかもしれません。
通常、非終端記号からこれらを区別するために、大文字で書きます。
たとえば、INTEGER、IDENTIFIER、IF、RETURN
のように書きます。
言語の個々のキーワードを表す終端記号は、
キーワードを大文字に変換してから命名するべきです。
終端記号errorは、エラーからの回復処理のために予約されています。
See Symbols。
ある終端記号は、C言語の文字定数のような、1文字リテラルを表している かもしれません。 トークンがちょうど1文字である（たとえば、かっこ、プラス記号など）ならば必ず、 そのトークンに対する終端記号として、同じ文字を使うべきです。
終端記号を表す第3の方法は、何文字かを含むC言語の文字列定数です。 詳細はSee Symbols。
文法規則は、Bisonの文法の中で、もう1つの式を持ちます。
たとえば、C言語のreturn文に対するBisonの規則があります。
クォート（'）で囲まれたセミコロンは、文に対するC言語の文法の一部分を表す、
1文字のリテラルトークンです。
クォートで囲まれていないセミコロンとコロンは、
あらゆる規則の中で使われる、Bisonの区切り文字です。
stmt: RETURN expr ';'
;
形式文法は、トークンを分類法に基づいてのみ、選びます。
たとえば、ある規則が`integer constant'という終端記号について言及するならば、
それは、文法的にそこに現れてよい任意の整数型定数を意味します。
その定数の正確な値は、入力が解析される方法と無関係です。
もし、x+4が文法的に正しいならば、x+1も、x+3989も、
同様に文法的に正しいのです。
しかし、いったん解析されれば、入力にとって正確な値はきわめて重要です。 プログラム中の定数として4と1と3989を区別できないコンパイラは、 役に立ちません。 そこで、Bison文法の中のそれぞれのトークンは、トークン型のほかに、 意味値（semantic value）を持ちます。詳細については、 See Defining Language Semantics。
トークン型は、INTEGER、IDENTIFIER、','のように、
文法の中で定義される終端記号です。
これは、そのトークンが正しい位置に現れているか確かめ、
他のトークンとどのようにグループ化するか決めるために必要な、
すべての情報を含んでいます。
文法規則は、トークンの型以外の何も知りません。
意味値は、トークンに関する、たとえば、整数の値や識別子の名前のような、
トークン型以外のあらゆる情報を持っています
（','のような区切り記号であるトークンは、
意味値を持つ必要がありません）。
たとえば、ある入力されたトークンは、トークン型がINTEGERで、
意味値が4であると分類されるかもしれません。
別の入力されたトークンは、同じINTEGER型で、
値が3989であるかもしれません。
文法規則がINTEGERの出現を許すのならば、
どちらのトークンもINTEGER型なので、受け入れられます。
構文解析器は、トークンを受け入れるときに、その意味値を記憶します。
それぞれのグループ化は、それに対応する非終端記号とともに、意味値を持てます。 たとえば、電卓の中では、1つの式は、通常、数値である意味値を持ちます。 プログラミング言語のコンパイラの中では、1つの式は、通常、 式の意味を表す木構造の意味値を持ちます。
役に立つようにするためには、プログラムは、入力を解析するだけでなく、 入力に基づくなんらかの出力を生成する必要があります。 Bison文法の中では、文法規則は、 Cで書かれたアクション（action）を持てます。 そのルールへのマッチを構文解析器が認識するたびに、アクションが実行されます。 See Actions
多くの場合に、アクションの目的は、部品の意味値から全体の意味値を 計算することです。 たとえば、1つの式とは2つの式の和でありうると仮定します。 構文解析器が和を認識すると、 部分式それぞれは、それがどのように構成されたかを表す意味値を持っています。 アクションは、新しく認識された合成式について、 同様の意味値を構成するべきです。
以下に、1つの式が2つの部分式の和となる規則の例を示します。
expr: expr '+' expr { $$ = $1 + $3; }
;
このアクションは、2個の部分式の値から、 式の和の意味値を生成する方法を示しています。
Bisonを使うときには、入力としてBison文法ファイルを指定します。 文法で記述された言語を解析する、Cのソースファイルが出力になります。 このファイルをBison構文解析器（Bison parser）と呼びます。 BisonユーティリティとBison構文解析器は、 別のプログラムであることに注意してください。 Bisonユーティリティの出力がBison構文解析器で、 あなたのプログラムの一部分になるのです。
Bison構文解析器の仕事は、文法規則に従って、トークンをグループ化することです。 たとえば、識別子と演算子から式を組み立てます。 このために、文法規則に対応するアクションを実行します。
トークンは、字句解析器（lexical analyzer）と呼ばれる関数によって得られ、
その関数を（Cで書くような）なんらかの方法で与える必要があります。
Bison構文解析器は、新しいトークンを必要とするたびに、
字句解析器を呼び出します。
Bison構文解析器は、トークンの「内部」がなんであるか知りません
（しかし、トークンの意味値は関係します）。
一般に、字句解析器は、テキスト中の文字を解析してトークンを得ますが、
Bisonはその方法を知りません。
See The Lexical Analyzer Function yylex。
Bison構文解析器ファイルは、Cのプログラムで、yyparseという名前の、
文法を実装する関数を定義します。
この関数は、完全なCのプログラムを構成しません。
いくつかの関数を補ってやる必要があります。
1つは、字句解析器です。
もう1つは、エラーを報告するために構文解析器が呼び出す、
エラー報告関数です。
さらに、完全なCプログラムはmain関数から実行を始める必要がありますので、
これを補って、そこからyyparseを呼び出してください。
See Parser C-Language Interface。
あなたが書くアクションの中でのトークンの型名と記号に関係なく、
Bison構文解析器の中で使われるすべての変数と関数の名前は、
yyまたはYYで始まります。
これは、字句解析関数yylexとエラー報告関数yyerrorおよび
構文解析関数yyparseのようなインターフェイス関数も含みます。
また、内部で使われる多数の識別子も同様です。
したがって、本書で定義されている場合を除いて、
Bison文法ファイルの中でyyまたはYYで始まる
Cの識別子の利用は避けるべきです。
Bisonを使って、文法の定義から実際に動くコンパイラやインタープリタを作るまでの、 言語設計手順は、次のようになります。
yylex）。
Lexを使って生成することも可能ですが、本書ではLexの使い方については解説
していません。
このソースプログラムを実行可能なプログラムにするために、 次の手順が必要です。
Bisonユーティリティへの入力は、 Bison文法ファイル（Bison grammar file）です。 Bison文法ファイルの一般的な書式は、次のとおりです。
%{
C宣言部（C declarations）
%}
Bison宣言部（Bison declarations）
%%
文法規則部（Grammar rules）
%%
追加のCプログラム部（Additional C code）
Bison文法ファイル中の%%、%{、%}は、
ファイルを節に分ける区切り記号です。
C宣言部では、
アクションの中で使われる型と変数を定義できます。
マクロを定義するためのプリプロセッサディレクティブや、
ヘッダファイルをインクルードするための#include命令も使用できます。
Bison宣言部には、終端記号、非終端記号、さらに、 演算子の優先順位、さまざまな記号の意味値のデータ型を記述できます。
文法規則部では、各非終端記号をその部品から組み立てる方法を 定義します。
追加のCプログラム部には、
あなたが望むCプログラムを記述できます。
よく字句解析関数yylexや
文法規則の中のアクションから呼ばれる関数をここに書きます。
単純なプログラムでは、4ここに
残りのプログラム全部を書きます。
本章では、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 The C Declarations Section）には、 2つのプリプロセッサディレクティブがあります。
#defineディレクティブで、トークンとグループの意味値に対する
Cのデータ型を指定するために、マクロYYSTYPEを定義します
（see Data Types of Semantic Values）。
Bison構文解析器は、YYSTYPEに定義された型を使います。
定義しないと、int型が使用されます。
各トークンと式は、浮動小数点数である記録値を持つので、
ここではdoubleを指定します。
べき乗関数powの宣言を使うために、
#includeディレクティブを使っています。
第2の部、Bison宣言は、Bisonのためにトークン型についての情報を用意します
（see The Bison Declarations Section）。
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 Actions。
これらのアクションをCで書く必要がありますが、
Bisonには規則の間で意味値を受け渡しする方法があります。
それぞれのアクションで、擬似変数$$は、
その規則が構成しようとしているグループの意味値を示します。
$$に値を代入することが、アクションの主な仕事です。
規則の部品の意味値は、$1、$2などの
名前で参照されます。
inputの説明inputの定義について考えます。
input: /* 空 */
| input line
;
この定義の意味は、「完全な入力とは、空文字列であるか、あるいは、
完全な入力に入力行が続いたものである」ということです。
「完全な入力」が、それ自身を使って定義されていることに注意してください。
列の中でinputが常に左端の記号なので、
このような定義を左再帰（left recursive）と呼びます。
See Recursive Rules。
最初の選択肢は、:と|の間に記号がないので空です。
これは、（トークンを含まない）空の入力文字列にマッチします。
電卓を起動した直後にCtrl-d 5を
押しても、正しい入力と扱われるように、この規則を入れました。
通常、空に対応する選択肢を最初に置き、そこに/* 空 */と
書きます。
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 Actions。
すべての規則に対してアクションを書く必要はありません。
アクションを省略すると、Bisonは$1の値を$$に複写します。
第1の規則では、NUMの値をそのまま複写するために、
このようになっています。
ここで示したリストは、望ましい書式ですが、 Bisonがこのように要求するわけではありません。 必要に応じて、空白、タブ、改行を置けます。 次のような書き方も可能です。
exp : NUM | exp exp '+' {$$ = $1 + $2; } | ...
これは、次のリストと等価です。
exp: NUM
| exp exp '+' { $$ = $1 + $2; }
| ...
しかし、後者のほうが可読性が優れています。
rpcalc字句解析器字句解析器の仕事は、低水準の構文解析で、文字または文字列を
トークンに変換します。
Bison構文解析器は、字句解析器を呼び出してトークンを得ます。
See The Lexical Analyzer Function yylex。
RPN（逆ポーランド記法）電卓には、簡単な字句解析器のみが必要です。
この字句解析器は、空白とタブを読み飛ばし、
数値を読み込んでdouble型のNUMトークンとして返します。
数値の一部分ではないその他の文字は、独立のトークンです。
1文字トークンのトークン符号はその文字自身であることに注意してください。
字句解析関数の戻り値は、トークン型を表す数値です。
Bison規則の中でトークン型を表すために使われる文字列と同じものが、
その型の数値符号を表すCの式でもあります。
これには、2種類の働きがあります。
もし、トークン型が文字リテラルならば、
その数値符号は文字のASCII符号であり、
数値を表すために字句解析器の中と同じ文字リテラルを使えます。
もし、トークン型が識別子ならば、適切な番号を定義するCのマクロとして、
その識別子がBisonによって定義されます。
したがって、この例では、NUMは、yylexのために使える
マクロにもなります。
トークンの意味値は、もし存在すれば、大域変数yylvalに記憶され、
Bison構文解析器はそこを見にいきます
（yylvalのCデータ型は、文法の最初で定義されるYYSTYPEです。
see Declarations for 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 ();
}
6
yyparseは、構文エラーを検出すると、エラーメッセージ
（必ずそうとはかぎりませんが、通常は"parse error"）を
表示するために、エラー報告関数yyerrorを呼び出します。
#include <stdio.h>
yyerror (s) /* エラーが起きるとyyparseから呼び出される */
char *s;
{
printf ("%s\n", s);
}
yyerrorから戻った後に、Bison構文解析器は、
文法に適切なエラー規則（see Error Recovery）があれば、
エラーから回復し、解析を継続できます。
そうでない場合には、yyparseが0でない値を返します。
この例では、エラー規則を書いていないので、
不正な入力はすべて電卓プログラムを終了させます。
これは、実際の電卓としてはきれいな動作ではありませんが、
最初の例としては十分です。
構文解析器を生成するためにBisonを実行する前に、
1つ以上のソースファイルのすべてをどのように整えるか、
決める必要があります。
このような単純な例では、すべてを1個のファイルに詰め込む方法が
いちばん簡単です。
yylex、yyerror、mainの定義を、
ファイルの「追加のCコード」部の最後に置きます
（see The Overall Layout of a Bison Grammar）。
大きなプロジェクトでは、ソースコードを複数のファイルに分け、
まとめてリコンパイルするためにmakeを使うでしょう。
1つのファイルにすべてのソースが入っているならば、 次のコマンドで、それを構文解析器ファイルに変換できます。
bison file_name.y
この例では、ファイルはrpcalc.y（逆ポーランド記法電卓）と
呼ばれています。Bisonは、元のファイル名から.yを取り除いて、
file_name.tab.cというファイルを生成します。
Bisonが出力したファイルには、yyparseのソースコードが含まれています。
入力ファイル中の追加の関数（yylex、yyerror、main）は、
出力にそのまま複写されます。
構文解析器ファイルをコンパイルする方法を示します。 7
# カレントディレクトリのファイルの一覧を見る。 % 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 Operator Precedence。
もう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 Error Recovery）。
yyerrokとyyerrorの違いに注意してください。
この形式のエラー回復は、構文エラーを扱います。
他の種類のエラーもあります。
たとえば、0による除算は、例外シグナルを発生し、通常は致命的です。
実際の電卓プログラムは、このシグナルをつかまえて、longjmpを使って
mainに戻り、入力行の構文解析を続ける必要があります。
さらに、現在の入力行の残りは破棄されるべきです。
しかし、これらの問題は、Bisonのプログラムに固有の問題ではないので、
本書では解説しません。
mfcalcBisonの基礎についての説明が終わったので、より高度な話題に移りましょう。
前述の電卓は、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 %
複数の代入8と 関数の入れ子9が 許されることに注意してください。
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 More Than One Value Type）。
%union宣言は、YYSTYPEの定義の代わりで、
可能な型の一覧を指定します。
ここで許される型は、（expとNUMのための）倍精度浮動小数点型と、
記号表の項目へのポインタです。
See The Collection of Value Types。
値がいろいろな型を持つことができるので、
意味値を使うそれぞれの文法記号に対して、
型を関連づける必要があります。
これらの記号はNUM、VAR、FNCT、expです。
それらの宣言は、不等号で囲まれた（<...>）データ型に関する
情報を付加されています。
Bisonは、ちょうど%tokenがトークン型の宣言に使われるのと同じように、
%typeが非終端記号の宣言に使われるようにします。
非終端記号は通常それらを定義する規則によって暗黙に宣言されるので、
%typeをその規則よりも先に使ってはいけません。
しかし、expは、その値の型を指定するので、
明示的に宣言する必要があります。
See Nonterminal Symbols。
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のようにあらかじめ定義された変数を追加するために
プログラムを変更することは、簡単な仕事でしょう。
math.hにある関数のいくつかを、初期化リストに追加しなさい。
init_tableを変更し、定数を記号表に追加しなさい。
定数に型VARを与えれば簡単でしょう。
Bisonは、文脈自由文法の仕様を入力として受け取り、 その文法の正しいインスタンスを認識する、 C言語の関数を生成します。
Bison文法ファイルの名前は、通常.yで終わります。
Bison文法ファイルは4つの主要な部分からなります。 それらを、適切な区切り文字とともに示します。
%{
C宣言部（C declarations）
%}
Bison宣言部（Bison declarations）
%%
文法規則部（Grammar rules）
%%
追加のCプログラム部（Additional C code）
/* ... */で囲まれたコメントは、どの部分にも書けます。
C宣言部（C declarations）には、マクロ定義と、文法定義のアクションで
使うための関数と変数の宣言があります。
これらは、yyparseの定義に優先するように、構文解析器ファイルの最初に
複写されます。
ヘッダファイルから宣言を得るには#includeを使います。
C宣言がまったく必要ない場合は、この部分を囲む
%{と%}を省略できます。
Bison宣言部（Bison declarations）は、終端記号と非終端記号の宣言、 演算子の優先順位の指定などを含みます。 単純な例では、宣言を省略できます。 See Bison Declarations。
文法規則部（grammar rules）は、1つ以上のBison文法規則を含み、 それ以外は含みません。 See Syntax of Grammar Rules。
少なくとも1つの文法規則が存在する必要があります。
また、文法規則より先に%%が必要で、
もしそれ以前に何も記述されていなくても、省略できません。
追加のCプログラム部（additional C code）は、C宣言部が構文解析器ファイルの先頭に複写
されるのと同じように、構文解析器ファイルの末尾にそのまま複写されます。
構文解析器ファイル中に置く必要があって、
yyparseの定義よりも前に置く必要のないものを、ここに置くと便利です。
たとえば、yylexとyyerrorの定義は、
よくここに置かれます。
See Parser C-Language Interface。
もし直前の部が空ならば、文法規則と区別するための
%%を省略できます。
Bison構文解析器は、名前がyyで始まる多くの静的変数と、
名前がYYで始まる多くのマクロを含んでいます。
本書で解説しているものを意図的に使う場合を除いて、
そのような名前を文法ファイルの追加のCプログラム部で使うのは避けるべきです。
Bison文法の記号（symbols）は、 言語の文法的分類を表現します。
終端記号（terminal symbol）
（トークン型（tokens types）ともいいます）は、
構文的に等価なトークンのクラスを表します。
そのクラスのトークンが許されることを表すために、
文法規則の中で記号を使えます。
その記号は、Bison構文解析器の中で番号で表現され、
yylex関数は、どのような種類のトークンが読み込まれたかを示すために、
トークン番号を返します。
これを表す記号を知っていればよく、その番号を知っている必要はありません。
非終端記号（nonterminal symbol）は、 構文的に等価なグループを表現します。 記号名は文法規則の記述に使われます。 通常、非終端記号名を小文字で書きます。
記号名は、英字、先頭以外での数字、下線記号（_）とピリオドからなります。
ピリオド記号（.）は、非終端記号の名前には使えますが、
終端記号の名前には使えません。
文法中で終端記号を記述するには3種類の方法があります。
%tokenのようなBison宣言とともに定義する必要があります。
See Token Type Names。
'+'は文字トークン型です。
意味値データ型（see Data Types of Semantic Values）、
結合性、優先順位（see Operator Precedence）を
指定する必要がなければ、
文字トークン型を宣言する必要はありません。
通常、文字トークン型は、特別な文字10から
なるトークンを表すためだけに使います。
たとえば、トークン型'+'を、
トークンとしての+文字を表すために使います。
このようにする義務はありませんが、そうしないと、
あなたが書いたプログラムを読む人が混乱するでしょう。
C言語の文字リテラルで使われる通常のエスケープシーケンス
11を、Bisonでも使えます。
しかし、'\0'だけはASCII符号の0を表し、
yylexがファイルの終わりを示す符号なので、
文字リテラルとしては使えません
（see Calling Convention for yylex）。
"<="がリテラル文字列トークンです。
意味値（see Value Type）、
結合性、優先順位（see Operator Precedence）を
指定する必要がなければ、
リテラル文字列トークンを宣言する必要はありません。
%token宣言（see Token Declarations）を使って、
リテラル文字列トークンを、記号名の別名として関連づけられます。
そうしないと、字句解析器は、
yytname表（see Calling Convention）を使って、
リテラル文字列トークンからトークン番号を検索する必要があります。
【警告】yaccではリテラル文字列トークンを使えません。
通常、特殊文字の列からなるトークンの表現にのみ、
リテラル文字列トークンを使います。
たとえば、トークンとしての<=を表すために、
トークン型"<="を使うべきです。
そうする義務はありませんが、そうしないと、
あなたが書いたプログラムを読む人が混乱するでしょう。
C言語で使えるエスケープシーケンスはすべてBisonでも使えます。 リテラル文字列トークンは、2文字以上からなります。 もし、トークンが1文字ならば、前述の1文字トークンを使ってください。
終端記号を書く方法は、終端記号の文法的意味に関係なく、 規則の中に現れる位置と、 構文解析器関数が記号を返す方法に関係します。
yylexが返す値は、終端記号のどれかを表し、
入力の終わりでは0です。
文法規則の中でどの方法でトークン型を書いても、
yylexを定義する書き方は同じです。
1文字トークン型に対する符号は、その文字のASCII符号なので、
yylexは必要な符号を生成するために同一の文字定数を使えます。
名前を付けられたトークン型はそれぞれ、
構文解析器ファイルの中でCのマクロになるので、
yylexは符号に対するマクロ名を使えます。
これが、終端記号の名前にピリオド記号を使えない理由です。
See Calling Convention for yylex。
yylexが構文解析器と別のソースファイルの中に書かれる場合には、
そこでトークン型マクロ定義を使えるように準備する必要があります。
-dオプションを付けてBisonを実行してください。
すると、マクロ定義がname.tab.hというファイルに書かれ、
必要に応じて別のソースファイルからインクルードできます。
See Invoking Bison。
記号errorは、エラー回復用に予約された終端記号（see Error Recovery）
で、他の目的に使うべきではありません。
実際に、yylexがこの値を返すことは決してありません。
Bison文法規則は、一般的に次の書式です。
result: components...
;
resultは、この規則が記述する非終端記号で、 componentsは、この規則で一緒に置かれるさまざまな 終端および非終端記号です。 例を示します。
exp: exp '+' exp
;
この例では、+トークンを間にはさんで
型expの2つのグループ化が行われ、
型expのより大きなグループができます。
規則の中の空白12は、 記号を分けるだけの意味を持ちます。 必要に応じて、余分な空白を書いてもかまいません。
componentsの周辺にあるものは、 規則の意味を決定するアクション（action）になることができます。 アクションは、次のようになります。
{C statements}
通常、1つだけのアクションと、それに続くcomponentsがあります。 See Actions。
同一の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 The Bison Parser Algorithm。
規則の結果が直接その右側には含まれず、 右側にある非終端記号の中に含まれるとき、 間接（indirect）すなわち相互（mutual）再帰が起きます。
例を示します。
expr: primary
| primary '+' primary
;
primary: constant
| '(' expr ')'
;
この例では、それぞれの規則が互いに参照しているので、 2個の相互再帰が定義されています。
言語に対する文法規則は、文法だけを決めます。 意味は、各種のトークンとグループ化に対応する意味値により、 各種のグループ化が認識されるときに、決定されます。
電卓の例では、式のそれぞれに対応する値が適切な数値なので、
電卓は正確に計算できます。
グループx + yに
対応するアクションが、xとyに関する数値の和を計算します。
単純なプログラムでは、言語の要素のすべての意味値に対して同じデータ型を 使えば十分です。 逆ポーランド記法と中間記法電卓の例では、そうでした （see Reverse Polish Notation Calculator）。
特に指定しないと、Bisonはすべての意味値に対してint型を使います。
他の型を使うには、次の例のように、マクロYYSTYPEを定義します。
#define YYSTYPE double
このマクロ定義は、文法ファイルのC宣言部に置く必要があります （see Outline of a Bison Grammar）。
多くのプログラムでは、異なる種類のトークンとグループに対して、
異なるデータ型が必要です。
たとえば、数値定数はint型やlong型を必要とし、
文字列定数はchar *型を必要とし、
識別子は記号表の項目へのポインタを必要とするでしょう。
同一の構文解析器内で、意味値に対して2つ以上のデータ型を使うには、 次の2項目が必要です。
%unionで、考えられるデータ型全体の集合を指定します
（see The Collection of Value Types）。
%tokenを使います
（see Token Type Names）。
グループ化に対する型の指定には、Bison宣言の%typeを使います
（see Nonterminal Symbols）。
文法規則にともなうアクションは、その規則が認識されるたびに実行される Cのプログラムからなります。 アクションの仕事のほとんどは、関連するトークンまたは小さいグループから 規則にしたがって構成されるグループの、意味値の計算です。
アクションは、Cの複文のように、ブレースで囲まれたCの文からなります。 アクションは、規則のどの場所にも置け、その場所で実行されます。 規則のほとんどは、規則の終わりの構成要素の並びの後に、 1つだけアクションを持ちます。 規則の途中に置かれたアクションは、手の込んだ方法で特別な目的に使われます （see 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 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 Symbols。
'+'や'*'のような1文字リテラルトークンを除く
すべてのトークンの型名を宣言する必要があります。
非終端記号については、その意味値に対してどのデータ型を使うか
指定したければ、宣言する必要があります
（see More Than One Value Type）。
特に指定しないと、文法ファイル中の最初の規則は、 開始記号を特定します。 他の記号を開始記号にしたければ、明示的に宣言する必要があります （see Languages and Context-Free Grammars）。
トークン型名、すなわち終端記号を、基本的には次のように宣言します。
%token name
Bisonは、これを、構文解析器の中の#defineディレクティブに変換します。
したがって、関数yylexが構文解析器ファイルの中にあれば、
そこで名前nameをこのトークン型を表すために使えます。
優先順位を指定したければ、%tokenの代わりに、
%left、%right、%nonassocのどれかを使います。
See Operator Precedence。
トークンの名前の直後に整数値を書くことで、 そのトークン型に対応する数値符号を明示的に指定できます。
%token NUM 300
しかし、Bisonにすべてのトークン型に対する数値符号の割り当てをまかせる ことがいちばんです。Bisonは、トークン型どうしやASCII文字符号と 衝突が起きないように、自動的に数値符号を割り当てます。
スタック型が共用体である場合には、
%tokenあるいは他のトークン宣言に、
小なり記号と大なり記号で区切った型名を追加する必要があります
（see 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 Calling Convention）。
トークンの宣言とトークンの優先順位および結合規則の指定をまとめて行いたいならば、
%left、%right、%nonassocのどれかを使います。
これらは、優先順位宣言（precedence declarations）と呼ばれます。
演算子の優先順位の詳細については、
See Operator Precedence。
優先順位宣言の構文は、%tokenを使う宣言の構文と同じです。
%left symbols...
次のようにも書けます。
%left <type> symbols...
これらの宣言は、%tokenを使う宣言が目的とする
すべての機能を持っています。
それに加えて、次のように結合性と、すべてのsymbolsについての優先順位を指定します。
x op y op zが
構文解析された場合に、最初にxとyがグループ化されるか、
それともyとzがグループ化されるかを指定します。
%leftは、左結合性、つまりxとyが先に結合されることを
指定します。%rightは、右結合性、つまり、
yとzが先に結合されることを指定します。
%nonassocは、無結合性を指定し、その場合、
x op y op zは
構文エラーとみなされます。
%union宣言は、意味値に対して可能なデータ型すべての集合を指定します。
キーワード%unionに続いて、C言語における共用体の宣言と同様に、
ブレースで囲んだ宣言の並びを書きます。
例を示します。
%union {
double val;
symrec *tptr;
}
これは、2つの選択可能な型doubleとsymrec *があると、
宣言しています。
それぞれの型には、名前valとtptrが与えられています。
これらの名前は、%tokenとtype宣言の中で、
終端記号あるいは非終端記号に対する型を選ぶために使えます
（see Nonterminal Symbols）。
C言語での共用体宣言とは異なり、閉じブレースの後にセミコロンを 書いてはいけないことに注意してください。
%unionを複数の値型を指定するために使うならば、
値を持つ各非終端記号の値型を宣言する必要があります。
そのためには、次のように%type宣言を使います。
%type <type> nonterminal...
ここで、nonterminalは非終端記号の名前で、
typeは%unionで指定した名前の中からあなたが選んだものです
（see The Collection of Value Types）。
同じ値型を持つ任意の数の非終端記号を、
1つの%type宣言の中に記述できます。
その場合、記号名を空白で区切ってください。
同様に終端記号の値型の宣言も可能です。
そのためには、終端記号の宣言の中で、同じ<type>の
書式を使います。
すべてのトークン宣言で、<type>が許可されています。
文法の中に衝突（see Shift/Reduce Conflicts）があると、
Bisonは通常警告を表示します。
しかし、実際の文法のほとんどは、無害なシフト還元衝突を含み、
その衝突は、予測可能な方法で回避できますが、除去は困難です。
衝突の数が変わらないかぎり、このような衝突の警告は
抑制させるべきです。
そのために、%expect宣言を使います。
次のように宣言します。
%expect n
ここで、nは10進の整数です。 この宣言によって、n個のシフト還元衝突があって、 還元/還元衝突がなければ、警告が表示されません。 シフト還元衝突の数がnでなかったり、 1つでも還元/還元衝突があった場合は、通常の警告が表示されます。
一般に、次のような手順で%expectを使います。
%expectなしで文法ファイルをコンパイルします。
衝突が起こる位置の詳細な目録を得るために、-vオプションを指定します。
Bisonは、衝突の数も表示します。
%expect宣言を追加します。
すると、Bisonはチェックした衝突について文句をいわなくなりますが、 文法ファイルを書き換えて衝突の数が変わると、 再び警告を表示します。
Bisonは、文法定義部にある最初の非終端記号を、
省略時の開始記号と仮定します。
次のような%start宣言で、明示的に開始記号を指定できます。
%start symbol
再入可能（reentrant）プログラムとは、進路を変えないプログラム、 いいかえれば、完全に純粋な（pure）（読み出し専用）コードからなる プログラムです。 13 再入可能性は、非同期実行が可能な場合に重要です。 たとえば、再入可能でないプログラムを、 シグナルハンドラから呼び出すことは危険です。マルチスレッド制御システムでは、 再入不能プログラムはインターロックからしか呼び出せません。
通常のBison構文解析器は、yylexと通信するために静的
14変数を使うので、
再入可能プログラムでありません。これらの変数には、
yylvalとyylocが含まれます。
次のような%pure_parser Bison宣言は、
再入可能な構文解析器を生成します。
%pure_parser
この宣言によって、上記の2個の通信用変数が、yyparseの局所変数になり、
yylex字句解析関数を呼び出す方法が変わります。
詳細については、See Calling Conventions for Pure Parsers。
yyparseの中のyynerrs変数も局所変数になります
（see The Error Reporting Function yyerror）。
yypase関数自体を呼び出す方法は変わりません。
Bison宣言の要約を示します。
%union
%token
%right
%left
%nonassoc
%type
%start
%expect
%pure_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
YYNNTS
YYNRULES
YYNSTATES
Bisonを使うプログラムのほとんどは、言語を1つだけ構文解析し、
したがって、Bison構文解析器を1つだけ含みます。
しかし、1つのプログラムで2種類以上の言語を構文解析したいときは、
どうすればよいでしょうか？ そうするためには、yyparse、yylval
などの2重定義の衝突を防ぐ必要があります。
これを容易にする方法が、オプション-p prefixの利用です
（see Invoking Bison）。
これによって、Bison構文解析器のインターフェイス関数と変数の名前が、
yyで始まる代わりにprefixで始まります。
これでそれぞれの構文解析器に、衝突しないような異なる名前を与えられます。
変更される名前は、
yyparse、yylex、yyerror、yynerrs、
yylval、yychar、yydebugで全部です。
たとえば、-p cオプションを使えば、これらの名前は、
cparse、clexなどに変わります。
Bisonに関連する上記以外の変数とマクロのすべての
名前は変わりません。これらは、広域ではないので、
異なる構文解析器で同じ名前が使われても衝突しません。
たとえば、YYSTYPEの名前は変わりませんが、
この定義は構文解析器ごとに異なる方法で行われるので、問題ありません
（see Data Types of Semantic Values）。
-pオプションは、さらに、構文解析器ソースファイルの始めで、
yyparseをprefixparseと定義するように、
マクロを定義します。
この結果、構文解析器ソースファイル全体で、ある名前を別の名前に変えます。
Bison構文解析器の正体は、yyparseという名前のCの関数です。
ここでは、yyparseとほかに使う必要がある関数の間の
インターフェイスの方法を示します。
構文解析器の内部では、多くのyyまたはYYで始まるCの識別子が
使われていることに注意してください。
本書で説明しているものを除いて、そのような識別子を
文法ファイルのアクションや追加のCプログラムの中で使うと、
問題が起きるでしょう。
yyparse and what it returns.
yylex
which reads tokens.
yyerror.
yyparse構文解析を始めるには、関数yyparseを呼び出します。
この関数は、トークンを読み、アクションを実行し、最後には入力ファイルの
終わりに達するか回復不可能な構文エラーに達して、戻ります。
読み込みを打ち切ってyyparse関数から戻るような
アクションを書くことも可能です。
構文解析が成功する、つまり入力ファイルの終わりに達すると、
yyparseからの戻り値が0になります。
構文解析が失敗する、つまり構文エラーが発生すると、 戻り値が1になります。
アクションの中で、次のマクロを使って、
yyparseからただちに戻れます。
YYACCEPT
YYABORT
yylex字句解析器（lexical analyzer）関数yylexは、
入力からトークンを認識し、構文解析器に返します。
Bisonはこの関数を自動的に生成しないので、
yyparseから呼び出されるようにyylexを書く必要があります。
関数yylexは"lexical scanner"と呼ばれることもあります。
単純なプログラムでは、よく文法ファイルの最後でyylexを
定義します。yylexが別のソースファイルの中で定義する場合は、
そこでトークン型マクロ定義を使えるように準備する必要があります。
そのためには、-dオプションを指定してBisonを実行してください。
すると、マクロ定義がヘッダファイルname.tab.hに
書き込まれ、それを必要とするソースファイルにインクルードできます。
See Invoking Bison。
yyparse calls yylex.
yylex must return the semantic value
of the token it has read.
yylex must return the text position
(line number, etc.) of the token, if the
actions want that.
yylexを呼び出す方法yylexが返す値は、見つかったトークンの型に対する番号で、
入力ファイルの終わりに達した場合には0を返します。
トークンが文法規則の中で名前で参照される場合、
構文解析器ファイルの中でのその名前は、
トークン型に対する適切な番号にCのマクロとして定義されます。
したがって、yylexは型を示すためにその名前を使用できます。
See Symbols。
文法規則の中でトークンが1文字リテラルとして参照される場合には、
その文字の文字符号がトークン型に対する番号でもあります。
そこで、yylexは、単純に文字符号を返します。
しかし、戻り値0は入力ファイルの終わりを意味するので、
ヌル文字（'\0'）の文字符号を返してはいけません。
以下に例を示します。
yylex ()
{
...
if (c == EOF) /* ファイルの終わりか調べる。 */
return 0;
...
if (c == '+' || c == '-')
return c; /* `+' に対するトークン型が '+' であると仮定する。 */
...
return INT; /* トークン型を返す。 */
...
}
このようなインターフェイスは、
lexが生成した字句解析器を、
yylexの定義を変えずに使えるように設計されています。
文法規則が文字列リテラルトークンを使っている場合には、
yylexがそれに対するトークン型番号を使う、
2つの方法があります。
yylexはその記号名を他のトークンの記号名と
同様に使えます。この場合、文法ファイルの中での文字列リテラルトークンの
利用は、yylexにまったく影響しません。
yylexは、yytname表の中で、
複数文字トークンを見つけられます。
トークンに対する表の添え字は、そのトークン型の番号です。
複数文字トークンはyytnameの中にダブルクォート記号で囲まれて
記憶されます。
トークンに含まれる文字はエスケープされず、
表の中の文字列にそのまま書き込まれています。
トークンを構成する文字列がtoken_bufferに記憶されていると仮定して、
yytnameからトークンを探し出すプログラムを示します。
for (i = 0; i < YYNTOKENS; i++)
{
if (yytname[i] != 0
&& yytname[i][0] == '"'
&& strncmp (yytname[i] + 1, token_buffer, strlen (token_buffer))
&& yytname[i][strlen (token_buffer) + 1] == '"'
&& yytname[i][strlen (token_buffer) + 2] == 0)
break;
}
yytname表は、%token_table宣言をした場合にのみ生成されます。
See Decl Summary。
通常の再入可能でない構文解析器では、
トークンの意味値が広域変数yylvalに代入される必要があります。
意味値に対してただ1つのデータ型を使っている場合には、
yylvalの型もそうです。
したがって、たとえば、宣言を省略して型がintならば、
次のように書けます。
... yylval = value; /* 値をBisonスタックに積む。 */ return INT; /* トークン型を返す。 */ ...
複数のデータ型を使っている場合には、
%union宣言で作られた共用体がyylvalの型になります
（see The Collection of Value Types）。
そこで、トークンの値を代入するには、
共用体のメンバの名前を指定する必要があります。
%union宣言の例を示します。
%union {
int intval;
double val;
symrec *tptr;
}
すると、yylexの中のプログラムは次のようになります。
... yylval.intval = value; /* 値をBisonスタックに積む。 */ return INT; /* トークン型を返す。 */ ...
アクションの中で@n機能
（see Special Features for Use in Actions）を
使っている場合には、トークンとグループのテキスト中の位置を
見失わないように、yylexの中で位置情報を提供する必要があります。
関数yyparseは、ちょうど解析されたトークンのテキスト中の位置が、
広域変数yyllocに記憶されていると仮定します。
そこで、yylexは、yylocに正しいデータを記憶する必要があります。
変数yyllocは構造体で、アクションの中で使われる場合にのみ、
メンバを初期化する必要があります。
メンバは、first_line、first_column、
last_line、last_columnの4つです。
この機能を使うと、構文解析器が著しく遅くなることに注意してください。
yyllocのデータ型は、YYLTYPEという名前を持っています。
純粋な、つまり再入可能な、構文解析器を生成するために、
%pure_parserをBison宣言すると、広域変数yylvalと
yyllocを使えなくなります
（see A Pure (Reentrant) Parser）。
このような構文解析器では、2つの広域変数の代わりに、
yylexへの引数として渡されるポインタを使います。
yylexを次のように宣言し、
これらのポインタを通して情報を受け渡しする必要があります。
yylex (lvalp, llocp)
YYSTYPE *lvalp;
YYLTYPE *llocp;
{
...
*lvalp = value; /* 値をBisonスタックに積む。 */
return INT; /* トークン型を返す。 */
...
}
文法ファイルがテキスト中の位置を参照するための@機能を
使っていない場合は、YYLTYPEは定義されません。
この場合、第2引数を省略し、yylexは
1個の引数をともなって呼び出されます。
再入可能な構文解析器を使っている場合、
再入可能な方法で構文解析器に追加の引数を渡す方法があります。
そのためには、マクロYYPARSE_PARAMを変数名として定義します。
すると、関数yyparseは、定義された名前で、型がvoid *の
追加の引数を受け取ります。
yyparseを呼び出すときに、オブジェクトの番地を
void *型にキャストして渡します。
文法のアクションは、ポインタを適切な型へのポインタへキャストし、
逆参照して、オブジェクトの内容を参照できます。
例を示します。
%{
struct parser_control
{
int nastiness;
int randomness;
};
#define YYPARSE_PARAM parm
%}
次のように構文解析器を呼び出します。
struct parser_control
{
int nastiness;
int randomness;
};
...
{
struct parser_control foo;
... /* fooに正しいデータを記憶 */
value = yyparse ((void *) &foo);
...
}
文法アクションの中では、データを参照するために次のような式を使います。
((struct parser_control *) parm)->randomness
yylexに追加の引数を渡したい場合には、
YYPARSE_PARAMと同様に、マクロYYLEX_PARAMを定義します。
例を示します。
%{
struct parser_control
{
int nastiness;
int randomness;
};
#define YYPARSE_PARAM parm
#define YYLEX_PARAM parm
%}
そして、yylexが追加の引数、parmの値を受け取るように、
yylexを定義する必要があります
（型YYLTYPEのどの引数が渡されるかに応じて、
引数の合計が2個または3個になります）。
引数を正しいオブジェクト型として宣言できます。すなわちvoid *として
宣言し、上記の番地を参照できます。
YYPARSE_PARAMを使わずに、%pure_parserを使って、
再入可能な構文解析器を生成することも可能です。
その場合、引数をつけずにyyparseを呼び出すべきです。
yyerrorBison構文解析器は、文法規則に適合しないトークンを読むたびに、
構文解析エラー（parse error）すなわち文法エラー（syntax error）を
検出します。文法中のアクションは、マクロYYERRORを使って、
明示的にエラーを示せます
（see Special Features for Use in Actions）。
Bison構文解析器は、yyerrorという名前の関数を使って、
エラーを報告するようになっています。
事前に用意が必要な
この関数は、文法エラーが発生するたびに、1個の引数をともなって、
yyparseから呼び出されます。
構文解析エラーに対して、引数の文字列は通常"parse error"です。
Bison定義部（see The Bison Declarations Section）で、
マクロYYERROR_VERBOSEを定義すると、
"parse error"の代わりに、
エラーを詳細に報告する文字列が用意されます。
マクロYYERROR_VERBOSEの定義はなんでもかまいません。
構文解析器は、もう1種類のエラーであるスタックオーバーフローを検出する
可能性があります。これは、入力がきわめて深い入れ子からなっていると
起こることがあります。Bison構文解析器は自動的にスタックの限界を大きく拡張し
ているので、スタックオーバーフローはめったに起きません。
しかし、もしスタックオーバーフローが起きれば、
"parser stack overflow"という
文字列の引数をともなって、yyerrorが呼び出されます。
単純なプログラムでは、次の例のようにyyerrorを定義できます。
yyerror (s)
char *s;
{
fprintf (stderr, "%s\n", s);
}
yyerrorから戻った後、yyparseは、
適切なエラー回復文法規則（see Error Recovery）があれば、
エラーからの回復を試みます。
もし、回復が不可能ならば、yyparseは即座に1を返します。
変数yynerrsには、それまでに出くわした文法エラーの数が記憶されています。
通常、この変数は広域変数です。
しかし、再入可能な構文解析器（see A Pure (Reentrant) Parser）
を生成した場合には、アクションからのみ参照可能な局所変数になります。
ここの表では、アクション中で有用な、Bisonの構造物、変数、 マクロを示します。
$$
$n
$<typealt>$
$$に似ていますが、%union宣言で指定された共用体の中の
typealtを選びます。
See Data Types of Values in Actions。
$<typealt>n
$nに似ていますが、%union宣言で指定された共用体の中の
typealtを選びます。
See Data Types of Values in Actions。
YYABORT;
yyparseからただちに戻り、失敗を示します。
See The Parser Function yyparse。
YYACCEPT;
yyparseからただちに戻り、成功を示します。
See The Parser Function yyparse。
YYBACKUP (token, value);
先読みトークンがすでにあるような、このマクロが無効な状況で
このマクロを使うと、メッセージcannnot back upをともなう
文法エラーが報告され、通常のエラー回復が行われます。
どちらの場合も、アクションの残りの部分は実行されません。
YYEMPTY
yycharに記憶されている値です。
YYERROR;
yyerrorを呼び出さず、
メッセージは表示されません。
もし、エラーメッセージを表示したければ、YYERROR文よりも先に、
明示的にyyerrorを呼び出してください。
See Error Recovery。
YYRECOVERING
yychar
yyparseの局所変数です）。
先読みトークンがない場合には、この変数に
YYEMPTYという値が入っています。
See Look-Ahead Tokens。
yyclearin;
yyerrok;
@n
struct {
int first_line, last_line;
int first_column, last_column;
};
たとえば、第3要素の開始行番号を知るには、
@3.first_lineとします。
この構造体のメンバを有効な情報にするためには、
yylexがそれぞれのトークンに対して、
情報を提供する必要があります。
一部分のメンバだけが必要ならば、
yylexはそのメンバの値を設定するだけでかまいません。
15
この機能を使うと、字句解析器が著しく遅くなります。
Bison構文解析器は、トークンを読むと、トークンの意味値とともにスタックに積みます。 このスタックを構文解析器スタック（parser stack）と呼びます。 トークンをスタックに積むことを、伝統的に シフト（shifting）と呼びます。
たとえば、中間記法電卓が、1 + 5 *をすでに読んでいて、
3を受け取ったと仮定します。
スタックには4個の要素があり、トークンそれぞれがシフトされています。
しかし、スタックに常に読み込まれたトークンそれぞれに対する 要素があるわけではありません。 最後のn個のトークンとグループが文法規則に当てはまる場合には、 それらは規則に従って組み合わされます。 これを、還元（reduction）と呼びます。 スタックにあったトークンとグループは、 規則の結果、つまり左側にある記号である、1個のグループに置き換えられます。 規則のアクションの実行は、結果のグループの意味値を計算するので、 還元の手順の1つです。
たとえば、中間記法電卓の構文解析器スタックの内容は次のようになります。
1 + 5 * 3
そして、入力された次のトークンが改行符号ならば、 次の規則に従って、最後の3個の要素が15に還元されます。
expr: expr '*' expr;
そして、スタックは3個の要素を持ちます。
1 + 15
この時点で、別の還元が可能になり、1個の値16を得ます。 そして、改行符号がシフトされます。
構文解析器は、シフトと還元によって、入力全体を 文法の開始記号である1個のグループに還元しようとします （see Languages and Context-Free Grammars）。
この種類の構文解析器は、ボトムアップ構文解析器として知られています。
Bison構文解析器は、必ずしも文法規則に適合する最後のn個のトークン またはグループが見つかるとすぐに還元を行うわけではありません。 そのような単純な方法は、多くの言語の処理に適さないからです。 その代わりに、還元が可能な場合に、構文解析器は次のトークンを 「先読み」し、次に何をするべきかを決定します。
トークンが読まれると、それはすぐにシフトされるのではなく、 まず、先読みトークン（look-ahead token）になり、 スタックには置かれません。 先読みトークンを残したまま、構文解析器が、スタック上のトークンまたは グループに対して1個以上の還元を実行します。 それ以上の還元が起こりえない場合に、 先読みトークンはスタックにシフトされます。 これは、すべての可能な還元が実行されたことを意味しません。 先読みトークンのトークン型に応じて、 いくつかの規則は適用を遅らされているかもしれません。
先読みが必要な簡単な例を示します。
下記の3個の規則は、2項加算演算子、単項階乗演算子（!）、
グループのためのかっこを含みます。
expr: term '+' expr
| term
;
term: '(' expr ')'
| term '!'
| NUMBER
;
トークン1 + 2が読み込まれてシフトされているときに、
何が起きるでしょうか。もし、続くトークンが)ならば、
最初の3個のトークンはexprの形式に還元される必要があります。
これが、唯一有効な道です。
なぜならば、)をシフトして、term ')'という記号列も
生成可能ですが、どの規則もそのような記号列を許していないからです。
もし、続くトークンが!ならば、それはただちにシフトされる必要があり、
2 !からtermが還元されます。
そうではなく、構文解析器がシフトの前に還元していれば、
1 + 2がexprに還元されます。
しかし、そのような還元をしようとするとexpr '!'という記号列を
スタックに生成しようとするので、!をシフトするのは不可能です。
そのような記号列は許されません。
現在の先読みトークンは、変数yycharに記憶されています
See Special Features for Use in Actions。
次の2個の規則で定められる、"if-then"と"if-then-else"文を持つ 言語の構文解析について考えます。
if_stmt:
IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
;
ここで、IF、THEN、ELSEは、
キーワードトークンを表す終端記号であると仮定します。
ELSEトークンが読まれて先読みトークンになったときに、
入力が正しいと仮定して、スタックの内容はちょうど
最初の規則で還元される右辺になっています。
しかし、いずれ起こるはずの第2の規則の還元のために、
ELSEトークンをシフトすることも有効です。
この、シフトと還元の両方が有効な場合を、 シフト還元衝突（shift/reduce conflict）と呼びます。 Bisonは、演算子優先規則宣言で特に指定されていないかぎり、 シフトを選ぶことで衝突を解決するように設計されています。 この理由を理解するために、別の選択肢と比較してみましょう。
構文解析器はELSEのシフトを選ぶので、その結果、
else節はもっとも内側のif文に対応し、次の2つの入力は等価になります。
if x then if y then win (); else lose; if x then do; if y then win (); else lose; end;
しかし、字句解析器がシフトでなく還元を選ぶと、その結果、 else節がもっとも外側のif文に対応し、次の2つの入力は等価になります。
if x then if y then win (); else lose; if x then do; if y then win (); end; else lose;
文法があいまいに書かれているために、衝突が起きます。
つまり、入れ子になったif文について、どちらの構文解析結果も正当なのです。
確立された習慣では、else節をもっとも内側のif文に対応させて、
あいまいさを解決しています。
これが、Bisonが還元よりもシフトを選ぶ理由です
（理想的には、あいまいでない文法を書くべきですが、この場合には困難です）。
この問題は、Algol 60の仕様の中に現れたのが最初で、
「ぶらさがりelse（dangling else）」問題と呼ばれています。
予測可能で正当なシフト還元衝突について、Bisonが警告を表示しないように、
%expect n宣言を使えます。
すると、ちょうどn個のシフト還元衝突があるかぎり、
警告は表示されません。
See Suppressing Conflict Warnings。
上記のif_stmtの定義は、衝突をわざと発生させるために書きましたが、
追加の規則がなければ実際には衝突が起きません。
次に、実際に衝突を含む完全なBison入力ファイルの例を示します。
%token IF THEN ELSE variable
%%
stmt: expr
| if_stmt
;
if_stmt:
IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
;
expr: variable
;
シフト還元衝突が起きる別の可能性は、算術式の中にあります。 この場合には、シフトの選択が望ましい解決策であるとは限りません。 どのような場合にシフトしてどのような場合に還元するべきか指定するために、 演算子の優先順位についてのBison宣言を使えます。
次のあいまいな文法の一部を見てください。
入力1 - 2 * 3が2通りに構文解析されうるので、
この文法はあいまいです。
expr: expr '-' expr
| expr '*' expr
| expr '<' expr
| '(' expr ')'
...
;
構文解析器が、1、-、2というトークンを
読み込んだと仮定します。構文解析器は、減算演算子の規則に従って、
これらのトークンを還元するべきでしょうか。
それは、次のトークンに依存します。
もちろん、次のトークンが)ならば、還元する必要があります。
なぜならば、もしシフトすると、- 2 )またはそれで始まる
記号列を還元する必要が生じ、そのような規則はないからです。
しかし、次のトークンが*または<ならば、
シフトと還元のどちらも可能です。
どちらを選んでも構文解析を完了できますが、解析の結果は異なります。
Bison字句解析器がどちらの処理をすべきか決めるために、
構文解析の結果を考慮する必要があります。
もし、次の演算子トークンopがシフトされるならば、
還元して差を求める可能性を許すために、
opは最初に還元される必要があります。
その結果は、1 - (2 op 3)となります。
逆に、opをシフトする前に減算を還元するならば、
結果は(1 - 2) op 3となります。
明らかに、シフトと還元のどちらが起こるべきかの選択は、
演算子-とopの相対的な優先順位に依存します。
*は先にシフトされるべきですが、<は違います。
1 - 2 - 5のような例ではどうなるでしょうか。
(1 - 2) - 5と処理するべきでしょうか。
それとも、1 - (2 - 5)と処理するべきでしょうか。
ほとんどの演算子については前者が適し、これを、
左結合性（left association）と呼びます。
後者の右結合性（right association）は、代入演算子に適します。
左結合性か右結合性かの判断は、スタックに1 - 2が含まれ、
先読みトークンが-である場合の、シフトか還元かの選択です。
シフトを選ぶと、右結合的になります。
演算子優先順位宣言%leftと%rightによって、
演算子の優先順位と結合規則を指定できます。
どちらの宣言も、優先順位と結合規則を指定したい演算子である、
トークンの並びからなります。
%left宣言はすべての演算子を左結合的に、
%right宣言はすべての演算子を右結合的に宣言します。
第3の選択肢は%nonassoc宣言で、これで宣言した演算子が
続けて2回以上現れると、構文解析器が文法エラーを指摘します。
異なる演算子の相対的な優先順位は、それらが宣言される順序で決まります。
文法ファイルの中の最初の%left宣言または%right宣言で
宣言された演算子が、もっとも低い優先順位を持ちます。
後から宣言される演算子ほど、高い優先順位を持ちます。
先ほどの例では、次のように宣言するべきでした。
%left '<' %left '-' %left '*'
もっと複雑な例では、より多くの演算子を使うだけでなく、
同じ優先順位を持つ演算子があります。
次の例では、'+'演算子と'-'演算子が同じ優先順位を持ちます。
%left '<' '>' '=' NE LE GE %left '+' '-' %left '*' '/'
（この例で、NEは「等しくない」演算子を表し、他も同様です。
これらのトークンは、2文字以上からなるので、
1文字リテラルではなく名前で表されると仮定しています）
優先順位宣言の最初の働きは、宣言された終端記号への優先順位の割り当てです。 第2の働きは、規則に含まれる最後の終端記号が優先順位を示すように、 ある規則に優先順位を割り当てることです （規則に対して、明示的に優先順位を指定することも可能です。 See Context-Dependent Precedence）。
最後に、衝突の解決は、問題になっている規則の優先順位と、
先読みトークンの優先順位の比較によって行われます。
もし、先読みトークンの優先順位が高ければ、還元されます。
もし、規則の優先順位が高ければ、シフトされます。
もし、優先順位が同じならば、その優先順位での結合規則によって決定されます。
-vオプションを付けてBisonを実行し、冗長な出力ファイルを得ると、
どのように衝突が解決されているかがわかります
（see Invoking Bison）。
すべての規則とトークンが優先順位を持っているとはかぎりません。 もし、規則と先読みトークンが優先順位を持っていなければ、 シフトが行われます。
しばしば、演算子の優先順位は文脈に依存します。
これは、最初は奇異に感じるかもしれませんが、
実際によく起きていることなのです。
たとえば、通常、減算演算子（-）は、
単項演算子としては非常に高い優先順位を持ちますが、
2項演算子としては乗除算よりも低い優先順位を持ちます。
Bisonの優先順位宣言、%left、%right、%nonassocは、
あるトークンに対して1回のみ使え、この方法では、
トークンは唯一の優先順位を宣言されます。
文脈に依存する優先順位のためには、別の方法、すなわち、
%precで規則を修飾する方法が必要になります。
%prec修飾子は、ある規則で使われるべき終端記号の優先順位を指定して、
その規則の優先順位を宣言します。
その記号がその規則の中以外に現れる必要はありません。
修飾子の記法は、次のようになっています。
%prec terminal-symbol
これは、規則の構成要素の後に書かれます。 これによって、通常の方法で導かれる優先順位に代わって、 terminal-symbolの優先順位を規則に割り当てます。 規則の優先順位が変更されて、その規則が関係している衝突の解決に影響します （see Operator Precedence）。
%precがどのように単項負記号を解決するかを示します。
まず、UMINUSという名前の終端記号に対する優先順位を宣言します。
この型のトークンは存在しませんが、
この記号が優先順位を表現するために使われます。
... %left '+' '-' %left '*' %left UMINUS
さて、UNIMISの優先順位を、規則の中で使えます。
exp: ...
| exp '-' exp
...
| '-' exp %prec UMINUS
関数yyparseは、有限状態機械を使って実装されています。
構文解析器のスタックに積まれる値は、トークン型番号だけでなく、
スタックの先頭またはその近くにある終端記号と非終端記号の列を
表現しています。現在の状態は、次にすべきことに関連する、
今までの入力の情報全体の集まりです。
先読みトークンが読まれるたびに、先読みトークンの型と 現在の構文解析器の状態によって、表が引かれます。 この表の項目には、「先読みトークンをシフトしなさい」というような ことが書かれています。この場合、その表の項目は、 先読みトークンが構文解析器スタックのトップに置かれた、 構文解析器の新しい状態をも示しています。 「n番目の規則を使って還元しなさい」というような項目もあります。 これによって、決められた数のトークンまたはグループがスタックのトップから 取り除かれ、1個のグループがスタックのトップに置かれます。 言い換えると、その数の状態がスタックからポップされ、 新しい1個の状態がスタックにプッシュされます。
これには、1つの例外があります。 先読みトークンが現在の状態に対してエラーであるという項目もあります。 この場合には、エラー処理が起こります （see Error Recovery）。
同一の入力列に対して2個以上の規則が適用可能であると、 還元/還元衝突が起きます。 これは、通常、文法の重大なエラーを意味します。
0個以上のwordの並びをグループ化する、
誤った試みの例を示します。
sequence: /* 空 */
{ printf ("empty sequence\n"); }
| maybeword
| sequence word
{ printf ("added word %s\n", $2); }
;
maybeword: /* 空 */
{ printf ("empty maybeword\n"); }
| word
{ printf ("single word %s\n", $1); }
;
エラーは、あいまいさにあります。
つまり、1個のwordをsequenceに構文解析する、
2個以上の方法があります。
wordは、maybewordに還元され、
第2の規則によってsequenceになりえます。
また、最初の規則で、空データがsequenceに還元され、
それが第3の規則によってwordと組み合わされて
sequenceになりえます。
さらに、空データがsequenceに還元される方法が2つ以上あります。
第1の規則で直接還元される方法と、
maybewordを経由して第2の規則で還元される方法です。
この違いは、特定の入力が正当であるかどうかに関係ないので、 ささいなことに思えるかもしれません。 しかし、これは、どのアクションが実行されるかに影響します。 ある構文解析手順では第2の規則のアクションが実行され、 別の構文解析手順では第1の規則のアクションと第3の規則のアクションが 実行されます。 この例では、プログラムの出力が異なります。
Bisonは、最初に現れた文法を選ぶことで、還元/還元衝突を解決しますが、
これに頼ることは非常に危険です。
還元/還元衝突のそれぞれは、人間によって解析され、
通常は取り除かれるべきです。
sequenceを定義する正しい方法を示します。
sequence: /* 空 */
{ printf ("empty sequence\n"); }
| sequence word
{ printf ("added word %s\n", $2); }
;
還元/還元衝突を起こす、別のありがちなエラーの例を示します。
sequence: /* 空 */
| sequence words
| sequence redirects
;
words: /* 空 */
| words word
;
redirects:/* 空 */
| redirects redirect
;
ここは、wordまたはredirectグループのどちらかを含む
列の定義が目的です。
sequence、words、redirectsそれぞれ個別の
定義にエラーはありません。しかし、3個を合わせると、あいまいになります。
空の入力には、無限個の構文解析方法があります。
空データがwordsになったと仮定しましょう。
それは、2個のwordsにも、3個のwordsにも、
何個のwordsにもなりえます。
あるいは、1個のwordsに3個のredirectsともう1個のwordが
続くことも考えられます。同様に、無限の解釈が可能です。
これらの規則を直す方法が2つあります。 第1に、1段階の列にする方法です。
sequence: /* 空 */
| sequence word
| sequence redirect
;
第2に、wordsとredirectsが空になるのを防ぐ方法です。
sequence: /* 空 */
| sequence words
| sequence redirects
;
words: word
| words word
;
redirects:redirect
| redirects redirect
;
そうなるはずがないように見えるのに、ときどき 還元/還元衝突が起きることがあります。 例を示します。
%token ID
%%
def: param_spec return_spec ','
;
param_spec:
type
| name_list ':' type
;
return_spec:
type
| name ':' type
;
type: ID
;
name: ID
;
name_list:
name
| name ',' name_list
;
この文法は、1個のトークンの先読みによって、構文解析できるように見えます。
たとえば、pram_specが読まれた後で、
IDはカンマかセミコロンが続くならばname、
そうでなければtypeとなります。
言い換えれば、この文法はLR(1)です。
しかし、Bisonは、多くの構文解析器生成器と同様に、
すべてのLR(1)文法を扱えるわけではありません。
前述の例では、IDの後で、そこがparam_specの先頭であるという
文脈と、そこがreturn_specの先頭であるという文脈は、
Bisonが同一であるとみなしてしまうほど似ています。
これらの文脈が似てしまう原因は、同じ規則の集合が有効になる、つまり、
nameへ還元するための規則と、typeへ還元するための規則の
両方が有効なことです。
Bisonは、その規則が2つの文脈で異なる先読みトークンを要求するような、
処理の段階を決定できず、両者から1つの構文解析器状態ができてしまいます。
2個の文脈の組み合わせは、後で衝突を起こします。
構文解析器の用語でいえば、この問題の発生は、
文法がLALR(1)でないことを意味します。
一般に、このような欠点は解決して、文書化するべきです。 しかし、この問題は本質的に解決困難です。 LR(1)文法を扱える構文解析器生成器は、作成困難で、 生成される構文解析器が巨大になってしまいます。 実用上、Bisonは今のままでも有用です。
このような問題が現れた場合に、混乱の元になっている2種類の構文解析器の
状態を区別し、それらが違うという目印か何かを追加することによって、
しばしば問題を解決できます。
前述の例では、次のようにreturn_specに規則を追加して、
問題を解決できます。
%token BOGUS
...
%%
...
return_spec:
type
| name ':' type
/* この規則は決して使われない。 */
| ID BOGUS
;
IDの次でreturn_specの先頭である文脈で、
追加の規則が有効になる可能性を導入して、問題を解決しています。
この規則は、param_specに関連する文脈では有効にならないので、
2個の文脈は、異なる構文解析器状態を持ちます。
BOGUSはyylexによっては決して生成されないので、
追加された規則は入力が実際に構文解析される方法には影響しません。
この具体例では、問題を解決する別の方法があります。
つまり、return_specの規則を、name経由ではなく
IDを直接使うように書き換えるのです。
return_specに対する規則は、nameに対する規則ではなく、
return_specに対する規則を有効にするので、
2つの混乱していた文脈は異なる有効な規則の集まりを持ちます。
param_spec:
type
| name_list ':' type
;
return_spec:
type
| ID ':' type
;
Bison構文解析器のスタックは、あまりにも多くのトークンがシフトされて
還元されないでいると、オーバーフローする可能性があります。
スタックがオーバーフローすると、オーバーフローを報告するためにyyerror
を呼び出して、関数yyparseは0でない値を返します。
マクロYYMAXDEPTHを定義して、スタックオーバーフローが起こらないように、
構文解析器のスタックの深さを調節できます。
マクロの値として、整数値を定義してください。
この値は、オーバーフローする前に、シフトされたが還元されていないトークンの
最大数になります。
マクロの値として、コンパイル時に決定可能な定数式を指定してください。
指定されたスタック領域は、割り当てられる必要はありません。
大きなYYMAXDEPTHを指定すると、
構文解析器はまず小さなスタック領域を割り当て、
必要に応じてより大きなスタック領域を割り当てます。
この割り当ての増加は、何も表示せずに、自動的に行われます。
したがって、スタックをあまり必要としない通常の入力に対して
メモリを節約するために、YYMAXDEPTHを小さくする必要はありません。
特に指定しないと、YYMAXDEPTHの値は10000になります。
マクロYYINIDEPTHを指定して、最初に割り当てられるスタックの量を
調節できます。この値は、コンパイル時に決定可能な整定数の必要があります。
特に指定しないと、200になります。
構文解析エラーが起きた場合に、構文解析プログラムが止まることは、 通常望ましくありません。 たとえば、コンパイラは入力の残りを構文解析して他のエラーを探せるように エラーから回復するべきですし、電卓は次の式を受け入れるべきです。
入力を1行ごとに処理する単純な対話的構文解析器は、
エラーが発生した場合にyyparseが1を返し、
入力行の残りを無視し、
yyparseをもう一度呼び出してもかまいません。
しかし、コンパイラでこのように処理すると、
エラーに先立つ文法的文脈を忘れてしまうので不都合です。
深い関数呼び出しの中で構文エラーが発生した場合に、
コンパイラがエラーに続く行をソースファイルの先頭のように
扱うべきではありません。
特別なトークンerrorを認識するような規則を書くことによって、
構文エラーから回復する方法を定義できます。
errorは定義済みの終端記号で、自分で宣言する必要はなく、
エラー処理のために予約されています。
Bison構文解析器は、構文エラーが起こるたびに、errorトークンを生成します。
現在の文脈でerrorトークンを認識できる規則を書いていれば、
構文解析を継続できます。
例を示します。
stmnts: /* 空文字列 */
| stmnts '\n'
| stmnts exp '\n'
| stmnts error '\n'
第4の規則は、errorとそれに続く改行が、任意のstmntsに
続くことを認めます。
expの中で構文エラーが発生するとどうなるでしょうか。
エラー回復規則は、厳密に解釈され、stmnts、error、改行からなる
列に適用されます。
expの中で構文エラーが起きると、おそらく、いくつかの余分なトークンまたは
部分式がスタック上の最後のstmntsの後に存在し、
したがって、次の改行を読む前に読むべきトークンが存在するでしょう。
したがって、この通常の方法では規則を適用できません。
しかし、意味文脈と入力の一部を捨てることによって、
Bisonは強制的にこの場合に規則を適用できます。
まず、errorトークンが受理可能な状態に戻るまで、
状態とオブジェクトがスタックから捨てられます
（これは、すでに構文解析された部分式が捨てられ、
最後の完全なstmntsに状態が戻ることを意味します）。
この時点で、errorトークンがシフトされます。
そして、古い先読みトークンのシフトは受理不可能なので、
受理可能なトークンを見つけるまで、
構文解析器はトークンを読んで捨てます。
前述の例では、次の改行がくるまで入力が読み捨てられ、
したがって、第4の規則が適用可能になります。
文法中のエラー規則の選択は、エラー回復の戦略の選択です。 単純で便利な戦略の1つは、エラーを検出したら、 単純に現在の入力行または文を読み飛ばすことです。
stmnt: error ';' /* エラーがあれば、「;」がくるまで読み飛ばす。 */
すでに構文解析された開き区切りトークン【訳注】C言語での([{、
Pascal言語でのbeginなど。を、閉じ区切りトークンに対応させることは、
エラー処理のうまい方法です。そうしなければ、閉じ区切りトークンが
後で不適切に現れて、別の重大なエラーを引き起こすでしょう。
primary: '(' expr ')'
| '(' error ')'
...
;
エラー回復の戦略は熟慮されるべきです。
戦略が悪いと、1つの構文エラーがしばしば別のエラーを引き起こします。
前述の例では、エラー回復規則は、1個のstmntの中で起きると
仮定されています。
そうでない可能性として、有効なstmntの中に誤ってセミコロンが
まぎれ込んでいることを考えてみましょう。
エラー回復規則が最初のエラーを回復した後で、まぎれ込んだセミコロンに続く
入力も無効なstmntなので、もう1つの構文エラーがただちにみつかります。
エラー報告の洪水を避けるために、 最初の構文エラーが起きた直後の他の構文エラーに対しては、 構文解析器はエラー報告を表示しないべきでしょう。 3個の連続する入力トークンのシフトに成功してから、 エラー報告を再開するべきです。
errorトークンを受け付ける規則も、他の規則と同様に
アクションを持てることに注意してください。
アクションの中でマクロyyerrokを使って、
ただちにエラー報告を再開できます。
もし、エラー規則のアクションの中でこのマクロを使えば、
エラー報告は抑制されません。
このマクロに引数は不要で、yyerrok;は有効なCの文です。
直前の先読みトークンは、エラーの直後に再解析されます。
これが不都合ならば、マクロyyclearinによって先読みトークンを
消してください。すなわち、エラー規則のアクションに
yyclearin;文を書いてください。
たとえば、構文エラーにおいて、構文解析を再開すべき場所まで入力を進めるような、
エラー処理手続きを考えてみましょう。
字句解析器から返される次の記号は、おそらく正しいでしょう。
以前の先読みトークンはyyclearin;によって捨てられるべきです。
マクロYYRECOVERINGは、式を表し、構文解析器がエラーから回復する
途中にあるならば値が1になり、通常の状態ならば値が0になります。
値が1であるということは、新たな構文エラーに対するエラーの報告が、
現在は抑制されていることを示します。
Bisonの枠組みは、まずトークンを読み、 次にトークンをより大きな文法的単位にグループ化することです。 多くの言語では、トークンの意味は文脈の影響を受けます。 文脈依存性によってBisonの枠組みが壊れますが、 （kludgesとして知られる）いくつかの技術を使って、 このような言語に対するBison構文解析器を書けます。
（実際に、「kludge」は、仕事を可能にしますが、 美しくも頑丈でもない技術を意味します）
C言語は文脈依存性をもっています。 すなわち、識別子の使われ方は、それの現在の意味に依存します。 次の例を考えてみてください。
foo (x);
これは、関数を呼び出す文のように見えます。
しかし、もし、fooがtypedefされた型名ならば、
この文はxの宣言になります。
C言語に対するBison構文解析器は、この入力を構文解析する方法を
どのように決定できるでしょうか。
GNU Cで使っている方法は、IDENTIFIERとTYPENAMEという、
2種類の異なるトークン型を使うことです。
yylexが識別子を見つけると、どちらのトークン型を返すか決めるために、
識別子の現在の宣言を検索し、typedefとして宣言されていれば
TYPENAMEを返し、そうでなければIDENTIFIERを返します。
そして、認識するトークン型を選ぶことによって、
文法規則は文脈依存性を表現できます。
IDENTIFIERは、式として受け入れられますが、
TYPENAMEは受け入れられません。
TYPENAMEは、宣言の始まりとして受け入れられますが、
IDENTIFIERは受け入れられません。
識別子の意味の区別が必要のない文脈、
たとえばtypedef名を隠す宣言の中では、
TYPENAMEとIDENTIFIERの両方が受け入れられます。
すなわち、2個のトークン型に対してそれぞれ1個の規則を書くことが可能です。
この方法は、どの種類の識別子が許されるかの判断が、
その識別子が構文解析される場所の近くで行われるならば、
単純に使えます。
しかし、C言語で、いつもそうであるとは限りません。
次の例のように、以前に指定された明示的な型に規定されたtypedef名の
再宣言が許されているからです。
typedef int foo, bar, lose; static foo (bar); /*barを静的変数として再宣言する。 */ static int foo (lose); /*fooを関数として再宣言する。 */
不幸にも、込み入った文法構造「宣言子(declarator)」によって、 宣言された名前は、その宣言の構造自身から切り離されます。
結果として、C言語に対するBison構文解析器は、
すべての非終端記号の名前を変えて、二重化されました。
第1は、typedef名が再定義されているかもしれない宣言を構文解析し、
第2は、再定義が起こりえない宣言を構文解析します。
二重化したものの一部分を、簡単にするためにアクションを省略して、示します。
initdcl:
declarator maybeasm '='
init
| declarator maybeasm
;
notype_initdcl:
notype_declarator maybeasm '='
init
| notype_declarator maybeasm
;
ここで、initdclはtypedef名を再宣言できますが、
notype_initdclは再宣言できません。
declaratorとnotype_declaratorの違いも同様です。
前述の技術と、後述の字句解析結び付きには、 字句解析に影響する情報が入力の別の部分を構文解析しているときに 変化させられるという、共通点があります。 前者では、情報が広域的で、プログラム16の別の目的に 使われることが異なります。 本当の字句解析結び付きは、文脈によって制御される、 特別の目的のフラグを持ちます。
文脈依存性を処理する1つの方法は、字句解析結び付き（lexical tie-in）で、 Bisonのアクションによって設定されるフラグが、 トークンが構文解析される方法に影響します。
たとえば、C言語によく似ていて、hex (hex-expr)という
特別な構造を持つ言語について、考えてみましょう。
予約語hexがきた後にかっこで囲まれた式が続いて、
そのかっこの中ではすべての整数が16進数になります。
特に、トークンa1bは、このような文脈に現れれば、
識別子ではなく整数として扱われる必要があります。
どのようにすればよいかを示します。
%{
int hexflag;
%}
%%
...
expr: IDENTIFIER
| constant
| HEX '('
{ hexflag = 1; }
expr ')'
{ hexflag = 0;
$$ = $4; }
| expr '+' expr
{ $$ = make_sum ($1, $3); }
...
;
constant:
INTEGER
| STRING
;
yylexは、hexflagの値が0でなければ、
すべての整数が16進数であると字句解析し、
英字で始まるトークンも可能な限り整数と解釈すると、仮定します。
hexflagの宣言は、アクションから参照可能なように、
文法ファイルのC宣言部に書かれる必要があります
（see The C Declarations Section）。
同様に、yylexのプログラムにも、hexflagの宣言が必要です。
字句解析結び付きは、厳密なエラー回復規則を要求します。 See Error Recovery。
その理由は、エラー回復規則の目的が、ある構成物の構文解析を中断し、 より大きな構成物の構文解析を再開することです。 前述のC言語に似ている言語の例では、次のように、 標準的なエラー回復規則は、次のセミコロンまでトークンを読み捨て、 新しい文の構文解析を再開します。
stmt: expr ';'
| IF '(' expr ')' stmt { ... }
...
error ';'
{ hexflag = 0; }
;
もし、hex (expr)の途中で構文エラーが発生すれば、
このエラー回復規則が適用され、完了したhex expr)に対する
アクションは決して実行されません。
すると、hexflagは、入力の残りの間ずっと設定されたままでいるか、
次のhex予約語の出現までそのままの状態でいて、
識別子が16進整数と誤解されます。
この問題を防ぐためには、エラー回復規則が
hexflagを元に戻すべきです。
さらに、式の内部で働くエラー回復規則があるかもしれません。 たとえば、次の例のように、かっこの中でエラーが発生すると、 閉じかっこまで読み捨てるようなエラー回復規則が考えられます。
expr: ...
| '(' expr ')'
{ $$ = $2; }
| '(' error ')'
...
もし、この規則がhex構造の中で働くならば、
その構造の中の内側のかっこに適用されるので、
構造を中断するべきではありません。
したがって、このアクションではフラグを戻すべきではなく、
hex構造の残りはフラグを有効にしたまま構文解析されるべきです。
状況に応じて、hex構造を中断できるかもしれないし、そうでないかもしれない
エラー回復規則があれば、どうなるでしょうか。
hex構造を中断すべきかどうか決定できるアクションを書けません。
そこで、もし、字句解析結び付きを使っているならば、
あなたが書いたエラー回復規則がそのようになっていないことを確かめるべきです。
それぞれの規則は、常にフラグを戻すべきか、あるいは常にフラグを戻さないべきか、
決定できるべきです。
もし、Bison文法ファイルが正しくコンパイルされたのに、
生成された構文解析器が思いどおりに動かない場合には、
yydebug構文解析器追跡機能が、調査の役に立つでしょう。
追跡機能のコンパイルを有効にするためには、
構文解析器をコンパイルするときに、マクロYYDEBUGを定義する必要があります。
そのためには、コンパイラのオプションに-DYYDEBUG=1を指定するか、
あるいは、文法ファイルのC宣言部に#define YYDEBUG 1と書いておく
必要があります（see The C Declarations Section）。
あるいは、Bisonを実行するときに(see Invoking Bison)、
-tオプションを指定しておくと、
YYDEBUGが定義され、追跡が可能になります。
追跡機能はstderrを使うので、C宣言部に
#include <stdio.h>と書いておく必要があります。
追跡機能付で構文解析器をコンパイルしたら、構文解析器の実行時に、
追跡機能を有効にするために、yydebug変数を0でない値にしてください。
C言語のプログラム(おそらくmain関数の中)でこの変数に代入するか、
あるいは、デバッガでこの変数の値を変えればいいでしょう。
yydebugが0でない場合、構文解析器はそれぞれの段階で、
1行まはた2行の追跡情報を生成し、stderrに出力します。
追跡情報には、次のような情報が含まれています。
yylexを呼ぶたびに、
読み込まれたトークンの種類が記録されます。
この情報を理解するためには、Bisonに-vオプション
（see Invoking Bison）を付けて実行すると生成される
明細ファイルが参考になるでしょう。
このファイルには、さまざまな規則の中での位置による表現で
各状態の意味が示され、また、
各状態がそれぞれの可能な入力トークンによって
どのように動作するかが示されています。
連続する追跡の意味を読むことによって、
明細ファイルで仕様が示されている構文解析器の機能について、理解できるでしょう。
何か望ましくないことが起きている部分を確認すれば、
文法ファイルのどこに問題があるかわかるでしょう。
構文解析器ファイルはC言語のプログラムなので、 Cのデバッガを使えますが、 何が起きているか調べることは困難です。 構文解析器関数は、有限状態機械インタープリタで、 アクションが実行されると、 プログラムの同じ部分が何度も何度も実行されます。 実用的なのは文法の中で変数の値を調べることだけでしょう。
デバッグ情報には、通常、それぞれのトークンのトークン型だけが含まれ、
トークンの意味値は含まれません。
マクロYYPRINTを定義することで、
トークンの意味値を表示させられます。
YYPRINTの定義には、3個の引数がともないます。
構文解析器は、YYPRINTに、標準入出力ストリーム、
トークン型の数値番号、トークンの値（yylvalによる）を渡します。
多機能電卓に適するYYPRINTの例を示します
（see Declarations for mfcalc）。
#define YYPRINT(file, type, value) yyprint (file, type, value)
static void
yyprint (file, type, value)
FILE *file;
int type;
YYSTYPE value;
{
if (type == VAR)
fprintf (file, " %s", value.tptr->name);
else if (type == NUM)
fprintf (file, " %d", value.val);
}
通常、Bisonは次のように実行します。
bison infile
ここで、infileは文法ファイルで、名前が通常.yで終わります。
生成される構文解析器ファイルは、文法ファイルの名前の.yを
.tab.cに変えたものです。
したがって、bison foo.yによってbison.tab.cを得られますし、
bison hack/foo.yによってhack/foo.tab.cを得られます。
Bisonは、伝統的な1文字のオプションと、記憶しやすい長いオプション名の
両方を受け付けます。長いオプション名は、-の代わりに、
--で指定します。
一意性を失わない範囲で、長いオプション名を省略できます。
長いオプションが引数をともなう場合、たとえば、--file-prefixでは、
オプション名と引数の間に=を入れます。
Bisonに対して指定可能なオプションの一覧を、アルファベット順に示します。 さらに、長い名前のアルファベット順の対応を示します。
-b file-prefix
--file-prefix=prefix
prefix.yであった場合と、
同じ結果を得られます。
-d
--defines
YYSTYPE、いくつかのextern変数宣言を含む、
追加の出力ファイルを生成します。
生成される構文解析ファイルの名前がname.cならば、
このファイルの名前はname.hになります。
yylex関数を独立なソースファイルの中で定義しているならば、
それはトークン型番号と変数yylvalを必要とするので、
このファイルを#includeする必要があります
See Semantic Values of Tokens。
-l
--no-lines
#lineプリプロセッサディレクティブを生成しません。
通常、Bisonはこれを生成し、Cコンパイラとデバッガが、
文法ファイルのどこでエラーが発生したかを見つけるために使います。
このオプションは、エラーと構文解析器の行番号を結び付け、
構文解析器を独立なソースファイルとして扱います。
-n
--no-parser
#defineディレクティブと
静的変数の宣言のみからなります。
このオプションにより、filename.actという名前のファイルに、
文法アクションに対するC言語のプログラムが書かれます。
その書式は、switch文に対応するブレースで囲まれたブロックです。
-o outfile
--output-file=outfile
他の出力ファイルのファイル名の指定は
-vと-dオプションの項を参照してください。
-p prefix
--name-prefix=prefix
yyでなくprefixで始まるように変えます。
影響を受ける名前は、
yyparse、yylex、yyerror、yynerrs、
yylval、yychar、yydebugです。
たとえば、-p cオプションを指定すれば、
名前はcparse、clexなどになります。
-r
--raw
%rawが指定されたように振る舞います。
See Decl Summary。
-t
--debug
YYDEBUGの定義を構文解析器ファイルに入れます
See Debugging Your Parser。
-v
--verbose
このファイルは、演算子の優先順位によって解決したものも解決しなかった ものも含めて、衝突についての説明を含んでいます。
生成されるファイルの名前は、構文解析器のファイルの名前から、
.tab.cまたは.cを取り除いて、
代わりに.outputを付けたものです。
したがって、入力の文法ファイルの名前がfoo.yならば、
特に指定しないと、構文解析器ファイルの名前はfoo.tab.cになり、
詳細な説明のファイルの名前はfoo.outputになります。
-V
--version
-h
--help
-y
--yacc
--fixed-output-files
-o y.tab.cと等価です。構文解析器ファイルの名前は
y.tab.cになり、他の出力ファイルの名前はy.outputと
y.tab.hになります。このオプションの目的は、
出力ファイルの名前をYaccに合わせることです。
次のシェルスクリプトは、Yaccの代用になります。
bison -y $*
オプションを、長い名前のアルファベット順に一覧表記して、 対応する1文字オプションを書きます。
VMS上のBisonのコマンドライン構文は、VMSの慣習に合わせて、 他のシステム上のBisonのコマンドライン構文と異なっています。
VMSでは、すべてのBisonのオプションについて、
--の代わりに/に続く長い名前のオプションを書き、
オプション名中の-を_に変えます。
VMS上での実行例を示します。
bison /debug/name_prefix=bar foo.y
これは、POSIX上での次のコマンドラインと等価です。
bison --debug --name-prefix=bar foo.y
VMSファイルシステムでは、foo.tab.cのようなファイル名が許されないので、
構文解析器の名前は、上記の例の場合には、foo_tab.cになります。
error
errorトークンが現在の先読みトークンになります。
errorに対応するアクションが実行されて、
先読みトークンがエラーの原因になったトークンに戻されます。
See Error Recovery。
YYABORT
yyparseが1を返します。
エラー報告関数yyerrorは呼び出されません。
See The Parser Function yyparse。
YYACCEPT
yyparseが0を返します。
See The Parser Function yyparse。
YYBACKUP
YYERROR
yyerrorを呼び、可能ならば通常のエラー回復処理
（see Error Recovery）を実行し、不可能ならば
yyparseが1を返します。
See Error Recovery。
YYERROR_VERBOSE
#defineによってこのマクロを定義すると、
yyerrorが呼ばれたときに表示されるエラー報告が詳しくなります。
YYINITDEPTH
YYLEX_PARAM
yyparseがyylexに渡すための、追加の引数または
引数の並びを指定するためのマクロです。
See Calling Conventions for Pure Parsers。
YYLTYPE
yylocのデータ型を示すマクロで、4個のメンバからなる構造体です。
See Textual Positions of Tokens。
yyltype
YYLTYPEの省略時の値です。
YYMAXDEPTH
YYPARSE_PARAM
yyparseが受け取るべき引数の名前を指定するマクロです。
See Calling Conventions for Pure Parsers。
YYRECOVERING
YYSTYPE
intになります。
See Data Types of Semantic Values。
yychar
int型の変数で、現在の先読みトークンの番号を記憶しています
（再入可能な構文解析器では、この変数はyyparseに局所的です）。
エラー回復規則のアクションは、この変数の値を調べられます。
See Special Features for Use in Actions。
yyclearin
yydebug
int型の広域変数で、初期値は0です。
yydebugの値が0でないと、構文解析器は、
読み込んだ記号と構文解析器のアクションに関する情報を表示します。
See Debugging Your Parser。
yyerrok
yyerror
yyparseから呼び出される、ユーザー定義関数です。
この関数は1個の引数を受け取り、その引数はエラーの報告を含む文字列への
ポインタです。
See The Error Reporting Function yyerror。
yylex
yylex。
yylval
yylexが置くための広域変数です
（再入可能な構文解析器では、これはyyparseの局所変数で、
その番地がyylexに渡されます）。
See Semantic Values of Tokens。
yylloc
yylexが置くための
広域変数です（再入可能な構文解析器では、この変数はyyparseに
局所的で、その番地がyylexに渡されます）。
文法アクションで@機能を使わないならば、
この値を無視してかまいません。
See Textual Positions of Tokens。
yynerrs
yyparseに局所的です）。
See The Error Reporting Function yyerror。
yyparse
yyparse。
%left
%no_lines
#lineディレクティブを生成しないための
Bison宣言です。
See Decl Summary。
%nonassoc
%prec
%pure_parser
%raw
%right
%start
%token
%token_table
%type
%union
Bison文法ファイルの中で使う、区切り記号があります。
%%
%{ %}
%{と%}の間に書かれたすべてのプログラムは、
そのまま構文解析器ファイルに複写されます。
このようなプログラムが、文法ファイルのC宣言部を構成します。
See Outline of a Bison Grammar。
/*...*/
:
;
|
if文です。
See Languages and Context-Free Grammars。
a+b+cでは、まずa+bが計算され、
次にcとの和が計算されます。
See Operator Precedence。
expseq1 : expseq1 ',' exp;が左再帰です。
See Recursive Rules。
yylex。
expseq1: exp ',' expseq1;は右再帰です。
See Recursive Rules.
【訳注】2文字以上の文字列、たとえば==を、
トークン名に使う機能。
【注意】
現在、このバージョン2の発行者(FSF)住所は、正式に新しい住所の
59 Temple Place, Suite 330, Boston, MA 02111-1307, USA
に変わっている。
【注意】現在、このバージョン2の発行者(FSF)住所は、 正式に新しい住所の 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA に変わっている。
【訳注】他のファイルに書くのではなく
【訳注】UNIXの標準的なコンソールの 設定で、入力の終わりを示す制御文字で、MS-DOSでは代わりにCtrl-z。
【訳注】古いK&R-C処理系を使う場合には前述の例のままでよいのですが、
ANSI-C処理系を使う場合には、main関数が返す値が
int型なので、次のように書くべきです。
他の関数についても同様です。本書の例のすべては古い書式で書かれています。
int main ()
{
return yyparse ();
}
【訳注】UNIX上でccコマンドを使ってコンパイルする方法を示します。
【訳注】例のalpha = beta1 = 2.3
【訳注】例のexp(ln(beta1))
【訳注】英数字以外の文字。
【訳注】\に続く表現。
【訳注】任意の数の空白文字、タブ符号、改行符号。
【訳注】ある手続きの終了を待たずに、その手続きを再度呼び出せる ことでもあります。
【訳注】他のソースファイルから見えないとう意味ではなく、 メモリ上の固定番地に置かれるという意味。
【訳注】yylexは、変数yyllocに、
トークンの位置情報を代入します。
【訳注】構文解析器。
【訳注】ある関数が終了する前に、 その同じ関数を非同期に呼び出してもよいということ。
【訳注】字句解析器によって