[Compiler] 10. Top-down parsing

Top-down parsing (하향식 구문 분석)

input string이 있으면, leftmost derivation을 통해 parse tree를 그린다.

Recursive descent parsing

Predictive parsers

• 하나 이상의 lookahead tokens을 사용해 input string의 다음 구성을 예측한다.
• LL(1), LL(k)
• 잘 안쓰인다. 보통 bottom-up parser를 사용하지만 이를 알기 위해선 top-down을 알아야 한다.

 

Recursive descent parsing

top-level의 non-terminal에서 시작한다.

• start symbol에 대한 rule을 순서대로 시도
• 각 단계에서, 사용할 다양한 production 선택
• 잘못된 선택 시 backtracking

ex)

문제점

infinite loop 발생시 recursive decent parsing이 동작하지 않는다.    ex) S -> Sa | b

이럴 때 보통 left recursion이 발생하지 않는 Grammar로 바꿔준다.

 

Summary of recursive descent

1. 간단하고 일반적인 parsing strategy다.
   
   • Left-recursion 먼저 제거해야한다.
   • 자동으로 할 수 있다.
2. Backtracking 때문에 인기가 없다.
   • 너무 비효율적
3. grammar를 제한해 backtracking 제거
   • 현재 input이 무엇인지 살펴보고 rule을 선택할 수 있다. => 예측

 

Predictive parsers

Recursive descent parser와 동작은 동일하다.

어떤 production을 선택할지는 input을 보고 예측할 수 있다.

몇 가지 제약을 거는 대신 효율적이다.

Predictive parsers는 LL(k) grammar를 받아들인다.

LL(k)

• 앞에서부터
• L : input이 있을 때 왼쪽에서 오른쪽으로 읽는다.
• L : leftmost derivation을 수행한다.
• k : 앞으로 처리할 string을 k개 만큼 보겠다. (lookahead)
• 많이 볼수록 powerful 하지만 많은 리소스를 사용하게 된다. 

 

LL(1) parsing

명시적으로 parsing stack이 존재한다.

Steps of top-down parser

1. start symbol을 stack에 push한다.
2. 일련의 작업 후, stack과 input이 비어있으면 input string을 accept한다.

Two actions

• Generate
  : 어떤 non-terminal을 rule에 따라 Generation 하는 것
• Match
  : 현재 parsing stack의 top과 input이 동일하면, 서로 지운다.

• G = ({S}, {(, )}, P, S)
• P : S -> ( S ) S | ε

	Parsing stack	Input	Action
1	$ S	( ) $	S -> ( S ) S
2	$ S ) S (	( ) $	match
3	$ S ) S	) $	S -> ε
4	$ S )	) $	match
5	$ S	$	S -> ε
6	$	$	accept

 

LL(1) parsing table

어떤 non-terminal A가 stack의 Top에 있을 때, 어떤 rule 사용할지 결정해야한다.

stack의 top이 terminal인 경우 고민할 필요 없다. -> input이랑 match되면 소비, 실패시 parsing error

LL(1) parsing table M[N, T] : 2차원의 matrix

• N : grammar의 non-terminals의 집합
• T : $를 포함한 grammar의 terminals의 집합

M[N, T]	(	)	$
S	S -> ( S ) S	S -> ε	S -> ε

input이 $이면 S -> ε rule을 사용한다.

• table이 비어있을 수 있는데, 그러면 error

 

LL(1) parsing for string ( )

1. start symbol을 stack에 push한다.
2. 일련의 작업 후, stack과 input이 비어있으면 input string을 accept하고, 아니면 reject한다.

M[N, T]	(	)	$
S	S -> ( S ) S	S -> ε	S -> ε

	Parsing stack	Input	Action
1	$ S	( ) $	M[S, (] => S -> ( S ) S
2	$ S ) S (	( ) $	match
3	$ S ) S	) $	M[S, )] => S -> ε
4	$ S )	) $	match
5	$ S	$	M[S, $] => S -> ε
6	$	$	accept

 

Left recursion

left recursion 발생시 parsing 불가하므로 제거해주어야 한다.

non-terminal A는 iff A =+> Aa (a ∈ V*)인 경우 left recursive

• left recursive nonterminal은 top-down deterministic parser의 loop를 야기한다.

Immediate left recursive (직접 좌재귀)

• A -> Aa

Indirect left recursive (간접 좌재귀)

• A =+> Aa

 

