1．1 オートマトンと状態遷移図

４．４ LR解析
（１）LR解析とは
■記号列を左から右へ一度だけみて解析する方法。
■いわゆる決定性言語を解析する。
■解析プログラムの自動生成に向いている。
■通常のプログラミング言語の構文に適用すると解析プログラムが
大きくなりすぎるので、改良型のSLR（Simple Left to right
Right most derivation）、LALR(Look Ahead Left to right
Right most derivation：例 UNIXのyacc)が提案されている
■解析能力は、SLR(1)<LALR(1)<LR(1)
【意味】
①左から右へ（Left to right ）
②最右導出（Rightmost Derivation）
（２）LR解析に必要なデータ
①スタックと解析表を持つ。
②スタックには状態（State）の記号siと文法の記号（終
端記号または非終端記号）Xiを
s0X1s1X2s2…Xmsm
の形で積む。
③s0を初期状態といい、スタックの底に置く。
④解析表はaction表と goto表から構成される
⑤action表の動作種類は、シフト、還元、受理、エラー
のいずれか。
（３）action表の動作種類
シフト(shift) ：入力記号列から記号を1つ読込み、表中の状態をプッ
シュする。
還元(reduce) ：表中に示された構文規則によってスタックトップにあ
るいくつかの記号を還元する。さらにこのときgoto表
に示された次の状態をスタックにプッシュ。
受理(accept) ：解析終了
エラー(error) ：エラー
（４）LR解析の手順
入力
出力
初期状態
：記号列W
： Wの最右導出
：入力W$
スタックs0
For(;;){
sをスタックトップの状態s、aを現在の入力記号とする。
If(action[s,a]==shift m){
push a; push m; 入力記号を次の記号にする;}
else if(action[s, a]==reduce A→u）{
2×length(u)個の記号をスタックからポップする。;
mを新たなスタックトップの状態とする；
Aをプッシュ；goto[m,A]をプッシュする；
A→uを出力；}
else if (action[s,a]==accept)
break;
else エラー処理；
｝
(1) E→E+T
(4) T→F
(2) E→T
(5) F→(E)
（５）LR解析表の例
(3) T→T*F
(6) F→i
si : シフトして状態iをプッシュ
rj : 番号jの規則で還元
状態
0
1
2
3
4
5
6
7
8
9
10
11
i
s5
---s5
-s5
s5
-----
action
+
*
--s6
-r2
s7
r4
r4
--r6
r6
----s6
-r1
s7
r3
r3
r5
r5
(
s4
---s4
-s4
s4
-----
)
--r2
r4
-r6
--s11
r1
r3
r5
$
-acc
r2
r4
-r6
---r1
r3
r5
goto
E
T
1
2
1
2
1
2
1
2
8
2
8
2
9
F
3
3
3
3
3
3
3
10
10
10
10
10
(1) E→E+T
(4) T→F
(2) E→T
(5) F→(E)
(3) T→T*F
(6) F→i
LR解析表の実行例
si : シフトして状態iをプッシュ
rj : 番号jの規則で還元
スタック
No.
(右側トップ）
1
0
2
0i5
3
0F3
4
0T2
5
0T2*7
6
0T2*7(4
7
0T2*7(4i5
8
0T2*7(4F3
9
0T2*7(4T2
10
0T2*7(4E8
11
0T2*7(4E8+6
12
0T2*7(4E8+6i5
（次のシートに続く）
入力
(左側が現在の入力）
i*(i+i)$
*(i+i)$
*(i+i)$
*(i+i)$
(i+i)$
i+i)$
+i)$
+i)$
+i)$
+i)$
i)$
)$
s5
r6
r4
r7
s4
s5
r6
r4
r2
s6
s6
r6
iと5をPush
F→i (Fのときgoto
T→F (Tのときgoto
*と7をPush
(と4をPush
iと5をPush
F→i (Fのときgoto
T→F (Tのときgoto
E→T (Eのときgoto
+と6をPush
iと5をPush
F→i (Fのときgoto
3)
2)
3)
2)
8)
3)
(1) E→E+T
(4) T→F
(2) E→T
(5) F→(E)
(3) T→T*F
(6) F→i
LR解析表の実行例（続く）
si : シフトして状態iをプッシュ
rj : 番号jの規則で還元
スタック
No.
12
13
14
15
16
17
18
19
入力
(右側トップ）
(左側が現在の入力）
0T2*7(4E8+6i5
0T2*7(4E8+6F3
0T2*7(4E8+6T9
0T2*7(4E8
0T2*7(4E8)11
0T2*7F10
0T2
0E1
)$
)$
)$
)$
$
$
$
$
r6
r4
r1
s11
r5
r3
r2
acc
F→i (Fのときgoto 3)
T→F (Tのときgoto 3)
E→E+T (4ポップ)(Eのときgoto 8)
)と11をプッシュ
F→（E) (Fのときgoto 10)
T→T*F (Tのときgoto 2)
E→T (Eのときgoto 2)
終了
（６）LR解析表作成のための定義
定義１
LR(0)項の定義
文法 G = (T, N, P, S)の各生成規則の右辺の各記号のどこか1箇所に、
解析の進行境界を示すドット（・）を置いたもの。
【例】
■規則 A → BCD のとき、4つの LR(0)項がある。
[A →・BCD] , [A →・BCD],
[A →・BCD], [A →・BCD]
■規則 A → εのときは次の1つの LR(0)項のみである。
[A →・]
定義２
閉包（closure）の定義
LR(0)項の集合Iに対する閉包closure(I)とは、
Iの各要素に対して次の操作を行って得られる集合である。
① Iの項はclosure(I)に入れる。
② [A→u・Bv]がclosure(I)にあり、B→wという生成規則がPにあると
き、[B→w]をclosure(I)に入れる。
定義３
goto(I,X)の定義
LR(0)項の集合 I と X ∈ T ∪ N に対して、
LR(0)項の集合 goto(I, X) とは、
[A →u・X v] ∈ I に対して、[A →u・X v]の形の
LR(0)項の集合
もっと簡単に
Goto(I, X)
状態 I において、記号 X を読み込むと至る状態
LR(0)の正規集合
canonical LR(0) collection
入力：文法 G = (T, N, P, S) に規則 S’→Sを追加した文法 G’
出力：G’ の LR(0) の正規集合 C
C = {closure({[S’→S]})}
repeat{
Cの中の各Iと各記号X∈T∪Nに対して、goto(I,X)が
まだCに入っていないとき、Cにgoto(I,X)を加える。
Until(新しいものが加わらない）
(1) E→E+T
(4) T→F
(2) E→T
(5) F→(E)
(3) T→T*F
(6) F→i
LR(0)の正規集合の例
I0
E’→･E
E→･E+T
E→･T
E→･T*F
T→･F
F→･(E)
F→･i
I1 E’→E･
E→E･+T
I2
E→T･
E→T･*F
I3 T→F･ I4 F→(･E)
E→･E+T
E→･T
T→･T*F
T→･F
F→･(E)
F→･i
I5
F→i･
I6 E→E+･T I7
T→･T*F
T→･F
F→･(E)
F→･i
T→T*･F
F→･(E)
F→･i
I8 F→(E･)
E→E･+T
I9
E→E+T･
T→T･*F
I10 T→T*F･ I11 F→(E)･
状態間の状態遷移図
E
I0
I1
+
I6
T
F
(
i
T
I2
F
*
I7
F
(
i
I3
I9
*
I3
I4
I5
I10
I4
I5
(
(
I4
E
T
F
i
i
I5
I8
I2
I3
I7
)
+
I11
I6
(1)
(2)
(3)
(4)
(5)
(6)
E→E+T
E→T
T→T*F
T→F
F→(E)
F→i
（７）SLR（１）の解析表
Simple Left to right Right most derivation
LR(0)の正規集合とFOLLOW(A)を用いる
入力：文法G=(T,N,P,S)に規則 S’→Sを追加した G’
出力：文法G’ に対するSLR(1)解析表
① LR(0)の正規集合 C={I0, I1,･･･, In}を作成（前述）
② 各Ij に対応して状態jを作成する。
ⅰ) [A→u･av]∈Ij ,a∈Tかつgoto(Ij,a)=Ikのとき、
action[j,a]をshift kとする。
ⅱ) [A→u･av]∈Ijかつ a≠S’ のとき,a∈FOLLOW(A)なるa∈T
に対して、action[j,a]をreduce A→u とする。
ⅲ) [S’→S･]∈Ijのとき、 action[j,a]をacceptとする。
③ goto(Ij,A)= Ikのときgoto[j,A]をkとする。
④ 残りの項目はエラーとする。
⑤ 初期状態は[S’→･S】から作成されるLR(0)項の集合I0に
対応する状態とする。
SLR（１）について
Simple Left to right Right most derivation
① 解析表の各項目に高々1つの要素が入る（２つ以上は入らない）
とき、「元の文法GはSLR(1)である」という。
② SLR(1)の解析では還元（reduce）動作をFOLLOW(A)で決めるが、
FOLLOW(A)は最左導出の概念であり、最右導出とは関係がない。
↓
最右導出における非終端記号に続く記号の範囲を調べれば、
より精密な還元動作が可能なはずである。
LR(1)解析表への拡張
（７）LR（１）の解析表
解析表作成のための定義
【定義】
① 文法G=(T,N,P,S)のLR(1)項[A→u･v,a]とは、
Gの各生成規則に各記号間のどこか１箇所にドット(･)を置いたも
のと、a∈Tの組である。
② ドットは先頭あるいは最後でもよい。
LR(1)の正規集合の作成(その1)
入力：文法G=(T,N,P,S)に規則 S’→Sを追加した G’
出力：文法G’ の正規集合C
以下の３関数を用いる。
① closure(I){
repeat{
Iの各項[A→u･Bv,a], G’の各規則 B→wとb∈FIRST(va)により
E=[B→･w, b]を作成する。
EがIになければEをIに加える。}
until ( Iに何も追加されない）
return I
｝
② goto(I,X)={
Iのある[A→u･Xv,a]の形の集合をJとする。
return J
}
(次のシートに続く）
LR(1)の正規集合の作成(その２)
入力：文法G=(T,N,P,S)に規則 S’→Sを追加した G’
出力：文法G’ の正規集合C
（前のシートから続く）
③ item(G’){
C={closure({[S’→･S, $]})};
repeat{
if(Cの各項目集合Iに対してgoto(I,X)が空でない)
X∈T∪Nに対してgoto(I,X)をCに加える;
}
until (Cに何も追加されない）
return C
｝
LR(1)解析表の作成
入力：文法G=(T,N,P,S)に規則 S’→Sを追加した G’
出力：文法G’ のLR(1)解析表
① C=item(G’)
② 各Ijに対応した状態jを作る。その解析の動作は以下のとおり。
ⅰ) [A→u･av, b]∈Ij, a∈T, かつgoto(Ij, a)=Ik のとき、
action表のaction[i, a]をshift kとする。
ⅱ) [A→u･, a]∈Ij, かつA≠S’のとき
action表のaction[i, a]をreduce Aとする。
ⅲ) [S’→S･, $]∈Ijのとき
action表のaction[i, $]をacceptとする。
③ goto(Ij, A)= Ikのとき、goto[i, a]をkとする。
④ 上記②と③の操作で何も入らないときエラーとする。
⑤ 初期状態は、[S’→･S, $]から作られるLR(1)項の集合I0に対応する
状態とする。
LR(1)解析について
① 解析表の各項目に高々１つの要素しか入らないとき
元の文法GはLR(1)であるという。
② LR解析は、SLR解析よりも広い範囲の適用が可能である。
③ 通常のプログラミング言語に適用すると、状態数が多くなりすぎ
（数千）実用に向いていない。
① LR(1)項の正規集合で、項の第１成分全体が集合として同じである
ような項集合（状態）同士をまとめてグルーピングする。
② 解析できる文法範囲は少し狭くなるが、状態の数をかなり減らすこ
とができる（数百）。
③ これをLALR(1)解析という。
【用語】LALR : Look ahead LR

Download Report