動作の解説

ウィキペディア小見出し辞書

動作の解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/16 05:20 UTC 版)

「Yacc」の記事における「動作の解説」の解説

たとえば、この構文規則から生成した構文解析器が、数値トークンNUM、End Of LineトークンEOLおよび演算子からなるトークン列 NUM '+' NUM '*' NUM '-' NUM EOL を読むとしよう。 ただこの前半では、トークンNUMが何の文字列をもってそう認識するかは定義されていない。Yaccにユーザが与えたYacc文法ファイルには、通常、字句解析をするための文法が存在していないからである（もっとも、無理に字句解析までやらせることは、複雜になるが不可能ではない）。その代わりトークンの入力は、yylex()という決まった名前の関数を呼ぶように展開される。目的の構文解析器の実行時に、Yaccによって生成されている構文解析器関数yyparse()は、ひとつひとつトークンをyylex()を呼んで要求する。yylex()はどこからか文字列を呼んでひとつトークンを返し，あれば変数lval経由でその意味値も同時に返し、ファイルの終端に達したとき（1行ごとにyyparser()から帰ってはまた呼び出す構文解析器を作るにおいては、行末に達したなどそのプログラムが解析のまとまりと認識している区切りに達したとき）はバイナリ0か負数を返して知らせる。 利用者はyylex()を自分でプログラミングするか、Lex、Flexなどの字句解析ツールを使って作成する必要がある。つまりLex、FLex、JFLexなどの字句解析器ジェネレータは、Yaccが作ってくれない関数yylex()を自動で作ってくれるツールといえる。 実際にはこの課題プログラムに 10+20*30-40 を与えたとして値も追跡したい。この場合「後半」のyylex()プログラムは構文解析器実行時に、次のトークン群、およびあれば以下でカッコ《》内に付記している意味値を、要求するたびに1個ずつ構文解析器関数yyparser()に返してくるはずである。 NUM《10》'+'NUM《20》'*'NUM《30》'-'NUM《40》EOL0（ファイル終端を表す） 最初に、スタックが空 の状態で内部にもつ状態番号を0にして%startで示されているdialogueが調べられる。適用できる規則は右辺が空の規則1なのでこれが適用される。状態スタックにはその0がはいる。このスタック状態を次のように図示できる。 0:dialogue そして状態番号は1に行く。yylex()の中で初回だけ、 Calculator start. と出し、prompt()というユーザ定義関数によって、 ?> と表示する。電卓ユーザまたはファイルから、 10+20*30-40 が入力されると、yylex()関数はトークン1個ずつyyparser()に返していく。 まずNUM《10》が読まれ，状態1での適用規則が探される。還元できる規則とはスタック右端がマッチしないので、ありえる記号としてそのテーブルに登録されている「NUM」に対する操作が行われる。すなわち、スタックにはじめてそれが1個シフトで入れられ状態5になる． 0:dialogue 1:NUM《10》 規則6 expr: NUM /* 規則6 「$$=$1;」は省略可 */ （単独のNUMはexpr）だけがマッチするからこれが適用され、 0:dialogue 1:expr《10》 に還元されてスタック内容が入れ替わる。 （この規則6にアクションは書いてなかったが、戻り値がないのではなく、Yaccの空でない規則に対するデフォルトアクション { $$ = $1; } が実行されて10がこのexprの値に代入されたのである。） そしてテーブルに書かれていた状態番号10になる。 ここで'+'を読んでシフトし、状態16になってNUM《20》までシフトしたとき、 0:dialogue 1:expr《10》 10:'+' 16:NUM《20》 となるから、先と同様に規則6でNUMがexprに還元され 0:dialogue 1:expr《10》 10:'+' 16:expr《20》 （←次に'*'が来る予定） となる（以下、内部状態番号の変化は省略するが次々と遷移していく）。 ここで現在スタックの右端にある3トークン「expr '+' expr」が規則9（加算式）にマッチして還元が起こりそうに思えるかもしれないが、起こらない。先読みしている次のトークンが現在の「+」よりも優先順位が高い「*」なので還元はせず、シフトを行う（もし演算子優先順位を同列にしていたら還元が起こって先に加算をするであろう）。 dialogue expr《10》 '+' expr《20》 '*' NUM《30》を読んでシフトし dialogue expr《10》 '+' expr《20》 '*' NUM《30》 規則6で還元し、 dialogue expr《10》 '+' expr《20》 '*' expr《30》 ここで、右端の3トークンが | expr '*' expr { $$ = $1 * $3; } /* 規則11 乗算．*/ にマッチしていて、次のトークンは'-'であり、今度は遠慮なく還元が実行されてスタックから3個消えて、意味値が600と計算された左辺のグループexprが押し込まれるので、 dialogue expr《10》 '+' expr《600》 のように2個分縮むことになる。 次に先読みしていた「-」を読み直す。ここの状態で右端の3トークンが | expr '+' expr { $$ = $1 + $3; } /* 規則9 加算．*/ にマッチしていて、次のトークンは'-'であり、これも還元が実行されてスタックから3個消えて、意味値が10+600=610と計算されたグループexprが押し込まれるので、 dialogue expr《610》 のようにまた2個分縮む。 （このように、還元が起こるたびに、まるでゲームのテトリスで同じ色のブロックが並んだときのように、スタックが伸びてはストンストンと短くなる。還元が長く起こらないとスタックが長くなって、既定のサイズを超えるとスタックオーバフロー例外で異常終了してしまうのも、ゲームオーバーに似ている。なお、スタックオーバフローを起こさないためには、 explist: exp | explist ',' exp のような右再帰の形を避けて explist: exp | exp ',' explist のような左再帰の形で定義することである。規模が大きくなる場合はスタックサイズの定義マクロYYMAXDEPTHの値を大きく指定する．） またまた先読みしていた「-」を読み直す。今度はさすがに適用できる規則がなくシフトされる。 dialogue expr《610》 '-' 次にNUM《40》が読まれてもシフトするしかない。 dialogue expr《610》 '-' NUM《40》 この状態で先読みトークンに、電卓ユーザが押した改行EOLがくる。 dialogue expr《610》 '-' NUM《40》 （←次にEOLが来る予定） この状態において、演算子優先度が関係ない先読みEOLに遠慮する必要がないので、 | expr '-' expr { $$ = $1 - $3; } /* 規則10 減算．*/ がマッチとして還元が実行されて、スタックから3個消える。その代わり、意味値が610-40=570と計算されたグループexprが押し込まれるので、 dialogue expr《570》 のようにまた2個分縮む。 先読みしていたEOLを読み直す。すると、この状態でexprには、 qa: expr { printf(" Ans = %Lg", $1); prompt(); }/* 規則5 改行で計算，表示．*/ しかマッチせず、アクションのprintf関数が実行されて， ?> Ans = 570 ?> という計算結果と次のプロンプトが標準出力に見事に出てくる。スタックは、 dialogue qa になった。 またまたEOLを読んで今度はシフトする。 dialogue qa EOL これはdialogueの再帰的な規則のひとつ | dialogue qa EOL /* 規則3 Q&A行. */ の3個のトークンとマッチするので、還元が実行されてスタックから3個消えて左辺のグループdialogueが押し込まれ、 dialogue だけになる。 このあと入力ファイルにまだ演算させたい式を書いた行が書かれていれば、上と同様に計算され結果が表示されるであろう。が、いまの場合はファイル終端になってyylex()が Bye. と表示して0を返す。すると内部的には$endという特殊トークンがシフトされ dialogue $end となるが、これが暗黙に定義されている規則0 $accept: dialogue $end とマッチするので、パーサは$accept（受理）を得て目的を成功裏に果たしたということでスタックをすべてクリーンアップして，yyparse()呼出元に制御を返す。 このようにYaccの作るパーサは、解析した文字列が最後に%startの記号（デフォルトは最初に書いた規則の左辺）に見事にマッチし文法に合格したと判断されたとき正常に戻り値0でyyparser呼出元に帰る。また、YYACCEPTマクロを実行すれば即正常で帰る。 構文解析エラーが起これば異常（戻り値1）でyyparser呼出元に帰る。また、YYABORTマクロを実行すれば即異常（戻り値1）で帰る。 途中、意味値をユーザ定義のアクションや関数で出力すれば、計算の目的が果たせたことになる。