TP Lex and Yacc - The Compiler Writer's Tools for Turbo Pascal == === === ==== = === ======== ======== ===== === ===== ====== Version 3.0 User Manual ======= === ==== ====== Albert Graef Schillerstr. 18 6509 Schornsheim ag@informatik.mathematik.uni-mainz.de June 17, 1991 Translated by Osamu TAKEUCHI http://www2.big.or.jp/~osamu/ osamu@big.or.jp Jan 28, 2001 はじめに ============ このドキュメントは、TP Lex and Yacc compiler generator toolset について説明したものです。このツールは、コンパイラーやそれに類似したテキスト処理ユーティリティ、コマンドインタプリータを Turbo Pascal (TM) を使って作るためのものです。 TP Lex and Yacc は、よく知られている UNIX (TM) 上の Lex , Yacc というプログラムを Turbo Pascal に翻訳したもので、それらはもともとベル研究所の M.E. Lesk と S.C. Johnson によって作られ、C 言語とともに使われてきました。 TP Lex and Yacc は、これらのプログラムとほぼ同等の動作をするよう設計されています。ただし、これらは「ドラゴンブック」として有名な、Aho、 Sethi および Ullman の「Compilers : principles, techniques and tools」（Reading (Mass.), Addison-Wesley, 1986) にもとづいて独立に開発された物です。 この種のほかのツールと同様に、TP Lex and Yacc は、初心者・遊び半分のプログラマー向けに作られたものではありません。正しく使うには、熟練したプログラミングの経験とともに、パーサの設計・実装の基礎をしっかり理解していることが必要となります。しかし、もしあなたが Turbo Pascal に慣れ親しんでおり、なおかつコンパイラー設計と形式言語に関する基礎を身につけていれば、TP Lex and Yacc はあなたの Turbo Pascal を強力に拡張することになるでしょう。 このマニュアルは、TP Lex and Yacc の入門書であり、これらについて簡単な解説を提供します。Ｃバージョンの Lex, Yacc の知識があれば役に立つでしょうが、必ずしも必要ではありません。この先を読み進むにあたって、以下を参照すると良いでしょう。 - Aho, Sethi and Ullman: "Compilers : principles, techniques and tools." Reading (Mass.), Addison-Wesley, 1986. - Johnson, S.C.: "Yacc - yet another compiler-compiler." CSTR-32, Bell Telephone Laboratories, 1974. - Lesk, M.E.: "Lex - a lexical analyser generator." CSTR-39, Bell Telephone Laboratories, 1975. - Schreiner, Friedman: "Introduction to compiler construction with UNIX." Prentice-Hall, 1985. - The Unix Programmer's Manual, Sections `Lex' and `Yacc'. では始めましょう --------------- The TP Lex and Yacc は IBM PC 互換機上の MS-DOS 3.0 以降と、Turbo Pascal コンパイラ (Version 4.0 以上) がある環境で動作します。512KB の RAM とハードディスクを備えていることを推奨します。 TP Lex and Yacc をあなたのシステムにインストールするには、単にインストールディスク上のファイルをあなたのハードディスクの適当なディレクトリにコピーして下さい。そうしたら、そのディレクトリを DOS の PATH に登録し、Turbo Pascal のユニットパスに指定してください。（こうすることで、Turbo Pascal コンパイラが TP Lex and Yacc のライブラリユニットを参照できるようになります) インストールディスク上のライブラリユニット (*.TPU) は、Turbo Pascal 6.0 でコンパイルされています。もしあなたが異なるバージョンの Turbo Pascal を持っているなら、これらのユニットをコンパイルしなおす必要があるでしょう。(ソースファイルは、LEXLIB.PAS および YACCLIB.PAS です) TP Lex and Yacc をインストールしたら、あなたの最初の TP Lex and Yacc プログラムとなる EXPR をコンパイルできるはずです。EXPR はシンプルなデスクトップ計算機で、TP Lex のソースコード EXPRLEX.L によって定義される語彙解析部と、TP Yacc のソースコード EXPR.Y によって定義されるパーサおよびメインプログラムによって構成されています。これらのプログラムをコンパイルするには、つぎのコマンドを入力します。 lex exprlex yacc expr これだけです！これだけで EXPR プログラムの、Turbo Pascal 用のソースファイル(EXPRLEX.PAS and EXPR.PAS) ができてしまいます。Turbo Pascal でこれらのファイルをコンパイルしましょう。 tpc expr さあ、これで EXPR プログラムを実行することができます。いくつか計算式を入力して、プログラムがちゃんと動いていることを確認してみてください。(プログラムは空の行を入力することで終了することができます) インストールディスクには、他にもたくさんの TP Lex and Yacc プログラムのサンプル (.L and .Y files) が含まれています。それらには、TP Yacc クロスリファレンスユーティリティや、標準パスカルの完全なパーサも含まれています。 TP Lex and Yacc ではコマンドラインの任意の場所にオプションを指定することができます。例： lex /o exprlex これは TP Lex の DFA 最適化を有効にします。 yacc /v expr これは TP Yacc を "verbose" モードで起動します。(TP Yacc は作成されるパーサに関する判読可能な記述を、*.LST と言うファイルに書き出します。) TP Lex and Yacc では次にあげるファイル名の拡張子をデフォルトで使います。 - .L: TP Lex 入力ファイル - .Y: TP Yacc 入力ファイル - .PAS: TP Lex and Yacc 出力ファイル 良くあるように、ファイル拡張子を明示的に記述することで、これらのデフォルト拡張子を無視して使うことができます。 もし TP Lex and Yacc の使い方を忘れたときには、引数を何も与えずに lex または、 yacc として起動してください。コマンドラインの使い方の簡単な説明が表示されます。 TP Lex ====== この章では TP Lex 語彙解析部作成プログラムについて説明します。 使い方 ----- LEX [options] lex-file[.L] [output-file[.PAS]] オプション ------- /v "Verbose:" Lex は作成される語彙解析ルーチンに関する判読可能な記述を作成します。 このファイルは lex-file の拡張子を .LST に変えたものになります。 /o "Optimize:" Lex は DFA テーブルが最小となるように最適化します。 説明 ----------- TP Lex はプログラムを自動生成するプログラムで、正規表現文法によって定義された入力言語を語彙解析するための Turbo Pascal ソースファイルを作るのに使われます。 TP Lex は lex-file (デフォルト拡張子は .L) に含まれる文法を読み、語彙解析用のサブルーチンを構築して指定された出力ファイル (デフォルト拡張子は .PAS) に書き出します。アウトプットファイルが指定されないときには、lex-file の拡張子を .PAS に変更したファイル名を使用します。もし作業中に何らかのエラーが発生した場合には、list file (拡張子 .LST) にエラーメッセージが出力されます。 生成された出力ファイルには、yylex という語彙解析ルーチンが含まれます。この関数は、以下の形式を持ちます。 function yylex : Integer; このルーチンが、語彙解析のためにあなたのメインプログラムから呼び出されることになります。yylex 関数の返り値は、通常語彙解析部によって認識されたトークンを識別します。(LexLib ユニットの return routine を参照) 通常、yylex ルーチンはファイルの終端に達すると 0 を返します。 yylex ルーチンを作成するためのコードテンプレートを YYLEX.COD ファイルに見つけることができます。このファイルは TP Lex が出力ファイルを作成するときに使用します。このファイルはカレントディレクトリか、TP Lex が実行されるディレクトリのどちらかに存在していなければなりません。( TP Lex はこれらのディレクトリをこの順番で検索します。) TP Lex ライブラリ (LexLib) ユニットは、プログラムから Lex によって生成された語彙解析ルーチンを使う際に必要となります。従って、語彙解析ルーチンを呼び出すプログラム、またはユニットに適切な uses 節を記述しなければならないでしょう。LexLib ユニットは、様々な便利なユーティリティルーチンも含んでいます。詳しくは、LEXLIB.PAS ファイルを参照してください。 Lex ソースファイル ------------------ TP Lex のプログラムソースは %% というデリミタに区切られた３つのセクションからなっています： definitions %% rules %% auxiliary procedures どのセクションも空である可能性があります。TP Lex 言語は行を意識しますので、definitions と rules は行が重要なセパレータになります。コメントを書くための文法は存在しませんが、TP Lex ソース中に埋め込まれるパスカルソース部分にパスカルスタイルのコメントを書くことができます。（下を参照） definitions セクションには以下の要素を含めることができます： - 標準形式の定義： name substitution この形式で、良く使われる部分式の省略形を定義することができます。以降、{name} と言う記述は、対応する substitution 部へ置き換えて解釈されることになります。name は識別子として適当な形を持たなければなりません。(先頭が英文字で後に英数字が続きます；アンダースコアは英文字に含まれます；大文字小文字は区別されます）標準形式の定義は再帰構造を持ってはなりません。 - 初期状態の定義： %start name ... この形式で、規則の初期状態を定義します。（詳しくは以下を参照）%start というキーワードは、%s または %S と書くこともできます。 - %{ と %} に囲まれた Turbo Pascal の宣言文： この形式で指定された部分は出力ファイルのグローバルスコープ部分に挿入されます。同様に、Lex の定義として解釈されない行はすべて Turbo Pascal のコードとして出力されます。たとえば空白やタブから始まる行がこれに該当します。特に、これによって Lex プログラム中に Turbo Pascal 形式のコメントを書くことが許されます。 rules セクションは、語彙解析ルーチンの実装を定義します。これは、一つの巨大な CASE 文と考えることができます。この CASE 文は、マッチを試みるそれぞれのパターンと、それに対応して起動される Turbo Pascal の文（アクション）を列挙したものです。それぞれの rule は入力と比較されることになる一つの正規表現と、それに対応するアクションからなります。アクションは、正規表現がマッチしたときに呼び出される Turbo Pascal の文です。正規表現と文とはホワイトスペース（空白文字またはタブ文字）によって区切られます。したがって、Lex の文法規則は次のようになります： expression statement; アクションは Turbo Pascal のただ一つの「文」であり、セミコロンで終わっていなければならないことに注意してください。（複合文を使いたければ、begin .. end を使うことができます）この文は複数行にわたることができます。この場合には２行目以降は空白文字またはタブ文字で始まっている必要があります。アクション部分に | という文字を書くこともできます。この記述は、この rule に対応するアクションは次の rule のアクションと同一であることを示します。 TP Lex のライブラリユニットは、さまざまな変数やルーチンを提供します。これらは、アクション部分を記述する再に便利に利用することができます。特に、yytext 文字列変数はマッチした文字列を保持しており、yyleng がその長さを表します。 文法規則中で特定の文字の並びを記述するのに正規表現が用いられます。正規表現は、キャラクタクラスやセンテンスを記述する usual constructs と、繰り返しや alternatives を記述する演算子からなります。正規表現の厳密な定義は次のセクションで記述されます。 rules セクションも、%{ と %} によって囲まれたTurbo Pascal 宣言文から始めることができます。それらは、actions ルーチンのローカルな宣言文として扱われます。 最後に、auxiliary procedure セクションに、任意の Turbo Pascal コード(たとえば、頻繁に使うサブルーチンや、メインルーチンなど)を含めることができます。 これらは単純に出力ファイルの最後に追加して出力されます。auxiliary procedure セクションは省略が可能です。 正規表現 ------------------- 次に示す表に、TP Lex で使える正規表現がまとめてあります。(Aho, Sethi, Ullman 1986, fig. 3.48 を参照のこと) ここで、 c は１文字を表します。 s は文字列を表します。 r は正規表現を表します。 n,m は、非負の整数値を表します。 正規表現 マッチ 使用例 ---------- ------------------------------------ ------- c 演算子として認識されない任意の文字 c a \c 文字 c \* "s" 文字列 s "**" . 改行文字以外の任意の文字 a.*b ^ 行頭 ^abc $ 行末 abc$ [s] s に含まれる任意の１文字 [abc] [^s] s に含まれない任意の１文字 [^abc] r* ０回以上の r の繰り返し a* r+ １回以上の r の繰り返し a+ r? r があっても無くてもよい a? r{m,n} m 回以上 n 回以下の r の繰り返し a{1,5} r{m} m 回の r の繰り返し a{5} r1r2 r1 の後に r2 が続く ab r1|r2 r1 または r2 a|b (r) r と同値 (a|b) r1/r2 r2 が後に続くときに限り r1 を受け入れる a/b r 初期条件 x が満たされるときに限り r abc ------------------------------------------------------------- 演算子の優先順位は、*, +, ?, {} が最も高く、並べて書かれた場合の優先順位が次に続きます。| 演算子は最も低い優先順位を持ちます。() 括弧は正規表現をグループ化して、演算子の優先順位を変更することができます。<> と / は一つの正規表現に高々１回しか現れることができません。 一般的な C-like なエスケープ文字も使うことができます： \n 改行 \r キャリッジリターン \t タブ \b バックスペース \f 改ページ \NNN ８進数でキャラクタコードを指定 また \ を使って、そのままでは演算子として使われる文字をクウォートし、通常の文字として使うことができます。[] を使ってキャラクタクラスを定義するときには - 文字を使ってキャラクタの範囲指定をすることができます。たとえば、[a-z] はすべての小文字英文字を含むキャラクタクラスを表します。 TP Lex プログラム中の正規表現は不定になることがあります。つまり、入力が複数の規則にマッチすることがありえると言うことです。このような場合、語彙解析ルーチンは、最長マッチを優先し、それでも一意に決まらない場合には、最初に現れたものを採用します。もしどのルールにもマッチしない場合には、語彙解析ルーチンはデフォルトのアクションを起こします。この場合、入力文字は出力にそのまま送られます。したがって、入力の一部分だけを変換し、その他の部分は変更しないような語彙解析ルーチンを作るには、特に処理したい部分に関する処理のみを記述すれば良いことになります。ただし、語彙解析ルーチンにすべての入力を吸収させるには、すべてにマッチするような rule を作っておく必要があります。次のような rule を使えば良いでしょう： . | \n ; これは、（他のものにマッチしない）すべてのキャラクタにマッチします。（そしてそれらを無視します） 時には、あるパターンのマッチがそのコンテキストに影響されることがあるかもしれません。そのような場合には / 演算子を使うと便利です。たとえば、a/b という正規表現は、あとに b が続くときに限り a にマッチします。b がそのマッチした文字列に含まれないことに注意してください。語彙解析ルーチンが a のマッチを判定するときには、a のマッチを宣言する前に、インプットを先読みして b が続いていることを確かめます。このような先読みはいくらでも複雑なものにできます（ただし、LexLib の入力バッファに収まる必要があります）。たとえば、a/.*b というパターンは、入力の残りの部分のどこかに b がある場合に限り a にマッチします。TP Lex は左側コンテキストを指定する方法も持っています。これについては次のセクションで説明します。 初期条件 ---------------- TP Lex は左側コンテキストを扱うことを可能にするためのいくつかの機能を備えています。^ という文字は、正規表現中で行頭の存在を示すのに使うことができます。もっと離れた場所の左側コンテキストは、rule に初期条件を課すことで簡単に記述することができます。 <> が先頭にくっついた rule は、語彙解析ルーチンが指定された初期状態にあるときのみ有効になります。たとえば、a と言う式は、語彙解析ルーチンが初期状態 x にあるときのみマッチする可能性があります。また、一つの rule に複数の初期状態を指定することもできます； たとえば、a 初期状態 x または y のときにのみマッチします。 初期状態は definitions セクションで定義されている必要があります(上述）。語彙解析ルーチンは LexLib に含まれる start ルーチンを呼び出すことで、所定の初期状態に移行することができます。たとえば、次のように書くことができます： %start x y %% a start(y); b start(x); %% begin start(x); if yylex=0 then ; end. この例では、初期化過程で語彙解析ルーチンは状態 x になります。そして、a にマッチして状態 y に移行するまで状態 x のままでいることになります。状態 y にいるときには b にマッチすることができ、b を見つければ再び状態 x に戻ることになるわけです。 初期条件は、左側コンテキストに依存して異なる解析をしなければならないとき（たとえば、行頭に特殊文字がある場合など）、あるいは複数の語彙解析ルーチンを組み合わせて使わなければならないときなどに便利です。初期条件無しに書かれた rule は、ユーザの定義したすべての初期状態で有効です。これには、語彙解析ルーチンのデフォルトの初期状態も含まれます。 Lex ライブラリ ----------- TP Lex ライブラリ(LexLib)ユニットは、さまざまな変数やルーチンを含んでおり、それらは Lex によって作られる語彙解析ルーチンやアプリケーションから利用することができます。そこには、語彙解析ルーチンで使われる入力・出力ストリーム、およびその他の内部データストラクチャ、また、アクションやアプリケーションから使うことのできるいくつかの変数やユーティリティルーチンを含んでいます。詳しい説明は LEXLIB.PAS を参照してください。 Lex ライブラリ、および、YYLEX.COD に含まれるコードテンプレートを変更して使うことも許されています。そうすることで、TP Lex をあなたのアプリケーション用に最適化することができるでしょう。たとえば、語彙解析ルーチンをファイルを読み書きするのではなくメモリ上で動作する用に改造して、特殊な用途に使うことができるでしょう。 実装の制限とバグ ------------------------------------ 内部テーブルのサイズと、利用可能なメインメモリの量によって、TP Lex が扱うことのできるソース文法ファイルの複雑さが制限されます。現在のところ、内部テーブルのサイズを変更することは不可能です。（これには TP Lex のソースファイル自体を変更する必要があります）しかし、TP Lex によって提供される最大の内部テーブルの大きさは、ほとんどの現実的なアプリケーションを実現する上で十分であると思います。現在の制限値は、600 p (positions)、300 s (states)、600 t (transitions) です。 現在の実装では、生成される DFA テーブルは型付配列定数として YYLEX.COD コードテンプレートに挿入されます。ここにはそれぞれの状態内部での遷移が順に記述されます。ご存知の通り、大きな CASE 文を生成することでより効率的なコードを作ることも可能です。しかし、そのような実装を大きな DFA テーブルに対して行うと、個々の手続きのコードサイズに対する Turbo Pascal の制限を超えてしまうと言う問題を生じてしまいます。そこで、私は異なるシンボルに対する同じ状態への遷移を一つの遷移としてまとめてしまうことにしました。これには、文字セットと対応する次の状態とを指定することになります。このようにすることで、各々の状態内部で定義された遷移の数をかなり小さくすることができ、なおかつ遷移テーブルに対してのアクセスをそこそこ効率的にすることができました。 As implemented, the generated DFA table is stored as a typed array constant which is inserted into the YYLEX.COD code template. The transitions in each state are stored in order. Of course it would have been more efficient to generate a big CASE statement instead, but I found that this may cause problems with the encoding of large DFA tables because Turbo Pascal has a quite rigid limit on the code size of individual procedures. I decided to use a scheme in which transitions on different symbols to the same state are merged into one single transition (specifying a character set and the corresponding next state). This keeps the number of transitions in each state quite small and still allows a fairly efficient access to the transition table. TP Lex プログラムは、DFA テーブルを最適化する /o というオプションを備えています。これによって最小の DFA テーブルを作ることができます。ここでは、Aho, Sethi, Ullman (1986) によって示されたアルゴリズムが使われています。TP Lex が扱うことのできる最大の DFA 状態数は 300 ですが、TP Lex の DFA 最適化アルゴリズムの始めの部分で扱える状態数はさらに 100 個に制限されています。従って、TP Lex が最適化無しの DFA テーブルを生成できる場合にも、/o オプションをつけることで 'integer set overflow' のメッセージが表示されることがあります。このような場合には最適化無しの DFA テーブルで満足してもらうしかありません。(いずれにせよ、上記のように遷移をまとめる手法を使っているおかげで、通常の場合 TP Lex の生成する最適化無しの DFA テーブルは最適化されたものに比べ大幅に劣ることはありません。ですから、ほとんどの場合 DFA 最適化は DFA テーブルのサイズを劇的に減らすことはできません。) Differences from UNIX Lex ------------------------- TP Lex と UNIX Lex との主な相違点を以下に列挙します。 - TP Lex は C ではなく Turbo Pascal 用の出力ファイルを生成します。 - キャラクタテーブル (%T) はサポートされていません。したがって、内部テーブルサイズを指定するための (%p, %n, etc.) といったディレクティブはサポートされません。 - ライブラリルーチンの名前は UNIX バージョンのものと異なっています。(たとえば、UNIX Lex の 'BEGIN' マクロは start ルーチンに置きかえられています) また、当然ですが、UNIX Lex でマクロとして実装されている ECHO, REJECT などは手続きとして実装されています。 TP Yacc ======= このセクションでは TP Yacc コンパイラコンパイラについて説明します。 使い方 ----- YACC [options] yacc-file[.Y] [output-file[.PAS]] オプション ------- /v "Verbose:" TP Yacc は、生成されたパーサに関する判読可能な記述を、yacc-file の拡張子を .LST に変更したファイルに書き出します。 /d "Debug:" TP Yacc はデバッグ用出力を行うパーサを生成します。 説明 ----------- TP Yacc は BNF-like な文法を持つ言語によって記述された入力ファイルからパーサを生成するプログラムです。対象言語の文法を記述し、その文法構造を処理する Turbo Pascal のコードを加えれば、TP Yacc は入力ファイルに対応するパーササブルーチン yyparse を生成してくれます。 TP Yacc は、yacc-file (デフォルト拡張子 .Y) に含まれる文法定義を読み、パーササブルーチンを構築して指定された出力ファイル（デフォルト拡張子 .PAS) に書き出します。出力ファイルが指定されない場合には、yacc-file の拡張子を .PAS に変更した名前のファイルに出力されます。コンパイル中になんらかのエラーがあった場合には、エラーメッセージがリストファイル(yacc-file の拡張子を .LST に変更したファイル）に出力されます。 構築されるパーサルーチン yyparse は次のように宣言されます： function yyparse : Integer; あなた書くメインプログラムはパーサを起動するためにこのルーチンを呼び出すことができます。yyparse の返り値はパースが成功したか失敗したかを示します。( 0 = 成功、1 = 続行不可能な文法エラーまたはスタックオーバフロー ) yyparse ルーチンのためのコードテンプレートが YYPARSE.COD に含まれています。出力ファイルを作成するときに TP Yacc がこのファイルを必要とします。このファイルは、カレントディレクトリか、TP Yacc の置かれているディレクトリに存在しなければなりません。TP Yacc はカレントディレクトリに置かれているものを優先します。 Yacc によって生成されたパーサを使うには、TP Yacc ライブラリ (YaccLib) ユニットが必要になります。したがって、パーサルーチンを使用するプログラムまたはユニットに、適切な uses 説を追加する必要があります。YaccLib ユニットは、パーサのアクションを制御するのに使われるいくつかのルーチンを含んでいます。詳しくは、YACCLIB.PAS をご覧下さい。 Yacc ソースファイル ----------- TP Yacc プログラムは %% によって区切られる３つのセクションを持っています： definitions %% rules %% auxiliary procedures TP Yacc 言語は、フリーフォーマットです。したがって、ホワイトスペース (空白、タブ、改行) はデリミタとして認識される以外は無視されます。コメントは、C-like に /* ... */ と書きます。コメントはホワイトスペースとして扱われます。文法記号は通常の形式の識別子(英文字を先頭とする英数字の並び。英文字にはアンダースコアが含まれる。大文字小文字は区別される。) によって表されます。TP Yacc 言語は % から始まるいくつかのキーワードを持っています。リテラルはシングルクウォートによって囲まれた文字列によって表されます。通常の C-like なエスケープ文字が利用可能です： \n 改行 \r キャリッジリターン \t タブ \b バックスペース \f 改ページ \NNN ８進数でキャラクタコードを指定 定義部 ----------- TP Yacc 文法ソースの最初のセクションでは、文法定義の中で使われる文法記号の定義を行います。ここには、以下に挙げるような定義を含めることができます： - 初期文法の定義： %start symbol この形式では、一番大元となる非終端記号を指定します。(この定義が省略された場合には、TP Yacc は一番始めの文法規則で左側に書かれる非終端記号を初期文法とします) - 終端記号の定義: %token symbol ... この形式で、対象となる言語の終端記号（トークン）を定義することができます。%token で定義された以外のすべての識別子は、非終端記号として扱われることになります。 TP Yacc に関する限り、トークンは内部構造を持たない最小構成単位として扱われます。入力ストリームをトークンに切り分け、個々のトークンまたはリテラルをパーサに渡すために、語彙解析ルーチン (例：yylex) が必ず必要となります。(語彙解析のセクションを参照してください) - 結合順位の定義: 各種の演算子となる終端記号には、結合順位の定義によって、評価順序を指定することができます。 %left symbol ... %right symbol ... %nonassoc symbol ... これらはそれぞれ左結合、右結合、非結合の演算子を定義するのに用いられます。それぞれの結合順位定義は、新しい結合順位レベルを生成します。一番始めのものがもっとも弱い結合順位を持ちます。たとえば、次のように書くことができます。 %nonassoc '<' '>' '=' GEQ LEQ NEQ /* 関係演算子 */ %left '+' '-' OR /* 加法演算子 */ %left '*' '/' AND /* 乗法演算子 */ %right NOT UMINUS /* 反転演算子 */ 結合順位定義に現れる終端記号は、%token によって明示的に定義してもよいし、しなくても構いません。 - 型宣言: 任意の文法記号（終端・非終端) はただ一つの型識別子と関連付けることができます。この型識別子は、意味論的な値を処理するのに使われます。<名前> と言う形の型タグを %token や、%left などの定義に付加して、終端記号の型を宣言することができます。たとえば： %token NUM %left '+' '-' 終端記号に型を宣言するには、%type 定義を使います: %type symbol ... たとえば: %type expr %type 定義では終端記号を省略することもできます。つまり、次のように書くことができるのです： %type この形式は、ある型が特定の終端記号に関係しているのではなく、型キャスト(文法規則とアクションのセクションを参照してください)でしか使われない場合に便利です。 - Turbo Pascal 宣言: 任意の Turbo Pascal 宣言コードを definitions セクションに書くことができます。この場合には、%{ と %} でコードを括ってください。このコードは何の変更も受けずに出力ファイルのグローバル宣言部に挿入されます。 文法規則とアクション ------------------------- TP Yacc 文法ファイルの第２のセクションでは、対象言語の文法規則が記述されます。文法規則は次の形式を持ちます。 name : symbol ... ; 規則の左側は識別子でなければなりません。この識別子が非終端記号を表すことになります。右側は任意の非終端記号および終端記号 (シングルクウォートで囲まれたリテラル文字でもよい) となります。右側は空であることもあります。最後のセミコロンも省くことができます。同じ左側の文法記号に対して複数の異なる規則を書くには、| を使って、複数の可能性を分けて書きます： name : symbol ... | symbol ... ... ; たとえば、単純な数式の文法を定義するのに、次のように書くことができます: %left '+' '-' %left '*' '/' %token NUM %% expr : expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | '(' expr ')' | NUM ; (文法の始めにある %left 定義は、演算子の結合規則や優先順位を指定するために必ず必要です。このことについては、あいまいな文法のセクションで詳しく触れます。) 文法規則はアクション、{ } に囲まれた Turbo Pascal の文、を含むことができます。アクションは、対応する文法規則が入力ファイル中に発見されたときに起動されることになります。さらに、規則は返り値を持つことができ、また、他の規則の返り値を参照することもできます。これらの意味論的な値は、$$ (左側の nonterminal symbol の値) または、$i ( 右側の i 番目の symbol の値 ) として記述されます。これらの値は、パーサによって自動的に管理される特殊なスタックに保持されます。 terminal symbol に関連付けられる値は語彙解析ルーチンによって指定されなければなりません。（語彙解析のセクションを参照してください）$$ := $1 という形式のアクションはごくしばしば省略可能です。なぜなら、この動作は、ユーザによって明示的にアクションが指定されていない規則における TP Yacc によるデフォルトの動作だからです。 デフォルトで、この意味論的な値は Yacc により Integer として扱われます。次のような宣言をすることも可能です: %{ type YYSType = Real; %} これを Yacc 文法ファイルに含めることでデフォルトの型を変更することができます。ただし、複数の型が必要となる場合には、宣言のセクションで説明された方法を利用した方が良いでしょう。そのような型宣言が行われた場合には、TP Yacc は YYSType の定義に必要な詳細をすべてを引き受け、また型チェックを厳しく行うことで文法記述中のエラーを発見するのを容易にします。 たとえば、上の例で、NUM と expr の型を Real と宣言し、これらの値をパースされた式の値を表すように利用することが可能です。 %left '+' '-' %left '*' '/' %token NUM %type expr %% expr : expr '+' expr { $$ := $1+$3; } | expr '-' expr { $$ := $1-$3; } | expr '*' expr { $$ := $1*$3; } | expr '/' expr { $$ := $1/$3; } | '(' expr ')' { $$ := $2; } | NUM ; (ここで、最後の規則でアクションが省かれていることに注目してください。個々で必要なコピーするというアクション $$ := $1 は、TP Yacc によって自動的に追加されます。) アクションは、常に規則の最後に来るわけではなく、途中に現れることもあります。これは、その規則がすべてパースされる前に何らかの処理を行いたい場合に有効な手段です。規則の途中に挿入されたそのようなアクションは、何も対応するものを持たない空の nonterminal symbol と同様に扱われます。したがって、 x : y { action; } z は、 x : y $act z $act : { action; } と同様に扱われます。規則の途中に挿入されたアクションも、そのアクションの左側にある値を参照することができます。また、$$ に値を代入することで値を返すことができます。そのようにしてアクションから返された値も、他のアクションから $i の形で参照することができます。したがって、次のように書くことができます。 x : y { $$ := 2*$1; } z { $$ := $2+$3; } この式は、x の値を、 2*(the value of y)+(the value of z). のように設定します。時には、上位のルールの値にアクセスすることが必要になるばあもあります。その場合には、$i の形で、i に i<=0 の値を入れて使います。$0 で現在のルールのすぐ左の値を参照できます。$-1 はその次といった具合です。このようなことをする場合には、参照される値は実際のパーススタックの内容に依存します。したがって、望みの値が望みの場所にあることを良く確かめてから使わなければなりません。 型情報を使った場合、特定の条件で TP Yacc が変数の型を特定できない場合がありえます。特に、上位の値にアクセスする場合や、規則の途中に挿入されたアクション中で $$ を使用する場合にこれがおこります。このような場合には、値の明示的な型キャストを行うことができます。このようなタイプキャストの形式は、$<型名>$ (左側の値)、または、$<型名>i (右側または上位規則の値) となります。型名は %token や %left、%type などで definition セクションに現れている必要があります。 例： $$, $1 Auxiliary Procedures -------------------- TP Yacc プログラムの３番目のセクションは省略可能です。もし存在した場合には、そこには任意の Turbo Pascal コードを含めることができます。 (サブルーチンやメインプログラムなど）これらは、出力ファイルの最後に付加される形で出力されます。 語彙解析 ---------------- TP Yacc によって生成される任意の parser には、yylex と言う名前の語彙解析ルーチンが必要となります。このルーチンは次のように宣言されていなければなりません。 function yylex : Integer; yylex ルーチンは手で書いても良いですし、語彙解析ルーチン生成プログラム TP Lex を使っても良いです。(`TP Lex' のセクションを参照してください) 語彙解析ルーチンは、メインプログラム中でパーササブルーチンの後にインクルードされなければなりません。（yyparese のコードテンプレートは、パーサが 語彙解析ルーチンにアクセスできるように yylex ルーチンの前方定義を含んでいます）たとえば、語彙解析ルーチンを TP Yacc 文法ファイルの auxiliary procedures セクションに、直接あるいは、Turbo Pascal のインクルードディレクティブ(*$I*) によって組み込むことができます。 パーサは、入力ファイルをトークンに切り分けるため yylex ルーチンを繰り返し呼び、個々の語彙単位を取り出します。リテラル文字に対して、yylex ルーチンは対応するキャラクターコードを返さなければなりません。入力言語中のその他の終端記号については、対応する Integer のコードを返さなければなりません。非終端記号のコードは文法定義の definitions セクションでトークン定義が現れる順に従って、 TP Yacc によって割り当てられます。語彙解析ルーチンでこれらの値を参照するには TP Yacc が出力するファイルに定義された整数定数を使います。 例えば、 %token NUM が Yacc 文法に現れる最初の定義だとすると、TP Yacc はこれに対応する定数を const NUM = 257; として出力ファイル中で宣言します。(TP Yacc は終端記号番号を257から順に自動的に割り当てます。1 から 255 まではリテラル文字のために予約されています。0 はファイルの終端を、256 はエラーを表す特殊トークンとして使われます。これについては 'エラーへの対応' のセクションで詳しく説明されます。) これらの定義は、例えば TP Lex プログラムで、以下のようにして使うことができます。 [0-9]+ return(NUM); 文法定義の中で、トークン番号を直接指定することもできます。これを行うには、definitions セクションでトークン識別子が初めて現れる時に、後ろに符号なし整数値を書きます。例えば、次のように書くことができます。 %token NUM 299 語彙解析ルーチンは yylex 関数の戻り値の以外に、認識したトークンに対する追加の意味論的情報を返すことができます。この値を yylval と言う名前の変数に入力することで、actions ルーチンから $i のような記法で参照することができます（上記の 「文法規則とアクション」のセクションを参照）。yylval 変数は YYSType 型になります（意味論的値の型：デフォルトではInteger)。YYPARSE.COD ファイルにその宣言を見つけることができます。 例えば、上の例で NUM トークンに整数値を与えるには、次のように書くことができます。 [0-9]+ begin val(yytext, yylval, code); return(NUM); end; このコードは NUM トークンの表す値を yylval に代入します(Turbo Pascal の標準手続き val を使っています)。 異なる型を持つトークンを同時に使う場合には(%token により定義される)、yylval 変数は Integer ではなく、TP Yacc 文法により定義されたすべての型を保持することのできるレコード型として宣言されます。この場合には、語彙解析ルーチンは意味論的な値を代入する際、レコードの中の対応する要素を指定しなければなりません。レコードの中の要素は yy という名前が付けられます。（ は型を表す識別子） 例えば、もし NUM が Real として宣言されていたならば、 %token NUM NUM トークンに対する値は yylval.yyReal に代入することになります。 パーサの動作 ------------ TP Yacc は Donald E. Knuth と F. DeRemer によって開発された LALR(1) 法を使い、単純、効率的でバックトラッキングの必要の無いボトムアップのパーサーを、文法定義から生成します。LALR 法は Aho/Sethi/Ullman (1986) に詳しく説明されています。小さなサンプル文法ファイルから TP Yacc が生成するパーサーのコードを見てみることは、LALR 法がどのように動作するかを知るのにとても役立つでしょう。次のような単純な数式の文法について考えてみましょう。 %token NUM %left '+' %left '*' %% expr : expr '+' expr | expr '*' expr | '(' expr ')' | NUM ; /v オプションをつけて上の文法を処理させると、TP Yacc はパーサについて以下のような診断を出力します。 state 0: $accept : _ expr $end '(' shift 2 NUM shift 3 . error expr goto 1 state 1: $accept : expr _ $end expr : expr _ '+' expr expr : expr _ '*' expr $end accept '*' shift 4 '+' shift 5 . error state 2: expr : '(' _ expr ')' '(' shift 2 NUM shift 3 . error expr goto 6 state 3: expr : NUM _ (4) . reduce 4 state 4: expr : expr '*' _ expr '(' shift 2 NUM shift 3 . error expr goto 7 state 5: expr : expr '+' _ expr '(' shift 2 NUM shift 3 . error expr goto 8 state 6: expr : '(' expr _ ')' expr : expr _ '+' expr expr : expr _ '*' expr ')' shift 9 '*' shift 4 '+' shift 5 . error state 7: expr : expr '*' expr _ (2) expr : expr _ '+' expr expr : expr _ '*' expr . reduce 2 state 8: expr : expr '+' expr _ (1) expr : expr _ '+' expr expr : expr _ '*' expr '*' shift 4 $end reduce 1 ')' reduce 1 '+' reduce 1 . error state 9: expr : '(' expr ')' _ (3) . reduce 3 パーサーのそれぞれの遷移状態 (state) は、ある時点ですでに読み込まれた入力文字列に対応しています。各々の遷移状態には、その状態が対応する可能性があるすべての文法規則が列挙され、おのおのの文法規則を仮定した際の現在位置がアンダースコア文字( "_" )で表示されます。遷移状態 #0 において（パーサーの初期状態です）、パースされつつある文法規則は、 $accept : expr $end となります。これは実際の文法規則とは対応しませんが、TP Yacc により自動的に追加された初期規則です。一般に、このような初期規則は次の形を持ちます。 $accept : X $end ここで、X は文法の初期終端記号であり、$end はファイルの終端を表す擬似トークンです。(パーサは文法記号 $end を使って入力のパースに成功したかどうかを決定します) 遷移状態 #0 において、初期文法規則は $accept : _ expr $end と表示されています。アンダースコア '_' が文法記号 expr の前にあることに注意してください。これは、パーサーが入力を受け入れ始め、数式(非終端記号expr)を受け入れようとしていることを表しています。 パーサーは入力を解釈する間に訪れた遷移状態を辿るためのスタックを持っています。それぞれの遷移状態において２つの基本的な動作が考えられます。１つは "shift" で、入力文法記号を読み込み、対応する次の遷移状態をスタックの一番上に積みます。もう一つは、"reduce" で、スタックから遷移状態をいくつか（"reduce" の行われる文法規則の右側にある文法記号の数だけ）取り出し、"goto" エントリーを見て "reduce" された文法規則の左側の文法記号に対応する、非対応な状態を探し出します。 パース中のいかなる時点においても、パーサーは常にある特定の遷移状態（スタックの一番上にある状態）にいます。そして、現在先読みされている文法記号（次に入力される文法記号）を見て、次に行うアクション - shift か reduce か - を決定します。パーサーは遷移状態 #1 において入力の終端記号を読み込むと即終了します。これは、遷移状態 #1 で $end に対して指定された "accept" アクションの動作です。 パーサーは先読みされたトークンを調べることなくアクションを起こすことがあります。例えば、遷移状態 #3 がこれにあたります。この場合、唯一のアクションは文法規則４による reduction になります。 . reduce 4 遷移状態のデフォルトのアクションが "error" であることもあります。これは、指定された以外の入力が文法エラーとなることを表します。（このようなエラーが生じた場合、パーサーは文法エラーからの復帰を始めます。これについては「エラー処理」のセクションで記述されます） ここで、パーサーが与えられた入力に対しどのように反応するかを見てみましょう。2+5*3 という入力文字列を考えましょう。これは、パーサーには次のようなトークン列として認識されます。 NUM + NUM * NUM 次の表は、この入力に対応するパーサーの動作を追ったものです。その時々の遷移状態とスタックの様子が示されています。 State Stack Lookahead Action ----- ------------ --------- -------------------------------------------- 0 NUM shift state 3 3 0 reduce rule 4 (pop 1 state, uncovering state 0, then goto state 1 on symbol expr) 1 0 + shift state 5 5 1 0 NUM shift state 3 3 5 1 0 reduce rule 4 (pop 1 state, uncovering state 5, then goto state 8 on symbol expr) 8 5 1 0 * shift 4 4 8 5 1 0 NUM shift 3 3 4 8 5 1 0 reduce rule 4 (pop 1 state, uncovering state 4, then goto state 7 on symbol expr) 7 4 8 5 1 0 reduce rule 2 (pop 3 states, uncovering state 5, then goto state 8 on symbol expr) 8 5 1 0 $end reduce rule 1 (pop 3 states, uncovering state 0, then goto state 1 on symbol expr) 1 0 $end accept 文法的に間違った入力にパーサーがどのように反応するかを見るのも勉強になります。例えば、次のような入力に対してパーサーが何をするか調べてみるのがよいかもしれません。 NUM + ) あるいは ( NUM * NUM 間違った入力が与えられた時、遅かれ早かれパーサーは常に error アクションにたどり着くのが確かめられるでしょう。一般に LALR パーサーが間違った文法規則を shift することは絶対に起こりえません。従って、入力を頭から順に読んで行くだけで文法エラーを可能な限り早い段階で検出することができます。 TP Yacc にデバッグオプション (/d) を与えることで、パーサーの実行するアクションを逐一追いかけることができます。文法が /d オプション付きでコンパイルされると、生成されたパーサーは入力をパースする際にアクションを表示します。 あいまいな文法規則 ------------------ 入力された文法規則によっては、TP Yacc が有効なパーサーを生成できない場合があります。LALR(1) パーサーは、パースを進めるのにたった一つしか入力から文法記号を先読みしないという特徴があります。文法規則があいまいな場合、もしくはただ一つの先読みではパースを進められない場合、TP Yacc はパーステーブルを作成できず "parsing conflicts" が発生します。２種類の conflicts が生じる可能性があります。１つは shift/reduce conflicts であり、ある遷移状態において１つの入力記号に対して shift と reduce の両方の可能性がある場合に対応します。もう１つは reduce/recuce conflicts であり、１つ以上の reduce の可能性がある場合です。shift/shift conflict が生じることは決してないことに注意してください。 文法が parsing conflicts を生じた場合、TP Yacc はパーステーブルを作成する際に見つかった shift/reduce conflicts と reduce/reduce conflicts の数を表示します。しかし、この場合にも TP Yacc はパーサー用のコードを出力します。parsing conflict を解決するため、TP Yacc は次のようなあいまい文法解決法を使います。 - shift/reduce conflict: shift action を選択します - reduce/reduce conflict: 一番初めの文法規則に対する reduction を選択します shift/reduce conflict に対するこの規則は、Pascal などの多くの言語の条件文で見られる、よく知られた else 節の文法に関するあいまい性や、それに類似の問題を正しく解決します。 %token IF THEN ELSE %% stmt : IF expr THEN stmt | IF expr THEN stmt ELSE stmt ; この文法はあいまいです。なぜなら、入れ子になった次のような例は、 IF expr-1 THEN IF expr-2 THEN stmt-1 ELSE stmt-2 以下の２通りの方法で解釈することができます。 IF expr-1 THEN ( IF expr-2 THEN stmt-1 ELSE stmt-2 ) もしくは、 IF expr-1 THEN ( IF expr-2 THEN stmt-1 ) ELSE stmt-2 第一の解釈では ELSE は一番最後に現れた ELSE を持たない IF に対応するとします。これは、多くのプログラミング言語で採用されているやり方です。そして、これが TP Yacc が生成するパーサーの動作になります。なぜなら、shift/reduce 解決規則は IF expr-2 THEN stmt-1 を reduce するという選択肢を無視し、ELSE 記号を shift します。これは、最終的に IF expr-2 THEN stmt-1 ELSE stmt-2 を reduce する結果となります。 reduce/reduce 解決規則は与えられた文字列を複数の文法規則で解釈できる時に生じます。このようなあいまい性は、例外処理的文法規則によりしばしば見られます。このような文法規則には準位付けがなされ、より specific な文法規則から順に、一般的な規則へと記述されることになります。 たとえば、次に示すのは UNIX の数式印刷プログラムである EQN の入力言語の文法における例外的処理です。 %right SUB SUP %% expr : expr SUB expr SUP expr | expr SUB expr | expr SUP expr ; ここでは、SUB と SUP の演算記号は下付きおよび上付き文字をそれぞれ表します。この例で重要な点は、下付き文字と上付き文字を両方持つ式はしばしば特別扱いが必要となることです。したがって、この例外的な条件は上の例では一番初めの規則により処理されるべきなのですが、これが３つめの規則と reduce/reduce conflict を生じます。このような conflict は一番初めの規則を選択することで解決されます。 上で見た両方の場合において、取り上げたあいまい性は文法規則を適当に書き直すことで除去することができます（文法は複雑で読みにくくなりますが）。しかし、あいまい性は常に除去可能ではありません。しばしば、あいまい性は文法の設計ミスによります。したがって、パーサの生成において TP Yacc が parsing conflict を報告した場合には、/v オプションをつけることによってパーサーの診断結果 (.LST ファイル) を出力し、TP Yacc が conflict を正しく解決したかどうかを確認する必要があります。 ここで、あいまい性が除去可能であるにもかかわらず、言語定義の簡明さのためにしばしばあいまいな文法が好まれる例を見てみましょう。数式の文法についてです。例えば、次に示すのは数式のあいまいでない定義の仕方です。 %token NUM %% expr : term | expr '+' term ; term : factor | term '*' factor ; factor : '(' expr ')' | NUM ; この文法により、* が + よりも優先して処理され、なおかつどちらも左結合型の演算子であることが分かるはずです。演算子の優先順位を定義することで、次のようなあいまいな文法定義によっても同じ文法を定義することができます。 %token NUM %left '+' %left '*' %% expr : expr '+' expr | expr '*' expr | '(' expr ')' | NUM ; 優先順位の定義を使わないと、このあいまいな文法は多くの shift/reduce conflict を生じます。優先順位を定義することで、これらの conflict を正しく解決することができます。（TP Yacc は優先順位を使って解決された conflicts を報告しません） 個々の優先順位定義は新しい優先順位レベル（低いほうから高い方へ）を作成し、対応する演算子が左結合であるか右結合であるか、それとも無結合（無結合演算子同士を同時に使うことは許されない：Pascal における関係演算子など）であるかを指定する。 TP Yacc は優先順位に関する情報を使って shift/reduce conflict を次のように解決する。個々の優先順位宣言に現れるすべての終端記号には、その優先順位番号が関連付けられる。そして、これらの終端記号が現れる文法規則には、一番右の終端記号に付けられた優先順位が関連付けられる（このデフォルト動作は %prec タグで変更可能である 下記参照）。shift/reduce conflict を優先順位に従って解決するには、先読みされた終端記号と現在の文法規則の両者に優先順位が割り当てられている必要がある。この場合、TP Yacc は次のようなアクションを実行する。 - 文法記号の優先順位の方が高かったら : shift - 文法記号の優先順位の方が低かったら : reduce - どちらも同じだったら、文法記号の結合性により動作を決定する - 左結合 : reduce - 右結合 : shift - 無結合 : error この規則がどのように働くかを示すために、以下の優先順位を持たないあいまいな数式文法について考えてみることにしよう。 %token NUM %% expr : expr '+' expr | expr '*' expr | '(' expr ')' | NUM ; この文法は４つの shift/reduce conflict を生じる。遷移状態 #8 の診断結果は次のようになる。 state 8: *** conflicts: shift 4, reduce 1 on '*' shift 5, reduce 1 on '+' expr : expr '+' expr _ (1) expr : expr _ '+' expr expr : expr _ '*' expr '*' shift 4 '+' shift 5 $end reduce 1 ')' reduce 1 . error この遷移状態において、+ の式 (1) が正常に処理できたところだとしよう。次の文法記号が + か * だったとすると、パーサーはこれを reduction するか shift するか決定しなければならない。デフォルトの shift/reduce conflict の解決法では、TP Yacc はどちらの場合も shift を選ぶ。 さて、ここで優先順位が定義されていたとすると、 %left '+' %left '*' * は + よりも高い優先順位を持ち、どちらも左結合性となる。(1) の規則の最も右の終端記号は + である。したがって、上の優先順位によれば、* に対する conflict は shift として解決される( * は + よりも高い優先順位を持っている)。また、+ の場合には reduce が選択される（ + は左結合性である）。 同様な conflict が遷移状態 #7 でも生じる: state 7: *** conflicts: shift 4, reduce 2 on '*' shift 5, reduce 2 on '+' expr : expr '*' expr _ (2) expr : expr _ '+' expr expr : expr _ '*' expr '*' shift 4 '+' shift 5 $end reduce 2 ')' reduce 2 . error ここでは、* の式 (2) を正しく処理したところで、次に + か * が続いたとしよう。* は左結合で + よりも高い優先順位を持っているので、どちらも reduce が選択されることになる。 もちろん、ある１つの優先順位レベルに複数の異なる演算子を置くこともできる。例えば、数式の文法を次のように拡張してみよう。 %token NUM %left '+' '-' %left '*' '/' %% expr : expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | '(' expr ')' | NUM ; ここでは、すべての加算演算子を１つ目の優先レベルに、すべての乗算演算子を２つ目のレベルに割り当てている。また、すべての演算子は左結合性である。例えば、5+3-2 は (5+3)-2 として処理される。 デフォルトで、TP Yacc はそれぞれの規則に対して最も右の終端記号に対する優先順位を割り当てる。これはほとんどの場合うまく行くが、まれにこのデフォルトの動作を変更し、規則の優先順位を自分で指定したい場合がありうる。このような場合、規則の後に次の形式で優先順位を指定することができる。 %prec symbol これにより、対応する規則には指定された演算子記号と同じ優先順位が割り当てられることになる。例えば、先の数式文法に単項の - 演算子を追加することを考える。この演算子は最高の優先順位を持つことになる。この場合、次のように書くことができる。 %token NUM %left '+' '-' %left '*' '/' %right UMINUS %% expr : expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | '-' expr %prec UMINUS | '(' expr ')' | NUM ; ここで、UMINUS というトークンが実際に入力記号として現れることはなく、単に単項マイナス演算子に正しい優先順位を与えるためだけに利用されていることは重要である。もしここで優先順位タグ(%prec)を付けなければ、単項および二項のマイナス演算子は同じ優先順位になってしまう。どちらも同じ入力記号を持つためである。 エラー処理 ---------- 文法エラーの処理はユーザーフレンドリーなパーサーを設計する際に頭を悩ますところである。通常パーサーが１番目始めのエラー地点で動作を停止してしまうことは好まれない。パーサーは文法エラーから回復し、入力からパースを継続できる地点をさがすことを試みるべきである。 TP Yacc はエラーからの回復機能を備えたパーサーを設計するための一般的なメカニズムを提供する。特殊な定義済みトークンである "error" を文法規則の中で使うことで、文法エラーが起こる可能性のある場所を示すことができる。パーサーがエラー状態に陥った場合（つまり、エラーを生じる入力記号を読み込んだ場合）エラーメッセージが表示され、エラーの回復作業が始まる。ここでは、error トークンを shift する動作を含む状態が見つかるまでスタックから状態が読み捨てられる。もしここで、そのような状態が見つからなければパーサーは１を返して終了する。これは回復不能な文法エラーの発生を表す。もし error トークンを shift する規則を含む遷移状態が見つかれば、パーサーは error トークンに対する shift を実行（あたかも error トークンという仮想的な入力記号が読み込まれたかのように）し、特殊な状態 error mode でパースを続行する。 error mode にいる間、パーサーは有効な shift 動作が起こるまで入力記号を単に読み捨てる。エラーメッセージが多重に出力されないよう、３つの入力記号が正常に shift されるまでパーサーは通常の状態にもどらない。つまり、もし１つめの shift の後再びエラーが見つかった場合には、エラーメッセージを表示することなく再度エラー回復処理が試みられる。TP Yacc ライブラリルーチン yyerrok を使って、パーサを強制的に通常状態に戻すこともできる。 単純な例として、次の規則を考えよう。 stmt : error ';' { yyerrok; } ここで、非終端記号 stmt の処理中に文法エラーが起こったとしよう。パーサーはエラーメッセージを表示し、エラー処理規則に対応する error トークンを shift できるところまでスタックを巻き戻す。error mode を処理中、パーサーはセミコロンを発見するまで入力記号を読み飛ばす。最後にセミコロンを見つけるとエラー処理規則を reduce する。yyerrok を呼ぶことで、パーサーにエラーが回復されたことを告げ通常状態への復帰を促す。このような「パニックモード」のエラー回復手法は文が常にセミコロンで区切られている場合にはうまく行く。パーサーは間違った文を単に読み飛ばしてパースを再開する。 すぐれたエラー回復手法を構築するのは難しい。Aho/Sethi/Ullman (1986) にこの問題に対するより賢い手法について解説がある。Schreiner と Friedman は Yacc を使う際の非常に優れた系統的なエラー回復技法を構築した（TP Yacc パーサーのエラー回復にこれが使われている）。Schreiner/Friedman (1985) を参照。 Yacc ライブラリ --------------- TP Yacc ライブラリ (YaccLib) ユニットに、いくつかのグローバルな定義があり、yyparse ルーチンから利用可能である。さらに、いくつかの変数やユーティリティルーチンを使ってパーサの動作を制御し、またエラー回復処理を実装することができる。これらの変数やルーチンに関しては YACCLIB.PAS を見てください。 Yacc ライブラリユニットを（また YYPARSE.COD ファイルを）変更することで、TP Yacc をあなたの利用方法に合わせてカスタマイズすることができます。 その他の機能 ------------ TP Yacc は「古い機能であり使うことは勧められない」と UNIX のマニュアルで書かれているすべての追加言語規則をサポートしています。これらは古い UNIX の Yacc との互換性を確保するためのものです。 - リテラルをダブルコーテーション " で括ることができます - 複数文字を含むリテラル。これは文字列としてではなく、他のトークン識別子と同様に、TP Yacc により割り当てられた１つの整数値を表すことに注意してください。このようなトークン識別子は出力ファイル中で定義されませんので、明示的にトークン番号を指定し、さらに語彙解析ルーチンで正しいコードを返すよう注意しなければなりません。 %token ':=' 257 - % の代わりに \ を使うことができる。つまり、\\ は %% として、\left は %left として解釈される。 - その他、次のような同義記法 %< -> %left %> -> %right %binary or %2 -> %nonassoc %term or %0 -> %token %= -> %prec - アクションを = { ... } や = single-statement; の形式で書くことができる。 - Turbo Pascal の宣言文 (%{ ... %}) を rules セクションの始めに書くことができ、これらは action ルーチンのローカル宣言として扱われる。 Implementation Restrictions --------------------------- TP Lex と同様、内部のテーブルサイズとＰＣのメモリ容量により、TP Yacc が扱える文法ソースファイルの複雑さには限界があります。現在のところ内部テーブルのサイズを変更する手段（TP Yacc 自身のソースコードを書き換える必要があります）、あるいは拡張メモリを使う手段はありません。しかし、TP Yacc によって使うことのできる最大のテーブルサイズはかなり複雑な文法（TP Yacc の配布ファイルに含まれる Pascal 文法など）を扱うにも十分な大きさがあります。現在の限界値は、600 s (遷移状態 state)、2400 i (LR0 カーネル項目数)、2400 t (shift および goto 遷移)、1200 r (reduction) です。 出力されるパーサーのデフォルトのスタックサイズは、TP Yacc ライブラリユニットに宣言されている通り yymaxdepth = 1024 です。この値は通常の用途には十分な値ですが、このスタックサイズは Yacc 文法ソースファイルに宣言を追加することで（あるいは YaccLib ユニットを変更することで）変更可能です。右再帰的な文法規則はスタックを大量に消費します。従って、可能な限り左再帰的な文法規則を使うのが良いでしょう。 UNIX Yacc との相違点 -------------------- TP Yacc と UNIX Yacc との相違点の主なものを以下に挙げます。 - TP Yacc は C ではなく、Turbo Pascal のソースコードを出力します。 - TP Yacc は %union 宣言をサポートしません。その代わり、文法記号値の型は %token に付けるタグや %type 宣言によって型識別子自身を宣言することができます。TP Yacc は自動的にYYSTypeレコード型を宣言するので、これを使うことで %token や %type によって使われるどんな型の値でも yylval 変数に格納することができます。 　型チェックはとても厳しくなっています。型定義が行われた場合、アクションの中で使われるすべての文法記号は、definitions セクションにおいて型を割り当てるか、明示的に $ 記法によってキャストして使われる必要があります。%type 定義の仕方は次の形を許したことで多少変更されました。 %type すなわち %type において終端記号を省くことができます。これは、文法記号に割り当てられることは無いが、$<...> 形式で使われることのある方を宣言する時に使われます。 - TP Yacc により生成されるパーステーブルは UNIX Yacc に比べて少し大きくなります。これは、TP Yacc はある遷移状態において reduce が唯一のアクションである場合に限ってこれをデフォルトのアクションとするためです。これに対して UNIX Yacc は shift アクションがあっても、reduce アクションが１つしかなければ、それをデフォルトのアクションとして使うのと異なります。 これは UNIX Yacc に潜むバグを取り除くために行われました。このバグのために、UNIX Yacc の生成するパーサーはいくつかの種類の文法エラーに対してエラー回復が非常に遅れると言う問題があります(Schreiner/Friedman, "Introduction to compiler construction with UNIX," 1985)。この他にも、多くの場合において TP Yacc は UNIX Yacc よりも、文法エラーを早く捕らえることができます。UNIX Yacc はこのような場合、エラーを発見する前に１つ分余計な(デフォルトの) reduce を行ってしまいます。 - ライブラリルーチンは UNIX バージョンと異なる名前になっています(例えば、UNIX Yacc での YYERROR マクロは yyerrlab ルーチンに置き換えられています)。また、もちろん UNIX Yacc におけるすべてのマクロ (YYERROR や YYACCEPT など) は手続きとして実装しなければなりませんでした。