衝突・構文エラーの解決ノウハウ

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

衝突・構文エラーの解決ノウハウ

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

「Yacc」の記事における「衝突・構文エラーの解決ノウハウ」の解説

Yacc実行時になんらかの衝突が報告されるとき、および、上記パーサ実行時に正しいはずの入力がsyntax errorとなるときの主な対処方法には、次のようなものがある。 syntax error発生時に少なくともそのときのトークン値、状態スタック中の状態番号列およびソースファイル上の行番号・文字番号を出力するように作っておくことで、正確な調査を可能にする。 ある非終端記号から別の非終端記号に至る呼び出しパスが複数あれば、それは間違いなので直す（前述）。 「トークンまたは空である」といった非終端記号をひとつの構文右辺の中に複数並べることによって、衝突が生じていることがある。ひとつの右辺の中には省略のないトークンだけを使うようにする。そして、省略する、しないのすべての組合せは、右辺の種類として列挙してOR（|）結合する形に変更する。人間には等価ないし汚くなるように思えても、Yaccにとっては明瞭化になる。 リストのリストは、繰り返し要素にinなどの接頭辞的なトークンが伴わない定義などでは、要素がどの段階のリストに属するのかという曖昧性を生じる。この場合、リストの段階数を減らすように工夫して明瞭化する。 問題の非終端記号を使う場面ごとに、元が同じ文字列でも別のトークンから構成するように、定義を変更して明瞭化する。そのためにそのトークンを上述のようにLex段階で、場面に応じて変換し分ける。 パーサ実行時の期待外トークンで、あるトークンが複数の場面でどう絡んでいるかを調べるには、y.outputファイルでその状態番号を見つけて熟読し、その状態番号へ飛んでくる状態を1, 2段階さかのぼってたどってみると見えてくるものである。y.outputにはまた、状態番号に対して衝突種類、トークンに対して実行されないアクションを囲むカッコ「[ ]」が出力されているので、場所や影響が分かる。 原因調査が難航している場合は、問題のある文法要素の周辺の定義だけを抽出した“ミニ文法”をYacc定義し、障害がぎりぎり再現する境目を探しすことで切り分けるアプローチもある。 混乱を招いているトークンを含む連続した2個以上のトークンを、Lex段階で1個の別トークンにまとめて明瞭化する。 上記場面がパーサのシフトや還元の状態だけでは記述しきれないとき、Lex段階でその場面を識別するための内部状態をもち、はいってくるトークンを見ながら状態遷移することで問題の箇所を検出する。そして、検出時には別のトークンに変更して出したり、特別なトークンを挿入することで明瞭化する。 上記明瞭化の努力によって、Bison実行で報告される衝突数が減少した場合は、効果が出ている場合が多いが、減少しなくても、特定の入力に対しての処理がエラーから正常に変わって改善している場合もある。増加した場合は逆効果として調べる必要がある。 入力言語があまりに複雜な場合、またはプリプロセッサ命令を含んでいる場合、パースを2段階の直列構成にするという大胆な解決策もある。すなわち、1段階めの前処理Yaccパーサは曖昧性を解決するだけのための簡単な文法で動く。その出力の曖昧性を解決したトークン列を2段階めの本処理Yaccパーサに渡す。3段以上にすることが有効な場合もあろう。文法の性格によっては、この構成にすることで、むしろそれぞれをすっきりさせることができる（エラー位置の表示処理は複雜になる）。