#freeze
[[FrontPage]]
削除しました（removed）

2008/03/14からのアクセス回数 &counter;

#contents

* 第4章　エラー・リカバリ [#hf6d7a8a]
実際のコンパイラでは、記述上の誤りを含んだ入力ファイルを取り扱うことがほとんどであ
る。この章では、入力エラーに対して、いかにしてパーサが十分に対応できるようにするかに
ついて述べる。このため、まず入力エラーを発見した際に、パーサ内で何が起きるかを追跡す
る。結局のところ、パーサとはエラー処理の間、スタックに保存された状態を捨てていくので
ある。しかしながら、yaccでは特別なerror終端記号が存在し、解析アルゴリズムを制御する
ことが可能となっている。4.2節では、パーサがエラーに対してきちんと対応ができるように
なっている場合に何が起きるかを示す。

課題となるのは、言語のルールに対して加えられたフォーミュレーションの中のerror記号
を用いて、エラーに強い文法を形成することである。幸運にも、いかなるエラーをも扱うよう
な方法で、プログラミング言語において頻繁に現われる多くの構成要素を拡張する方法がある。
この手法は4.3節で紹介している。また、4.5節では、どのようにsampleCのためのエラー
に強い解析機構が定義されるか、およびエラー発生時の解析機構の振舞いはどのように示され
るかについて述べる。

** 問題点 [#d2ece98a]
ここまでは、我々のパーサはある文章、すなわち正しい入力ファイルを解析し、処理するよ
うになっていた。3.4節で示した例の1つにおいて、つまり次のような'一'演算子が左優先とし
て定義されている規則、

#pre{{
a - -
}}

に基づいているパーサに対して、正しくない入力、

#pre{{
expression
	: expression '-' expression
	| IDENTIFIER
}}

を与えた場合、どのようなことが起こるのであろうか。yyparse()は、次のようにスタックを捨
てていく。

#pre{{
[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にある場合、その状態遷移行列におけるエラー処理は、次のように導か
れる。

#pre{{
state 3
	expression : expression -_expression

	IDENTIFER  shift 2
	.  error

	expression goto 4
}}

いったんエラー・メッセージが出力されると、yyparse()は何かを見つけ出した場合と同じよう
に、スタックからすべての状態に関する情報を消去してしまう。スタックが処理中にクリアさ
れてしまうので、yyparse()は関数値1を返し、解析作業は入力中の最初のエラーの発生によっ
て失敗してしまう。

** 基本的な解決方法 [#kc96c774]
ここで用いている字句解析機構は、通常、パターン・テーブルの最後に、次のようなエント
リを持っている。

#pre{{
return yytext[0];
}}

このパターンは、1文字で表現されるオペレーションを取り上げるためのものである。しかし、
このエントリはいかなる1文字に対しても、その文字に対応した整数値をyylex()の戻り値と
して返す。つまりその文字がそれ以前のパターンで解析されない限り、終端記号として扱われ
る。

このようにして、予期されない文字は、まるでそれが1文字で表現された正しい終端記号で
あるかのように、字句解析部からパーサに対して渡される。この特徴を利用すると、すべての
入力エラーに対してはある一つの決まった方法で対処することになる。このレベルでの別の解
決方法は、字句解析部で誤1)に関する情報を出力させて、パーサではその情報を無視すること
である。しかしこの方法では、1文字単位にメッセージが出力されるため、その量が多くなっ
てしまう。

記号のレベルでは、入力中に現われる可能性はあっても、それが誤りであるようなフォーミ
ュレーションを文法に加えるという方法がある。この方法を用いると、パーサは言語の設計者
の意図したもの以上に寛容なものとなる。しかしこの方法では、頻繁に起きる利用者のエラー
の大部分を許すことになるので、高い成功確率は望めなくなり、誤まった入力を正確に把握す
ることはほとんど不可能となる。

