[Compiler] 11-2. Bottom-up parsing

SLR(1) Parsing = Simple LR(1) Parsing

1 -> Lookahead를 한다!

- LR(0) item으로 만들어진 DFA를 그대로 사용한다.

• input string의 다음 token을 사용해 action을 수행하여, LR(0) parsing의 power를 높인다.
• DFA를 구성할 때 LR(0) || SLR(1)은 lookahead를 무시한다.
  -> SLR(1)은 lookahead를 하지만 만들 때 현재 parsing state의 DFA들은 LR(0) item을 그대로 쓰기 때문에 simple
• 일반 LR(1)은 DFA를 구성할 때 lookahead를 사용한다.

- Two ways

• 적절한 DFA 전환이 존재하는지 확인하기 위해 transition 전에 input token을 참조한다.
  -> action 전에 다음 input이 무엇인지 보고 결정하는 것
• reduce를 수행해야 하는지 여부를 결정하려면, non-terminal의 FOLLOW 집합 사용

 

SLR(1) Parsing algorithm

현재 state가 S라고 하자

1. 다음 A -> α . B β item이 shift로만 가게 되어있다면, shift 한다.

2. 어떤 state가 A -> α . complete item을 가지고 있고, 다음에 나타날 input을 lookahead했을 때 FOLLOW(A)에 속하면, reduce A -> α를 수행

• FOLLOW(A)에 속해있다
• FOLLOW(A)는 A 다음에 나타나는 terminal symbol의 집합
• reduce를 수행해도 valid하게 뒤를 처리할 수 있다.

ex) E -> E + n

• FOLLOW(E)에 '+'가 포함되어 있으므로 reduce 가능
• 만약 포함되지 않았다면 shift
• LR(0)에선 불가능한 방법

 

Parsing table for SLR(1)

- SLR(1) parser에서 한 state는 shift와 reduce 모두 가질 수 있다.

- Input 마지막에 $ symbol은 lookahead를 할 때 끝이라는 것을 명확히 알기위해 넣는다.

ex)

• G = ({E, E'}, {+, n}, P, E')
• P : E' -> E
  E -> E + n | n
• non-terminal에대한 FOLLOW
  FOLLOW(E') = {$}
  FOLLOW(E) = {$, +}
• r -> reduce // r2 -> 2번 rule로 reduce
• s -> shift // s2 -> 2번 state로 shift

State	Input			Goto
	n	+	$	E
0	s2			1
1		s3	accept
2		r2	r2
3	s4
4		r1	r1

ex) string : n + n + n

(1) E -> E + n
(2) E -> n

	Parsing stack	Input	Action
1	$ 0	n + n + n $	shift
2	$ 0 n 2	+ n + n $	reduce E -> n
3	$ 0 E 1	+ n + n $	shift
4	$ 0 E 1 + 3	n + n $	shift
5	$ 0 E 1 + 3 n 4	+ n $	reduce E -> E + n
6	$ 0 E 1	+ n $	shift
7	$ 0 E 1 + 3	n $	shift
8	$ 0 E 1 + 3 n 4	$	reduce E -> E + n
9	$ 0 E 1	$	accept

 

Limits of SLR(1) Parsing

- LR(0) parsing의 간단하고 효과적인 확장

• 거의 모든 Programming Language에서 동작한다.

- 그러나 SLR(1) parsing이 제대로 이루어지지 않는 경우가 있다.

Two solution

1. SLR(k) parsing : parsing 작업은 lookahead의 k ≥ 1 기호를 기반으로 한다.

2. 더 강력한 일반 LR(1) 및 LALR(1) parsing 이용

 

General LR(1), LALR(1) parsing

- General LR(1) parsing - canonical LR(1) parsing

• 이름에서 알 수 있듯 powerful하다.
• 너무 복잡해서 잘 쓰이지 않는다.
  state가 매우 많아진다.

- LALR(1) parsing (lookahead LR parsing)

• general LR(1) 보다는 power가 떨어진다.
• SLR(1)보다는 powerfule 하다.
• 대부분의 Language를 LALR로 parsing한다.
• CLR >= LALR >= SLR

 

Finite automata of LR(1) items (LR(1) - characteristic automaton)

- 처음부터 구조에 lookahead가 내장된 새로운 DFA를 사용한다.

- LR(1) item

• LR(0) item과 lookahead token을 합쳐놓은 것
• ex) [A -> α . β, a]
  a token

 

Finite automata of LR(1) items

- 모든 terminal a에 대해,

• input a가 state [A -> α . a β, b]에서 dot을 shift해 state [A ->α a . β, b]를 얻는다.

- 모든 non-terminal B에 대해,

• input B가 state [A -> α . B β, b]에서 dot을 shift해 state [A -> α B . β, b]를 얻는다.
• input ε가, leftmost B와 모든 a ∈ FIRST(βb)를 가진, 모든 production B -> Yi로 transition되어 state [B -> . Yi, a]를 얻는다.

 

- start state : [S' -> . S, $]

- [A -> β ., b] 형태는 final state다.

• dot이 rightmost position -> complete

- rule을 반드시 argumented 해주어야 한다.

ex)

