Bottom-up parsing

Bottom-up parsing

Bottom-up paring(상향식 구문 분석):

• Input string을 읽어가면서 reduce에 의해 start symbol을 찾아가는 방법
• Input string이 start symbol로 reduce되면 올바른 문장이라고 판단, 파스트리 출력
• 그렇지 않으면 문법에 맞지 않은 문자으로 판단, 에러 메시지를 출력한다.
• Bottom-up parsing(상향식 구문 분석)은 rightmost derivation(우단 유도)의 역순이다. 

reduce, handle:

S⇒*ɑAw⇒ɑβw의 유도 과정이 존재할 때

• reduce(감축) : sentential form ɑβw에서 β를 A로 대체하는 것
• handle(핸들) : β. 즉 한 sentential form에서 reduce되는 부분

Example

Sentential form	handle	production rule
id+id*id	id1	F->id (6)
F+id*id	F	T->F (4)
T+id*id	T	E->T (2)
E+id*id	id2	F->id (6)
E+F*id	F	T->F (4)
E+T*id	id3	F->id (6)
E+T*F	T*F	T->T*F (3)
E+T	E+T	E->E+T (1)
E

문법이 unambiguous하면 단 하나의 핸들만 존재한다 : deterministic parsing 가능

 

handle pruning

S⇒w1⇒w2⇒...⇒wn-1⇒wn=w의 rightmost derivation과정이 있을 때,

handle pruning : 각 wi의 sentential form에서 핸들을 찾아 wi-1로 reduce하면서 start symbol로 가는 과정이다.

---

Shift-reduce parsing

Shift-reduce parsing(이동-감축 구문분석)

Shift-reduce Parser

•  stack과 input buffer를 사용하여 구현
• Stack : handle을 찾기 위한 grammar symbols을 유지. $로 초기화
• Input buffer : parsing될 input string을 유지. w$로 초기화(w : 입력 문자열)

Shift(이동) : 현재의 input symbol을 스택의 top에 옮기는 것을 의미. 이 과정은 스택의 톱에 핸들이 나타날 때까지 계속

Reduce(감축) : 핸들의 오른쪽 끝이 스택의 top에 나타나면 핸들의 왼쪽 끝을 찾아서 완전한 형태의 핸들을 찾은 다음, rhs가 핸들인 production rule을 찾아 lhs에 있는 기호로 대체되는 것

Accept : 주어진 string이 주어진 문법에 맞다는 것을 나타냄

Error : 주어진 string이 주어진 문법에 맞지 않다는 것을 나타냄

 

Shift-reduce parsing 순서

1. 초기 상태에서 시작하여 스택(왼쪽)의 top에 핸들이 나타날 때까지 input symbol을 하나씩 stack으로 옮김(shift)
2. Shift를 하다가 핸들을 찾으면 production rule을 찾아 lfs에 있는 symbol로 reduce하고 부분 파스 트리를 구성한다.
3. 같은 방법으로 계속 진행한다. 핸들(바꿔줘야 할 것)이 찾아지지 않거나 입력 버퍼가 비었는데 시작 기호가 나타나지 않으면 에러 출력
4. 입력 문자열을 모두 읽은 후 start symbol을 만나면 accept

Example

Step	Stack	Input symbol	Action
1	$	id+id*id$	shift id1
2	$id	+id*id$	Reduce F->id
3	$F	+id*id$	Reduce T->F
4	$T	+id*id$	Reduce E->T
5	$E	+id*id$	Shift +
6	$E+	id*id$	Shift id
7	$E+id	*id$	Reduce F->id
8	$E+F	*id$	Reduce T->F
9	$E+T	*id$	Shift *
10	$E+T*	id$	Shift id
11	$E+T*id	$	Reduce F->id
12	$E+T*F	$	Reduce T->T*F
13	$E+T	$	Reduce E->E+T
14	$E	$	Accept

Step	Stack	Input symbol	Action
1	$	id+id*id$	Shift id1
2	$id	+id*id$	Reduce E->id
3	$E	+id*id$	Shift +
4	$E+	id*id$	Shift id2
5	$E+id	*id$	Reduce E->id
6	$E+E	*id$	Shift *
7	$E+E*	id$	Shift id3
8	$E+E*id	$	Reduce E->id
9	$E+E*E	$	Reduce E->E*E
10	$E+E	$	Reduce E->E+E
11	$E	$	Accept

 

이 문제에서 Shift-reduce parsing의 한계가 보이는데 5단계에서 id를 E로 reduce하였지만, *를 shift할 수도 있고, 6단계에서 *를 shift했지만 E+E가 핸들이 될 수도 있다.

 

핸들을 어떻게 찾느냐와 어떤 production rule을 적용하는지에 따라서 parsing의 결과가 달라 질 수 있기 때문에 shift-reduce parsing은 완벽하지 못하다.

---

LR parser

LR(k) parser (Left-to-right and Right parse)