もっと良い解決方法は、入力エラーを特殊な終端記号として扱うことである。yaccには、こ
の目的のための予約終端記号として、errorが存在する。errorはフォーミュレーションの中で
終端記号と同じように使用できる。しかし、error終端記号は(通常は)字句解析部では作られな
い。その代わりに、パーサは現在の状態に対する状態遷移行列において、実際に入力された次
の終端記号がエラー処理を引き起こす場合に、その終端記号をerrorであると解釈する。このよ
うにしてerror終端記号が内部的に作成され、そのエラーに対するエラー・メッセージが発生す
ると、yyparse()はその後errorを他の終端記号とほとんど同じように受け付ける。

先に示した規則を、次のように修正することを考えてみよう。

#pre{{
expression
	: expression '-' expression
	| IDENTIFIER
	| error
}}

この文法に従ったパーサは、誤った入力を、何のエラー・メッセージも出さずに、受け付け
てしまう。なぜそうなるのかを理解するために、いくつかの例に対する処理の追跡(トレース)
を行なってみよう。yaccは次のようなy.outputファイルを作成する。

#pre{{
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の処理を与える終端記号として表れている点に注意してほしい。

さて、このパーサが誤った入力、

#pre{{
a - - b
}}

に対してどのような反応を示すかを見てみよう。その追跡結果は、パーサが二番目の要素を読
むまで、先にしめしたものと全く同じ処理を行っていることを示している。

#pre{{
[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への遷移が行なわれる。

#pre{{
[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ヘの遷移を促し、最終的に入力からの
'-'記号は受け入れられることになる。その後、すべては通常の状態に戻り、解析は成功する。
#pre{{
[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が通常の終端記号とまったく異なるものとして扱われる理
由である。

#pre{{
a + - b
}}

という入力を解析する場合に、どのような処理か行なわれるかを見てみよう。ここで、'+'は
正当な終端記号とまったく同様に、yylex()から与えられた誤まった文字であり、捨てられなけ
れぱならないものである。

#pre{{
[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への遷移が起きる。

#pre{{
[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()は次の終端記号は捨ててしまい、したがって、この例の場合で言えば、解析が
完了する。

#pre{{
[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
}}

次に、二つのエラーがともに生じる場合を考えてみよう。

#pre{{
a - - b + - c
}}

トレースを行なわない場合、入力、
は、エラー・メッセージを一つしか出力しない。

#pre{{
[error 1] line 1 near "-": expectiong: IDENTIFIER
yyparse() = 0
}}

トレースを行なうと、実際には両方のエラーが認識されていることがわかる。

#pre{{
[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;アクションに関するもっと微妙な例は、以下に示すような、文法の拡張である。

#pre{{
expression
	: expression '-' expression
	| IDENTIFIER
		{ yyerrok; }
	| error
}}

ここで、errorに続いてIDENTIFIERが現われた場合、expressionの右要素を得た状態に戻
ることを仮定すること、そしてその後に続くエラーに対しての報告を行なうようにすることは
意味のあることである。この拡張を行なうことで、先の例に対して二つのエラー・メッセージ
が出力される。

#pre{{
[error 1] line 1 near "-": expection: IDENTIFIER
[error 1] line 1 near "+": expection: '-'
yyparse() = 0
}}

error記号とyyerrok;アクションは、パーサをエラーに対して強力なものにするために・
yaccが備えている特徴である。残された課題はこれらの基本機能を賢明に使用することである。