- Consider a grammar

• G = {A}, {(, ), a}, P, A}
  P : A -> ( A ) | a

- Convert agumented grammar

• G' = ({A, S'}, {(, ), a}, P, S'}
  P : S' -> A
  A -> ( A ) | a
• LR(0) item
  • A -> . ( A )
  • A -> ( . A )
  • A -> ( A . )
  • A -> ( A ) .
  • A -> . a
  • A -> a .

- Initial LR(1) item : [S' -> . A, $]

- First

• 0 : [S' -> . A, $]
  • First(βb) : First(ε$) = {$}
  • ε-transition : [A -> . ( A ), $], [A -> . a, $]
• 0 -> 2 : [A -> ( . A ), $]
  • First( )$ ) = { ) }
  • ε-transition : [A -> . ( A ), )], [A -> . a, )]
• 2 -> 5 : [A -> ( . A ), )]
  • First( )) ) = { ) }
  • ε-transition : [A -> . ( A ), )], [A -> . a, )]

 

General LR(1) Parsing algorithm

S가 현재 state라고 가정

1. state S가 [A -> α . X β, b] 형식의 item을 포함한다면, X는 terminal이고 input string에서 다음 token이다.
action은 현재 input token을 stack으로 shift하는 것이다.

• 새로운 state가 stack으로 push된다.

2. state S가 input string b의 다음 token인 [A -> α ., b]와 같은 complete item을 포함한다면, rule A -> α 로 reduce한다.

• rule S' -> S로 reduce되는 것은 accept 되는것이다.
• 나머진 SLR과 동일

 

LR(1) Parsing table

G = ({A, S'}, {(, ), a}, P, S')

P : S' -> A
A -> ( A ) | a

Numbering rules

1. A -> ( A )
2. A -> a

State	Input				Goto
	(	a	)	$	A
0	s2	s3			1
1				accept
2	s5	s6			4
3				r2
4			s7
5	s5	s6			8
6			r2
7				r1
8			s9
9			r1

	Parsing stack	Input	Action
1	$ 0	( ( a ) ) $	shift
2	$ 0 ( 2	( a ) ) $	shift
3	$ 0 ( 2 ( 5	a ) ) $	shift
4	$ 0 ( 2 ( 5 a 6	) ) $	reduce A -> a
5	$ 0 ( 2 ( 5 A 8	) ) $	shift
6	$ 0 ( 2 ( 5 A 8 ) 9	) $	reduce A -> ( A )
7	$ 0 ( 2 A 4	) $	shift
8	$ 0 ( 2 A 4 ) 7	$	reduce A -> ( A )
9	$ 0 A 1	$	accept

 

LR(0) items vs LR(1) items

LR(1)은 lookahead 때문에 LR(0) 보다 state의 수가 증가했다.

이 state의 수를 줄이고 싶다. 그래서 사용하는게 LALR(1)

 

LALR(1) Parsing

- LR(1) item을 SLR(1)처럼 만들려고 한다. SLR(1)처럼 효율적으로 동작하기 위해서

- LR(0) item의 DFA 크기를 더 작게 유지하면서, SLR(1) parsing보다 LR(1) parsing의 이점을 갖는다.

- LR(1) item의 DFA state의 핵심은, LR(0) item의 집합이 모든 LR(1) item의 첫 번째 구성 요소로 구성된다는 것이다.

Two way

1. LR(1) state를 결합해 LALR(1) item의 DFA를 만든다.

• 장점 : 쉽다.
• 단점 : 오래걸린다.

2. Lookahead proagation : LR(0) item들로부터 lookahead token을 추가해 얻는다.

• 장점 : 
• 단점 : 과정이 복잡하다.

 

Combining LR(1) states to form the DFA of LALR(1) items

• 첫 번째 요소가 같은 state를 합하는 것
• 이렇게 합하고자 하는게 LALR(1)
• 합하는 방법 : LR(1) DFA를 만든 후 state를 순회해 앞 부분 같은 것들을 모아서 merge한다.
• lookahead token에 여러개 올 수 있다.

 

Disambiguating rules for parsing conflicts

- Ambiguous grammar

• 프로그래밍 언어에 대한 문법을 쉽게 (짧고 자연스럽게) 작성할 수 있다.
• 그러나 shift-reduce || reduce-reduce conflicts가 발생한다.

- Shift-reduce conflicts

• 자연스러운 모호성 해소 규칙 : reduce보다 shift를 선호한다.
• 대부분의 shift-reduce parser는 reduce 보다 shift를 선호하여 shift-reduce 충돌을 자동으로 해결한다.

- Reduce-reduce conflicts

• 우선순위를 고려한다.

 

Error recovery in Parsers

- parsers에서 error를 감지한다.

- Parser

• 의미있는 에러 메세지를 제공한다.
• 에러 수정 시도 : 주어진 잘못된 프로그램에서 올바른 프로그램을 추론한다.
• error recovery를 위한 기술의 대부분은 ad hoc 이다. 
• 에러 cascade 프로그램과 무한루프 방지