• L : input string을 왼쪽에서 오른쪽으로 읽어가며, R : right parse를 생성
• k : 한번에 읽은 input symbol의 개수. k=1일 경우 생략 가능

Strengths(장점)

• Unambiguous CFG로 쓰여진 모든 언어에 대해 구성 가능
• Deterministic parsing - backtracking이 없음
• 에러 검출이 용이

Weakness(약점)

• Top-down parser에 비해 구현이 복잡함

Parsing table in LR parser : action과 GOTO로 구성

 

Variants(parsing table을 구성하는 방법에 따라서 분류)

• SLR(simple LR) : LR(0) item sets + FOLLOW로 구성
• CLR(canonical LR) : LR(1) item sets으로 구성
• LALR(lookahead LR) : LR(0) item sets + lookahead 또는 LR(1) item sets으로 구성

LR(k) Grammar

• LR(k) grammar는 모든 entry에 대해 유일하게 정의되는 parsing table을 만들 수 있다.(entry는 두개 이상 올 수 없다.)

Augmented Grammar

• Grammar G = (Vn,Vt,P,S)에 augment(첨가) 된 문법
• G' = (Vn ∪ {S'}, Vt, P ∪ {S'->S}, S')로 표현됨 (S': start symbol, S'->S : augmented production rule)
• S'->S를 추가하는 이뉴는 Parser로 하여금 S를 S'로 reduce할 경우 이제 파싱을 끝내고 문장을 Accept 하도록 설계하기 위하여 사용한다. 

---

LR(0) items

LR(0) item

• rhs에 dot symbol를 가진 production rule이다.

ex) Production rule A->BCD의 LR(0) items : { [A->·BCD], [A->B·CD], [A->BC·D], [A->BCD·] }

• A->B·CD : B를 읽었고 CD는 앞으로 읽을 기호임을 나타낸다.
• A->BCD· : BCD를 읽었고 이제 BCD를 A로 reduce 할 수 있음을 나타낸다.

Marking : LR(0) item을 얻기 위해 production rule에 dot symbol을 추가하는 것

Mark symbol : LR(0) item에서 dot symbold 오른쪽에 있는 기호

 

Three types of LR(0) items

• Kernel item : [A->ɑ·β]에서 ɑ≠𝜀 이거나 A=S'인 경우
• Closure item : dot symbol이 rhs 맨 왼쪽에 있는 경우 ( ex : [A->·BCD] )
• Reduce item : dot symbol이 rhs 맨 오른쪽에 있는 경우 ( ex : [A->BCD·] )

Canonical collection

• 어떤 문법의 LR(0) items로 구성된 set
• LR parse table을 구성하는데 반드시 필요

---

CLOSURE(I)

CLOSURE(I) 구하는 법

1. 먼저 I에 속한 모든 LR(0) items를 CLOSURE(I)에 추가한다.
2. CLOSURE(I) = I ∪ { [B->·𝛾] | [A->ɑ·Bβ] ∈ CLOSURE(I), B->𝛾 ∈P }

CLOSURE(I) algorithm

begin

   CLOSURE(I) = I;

   repeat

      if [A -> ɑ·Bβ] ∈ CLOSURE(I) and B->𝛾 ∈P

      then CLOSURE(I) = CLOSURE(I) ∪ [B->·𝛾]

   until CLOSURE가 변하지 않을 때까지

end

CLOSURE([E'->·E]) = { [E'->·E], [E->·E+T], [E->·T], [T->·T*F], [T->·F], [F->·(E)], [F->·id] }

---

GOTO function

LR(0) item의 GOTO Function

• Item set I와 X∈V에 대해, GOTO(I,X) = CLOSURE( { [A->ɑX·β] | [A->ɑ·Xβ] ∈ I } )
• Parsing을 위해서 mark symbol을 하나씩 읽겠다는 의미

Example

I = { [E'->E·], [E->E·+T] } 일 때 GOTO(I,+)를 계산해보자.

---

Canonical collection

LR(0) item set의 canonical collection C0

 

 

 

Example

---

SLR parser

SLR parsing table 만드는 법

1. LR(0) item set과 FOLLOW를 구한다.
2. LR(0) item의 canonical collection으로부터 Shift/GOTO action을 구한다.
3. Production rule에 있는 nonterminals의 FOLLOW로 부터 reduce를 결정한다.

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을 작성한다.

State	Action						GOTO
	id	+	*	(	)	$	E	T	F
0	s5			s4			1	2	3
1		s6				ACC
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

실수 안하는 팁(순서대로 확인)

1. reduce 할 수 있는지 확인
2. nonterminal로 가는거 확인
3. terminal 가는거 확인

---

LR parsing algorithm

[입력] Input string w와 LR parse table

[출력] 만약 w가 문법에 맞으면 w에 대한 파스 트리를 생성하고, 그렇지 않으면 에러

---

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	$	acc