** error記号の追加 [#dbd8d417]
error記号を置く位置は、次の相反する目標から導かれる。

: できる限り文法記述の開始の記号の近く |
これは、常にそこから回復するためのポイントを設定しておくことである。なぜなら、
errorが受け入れられる状態は、スタック上の低位に存在しなければならないためである。
これによって、パーサが字句解析部からのファイルの終りの報告を受ける前の早い時点で、
スタックをクリアして終了してしまうことになる。

: できる限りおのおのの終端記号の近く |
これは、おのおののエラーで必要最小限の入力が読み飛ばされるためのものである。こ
の機能はyyerrok≡アクションで実現される。

: conflict を起こさないように |
これはきわめて難しいことである。実際、shift/reduce conmctをそのままにしておく
ことは、それらが文字列を長くするために役立つ限り、意義があることである。たとえば・
そのステートメントのレベルで同じエラーを受け入れ、残りの入力を捨ててしまうのでは
なく、エラー後も解析を続けることができる。

これらの目標から、次のようなerror記号の標準的な位置が推薦できる。

- おのおのの再帰的な構成の中に置く、つまりおのおのの繰返しの中に置く。
- フォーミュレーションの最後には置かない方が望ましい。
これによってエラーに強いリカバリ、つまり続行が意味のある部分からのリカバリが可
能となる。errorやyyerrok;アクションを最後に加えることは、エラー・メッセージの連
続出力をもたらすか、あるいはパーサが入力を捨ててしまうことができなければ、ループ
を形成することにもなる。
- 空でないリストは二種類のerrOrを必要とする。一つはリストの先頭で生じる問題に対し
て、もう一つはリストの最後で生じる問題に対してである。
- 空であることもあるリストは、空である場合の解析にerror記号を必要とする。もし、この
リストを形成することが不'可能であるとわかったなら、それが使用されている場所に
error記号を加えなければならない。

次の表は、もっともよく使われる繰返し構造におけるerror記号の位置について、推薦できる
ものを示す。((この繰返し構造の拡張は、ya㏄のバグを明らかにする。(Bell version7やBerkeley4.2bsdやその他のバージョンで)このバグはある状態においてのデフォルトのアクションがreduceであり、次の終端記号がシフトされないが、errorであればシフトされる(たとえば、規則内での最後に加えられているerrOr〕という場合、たとえ次の終端記号がその後シフトされても、yaccのテーブルはリダクションが生じるように生成されてしまう。このような場合、エラー・リカバリは"非常に遅れで"起こり、実際には、パーサはループに陥ってしまったり、誤って何回もルールをリデュースしてしまったりする。4.1bsdでは[Gra79]に基づいたこのバグの修正が含まれている。本質的に、これらの場合には、エラーを検出するために、すべての入力が列挙されなければならない。したがって、パーサのテーブルはきわめて巨大なものとなる。しかし、4.1bsdでの修正は印刷上の誤りを含んでいる。限定的な修正は作者によってなされているlS.Johnson, personal communication.1982)。))

, construct , EBNF , yacc input 
,optional sequence ,x: { y } ,x: /* null */
, ,==,| x y { yyerrok; }
, ,==,| x error
,sequence ,x: y { y } ,x: y
, ,==,| x y { yyerrok; }
, ,==,| error
, ,==,| x error
,list ,x: y { T y } ,x: y
, ,==,| x T y { yyerrok; }
, ,==,| error
, ,==,| x error
, ,==,| x error y { yyerrok; }
, ,==,| x T error


さてここで、この三つの場合についてその例を示す。それぞれの場合で、字句解析機構とし
ては3・5節で示した卓上計算機のために作成したものを利用する。optional sequenceに関す
るエラー・リカバリについては、以下のようなyaccに対する入力を使うと理解できる。

#pre{{
%{
#include <stdio.h>
#define put(x)	printf("%fd ", x)
#define err(x)	fputs("err x ", stdout)
%}
%token	Constant
%%

line
	: /* empty */
	| line optional_sequence '\n'
		{ putchar('\n');
		  yyerrok;
		}

optional_sequence
	: /* empty */
	| optional_sequence Constant
		{ put($2);
		  yyerrok;
		}
	| optional_sequence error
		{ err(1); }

%%

main(argc)
{	extern FILE * yyerfp;

	yyerfp = stderr;	/* separate listings */
	printf("yyparse() = %d\n", yyparse());
}
}}

ここでstderrはエラー・メッセージのためのファイル・ポインタに割り当てられている(3.3
節)。これはエラー・メッセージ出力を、動作した際の出力とは別にするためである。アクショ
ンはこのパーサのリダクションの振舞いを示すように設計されている。入力、


となり、エラー・メッセージは、

#pre{{
10 20

10 +
10 + 20
}}

に対して、出力は

#pre{{
10 20

