제7장 LL 파싱

컴파일러 구성론

강 승 식

∙ LL parsing

- backtracking이 없이 deterministic한 top-down parsing

⇒  문법이 LL 조건 만족해야

- LL이란?  Left-to-right scanning & Leftmost derivation

- 현재의 input symbol을 보고 적용될 생성규칙을 deterministic하게 선택

7.1 결정적 구문 분석

7.1.1 FIRST

*

[정의 7.1] FIRST(A) = { a ∪ {[eqn: epsilon]} | A ⇒[eqn: a gamma], a∈VT, [eqn: gamma]∈V* }

즉, nonterminal A로부터 유도되어 첫번째로 나타날 수 있는 terminal 집합.

예1) 다음 생성규칙에서 각 nonterminal에 대한 FIRST를 구하시오.

A → aB | B

B → bC | C

C → c

1.	A ⇒ aB

A ⇒ B ⇒ bC

A ⇒ B ⇒ C ⇒ c

FIRST(A) = { a, b, c }

2.	B ⇒ bC

B ⇒ C ⇒ c

FIRST(B) = { b, c }

3.	C ⇒ c

FIRST(C) = { c }

[정의 7.2] nonterminal A가 [eqn: epsilon]을 유도할 수 있으면, A를 nullable하다고 한다.

*

즉, A ⇒[eqn: epsilon]이면, A는 nullable하다.

[정의 7.3] ring sum의 정의

1. if [eqn: epsilon]∉A, then A ㊉ B = A

2. if [eqn: epsilon]∈A, then A ㊉ B = (A-{[eqn: epsilon]}) ∪ B

예2) ring sum 연산의 예

{a, b, c} ㊉ {c, d} = {a, b, c}

{a, b, c,[eqn: epsilon]} ㊉ {c, d} = {a, b, c, d}

{a, b,[eqn: epsilon]} ㊉ {c, d,[eqn: epsilon]} = {a, b, c, d,[eqn: epsilon]}

[정의 7.4] FIRST(A1A2⋯An)

= FIRST(A1) ㊉ FIRST(A2) ㊉ ⋯ ㊉ FIRST(An)

∙ FIRST(X)를 구하는 방법

1. X가 terminal이면 X의 FIRST는 자기자신이 된다.

FIRST(X) = {X}, if X∈VT.

2. X→[eqn: a alpha]의 생성규칙이 존재하면 a가 FIRST(X)에 포함된다.

FIRST(X) = FIRST(X) ∪ {a}, if X→[eqn: a alpha] and a∈VT.

또한, X가 [eqn: epsilon]-생성규칙을 가지면 FIRST에 [eqn: epsilon]이 포함된다.

3. X→Y1Y2⋯Yk인 생성규칙에 대하여

FIRST(X) = FIRST(X) ∪ FIRST(Y1Y2⋯Yk)

예3) 다음 문법에 대하여 FIRST를 구하시오.

S → ABe

A → dB | aS | c

B → AS | b

FIRST(S) = FIRST(ABe) = FIRST(A) = { a, c, d }

FIRST(B) = FIRST(A) ∪ { b } = { a, b, c, d }

예4) 다음 문법에 대하여 FIRST를 구하시오.

E → TE'

E' → +TE' |[eqn: epsilon]

T → FT'

T' → *FT' |[eqn: epsilon]

F → (E) | id

FIRST(E) = FIRST(TE') = FIRST(T) = FIRST(FT')

= FIRST(F) = { (, id }

FIRST(E') = { +, [eqn: epsilon] }

FIRST(T') = { *, [eqn: epsilon] }

7.1.2 FOLLOW

∙ nonterminal A가 nullable이면 FIRST(A)에 [eqn: epsilon]이 속하므로 FIRST만으로

생성규칙을 deterministic하게 선택할 수 없다.

∙ [eqn: epsilon]-생성규칙을 갖는 문법에 대해서는 nonterminal 다음에 오는 terminal을 알아야 한다.

*

[정의 7.5] FOLLOW(A) = { a ∪ {$} | S⇒[eqn: alpha]Aa[eqn: beta], [eqn: alpha, beta]∈V*, a∈VT }

∙ FOLLOW 구하는 방법

1. start symbol은 $를 초기값으로 갖는다.

FOLLOW(S) = {$}

2. A → [eqn: alpha B beta], [eqn: beta]≠[eqn: epsilon]일 때

FOLLOW(B) = FOLLOW(B) ∪ (FIRST([eqn: beta])-{[eqn: epsilon]})

*

3. A→[eqn: alpha B] 또는 A→[eqn: alpha B beta]이고 [eqn: beta]⇒[eqn: epsilon]일 때

FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(A)

예5) [예4]의 문법에 대한 FOLLOW

E → TE'

E' → +TE' |[eqn: epsilon]

T → FT'

T' → *FT' |[eqn: epsilon]

F → (E) | id

FOLLOW(E) = {$} ∪ FIRST()) = { ), $ }