Eliminate left recursions

반복되는 부분을 right-recursion으로 변환해 표현한다.

ex)

• G = ({S}, {a, b}, P, S)
• P : S -> Sa | b

b, ba, baa, baaa, ... => 직접 좌재귀

• S -> bS'
• S' -> aS' | ε

 

Left refactoring (좌 인수분해)

2개 이상의 grammar rule을 선택할 수 있을 때, 공통 접두사 문자열을 공유하는 경우 Left refactoring이 필요하다.

ex)

lookahead로 1개의 token만 보는 경우

• A -> ab | ac

solution : 왼쪽에 있는 a(공통 접두사 문자열)를 factor하고 규칙을 두 가지 규칙으로 다시 작성

* 접두 문자열 가장 긴 것을 찾아 하나로 묶어준다.

• A -> aA'
• A' -> b | c

 

LL(1) parsing table 만들기

LL(1) parsing table을 구성하는 알고리즘이 필요하다.

FIRST 및 FOLLOW를 정의하고 두 sets를 이용해 구문 분석 테이블을 구성하는 방법을 보여준다.

 

FIRST

non-terminal A로부터 derivation되어 첫 번째로 나타날 수 있는 터미널 기호의 집합

context free grammar G=(VN, VT, P, S)가 주어졌을 때, 모든 non-terminal A ∈ VN은 다음을 따른다.

FIRST(A) = { b ∈ VT ∪ {ε} | A =+> bβ, β ∈ V*}

ex)

• G = ({S, C, D}, {a, b, c, d}, P, S)
• P :
  S -> C | D
  C -> aC | b
  D -> cD | d

FIRST(S) = {a, b, c, d}

• S -> C -> aC => {a}
• S -> C -> b => {b}
• S -> D -> cD => {c}
• S -> D -> d => {d}

 

computation of FIRST(A)

실제 프로그래밍을 위한 쉬운 방법

a ∈ VT 일 때, FIRST(a) = {a}로 자기 자신이다.

a는 아래 중 하나

• INITFIRST(A) = {a ∈ VT | A -> aα ∈ P, α ∈ V*}
• {a | a ∈ FIRST(B), A -> Bα ∈ P, α ∈ V*, A != B}

non-terminal A에 대해 FIRST(A) = INITFIRST(A) ∪ U(모든 submation) {FIRST(B) | A -> Ba ∈ P, A != B}

ex)

• G = ({S, C, D}, {a, b, c, d}, P, S)
• P : 
  S -> C | D
  C -> aC | b
  D -> cD | d
• Pass1 -> INITFIRST

Grammar Rule	Pass 1	Pass 2
S -> C		FIRST(S) = {a, b}
S -> D		FIRST(S) = {a, b, c, d}
C -> aC	FIRST(C) = {a}
C -> b	FIRST(C) = {a, b}
D -> cD	FIRST(D) = {c}
D -> d	FIRST(D) = {c, d}

 

FOLLOW

non-terminal A 다음에 나오는 터미널 기호들의 집합

context free grammar G=(VN, VT, P, S)가 주어졌을 때, 모든 non-terminal A ∈ VN은 다음을 따른다.

FOLLOW(A) = {a ∈ VT ∪ {$} | S =+> αAaβ, α, β ∈ V*}

• $ : endmarker
  input string의 끝
• A가 start symbol이라면, $는 FOLLOW(A)다.

ex1)

• G = ({S, C, D}, {a, b, c, d}, P, S)
• P :
  S -> C | D
  C -> aC | b
  D -> cD | d

FOLLOW(S) = {$}

FOLLOW(C) = {$}

• S -> C => FOLLOW(S) ⊆ FOLLOW(C)

FOLLOW(D) = {$}

• S -> D => FOLLOW(S) ⊆ FOLLOW(D)

ex2)

• G = ({T, T', E, E', F}, {+, *, (, ), a}, P, E)
• P :
  E -> TE'
  E' -> +TE' | ε
  T -> FT'
  T' -> *FT' | ε
  F -> (E) | a

FOLLOW(E) = {$, )}

• F -> (E)