10 err 1
10 err 1 20
yyparse() = 0
}}

となり、エラー・メッセージは、

#pre{{
[error 1] line 3 near "+": expection: '\n' Constant
[error 2] line 4 near "+": expection: '\n' Constant
}}

となる。すべての終端記号は入力エラーが生じているにもかかわらず、適当にリデュースされ

ている。

もし、sequence が少なくとも一つの要素を含んでいなくてはならない場合、パーサを少し変
更する必要がある。

#pre{{
sequence
	: Constant
		{ put($1); }
	| sequence Constant
		{ put($2);
		  yyerrok;
		}
	| error
		{ err(1); }
	| sequence error
		{ err(2); }
}}

先に示した入力に対して、

#pre{{
10 20
err 1
10 err 2
10 err 2 20
yyparse() = 0
}}

という出力が作成され、空白行に対するエラー・メッセージが増える。

#pre{{
[error 1] line 2: expection: Constant
[error 2] line 3 near "+": expection: '\n' Constant
[error 3] line 4 near "+": expection: '\n' Constant
}}

ここでも、すべての終端記号は適当にリデュースされている。

少なくとも一つの要素を持ち、かつそれぞれの二つの要素の間にデリミタを持つsequence
であるlistの場合は、エラーの生じる可能性がもっと高くなる。

#pre{{
list
	: Constant
		{ put($1); }
	| list ',' Constant
		{ put($3);
		  yyerrok;
		}
	| error
		{ err(1); }
	| list error
		{ err(2); }
	| list error Constant
		{ err(3);
		  put($3);
		  yyerrok;
		}
	| list ',' error
		{ err(4); }
}}


テスト・データは、新しく加わった構造を反映したものとする。

#pre{{
10 , 20

10 +
10 20
10 ,
10 + 20
}}

この入力に対して、出力は、

#pre{{
10 20
err 1
10 err 2
10 err 3 20
10 err 4
10 err 2
yyparse() = 0
}}

エラー・メッセージは、

#pre{{
[error 1] line 2: expection: Constant
[error 2] line 3 near "+": expection: '\n' ','
[error 3] line 4 near "20": expection: '\n' ','
[error 4] line 5: expecting: Constant
[error 5] line 6 near "+": expecting: '\n' ','
}}


となり、いかなる場合にもエラーからの回復が可能なことがわかる。残念なことに、入力、

#pre{{
10 + 20
}}

に対して、ルールが、

#pre{{
list : list error
}}

であった場合、エラー・リカバリはまったく問題なく行なわれるが、list中の二番目の要素は捨
てられてしまう。しかし、もしこのフォーミュレーションを削除してしまった場合、最後の部
分でのエラーに対しては認識が適当に終了することができなくなる。

以上のerror記号の位置に関する提案は、有効な入力記号がいくつかのエラーの状況におい
て無視されることがないことを保証するものではない。しかし、これらの方法は一般的な言語
の構成に対しての非常に強力なパーサを、一定の手順にのっとった、決まりきった手法で実現
することを可能にするので、実際の場では納得できるものである。

** "yyerrok" アクションの追加 [#p5f8456e]
yyerrok;アクションは、そこでフォーミュレーションがerrorで終了し、正式な、しかも重
要な終端記号がそれに続くすべての地点で、終端記号に続けて置かれる。先に述べた繰返し構
造は、すでに重要なアクションを含んでいた。

いったん終端記号がリデュースされてしまうと、その後に続くすべてのエラーが何度でも出
力されてしまうということは、three-symbol-rulesもこれに逆らうものではない。

実際には、いくつかの記号がかなり重要になってくる。たとえば、samp1eCでは次のような
ものである。

#pre{{
sc	;
rp	)
rr	}
}}

コンマは重要とはならない。というのも、繰返し構造においてはコンマはerrorの前に来るか
もしれないし、来ないかもしれないが、いずれにしても、そこで扱われるからである。

これらの重要な終端記号に対しては、単に“終了アクションのための規則"が生成されるの
みである。これは、ちょうどフォーマッタにおいてすべての終端記号をそのように扱ったのと
同じである。