FOLLOW(E') = FOLLOW(E)

FOLLOW(T) = (FIRST(E')-{[eqn: epsilon]}) ∪ FOLLOW(E) ∪ FOLLOW(E')

= { +, ), $ }

FOLLOW(T') = FOLLOW(T)

FOLLOW(F) = (FIRST(T')-{[eqn: epsilon]}) ∪ FOLLOW(T) ∪ FOLLOW(T')

= { +, *, ), $ }

7.1.3 LL 조건

∙ sentential form에서 nonterminal을 대치하기 위한 생성규칙을 deterministic하게 선택하기 위한 조건

∙ X → [eqn: alpha_1 ~|~ alpha_2 ~|~ alpha_3~ |~ ⋯ ~|~ alpha_n] 과 같은 생성규칙이 있을 때, 현재의 input symbol ai를 보고 X-생성규칙 중에서 하나를 deterministic하게 선택하는 조건

sentential form : a1a2⋯ai-1X[eqn: alpha]

input string    : a1a2⋯ai-1aiai+1⋯an

[정의 7.6] LL 조건

임의의 생성규칙 A→[eqn: alpha~|~beta] 에 대하여 다음 조건을 만족하여야 한다.

1. FIRST([eqn: alpha]) ∩ FIRST([eqn: beta]) = [eqn: phi]

2. [eqn: epsilon]∈FIRST([eqn: alpha]) 이면, FOLLOW(A) ∩ FIRST([eqn: beta]) = [eqn: phi]

예6) 다음 문법으로 string i[e]←e 를 deterministic하게 parsing할 수 있는지

A → iB ← e

B → SB |[eqn: epsilon]

S → [eC] | .i

C → eC |[eqn: epsilon]

(1) LL 조건 test

1. nulllable symbols = { B, C }

2. 각 nonterminal의 FIRST

FIRST(A) = { i }	FIRST(B) = { [, ., [eqn: epsilon] }

FIRST(S) = { [, . }	FIRST(C) = { e, [eqn: epsilon] }

3. 각 nonterminal의 FOLLOW

FOLLOW(A) = { $ }	FOLLOW(B) = { ← }

FOLLOW(S) = { [, ., ← }	FOLLOW(C) = { ] }

4. [정의 7.6]에 의하여 LL 조건 test

(2) i[e]←e 에 대한 좌단유도 과정

A ⇒ iB ← e	i[e] ← e

⇒ iSB ← e	i[e] ← e

⇒ i[eC]B ← e	i[e] ← e

⇒ i[e]B ← e	i[e] ← e

⇒ i[e] ← e	i[e] ← e

7.2 Recursive-descent 파서

∙ recursion을 이용하여 구현한 LL 파서

∙ 각 nonterminal에 대해 recursive procedure를 작성

-->  procedure call에 의하여 유도

∙ 생성규칙의 선택 방법 : LOOKAHEAD

*	*

[정의 7.7] LOOKAHEAD(A→[eqn: alpha]) = FIRST({[eqn: omega]| S ⇒[eqn: mu A beta] ⇒[eqn: mu alpha beta]⇒[eqn: mu omega] ∈ VT*})

어떤 생성규칙을 적용했을 때 생성될 수 있는 terminal들의 집합

LOOKAHEAD(A→X1X2⋯Xn)

= FIRST(X1) ㊉ FIRST(X2) ㊉ ⋯ ㊉ FIRST(Xn) ㊉ FOLLOW(A)

예7) [예4]의 문법에서 각 생성규칙의 LOOKAHEAD를 구해 보자.

E → TE'

E' → +TE' |[eqn: epsilon]

T → FT'

T' → *FT' |[eqn: epsilon]

F → (E) | id

LA(E → TE') = FIRST(T) ㊉ FIRST(E') ㊉ FOLLOW(E) = { (, id }

LA(E' → +TE') = FIRST(+) ㊉ FIRST(T) ㊉ FIRST(E') ㊉

FOLLOW(E') = { + }

LA(E' → [eqn: epsilon]) = FIRST([eqn: epsilon]) ㊉ FOLLOW(E') = { ), $ }

LA(T → FT') = FIRST(F) ㊉ FIRST(T') ㊉ FOLLOW(T) = { (, id }

LA(T' → *FT') = FIRST(*) ㊉ FIRST(F) ㊉ FIRST(T') ㊉

FOLLOW(T') = { * }

LA(T' → [eqn: epsilon]) = FIRST([eqn: epsilon]) ㊉ FOLLOW(T') = { +, ), $ }

LA(F → (E)) = { ( }

LA(F → id) = { id }

[정의 7.8] strong LL 조건, strong LL(1) 문법

임의의 생성규칙 A→[eqn: alpha~|~beta] 에 대하여 다음 조건을 strong LL 조건이라 한다.

LOOKAHEAD(A→[eqn: alpha]) ∩ LOOKAHEAD(A→[eqn: beta]) = [eqn: phi]

예8) 다음 문법은 stong LL(1)문법인가? No

S → bRS | RcSa |[eqn: epsilon]

R → acR | b

LOOKAHEAD(S→bRS) = { b }

LOOKAHEAD(S→RcSa) = { a, b }

∴ LOOKAHEAD(S→bRS) ∩ LOOKAHEAD(S→RcSa) ≠[eqn: phi]

※ Recursive-descent 파서의 구현

1. Terminal symbol a에 대한 procedure pa, a의 token number를 qa라 했을 때

procedure pa;

begin

if nextsymbol = qa then get_nextsymbol

else error

end;

2. Nonterminal A에 대한 procedure pA

procedure pA;

begin

case nextsymbol of

LOOKAHEAD(A→X1X2⋯Xm):

for i:=1 to m do pXi;

LOOKAHEAD(A→Y1Y2⋯Yn):

for i:=1 to n do pYi;

........

LOOKAHEAD(A→Z1Z2⋯Zr):

for i:=1 to r do pZi;

otherwise: error;

end

end;

3. main procedure

begin

get_nextsymbol;

pS;

if nextsymbol = q$ then accept else error

end.

예9) 다음 문법에 대한 recursive-descent 파서를 구현하시오.

S → aAb

A → aS | b

예10) if 문에 대한 EBNF 표기법과 procedure

<if_st> ::= ‘if’ <C> ‘then’ <S> [‘else’ <S>]

예11) 명칭 list에 대한 EBNF 표기법과 procedure

<id_list> ::= ‘id’ {‘,’ ‘id’}

7.3 Predictive 파서

∙ recursive-descent 파서의 단점 ⇒ 생성규칙이 바뀌면 parser의 procedure를 수정해야 한다.

∙ predictive 파서 : [그림 7.1]

- 생성규칙이 바뀌더라도 parsing table만 수정하면 된다.

- predictive parser는 input, stack, parser, parsing table로 구성된다.

- output : left parse

∙ predictive 파서의 행동

1. 제거(pop)

: stack의 top symbol과 현재의 input symbol이 같은 경우

2. 확장(expand)

: stack의 top symbol이 nonterminal이면 생성규칙 적용하여 확장

즉, M[A,a] = {A→XYZ} 일 때 A를 pop하고 ZYX 순서로 push

3. 인식(accept)

: stack의 top symbol과 현재의 input symbol이 모두 $인 경우

4. 오류(error)

: stack의 top symbol이 nonterminal이면서

현재의 input symbol을 유도할 수 없는 경우

예12) 아래 문법에 대한 predictive parsing table

1. S → aSb

2. S → bA

3. A → aA

4. A → b

VT VN	a	b	$
S	1	2
A	3	4

예13) 다음 문법에 의하여 string aabccd를 predictive 파싱하는 과정

1. S → aS

2. S → bA

3. A → d

4. A → ccA

VT VN	a	b	c	d	$
S	1	2
A			4	3

Step	Stack	Input buffer	Action	Parse
1 2 3 4 5 6 7 8 9 10 11 12	$S $Sa $S $Sa $S $Ab $A $Acc $Ac $A $d $	aabccd$ aabccd$ abccd$ abccd$ bccd$ bccd$ ccd$ ccd$ cd$ d$ d$ $	expand 1 pop & advance expand 1 pop & advance expand 2 pop & advance expand 4 pop & advance pop & advance expand 3 pop & advance accept	1 1 11 11 112 112 1124 1124 1124 11243 11243 11243

7.4 predictive 파싱표의 구성

• 파싱표 : 2차원 배열 --- 크기는 |VN| * (|VT|+1), 원소는 생성규칙 번호

• 파싱표 구성 방법

1. 모든 a∈FIRST([eqn: alpha])에 대하여 M[A,a] = A→[eqn: alpha]

2. [eqn: epsilon]∈FIRST([eqn: alpha])이면, b∈FOLLOW(A)에 대하여 M[A,b] = A→[eqn: alpha]

※ LL(1) 문법일 조건

임의의 생성규칙 A→[eqn: alpha~ |~ beta]에 대하여

1. FIRST([eqn: alpha]) ∩ FIRST([eqn: beta]) = [eqn: phi]

2. [eqn: epsilon]∈FIRST([eqn: alpha])이면, FOLLOW(A) ∩ FIRST([eqn: beta])

예14) 파싱표 구성 예

