- 上向き構文解析法では原始プログラムを左から右へと走査しながら、還元できるものを順次還元していく方法である
- 還元した結果はスタックに積んでおいて、スタックの中に還元できるものがそろったら、それを置き換える
- 還元できなければ、原始プログラムの次のトークンを読んでそれをスタックに積む。これをシフトという
- LR構文解析では、スタックに文法記号だけでなくLR状態と呼ばれるものを積んでおき、スタックの先頭のLR状態と原始プログラムの次の終端記号の組によって、シフトか還元かを決定する
- 文法Ｇ＝｛Ｐ，Ｓ｝のLR(0)項とは、Ｐの任意の生成規則に対して、その右辺の左端、右端および終端記号または非終端記号の間、のどれか１カ所に「・」を付けたものである。
- LR(0)項のうち、最後の記号の後ろに「・」が付いたときは、今までに読んだものを還元する状態である。これを還元状態とよぶ。還元状態にはそれをはっきり区別するために特別な記号「＃」を最後に付けることにする。例えばＡ→ｘｙｚ・＃。
- 文法ＧのLR(0)項の集合Iの閉包closure(I)とは次のようにして得られるものである
- closure(I)=I
- Ａ→α・Ｂβ∈closure(I)に対して、Ｂ→γという生成規則があればＢ→・γをclosure(I)に加える
- 上記２を新たに加えるものが無くなるまで繰り返す
- LR(0)項の集合Ｉから終端記号または非終端記号Ｘによって遷移する先をGOTO(I,X)と表す
- 次に還元することが可能だが、次の文字によってはシフトをしなければならない場合がある。これをシフト／還元競合という。この解決の方法によってＳＬＲやＬＡＬＲ、ＬＲなどの構文解析手法が分かれる
- LR構文解析は最右導出の逆の操作をしていることになる
- 競合を解決するためにFollow集合を使うのがSLR(1)構文解析であり、Follow集合だけで解決できる文法がSLR(1)文法である
- どの組み合わせの時にどの動作を取るかを記述した表と、さらに還元した後の遷移先を示す表があれば、構文解析の動作が一意に定まる。これをＳＬＲ構文解析表といい、以下のような手順で作成する。このとき、LR(0)状態の集合をC={I0, I1,・・・,In}とする。また、以下でA[Ii, a]はスタックの先頭の状態がIiで次の入力記号がaのとき取るべき動作を示し、sjはシフトして状態Ijに遷移することを表す。また、生成規則に番号を付けて、i番目の生成規則の還元はriと書くことにする。
- 初期状態はS'→・S$を含む状態とする
- GOTO(Ii, a)=IjならばA[I, a]=sjとする
- A→α・#∈Iiでa∈Follow(A)ならばA[Ii,a]={A→αで還元}とする
- S'→S・$∈IiならA[I, $]={受理}とする
- LRの場合は還元のときに意味処理をすることができる
- LR(1)構文解析ではFollow集合を使うのではなく、その生成規則の直後にくる一つの終端記号を添えたLR(1)項を作成する。ただし、直後の終端記号を項に含むので、その文だけ状態数が増加し、実用的でないといわれる。
- LALR(1)では、LR(1)項における核が一致している場合に状態を統合して、状態数を削減する。ただし、実際はLR(1)項を作るのは煩雑なため、LR(0)項をつくりSLR(1)の表を作ってから還元の部分だけを別に作成する。