** 例 [#fb95a336]
我々は、1.6節で示されたsamp1eCの文法に、4.3節で規定したように、error記号と
yyerrok;アクションを付け加えた。また、我々は、4.4節で示したように';'や')'や'}'を非終
端記号と置換した。これは、常にこれらの記号に対してyyerrok;アクションを行なうようにす
るためである。これらの変更を行なった入力をyaccに与えると、二つのshift/reduce conf1ict
と二つのreduce/reduce conflictが生じてしまう。y.outputファイルは、以下のように、この
問題を示す。

#pre{{
40: shift/reduce conflict (shift 46, red'n 39) on error
state 40
	compound_statement : { declarations_statements rr
	declarations :  declarations_declaration
	declarations :  declarations_error
	statements : _	(39)

	error  shift 46
	Identifier  reduce 39
		...
	.  error

	declaration  goto 45
	statements  goto 44

53: reduce/reduce conflict (red'ns 41 and 56) on error
53: reduce/reduce conflict (red'ns 41 and 56) on ;
state 53
	statements :  statements error_	(41)
	expression :  error_	(56)

	.  reduce 56
	.  reduce 41
83: shift/reduce conflict (shift 115, red'n 49) on ELSE
state 83
	statements :  if_prefix statements_	(4)
	statements :  if_prefix statements_ELSE statement

	ELSE  shift 115
	. reduce 49
}}

state 38 での shift/reduce conflict は、declarations と statements がともに optional
sequence であることから生じているものである。つまりこれらの要素が存在しなくても良く、一つ
の error から成りなっていても良く、さらに前後に error が存在しても良い。もし、この conflict
を受け入れるなら、これは declarations を可能な限り拡張することとなるが、それは望ましい
ことである。

他の shift/reduce conflict は、文法がもともと持っていた "dangling else 問題”(1.5 節の
「一般的な落とし穴」参照）である。残りの二つの reduce/reduce conflict は、expression の
終わりを検出できないことによるものである。ここで、

#pre{{
expression
	: error
}}
を
#pre{{
expression
	: error ',' binary
	| error binary
}}
と交換すると、意図したとおりに reduce/reduce conflict は消えるが、新たに五つの shift/reduce
conflict が生じてしまう。y.output は、以下のような結果を示す。

