![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
2008/03/14からのアクセス回数 8803
実際のコンパイラでは、記述上の誤りを含んだ入力ファイルを取り扱うことがほとんどであ る。この章では、入力エラーに対して、いかにしてパーサが十分に対応できるようにするかに ついて述べる。このため、まず入力エラーを発見した際に、パーサ内で何が起きるかを追跡す る。結局のところ、パーサとはエラー処理の間、スタックに保存された状態を捨てていくので ある。しかしながら、yaccでは特別なerror終端記号が存在し、解析アルゴリズムを制御する ことが可能となっている。4.2節では、パーサがエラーに対してきちんと対応ができるように なっている場合に何が起きるかを示す。
課題となるのは、言語のルールに対して加えられたフォーミュレーションの中のerror記号 を用いて、エラーに強い文法を形成することである。幸運にも、いかなるエラーをも扱うよう な方法で、プログラミング言語において頻繁に現われる多くの構成要素を拡張する方法がある。 この手法は4.3節で紹介している。また、4.5節では、どのようにsampleCのためのエラー に強い解析機構が定義されるか、およびエラー発生時の解析機構の振舞いはどのように示され るかについて述べる。
ここまでは、我々のパーサはある文章、すなわち正しい入力ファイルを解析し、処理するよ うになっていた。3.4節で示した例の1つにおいて、つまり次のような'一'演算子が左優先とし て定義されている規則、
a - -
に基づいているパーサに対して、正しくない入力、
expression : expression '-' expression | IDENTIFIER
を与えた場合、どのようなことが起こるのであろうか。yyparse()は、次のようにスタックを捨 てていく。
[yydebug] push state 0 [yydebug] reading IDEINTIFIER [yydebug] push state 2 [yydebug] reduce by (2), uncover 0 [yydebug] push state 1 [yydebug] reading '-' [yydebug] push state 3 [yydebug] reading '-' [error 1] line 1 near "-": expecting IDENTIFIER [yydebug] recovery pops 3, uncovers 1 [yydebug] recovery pops 1, uncovers 0 [yydebug] recovery pops 0, stack is empty yyparse() == 1
2番目の'-'がstate3にある場合、その状態遷移行列におけるエラー処理は、次のように導か れる。
state 3 expression : expression -_expression IDENTIFER shift 2 . error expression goto 4
いったんエラー・メッセージが出力されると、yyparse()は何かを見つけ出した場合と同じよう に、スタックからすべての状態に関する情報を消去してしまう。スタックが処理中にクリアさ れてしまうので、yyparse()は関数値1を返し、解析作業は入力中の最初のエラーの発生によっ て失敗してしまう。
ここで用いている字句解析機構は、通常、パターン・テーブルの最後に、次のようなエント リを持っている。
return yytext[0];
このパターンは、1文字で表現されるオペレーションを取り上げるためのものである。しかし、 このエントリはいかなる1文字に対しても、その文字に対応した整数値をyylex()の戻り値と して返す。つまりその文字がそれ以前のパターンで解析されない限り、終端記号として扱われ る。
このようにして、予期されない文字は、まるでそれが1文字で表現された正しい終端記号で あるかのように、字句解析部からパーサに対して渡される。この特徴を利用すると、すべての 入力エラーに対してはある一つの決まった方法で対処することになる。このレベルでの別の解 決方法は、字句解析部で誤1)に関する情報を出力させて、パーサではその情報を無視すること である。しかしこの方法では、1文字単位にメッセージが出力されるため、その量が多くなっ てしまう。
記号のレベルでは、入力中に現われる可能性はあっても、それが誤りであるようなフォーミ ュレーションを文法に加えるという方法がある。この方法を用いると、パーサは言語の設計者 の意図したもの以上に寛容なものとなる。しかしこの方法では、頻繁に起きる利用者のエラー の大部分を許すことになるので、高い成功確率は望めなくなり、誤まった入力を正確に把握す ることはほとんど不可能となる。
もっと良い解決方法は、入力エラーを特殊な終端記号として扱うことである。yaccには、こ の目的のための予約終端記号として、errorが存在する。errorはフォーミュレーションの中で 終端記号と同じように使用できる。しかし、error終端記号は(通常は)字句解析部では作られな い。その代わりに、パーサは現在の状態に対する状態遷移行列において、実際に入力された次 の終端記号がエラー処理を引き起こす場合に、その終端記号をerrorであると解釈する。このよ うにしてerror終端記号が内部的に作成され、そのエラーに対するエラー・メッセージが発生す ると、yyparse()はその後errorを他の終端記号とほとんど同じように受け付ける。
先に示した規則を、次のように修正することを考えてみよう。
expression : expression '-' expression | IDENTIFIER | error
この文法に従ったパーサは、誤った入力を、何のエラー・メッセージも出さずに、受け付け てしまう。なぜそうなるのかを理解するために、いくつかの例に対する処理の追跡(トレース) を行なってみよう。yaccは次のようなy.outputファイルを作成する。
state 0 $accept : _expression $end error shift 3 IDNETIFIER shift 2 . error expression goto 1 state 1 $accept : expression_$end expression : expression_- expression $end accept - shift 4 . error state 2 expression : IDENTIFIER_ (2) . reduce 2 state 3 expression : error_ (3) . reduce 3 state 4 expression : expression -_expression error shift 3 IDENTIFIER shift 2 . error expression goto 5 state 5 expression : expression_- expression expression : expression - expression_ (1) . reduce 1
errorが、処理としていくつかの状態に表れている点、また state 0とstate 4では、遷移行 列においてshift 3の処理を与える終端記号として表れている点に注意してほしい。
さて、このパーサが誤った入力、
a - - b
に対してどのような反応を示すかを見てみよう。その追跡結果は、パーサが二番目の要素を読 むまで、先にしめしたものと全く同じ処理を行っていることを示している。
[yydebug] push state 0 [yydebug] reading IDEINTIFIER [yydebug] push state 2 [yydebug] reduce by (2), uncover 0 [yydebug] push state 1 [yydebug] reading '-' [yydebug] push state 3 [yydebug] reading '-' [yydebug] push state 4 [yydebug] reading '-' [error 1] line 1 near "-": expecting IDENTIFIER
state4にいる状態で・新しい'-'はエラー処理を引き起こす。これまでに見てきたように、 yyparse()はここで・次の終端書己号がerrorであると仮定する。遷移行列は、error終端記号は 受け入れられるべきであることを規定し、状態はstate 3に遷移する。
処理の流れは、y.outputに示された遷移行列によって追うことができる。state3ではリダク ションが可能であり、expressionはerrorからでも扱うことが可能である。そのため、スタッ ク上に示されたstate 4からstate 5への遷移が行なわれる。
[yydebug] reduce by (3), uncover 4 [yydebug] push state 5 [yydebug] reduce by (1), uncover 0 [yydebug] push state 1 [yydebug] push state 4
別のリダクションが可能になるため、スタック上でstate Oへの遷移が行なわれる。また、リデ ュースされたexpressionに対するgoto処理はstate 1ヘの遷移を促し、最終的に入力からの '-'記号は受け入れられることになる。その後、すべては通常の状態に戻り、解析は成功する。
[yydebug] reading IDEINTIFIER [yydebug] push state 2 [yydebug] reduce by (2), uncover 4 [yydebug] push state 5 [yydebug] reduce by (1), uncover 0 [yydebug] push state 1 [yydebug] reading [end of file] yyparse() == 0
この場合、実際にはエラー・リカバリは、入力中の二つの'一'記号の間にerror記号を挿入す ることから成立している。これによって入力は拡張された文法規則によって解析されるように なった。しかし、以上に見てきたことがすべてではない。ある場合には、エラー・リカバリの 機構は、処理を続行するために、入力された記号を捨ててしまうことも必要である。これが、 yaccとyyparse()において、errorが通常の終端記号とまったく異なるものとして扱われる理 由である。
a + - b
という入力を解析する場合に、どのような処理か行なわれるかを見てみよう。ここで、'+'は 正当な終端記号とまったく同様に、yylex()から与えられた誤まった文字であり、捨てられなけ れぱならないものである。
[yydebug] push state 0 [yydebug] reading IDEINTIFIER [yydebug] push state 2 [yydebug] reduce by (2), uncover 4 [yydebug] push state 1 [yydebug] reading '+' [error 1] line 1 near "+": expectiong '-'
今度はState1において問題が生じる。ここでも内部的にerror記号が作成されるが、その作成 は、state4のような状態ではなく、その遷移行列がerror記号に対してのエラー処理を含んで いるstate1で行なわれる。(y-outputでは'.'は“その他のすべての記号"を表現している。)
この状態で、yyparse()はスタックをポップする。スタック.上では、en・or記号を受け付ける ことが可能な状態が深される。もし、そのような状態がスタック上に存在しなければ、すなわ ち・error記号を次の記号として受け付けることのできるような状態の定義がそれまでになさ れていなければ、yyparse()はすべてのスタックをクリアし、関数値を１として終了する。
この例では、"幸運なことに"、スタック上にはstate Oが存在し、この状態でerror記号が受 け付けられる。ここでもstate 3への遷移が起こり、expressionが作成され、state Oへの回帰 が生じ、expressionを伴ってstate 1への遷移が起きる。
[yydebug] recovery pops 1, uncovers 0 [yydebug] acceptiong $error [yydebug] push state 3 [yydebug] reduce by (3), uncover 0 [yydebug] push state 1
これによると、何も特別なことは生じなかったかのように見える。もう一度state 1という状態 になったとしても、'+'は再び次の終端記号として受け付けられる。しかし、yyparse()は最後 のエラーからシフト処理がまったく行なわれていないことを記憶している。ループを避けるた めに、yyparse()は次の終端記号は捨ててしまい、したがって、この例の場合で言えば、解析が 完了する。
[yydebug] recovery discards "+' [yydebug] reading '-' [yydebug] push state 4 [yydebug] reading IDEINTIFIER [yydebug] push state 2 [yydebug] reduce by (2), uncover 4 [yydebug] push state 5 [yydebug] reduce by (1), uncover 0 [yydebug] push state 1 [yydebug] reading [end of file] yyparse() == 0
次に、二つのエラーがともに生じる場合を考えてみよう。
a - - b + - c
トレースを行なわない場合、入力、 は、エラー・メッセージを一つしか出力しない。
[error 1] line 1 near "-": expectiong: IDENTIFIER yyparse() = 0
トレースを行なうと、実際には両方のエラーが認識されていることがわかる。
[yydebug] push state 0 [yydebug] reading IDEINTIFIER ... [yydebug] reading '-' [error 1] line 1 near "-": expectiong: IDENTIFIER [yydebug] acceptiong $error ... [yydebug] reading '+' [error 1] recovery pops 1, uncovers 0 [yydebug] acceptiong $error ... [yydebug] recovery discards '+' ... yyparse() = 0
エラー・メッセージが連続して出力されることを防ぐために、パーサは別のエラーによるエラ ー・メッセージの出力が行なわれる前に、エラーの生じた部分の前で三つの終端記号をシフト しなくてはならない。このようにして、ひとかたまりのエラーは一つのエラー・メッセージと なる。この例では、二番目のエラー・メッセージが出力されない。 yyerrok;アクションを用いると、パーサは必要な終端記号を適切に受け入れることが可能に なり、きわめて近接したエラーに対しても、それぞれについてエラー・メッセージを出力する ことができるようになる。
しかし、ここには欠点が存在する。もしyyerrok;アクションがerrorのみから成立している
フォーミュレーションにアクションとして付け加えられた場合には、yyparse()はただちに必 要な終端記号がシフトされたものと言忍識し、誤った人力記号を捨てなくなってしまう。
yyerrok;アクションに関するもっと微妙な例は、以下に示すような、文法の拡張である。
expression
: expression '-' expression
| IDENTIFIER
{ yyerrok; }
| error
ここで、errorに続いてIDENTIFIERが現われた場合、expressionの右要素を得た状態に戻 ることを仮定すること、そしてその後に続くエラーに対しての報告を行なうようにすることは 意味のあることである。この拡張を行なうことで、先の例に対して二つのエラー・メッセージ が出力される。
[error 1] line 1 near "-": expection: IDENTIFIER [error 1] line 1 near "+": expection: '-' yyparse() = 0
error記号とyyerrok;アクションは、パーサをエラーに対して強力なものにするために・ yaccが備えている特徴である。残された課題はこれらの基本機能を賢明に使用することである。
この記事は、
皆様のご意見、ご希望をお待ちしております。
