曖昧な文法への対処

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

曖昧な文法への対処

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

「Yacc」の記事における「曖昧な文法への対処」の解説

この方式では、次の有名な例のように、同じ入力を同じ構文規則で複数の解釈ができてしまう曖昧性が避けられない。 /* stmt2って一体どっちのIFが不成立のときに実行したいの？ */ IF expr1 IF expr2 stmt1; ELSE stmt2; Yaccではyaccコマンド実行時に解釈が複数生じる曖昧なケースを発見した場合に「還元／還元衝突警告」または「シフト／還元衝突警告」を出す。これによって、文法を作成中なら文法を、そうでなければ構文規則を改良するきっかけが得られる。 まず「還元／還元衝突警告」が出た場合であるが、パーサが正しい処理をできない構文要素が生じてしまうので、文法、または構文規則のYacc定義を直した方がよい。 ある非終端記号から別の非終端記号に至る呼び出しパスが複数あれば、それは間違いなので直す。 しかし元の言語が複雜すぎてうまく直せない場合は、片方を実体は同じでも別の名前を付けるトークン由来で構成するようにし、Lex側がどちらのトークンをYaccパーサに出すかは状態に応じて変えるようにコーディングしておく方法がある： 状態がトークン列だけから一意に決められるならLex単独で処理できる。しかし、Yaccが実行時にあるルールのマッチを検出したときにはじめて状態を変えたいという複雜なケースでは、次のようにする。LexとYaccで共通の状態変数を設けておき、Yaccの{ }内に記述するアクションで、区別したい何かのフェーズなどの状態に応じて状態変数値を変えてやる。そうすればLexの生成したレキシカルアナライザは、実行時にまさに読んでいる入力トークン列による状態変数値に応じて、ある入側トークンを別々のトークンに動的に変換し分けてYaccの生成したパーサに渡す、という方法である。非常にダイナミックな技である。 次に「シフト／還元衝突」であるが、このときYaccは標準で、（特に演算子優先規則で指定されていないかぎり）シフトを選ぶようにできている。たとえば上記の例ではexpr2不成立のときにstmt2を実行するようにパーサのテーブルが作られる。このように距離の近い記号の関係を優先するよう動作するのは、多くのプログラミング言語のコンパイラに向いているといわれているが、後述のように注意が必要である。 構文上期待外のトークンがくるとアクションが見つからないので、パーサは、状態を戻して、errorという特定トークンのアクションがその状態に定義されているかどうか調べ、あれば実行する。最大3回まで戻しても見つからないときには入力テキストが途中でもそこでパースを打ち切ってしまう。これを利用してたとえば命令リストにerrorトークンのみの右辺をOR（|）結合しておけば、ある命令に属するオペランドに期待外トークンがあっても、そこで警告を出して次の命令以降のパースを続行してくれる、使いやすいコンパイラを作ることができる。ただ最大3回固定なので、深さの差3以内の上位にerrorを処理する構文を書いておかなければ利用できない。またはy.tab.cファイルの変数yyerrstatusの初期値を10などと増やしてやる必要がある。 Yacc実行時に報告されるシフト／還元衝突は、シフトが選ばれるだけで十分と確信できるケース以外は、実は本来0件にしておくべきである。なぜならパーサ実行時にシフトが選ばれて動作することにより、入力されたトークン列によっては行き止まりになる。すなわち期待外のトークンとされ、上記のエラー処理に飛んでしまうからである。Yaccは衝突に対応する枝分かれをすべてバックトラックでたどって解空間を全探索するようにはできていないのである。このため、衝突を残しておくとパーサを当然通ると思った入力が通らず苦労することになる。