#pre{{
53: shift/reduce conflict (shift 66, red'n 41) on Identifier
53: shift/reduce conflict (shift 67, red'n 41) on Constant
53: shift/reduce conflict (shift 68, red'n 41) on (
53: shift/reduce conflict (shift 69, red'n 41) on PP
53: shift/reduce conflict (shift 70, red'n 41) on MM
state 53
	statements :  statements error_	   (41)
	expression :  error_, binary
	expression :  error_binary

	Idnetifier  shift 66
	Constant  shift 67
	(  shift 68
	PP  shift 69
	MM  shift 70
	.  shift 75
	.  reduce 41

	binary  goto 76
}}


binaryに先立って終端記号が存在しても良く、かつexpressionのためのすべての適切なフ
ォーミュレーション内にはコンマの存在を許すべきである。また、argument_liStとの類似性か
ら見ても、これらのshift/reduceconflictは消去することができる。
最終的に、効率を考えて、いくつかの場所にerror記号を追加する。

#pre{{
if_prefix
	: IF error

loop_prefix
	: WHILE error

binary
	: '(' error rp
}}

このような効率化のための調整を行なう別の方法は、return 文にすることであろう・

エラー・リカバリがうまく働くことを示すために、我々はerror記号を含んだ各ルールに対し
てアクションを加えた。その文法の変更部分を以一下に示す。

#pre{{
/*
 *	sample C
 *	syntax analysis with error recovery
 *	(s/r conflicts: one on ELSE, one on error)
 */

%{
#define ERROR(x) yywhere(), puts(x)
%}

/*
 *	terminal symbols
 */

/*
 *	precedentce table
 */

%%

program
	: definitions

definitions
	: definition
	| definitions definition
		{ yyerrok; }
	| error
		{ ERROR("definitions: error"); }
	| definitions error
		{ ERROR("definitions: definitions error"); }

definition

function_definition
	: Identifier '(' optional_parameter_list ')'
	| parameter_declarations compound_statement

optional_parameter_list

parameter_list
	: Identifier
	| parameter_list ',' Identifier
		{ yyerrok; }
	| error
		{ ERROR("parm_list: error"); }
	| parameter_list error
		{ ERROR("parm_list: parm_list error"); }
	| parameter_list error Identifier
		{ ERROR("parm_list: parm_list error Id");
		  yyerrok;
		}
	| parameter_list ',' error
		{ ERROR("parm_list: parm_list ',' error"); }

parameter_declarations
	: /* null */
	| parameter_declarations parameter_declaration
		{ yyerrok; }
	| parameter_declarations error
		{ ERROR("parm_decls: parm_decls error"); }
	

parameter_declaration
	: INT parameter_declarator_list sc

parameter_declarator_list
	: Identifier
	| parameter_declarator_list ',' Identifier
		{ yyerrok; }
	| error
		{ ERROR("parm_decl_l: error"); }
	| parameter_declarator_list error
		{ ERROR("parm_decl_l: parm_decl_l error"); }
	| parameter_declarator_list error Identifier
		{ ERROR("parm_decl_l: parm_decl_l error Id");
		  yyerrok;
		}
	| parameter_declarator_list ',' error
		{ ERROR("parm_decl_l: parm_decl_l ',' error"); }

compound_statement
	: '{' declarations statements rr

declarations
	: /* null */
	| declarations declaration
		{ yyerrok; }
	| declarations error
		{ ERROR("declarations: declarations error"); }

declaration
	: INT declarator_list sc

declarator_list
	: Identifier
	| declarator_list ',' Identifier
		{ yyerrok; }
	| error
		{ ERROR("decl_list: error"); }
	| declarator_list error
		{ ERROR("decl_list: decl_list error"); }
	| declarator_list error Identifier
		{ ERROR("decl_list: decl_list error Id");
		  yyerrok;
		}
	| declarator_list ',' error
		{ ERROR("decl_list: decl_list ',' error); }

statements
	: /* null */
	| statements statement
		{ yyerrok; }
	| statements error
		{ ERROR(statements: statements error"); }

statement
	: expression sc
	| sc
	| BREAK sc
	| CONTINUE sc
	| RETURN sc
	| RETURN expression sc
	| compound_statement
	| if_prefix statement
	| if_prefix statement ELSE statement
	| loop_prefix statement

if_prefix
	: IF '(' expression rp
	| IF error
		{ ERROR("if_prefix: IF error"); }

loop_prefix
	: WHILE '(' expression rp
	| WHILE error
		{ ERROR("loop_prefix: WHILE error"); }

expression
	: binary
	| expression ',' binary
		{ yyerrok; }
	| error ',' binary
		{ ERROR("expression: error ',' binary"); }
		  yyerrok;
		}
	| expression error
		{ ERROR("expression: expression error"); }
	| expression ',' error
		{ ERROR("expression: expression ',' error"); }

binary
	: Identifier
	| Constant
	| '(' expression rp
	| '(' error rp
		{ ERROR("binary: '(' error ')'"); }
	| Identifier '(' optional_argument_list rp
	| PP Identifier
	| MM Identifier
	| binary '+' binary
	| binary '-' binary
	| binary '*' binary
	| binary '/' binary
	| binary '%' binary
	| binary '>' binary
	| binary '<' binary
	| binary GE binary
	| binary LE binary
	| binary EQ binary
	| binary NE binary
	| binary '&' binary
	| binary '^' binary
	| binary '|' binary
	| Identifier '=' binary
	| Identifier PE binary
	| Identifier ME binary
	| Identifier TE binary
	| Identifier DE binary
	| Identifier RE binary

optional_argument_list

argument_list
	: binary
	| argument_list ',' binary
		{ yyerrok; }
	| error
		{ ERROR("arg_list: error"); }
	| arguments_list error
		{ ERROR("arg_list: arg_list error"); }
	| argument_list ',' error
		{ ERROR("arg_list: arg_list ',' error"); }

/*
 *	make certain terminal symbols very important
rp	: ')'	{ yyerrok; }
sc	: ';'	{ yyerrok; }
rr	: '}'	{ yyerrok; }
}}

以下に示す入力ファイルは、この文法によって導かれるエラー・リカバリ機構の検査を行う。

#pre{{
f1() { }
char x; /* 2: bad definition */
char y; /* this one is swallowed -- no yyerrok */

f2() { }	/* this si parsed again */

f3(a,
	int,	/* 7: bad parameter */
	c) { }

f4(int		/* 10: bad parameter */
	) { }

f5(a, b)
	int a;
	while; /* 15: bad declaration */
	int b;
	{ }

int a,
	while,	/* 20: bad declarator */
	b;

f6() {
	break	/* 24: bad statments */
	break;
	return;
	}

f7() {
	a,
	int,	/* 31: bad expression */
	b;
	}

f8() {
	f7(a,
	int,	/* 37: bad argument */
	b);
	}
}}

この入力に対して、次のような結果が得られる。

#pre{{
[error 1] line 2 near "x": expection: '('
line2 near "x": definitions: definitions error
line2 near ";": definitions: definitions error
line3 near "y": definitions: definitions error
line3 near ";": definitions: definitions error
[error 2] line 8 near "int": expection: Identifier
line 8 near "int": parm_list: aprm_list ',' error
[error 3] line 11 near "int": expecting: Identifier
line 11 near "int": parm_list: error
[error 4] line 16 near "while": expectiong: '{' INT
line 16 near "while": parm_decls: parm_decls error
[error 5] line 21 near "while": expecting: Identifier
line 21 near "while": decl_list: decl_list ',' error
[error 6] line 26 near "break": expecting: ';'
line 26 near "break": statements: statements error
[error 7] line 32 near "int": expecting: '(' Ident. Const. PP MM
line 32 near "int": expression: expression ',' error
[error 8] line 38 near "int": expecting: '(' Ident. Const. PP MM
line 38 near "int":arg_list: arg_list ',' error
}}

結果からわかる通り、いくつかの関連して生じるエラーについては、その個々の内容が報告される
ことはない。

** 問題 [#n4669927]
+ 4.5節で示されたバージョンのsampleCに対して、errorを含んでいる各フォーミュレーション
を検査するために用いられるような入力ファイルを作成せよ。
+ 例の中では定義中のいくつかのエラーが一つのものとして報告されている。これはどの
ようにして生じるのか? 適当なエラーを含んだ入力ファイルを使って、自分の考えを確
記せよ。
+ 3.5節で示した卓上計算機の例に、エラー・リカバリ機能を加えよ。また3.8節の問題
1で作成した自分自身の例に対して、エラー・リカバリ機能を加えよ。
ヒント:行のレベルでの基本的な手法は4.3節に示されている。式のレベルでのエラ
一・リカバリ機能の追加は、行のレベルよりはむずかしくなる。
+ 問題3の式について用いた手法を、sampleCのためのエラー・リカバリ機能にまとめ
よ。
+ 問題3の卓上計算機を、なんらかのエラーの後で、利用者からの正しい入力を促すよう
に修正せよ。
ヒント:yyerrok;ステートメントの位置には特に注意しなくてはならない。というの
は、パーサが元の入力行のエラーに対しての反応を示す際に、その一部として再入力され
た行の一部を捨ててしまうことを防がなくてはならないからである。
+ 1.8節の問題1にあるPascal subsetの文法にエラー・リカバリ機能を加えよ。適当な誤
ったPascalのコードを含んだ入力ファイルを与えて、作成した文法の正当性を検査せよ。

** コメント [#r6ef53e9]
この記事は、

#vote(おもしろかった,そうでもない,わかりずらい)

皆様のご意見、ご希望をお待ちしております。

#comment_kcaptcha
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
SmartDoc