mojo's Blog
Canonical Collection 본문
Canonical collection
LR(0) item set의 canonical collection C0
- C0 = {CLOSURE ({[S′ →•S])} ∪ {GOTO (I, X) | I ∈ C0, X ∈ V}
Example: LR(0) item set의 canonical collection을 구해보자.
P:
① E → E ＋ T
② E → T
③ T → T ＊ F
④ T → F
⑤ F → (E)
⑥ F → id
(1) Augmented grammar 를 추가한다.
S' -> E
(2) CLOSURE 를 구한다.
I0 = CLOSURE([S' -> •E])
= {[S' -> •E], [E -> •E + T], [E -> •T], [T -> •T * F], [T -> •F], [F -> •(E)], [F -> •id]}
(3) GOTO 를 구한다.
GOTO(I0, E) = CLOSURE({[S' -> E•], [E -> E• + T]})
= {[S' -> E•], [E -> E• + T]} = I1
GOTO(I0, T) = CLOSURE({[E -> T•], [T -> T• * F]})
= {[E -> T•], [T -> T• * F]} = I2
GOTO(I0, F) = CLOSURE({[T -> F•]})
= {[T -> F•]} = I3
GOTO(I0, +) = ∅
GOTO(I0, ( ) = CLOSURE({[F -> (•E)]})
= {[F -> (•E)], [E -> •E + T], [E -> •T], [T -> •T * F], [T -> •F], [F -> •(E)], [F -> •id]} = I4
GOTO(I0, id) = CLOSURE({[F -> id•]})
= {[F -> id•]} = I5
GOTO(I1, +) = CLOSURE({[E -> E + •T]})
= {[E -> E + •T], [T -> •T * F], [T -> •F], [F -> •(E)], [F -> •id]} = I6
GOTO(I2, *) = CLOSURE({[T -> T * •F]})
= {[T -> T * •F], [F -> •(E)], [F -> •id]} = I7
I3는 GOTO를 할 수 없음.
GOTO(I4, E) = CLOSURE({[F -> (E•)], [E -> E• + T]})
= {[F -> (E•)], [E -> E• + T]} = I8
GOTO(I4, T) = CLOSURE({[E -> T•], [T -> T• * F]})
= {[E -> T•], [T -> T• * F]} = I2
GOTO(I4, F) = CLOSURE({[T -> F•]})
= {[T -> F•]} = I3
GOTO(I4, ( ) = CLOSURE({[F -> (•E)]})
= {[F -> (•E)], [E -> •E + T], [E -> •T], [T -> •T * F], [T -> •F], [F -> •(E)], [F -> •id]} = I4
GOTO(I4, id) = CLOSURE({[F -> id•]})
= {[F -> id•]} = I5
I5는 GOTO를 할 수 없음.
GOTO(I6, T) = CLOSURE({[E -> E + T•], [T -> T• * F]}
= {[E -> E + T•], [T -> T• * F]} = I9
GOTO(I6, F) = CLOSURE({[T -> F•]})
= {[T -> F•]} = I3
GOTO(I6, ( ) = CLOSURE({[F -> (•E)]})
= {[F -> (•E)], [E -> •E + T], [E -> •T], [T -> •T * F], [T -> •F], [F -> •(E)], [F -> •id]} = I4
GOTO(I6, id) = CLOSURE({[F -> id•]})
= {[F -> id•]} = I5
GOTO(I7, F) = CLOSURE({[T -> T * F•]})
= {[T -> T * F•]} = I10
GOTO(I7, ( ) = CLOSURE({[F -> (•E)]})
= {[F -> (•E)], [E -> •E + T], [E -> •T], [T -> •T * F], [T -> •F], [F -> •(E)], [F -> •id]} = I4
GOTO(I7, id) = CLOSURE({[F -> id•]})
= {[F -> id•]} = I5
GOTO(I8, ) ) = CLOSURE({[F -> (E)•]})
= {[F -> (E)•]} = I11
GOTO(I8, +) = CLOSURE({[E -> E + •T]})
= {[E -> E + •T], [T -> •T * F], [T -> •F], [F -> •(E)], [F -> •id]} = I6
GOTO(I9, *) = CLOSURE({[T -> T * •F]})
= {[T -> T * •F], [F -> •(E)], [F -> •id]} = I7
I10은 GOTO를 할 수 없음.
I11는 GOTO를 할 수 없음.
따라서 GOTO전부 구했다.
SLR parser
LR(0) item set과 FOLLOW를 이용하여 SLR parsing table를 만든다.
- LR(0) item의 canonical collection으로부터 Shift/GOTO action을 구하고,
- Production rule에 있는 nonterminals의 FOLLOW로부터 reduce을 결정한다.
[알고리즘] SLR parse table
- [입력] Grammar G = (VN, VT, P, S)
- [출력] Augmented grammar G′에 대한 SLR 파싱표
- [방법]
1. G′를 위한 LR(0) item set의 canonical collection C0 = {I0, I1, …, In}을 구성한다.
2. State i는 Ii 에서 구성된다. 상태 i를 위한 parsing action은 다음과 같이 결정된다.
- 만약 [A → α•aβ] ∈ Ii , GOTO(Ii , a) = Ij 이면 action 표의 M[i, a] = Shift j
- 만약 [A → α•] ∈ Ii 이면 FOLLOW(A)에 속한 모든 기호 a에 대해 action 표의
M[i, a] = Reduce A → α
- 만약 [S′ → S•] ∈ Ii 이면 action 표의 M[i, $] = Accept
3. 만약 [A → α•Bβ] ∈ Ii 이고 GOTO(Ii , B) = Ij 이면 GOTO 표의 M[i, B] = j
4. 첨가된 생성 규칙의 LR(0) 항목 [S′ →•S]를 포함하는 state가 initial state이다.
5. 이렇게 해서 정의되지 않은 parse table의 entry는 모두 에러가 된다.
SLR parser implementation
1. Grammar G가 주어진다.
2. Augmented grammar G’를 만든다.
3. LR(0) item sets의 canonical collection C0를 구한다.
4. Reduce action을 결정하기 위해 FOLLOW를 계산한다.
5. SLR parsing table을 작성한다.
Example ) SLR parsing table 을 만들어보자.
P:
① E → E ＋ T
② E → T
③ T → T ＊ F
④ T → F
⑤ F → (E)
⑥ F → id
위에서 만든 GOTO 를 이용하여 I0 ~ I11 에 대한 그래프를 만든다.
FOLLOW(E) = {$, +, )}
FOLLOW(T) = {*, +, ), $}
FOLLOW(*, +, ), $}
FOLLOW를 참고하여 SLR parsing table을 채우도록 하자.
| State | Action | GOTO | |||||||
| id | + | * | ( | ) | $ | E | T | F | |
| 0 | s5 | s4 | 1 | 2 | 3 | ||||
| 1 | s6 | Accept | |||||||
| 2 | r2 | s7 | r2 | r2 | |||||
| 3 | r4 | r4 | r4 | r4 | |||||
| 4 | s5 | s4 | 8 | 2 | 3 | ||||
| 5 | r6 | r6 | r6 | r6 | |||||
| 6 | s5 | s4 | 9 | 3 | |||||
| 7 | s5 | s4 | 10 | ||||||
| 8 | s6 | s11 | |||||||
| 9 | r1 | s7 | r1 | r1 | |||||
| 10 | r3 | r3 | r3 | r3 | |||||
| 11 | r5 | r5 | r5 | r5 | |||||
LR parsing algorithm
LR parsing algorithm
- [입력] Input string w와 LR parse table
- [출력] 만약 w가 문법에 맞으면 w에 대한 파 스 트리를 생성하고, 그렇지 않으면 에러
Parser는 스택의 초기 상태인 S0을 가지고 있다.
begin
ip는 w$의 처음 기호를 나타낸다.
repeat
s 는 stack의 톱 상태
a 는 ip에 의해 지적된 기호;
if action [s, a] = shift sʹ
then begin
a를 스택에 삽입하고 그 다음에 sʹ를 스택에 삽입한다.
ip 가 다음 입력 기호로 이동한다.
end
else
if action [s, a] = reduce sʹ(생성 A → β)
then begin
|β|개의 기호를 스택에서 삭제한다.
삭제된 후 스택의 top이 가리키는 state p에 대하여 GOTO[p, A] = n 을 찾는다.
A를 스택에 삽입한다.
n을 스택에 삽입한다.
end
else
if action [s, a] = 수락
then return
else 에러
until (ip = $이고 스택의 톱 = $)
end.
ex ) Sentence : id * (id * id) 에 대한 LR Parsing을 구하기
P:
① E → E ＋ T
② E → T
③ T → T ＊ F
④ T → F
⑤ F → (E)
⑥ F → id
| Step | Stack | Input string | Action |
| 0 | 0 | id*(id*id)$ | s5 |
| 1 | 0id5 | *(id*id)$ | r6 |
| 2 | 0F | *(id*id)$ | GOTO 3 |
| 3 | 0F3 | *(id*id)$ | r4 |
| 4 | 0T | *(id*id)$ | GOTO 2 |
| 5 | 0T2 | *(id*id)$ | s7 |
| 6 | 0T2*7 | (id*id)$ | s4 |
| 7 | 0T2*7(4 | id*id)$ | s5 |
| 8 | 0T2*7(4id5 | *id)$ | r6 |
| 9 | 0T2*7(4F | *id)$ | GOTO 3 |
| 10 | 0T2*7(4F3 | *id)$ | r4 |
| 11 | 0T2*7(4T | *id)$ | GOTO 2 |
| 12 | 0T2*7(4T2 | *id)$ | s7 |
| 13 | 0T2*7(4T2*7 | id)$ | s5 |
| 14 | 0T2*7(4T2*7id5 | )$ | r6 |
| 15 | 0T2*7(4T2*7F | )$ | GOTO 10 |
| 16 | 0T2*7(4T2*7F10 | )$ | r3 |
| 17 | 0T2*7(4T | )$ | GOTO 2 |
| 18 | 0T2*7(4T2 | )$ | r2 |
| 19 | 0T2*7(4E | )$ | GOTO 8 |
| 20 | 0T2*7(4E8 | )$ | s11 |
| 21 | 0T2*7(4E8)11 | $ | r5 |
| 22 | 0T2*7F | $ | GOTO 10 |
| 23 | 0T2*7F10 | $ | r3 |
| 24 | 0T | $ | GOTO 2 |
| 25 | 0T2 | $ | r2 |
| 26 | 0E | $ | GOTO 1 |
| 27 | 0E1 | $ | Accept |
'학교에서 들은거 정리 > 기초컴파일러구성' 카테고리의 다른 글
| Semantic Analysis (0) | 2021.11.20 |
|---|---|
| LALR Parsing (0) | 2021.11.12 |
| CLR Parse / LALR Parse (0) | 2021.11.05 |
| SLR Parsing / CLR Parser (0) | 2021.11.04 |
| Bottom-up Parsing (0) | 2021.10.27 |