1. E → TE'

2. E' → +TE'    3. E' → [eqn: epsilon]

4. T → FT'

5. T' → *FT'    6. T' → [eqn: epsilon]

7. F → (E)      8. F → id

(1) FIRST 계산

FIRST(E) = FIRST(T) = FIRST(F) = { (, id }

FIRST(E') = { +, [eqn: epsilon] }

FIRST(T') = { *, [eqn: epsilon] }

(2) FOLLOW 계산

FOLLOW(E) = FOLLOW(E') = { ), $ }

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

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

(3) 파싱표

VT VN	id	+	*	(	)	$
E E' T T' F	1 4 8	2 6	5	1 4 7	3 6	3 6

예15) 다음 문법에 대하여 물음에 답하시오.

S → aA | abA

A → Ab | a

(1) LL(1) 문법으로 고치고,

Left-factoring & left-recursion 제거

1. S → aS'

2. S' → A

3. S' → bA

4. A → aA'

5. A' → bA'

6. A' → [eqn: epsilon]

(2) FIRST와 FOLLOW를 구하여,

FIRST(S) = { a }	FOLLOW(S) = { $ }

FIRST(A) = { a }	FOLLOW(S) = { $ }

FIRST(S') = { a, b }	FOLLOW(S) = { $ }

FIRST(A') = { b, [eqn: epsilon] }	FOLLOW(S) = { $ }

(3) 파싱표를 작성하고,

VT VN	a	b	$
S S' A A'	1 2 4	3 5	6

(4) abab를 파싱하는 과정

Step	Stack	Input buffer	Action	Parse
1 2 3 4 5 6 7 8 9 10	$S $S'a $S' $Ab $A $A'a $A' $A'b $A' $	abab$ abab$ bab$ bab$ ab$ ab$ b$ b$ $ $	expand 1 pop & advance expand 3 pop & advance expand 4 pop & advance expand 5 pop & advance expand 6 accept	1 1 13 13 134 134 1345 1345 13456 13456

※ 파싱표 작성 연습

1. S → iCtSS'

2. S → a

3. S' → eS

4. S' → [eqn: epsilon]

5. C → b

VT VN	a	b	e	i	t	$
S S' C	2	5	3, 4	1		4

7.5 Strong LL(k) 문법과 LL(k) 문법

*	*

[정의 7.9] FIRSTk([eqn: alpha]) = { [eqn: omega] | [eqn: alpha]⇒[eqn: omega beta], |[eqn: omega]|=k, or [eqn: alpha]⇒[eqn: omega] and |[eqn: omega]|<k }

[정의 7.10] Strong LL(k) 문법

고정된 k에 대하여 2개의 좌단유도 과정이 존재할 때마다 다음을 만족한다.

( 생성규칙 A→[eqn: alpha~|~beta]에 대하여 )

*	*

1. S ⇒[eqn: u A gamma] ⇒[eqn: u alpha gamma] ⇒[eqn: ux] ∈ VT*와

*	*

2. S ⇒[eqn: v A delta] ⇒[eqn: v beta delta] ⇒[eqn: vy] ∈ VT*가 존재하여

3. FIRSTk(x) = FIRSTk(y)이면 [eqn: alpha = beta]이다.

[정의 7.13] LL(k) 문법

고정된 k에 대하여 2개의 좌단유도 과정이 존재할 때마다 다음을 만족한다.

( 생성규칙 A→[eqn: alpha~|~beta]에 대하여 )

*	*

1. S ⇒[eqn: u A gamma] ⇒[eqn: u alpha gamma] ⇒[eqn: ux] ∈ VT*와

*	*

2. S ⇒[eqn: u A delta] ⇒[eqn: u beta delta] ⇒[eqn: uy] ∈ VT*가 존재하여

3. FIRSTk(x) = FIRSTk(y)이면 [eqn: alpha = beta]이다.

※ Strong LL(k) 문법과 LL(k) 문법의 차이점

LL(k)는 A 앞에 생성된 terminal들이 같아야 하지만 Strong LL(k)는 그렇지 않다.

*	*

[정의 7.11] k-LOOKAHEAD(A→[eqn: alpha]) = FIRSTk({[eqn: omega] | S ⇒[eqn: u A beta] ⇒[eqn: u alpha beta] ⇒[eqn: u omega] ∈ VT*})

[정의 7.12] Strong LL(k) 문법의 조건

임의의 생성규칙 A→[eqn: alpha~|~beta]에 대하여

k-LOOKAHEAD(A→[eqn: alpha]) ∩ k-LOOKAHEAD(A→[eqn: beta]) = [eqn: phi] 이다.

※ Strong LL(k) 문법의 검사 : k 값을 1씩 증가시키면서 [정의 7.12] 적용.

예16) 다음 문법은 strong LL(k) 문법인가? strong LL(2)이다.

S → bRS | RcSa | [eqn: epsilon]

R → acR | b

(1)	1-LOOKAHEAD(S → bRS) = { b }

1-LOOKAHEAD(S → RcSa) = { a, b }

1-LOOKAHEAD(S → bRS) ∩ 1-LOOKAHEAD(S → RcSa) = { b }

∴ strong LL(1) 문법이 아니다.

(2)	2-LOOKAHEAD(S → bRS) = { ba, bb }

2-LOOKAHEAD(S → RcSa) = { ac, bc }

2-LOOKAHEAD(S → [eqn: epsilon]) = { $, a, aa }

2-LOOKAHEAD(R → acR) = { ac }

2-LOOKAHEAD(R → b) = { b, ba, bb, bc }

2-LOOKAHEAD(S → bRS) ∩ 2-LOOKAHEAD(S → RcSa) ∩

2-LOOKAHEAD(S → [eqn: epsilon]) = [eqn: phi]

2-LOOKAHEAD(R → acR) ∩ 2-LOOKAHEAD(R → b) = [eqn: phi]

∴ strong LL(2) 문법이다.

예17) 다음 문법은 strong LL(2)는 아니지만 LL(2)인 경우이다.

S → aAaa | bAba

A → b |[eqn: epsilon]

(1)	2-LOOKAHEAD(A → b) = { ba, bb }

2-LOOKAHEAD(A → [eqn: epsilon]) = { aa, ba }

2-LOOKAHEAD(A → b) ∩ 2-LOOKAHEAD(A → [eqn: epsilon]) = { ba }

∴ strong LL(2) 문법이 아니다.

(2)	유도 과정이 S ⇒ aAaa ⇒ abaa인 경우에 A → b 를 적용한다.

유도 과정이 S ⇒ bAba ⇒ bba인 경우에 A → [eqn: epsilon] 를 적용한다.

※ strong LL(1) ⇔ LL(1) : 증명

즉, LL(1) 문법과 strong LL(1) 문법은 동등하다.

연습문제 풀이