構文解析アルゴリズム

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

構文解析アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/11/21 17:57 UTC 版)

「LR法」の記事における「構文解析アルゴリズム」の解説

LR法のアルゴリズムは次のように動作する: スタックは [0] で初期化される。現在状態は常にスタックのトップにある状態で表される。 現在状態と入力にある記号からアクション表を参照する。ここで4つのケースがある:sn に従って状態遷移する。現在の終端記号を入力ストリームから取り除く。 状態 n をスタックにプッシュし、それを現在状態とする。 rm に従って文法規則を適用する。番号 m を出力ストリームに書き出す。 m 番の規則の右側にある各記号についてスタックから状態を削除する（例えば E * B なら3個ポップする）。 その時点のスタックのトップを状態とし、それと m 番の文法規則の左側からGOTO表を参照し、そこにある状態をスタックにプッシュして新たな状態とする。 受容の場合、文字列の構文解析が完了。 アクションが指定されていない場合、文法エラーを報告する。 上のステップを「受容」となるか「文法エラー」となるまで繰り返す。 このアルゴリズムが何故うまく動作するのかを説明するため、文字列 "1 + 1" をこの構文解析器で解析する例を示す。下記の表はその処理の各ステップを示したものである。状態はスタックのトップで示されている（一番右の値）。次のアクションは上にあるアクション表を参照して決めている。また、入力の最後を示すため、 $ が追加されている。 状態入力ストリーム出力ストリームスタック次のアクション0 1+1$ [0] Shift 2 2 +1$ [0,2] Reduce 5 4 +1$ 5 [0,4] Reduce 3 3 +1$ 5,3 [0,3] Shift 6 6 1$ 5,3 [0,3,6] Shift 2 2 $ 5,3 [0,3,6,2] Reduce 5 8 $ 5,3,5 [0,3,6,8] Reduce 2 3 $ 5,3,5,2 [0 3] Accept 構文解析を開始したとき、常に状態 0 から始まる。スタックは次のようになっている: [0] 構文解析器が最初に見る入力記号は '1' であり、アクション表を参照すると状態 2 への遷移が指示されているので、スタックが次のようになる: [0 '1' 2] スタックのトップは右端である。なお、説明のために状態遷移の原因となった記号（ここでは '1'）をその前に記している。もちろん、本当のスタックにはこのような記号はプッシュされない。 状態 2 ではアクション表によれば、次の入力記号が何であれ、5 番の文法規則を適用しなければならない。これはつまり、5 番の規則の右辺を認識したことを示す。そこで、出力ストリームに 5 を書き出し、スタックから1個の状態をポップし、GOTO表から（状態 0 で非終端記号 B）状態 4 をスタックにプッシュする。結果としてスタックは次のようになる: [0 B 4] 状態 4 の場合、アクション表を見ると文法規則 3 番の適用をしなければならない。そこで出力ストリームに 3 を書き出し、スタックから1個の状態をポップして、GOTO表から（0、E）状態 3 を新たにプッシュする。スタックは次のようになる: [0 E 3] 次の入力記号を見ると '+' であり、アクション表によれば状態 6 に遷移しなければならない。 [0 E 3 '+' 6] このスタックは有限オートマトンの動作履歴のようなものであり、現在は非終端記号 E を読んだ直後に終端記号 '+' を読んだ状態を示している。このオートマトンの状態遷移表はアクション表の shift 指定と GOTO表から構成される。 次の入力記号は '1' なので、アクション表から状態 2 への遷移となる: [0 E 3 '+' 6 '1' 2] 前に '1' を読んだときと同様、文法規則の適用により B に還元され、スタックは次のようになる: [0 E 3 '+' 6 B 8] これは有限オートマトンが、非終端記号 E と 終端記号 '+' と 非終端記号 B を順に読んだ状態である。状態 8 では常に規則 2 番を適用する。従ってスタック上の3個の状態がその文法規則の右辺の3個の記号に対応する。 [0 E 3] 最後に '$' を入力ストリームから読むと、現在状態は 3 なので「受容」すなわち構文解析完了である。以上から出力ストリームに書かれる規則番号の列は [5, 3, 5, 2] となる。これは "1 + 1" という文字列を右端導出する際の適用規則列を逆転させたものと同じである。