Left-toright parse, Rightmost-derivation, k-token lookahead

左から読んでいき、最右導出で解析していく

LR(k)法はk個のTokenを先読みして、「生成規則の右辺全体」に一致する入力トークンを走査し終わるまで、決定を延期する

多くのプログラミング言語はLR法で解析できる

C++とPerlは無理らしい ref

なんで #??

嬉しいところ

効率が良い

左から右へ読んでいくものの中では構文エラーを素早く検出できる

欠点

LL法に比べエラーメッセージを適切に出しにくい

以下の3つより構成される

入力

parserの入力にあたるToken列のこと

ex. [a,+,b,*,c,$]

スタック

つまりなに #??

状態と記号を交互に積む

s_0,X_1,s_1,X_2,s_2,\cdots,X_m,s_m

sは状態に対応した終端記号

普通に入力の一文字のこと？

ちがう

終端記号と非終端記号

これは微妙に流派があり、状態は積まないものもある

Wikiとか

積んだもののほうがわかりやすいと思う

以下の2つの動作で構文解析を実行する

参考

タイガーブック p.50~