FOLLOW(E') = {$, )}

• E -> TE'
• FOLLOW(E) ⊆ FOLLOW(E')

FOLLOW(T) = {$, ), +}

• E' -> +TE'
• FOLLOW(E') & FIRST(E') ⊆ FOLLOW(T)

FOLLOW(T') = {$, ), +}

• T -> FT'
• FOLLOW(T) ⊆ FOLLOW(T')

FOLLOW(F) = {$, ), +, *}

 

Computation of FOLLOW(A)

a는 아래중 하나

• INITFOLLOW(A) = {a ∈ VT | B -> αAXβ, a ∈ FIRST(X), α, β ∈ V*}
• {a | a ∈ FOLLOW(B), B -> αA ∈ P, α ∈ V*, A != B}

B -> αa ∈ p, with A != B

• FOLLOW(B) ⊆ FOLLOW(A)

non-terminal A에 대해 FOLLOW(A) = INITFOLLOW(A) ∪ U {FOLLOW(B) | B -> αA ∈ P, α ∈ V*, A != B}

ex)

• G = ({T, T', E, E', F}, {+, *, (, ), a}, P, E)
• P :
  E -> TE'
  E' -> +TE' | ε
  T -> FT'
  T' -> *FT' | ε
  F -> (E) | a
• FIRST(E) = {(, a}
  FIRST(E') = {+, ε}
  FIRST(T) = {(, a}
  FIRST(T') = {*, ε}
  FIRST(F) = {(, a}

Grammar rule	Pass 1
E -> TE'	FOLLOW(E) = {$}     (start symbol) FOLLOW(T) = {$}     (FIRST(E') - {ε} = {+}) FOLLOW(E') = {$}    (FOLLOW(E) ⊆ FOLLOW(E')) FOLLOW(T) = {$, +} (FOLLOW(E) ⊆ FOLLOW(T) BECAUSE {ε} ∈ {FIRST(E')) => ε이 포함되면 뒤에 있는 VN의 FOLLOW도 가져올 수 있다.
E -> TE'	FOLLOW(T) = {$, +}
E' -> ε
T -> FT'	FOLLOW(F) = {*}           (FIRST(T') - {ε} = {*}) FOLLOW(T') = {$, +}      (FOLLOW(T) ⊆ FOLLOW(T')) FOLLOW(F) = {$, *, +}    (FOLLOW(T) ⊆ FOLLOW(F) BECAUSE {ε} ∈ {FIRST(T'))
T' -> *FT'	FOLLOW(F) = {$, *, +}
T' -> ε
F -> (E)	FOLLOW(E) = {$, )}    (FIRST()) = {)})
F -> a

• 최종이므로 E를 포함하는 것을 업데이트 해주어야 함
  해당 과정 반복
• 최종
  FOLLOW(E) = {$, )}
  FOLLOW(E') = {$, )}
  FOLLOW(T) = {$, ), +}
  FOLLOW(T') = {$, ), +}
  FOLLOW(F) = {$, ), +, *}

 

construct LL(1) parsing table 만들기

다음 두 단계를 반복한다.

1. FIRST(α)의 각 terminal symbol a 에 대해 M[A, a] 항목에 A -> a를 추가한다.
2. 만약 FIRST(α)에 ε이 존재한다면, FOLLOW(A)의 각 요소 a에 대해 A -> α를 M[A, a]에 추가한다.

ex)

• G = ({S}, {(, )}, P, S)
• P : S -> (S)S | ε

Grammar rule	Pass 1
S -> (S)S	FIRST(S) = {(}
S -> ε	FIRST(S) = {(, ε}

Grammar rule	Pass 1
S -> (S)S	FOLLOW(S) = {$} FOLLOW(S) = {$, (}

M[N, T]	(	)	$
S	S -> ( S ) S	S -> ε	S -> ε

1. S -> (S)S
   
   • FIRST( (S)S ) = FIRST( ( ) = {(}
   • M[S, (] = S -> (S)S
2. S -> ε
   • FIRST(ε) = {ε}
   • FOLLOW(S) = {$, )}
   • M[S, $] = S -> ε
   • M[S, )] = S -> ε

+++

빈칸이 발생할 수 있는데 이는 PARSING ERROR

빈칸에 상황에 맞는 ERROR MASSAGE 적어주면 사용자에게 알려줄 수 있다.

 

Extending the lookahead : LL(k) parsers

FIRST_k(A) = {Wk | A =*> W}

FOLLOW_k(A) = {Wk | S$ =*> aAw}

• Parsing talbe은 훨씬 커진다.
• column 수가 k로 인해 기하급수적으로 증가한다.
• 테이블이 커질수록 표현력이 높아지지만 비효율적이고 무겁다.