[컴파일러] Top-down 파싱 | 예측구문분석기 - 파싱테이블 구성하는 방법 | (Predictive, LL parser)

Intro : LL(1) 파서 구현방법

ⓐ Recursive descent parser (재귀적 하강 구문분석기)

- 직관적, 쉽다

- 문법이 바뀔 때마다 parser 전체를 바꿔야 한다. 

 

ⓑ Predictive parser (예측 구문분석기, LL(1) 구문분석)

- 파싱테이블을 이용한다

- 문법이 바뀌어도 parser를 바꾸는게 아니라 파싱테이블만 바꾸면 된다.

- recall) LL : Left to Right 스캐닝 & Left 유도

- recall) LL(1) : lookahead가 1이라는 거다. 2, 3만 되어도 파싱테이블이 엄청 커져서 컴파일러에 부적합하여 대부분 1로 한다. 이 글에서 LL이라고 하면 LL(1)을 칭하겠다.

 

.

.

 

Predictive parser에서 구문분석할 때 '파싱 테이블'을 이용한다.

파싱 테이블을 만들어두면 이 테이블을 보고 기계적으로 파싱해나갈 수 있다.

LL(1)이기 때문에 기계적으로 입력문자 하나씩 보면 된다.

 

이 글은 파싱 테이블은 어떻게 구성되는지, 어떻게 만드는지에 대한 글이다.

 

파싱 테이블을 구성하는 알고리즘을 먼저 보이자면 이렇다.

for each A →α ∈ 생성규칙

  if : α is not nullable & terminal a ∈ FIRST(α) 

  then : M[A, a] = A→α

  if : α is nullable

  then : for b ∈ FOLLOW(A), M[A, b] = A→α

아래서 예제와 함께 익숙해져보자.

 

 

 

---

Predictive parser의 구성

Predictive parser는 크게 3가지로 구성된다.

ㄴ stack

ㄴ input buffer

ㄴ parsing table

$ : 스택의 bottom marker, 입력 문자열의 끝을 가리키는 end marker

 

 

---

파싱 테이블

문법 G에 대한 파싱테이블을 만들어보면, G가 LL문법인지 아닌지를 알 수 있다.

테이블의 모든 칸에 2개이상의 생성규칙이 들어가 있지 않으면 LL문법이다.

 

 

▼ predictive 파싱 테이블 구성 방법

for each A →α ∈ 생성규칙

  if : α is not nullable & terminal a ∈ FIRST(α) 

  then : M[A, a] = A→α

  if : α is nullable

  then : for b ∈ FOLLOW(A), M[A, b] = A→α

 

(와닿지 않으면 몇번 직접 해보면 된다. 금방 한다.)

 

 

 

● input string이 LL문법일 경우 파싱 테이블 예제

 

- 다음 문법에 대한 파싱 테이블 구하기

 

1. E -> TE'	2. E' -> +TE'
3. E' -> ε	4. T -> FT'
5. T' -> *FT'	6. T' -> ε
7. F -> (E)	8. F -> id

 

 

- FIRST와 FOLLOW를 구해둔다

-- FIRST

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

First(T') = { *, ε }

First(E') = { +, ε } 

-- FOLLOW

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

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

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

 

 

- 파싱 테이블을 작성한다.

행 : Non-terminal 

열 : terminal

파싱 테이블 : non-terminal x terminal = 적용될 생성규칙 번호

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

 

 

아래 생성규칙 넘버를 잘 채워넣는다.

 

1. E -> TE'	2. E' -> +TE'
3. E' -> ε	4. T -> FT'
5. T' -> *FT'	6. T' -> ε
7. F -> (E)	8. F -> id

 

 

<풀이과정>

* FIRST를 먼저 보자. 

lhs가 E인 규칙1을 보면 FIRST(E)에 id, ( 가 포함된다. 따라서 M[E, id] = M[E, ( ] = 규칙1

lhs가 E'인 규칙2, 3을 보면 FIRST(E')에 +, ε이 포함된다. 

따라서 M[E', +]=규칙2 다.

그런데 규칙3을 보면 E'가 nullable이므로, 규칙3은 FOLLOW(E')를 보고 넣어야 한다.

lhs가 T인 규칙4를 보면 FIRST(T)에 id, ( 가 포함된다. 따라서 M[T, id] = M[T, ( ] = 규칙4

lhs가 T'인 규칙5, 6을 보면 FIRST(T')에 *, ε가 포함된다.

따라서 M[T', *]=규칙5 다.

그런데 규칙6을 보면 T'가 nullable이므로, 규칙6은 FOLLOW(T')를 보고 넣어야 한다.

lhs가 F인 규칙 8을 보면 FIRST(F)에 ( 와 id가 포함된다. 따라서 M[F, ( ]=규칙7 그리고 M[F, id]=규칙8이다.

* null이었던 것에 대해 FOLLOW를 보자.

규칙3에서 E'가 nullable이었다. FOLLOW(E')={ ), $}다.

따라서 M[E', ) ] = M[E', $] = 규칙3

규칙6에서 T'가 nullable이었다. FOLLOW(T')={ +, ), $ }다.

따라서 M[T', +] = M[T', ) ] = M[T', $] = 규칙6

 

끝나따!

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡ

▼ 같은 내용

∨ FIRST

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

- Non-terminal E에서 terminal {id}, { ( }가 유도되려면 생성규칙 1번 적용

- Non-terminal T에서 terminal {id}, { ( }가 유도되려면 생성규칙 6번 적용

- Non-terminal F에서 terminal {id}가 유도되려면 8번이, { ( }가 유도되려면 7번 적용

First(T') = { *, ε }

- Non-terminal T'에서 terminal { * }가 유도되려면 생성규칙 5번 적용

First(E') = { +, ε } 

- Non-terminal E'에서 terminal { + }가 유도되려면 생성규칙 2번 적용

 

∨ FOLLOW를 보고 마저 채워보자. FOLLOW는 nullable일때 본다는 것을 주의하자.

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

- Non-terminal E'에서 terminal { ) }, { $ }가 유도되려면 생성규칙 3번 적용

- E에서 ), $ 유도하는 건 왜 안따지지? 앗 E -> TE'에서 TE'가 not nullable이라서!

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

- Non-terminal T'에서 terminal { + }, { ) }, { $ }가 유도되려면 생성규칙 6번 적용

- T에서 +, ), $ 유도하는 건 왜 안따지지? 아아 얘도 T -> FT'에서 FT'가 not nullable이라서!!

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

- Non-terminal F도 볼 필요 없다. not nullable이라서!!!

 

가만보면 파싱테이블의 모든 Non-terminal X terminal 한 칸에 두개 이상의 생성규칙은 들어가지 않는다.

=> 그러면 LL문법이다!

 

 

 

 

● input string이 LL문법이 아닐 경우 파싱 테이블 예제

 

- 다음 문법에 대한 파싱 테이블 구하기

1. S -> iCtSS'

2. S -> a

3. S' -> eS

4. S' -> ε

5. C -> b

 

 

- FIRST와 FOLLOW를 구해둔다

-- FIRST

First(S) = {i, a}

First(S') = {e, ε}

First(C) = {b}

-- FOLLOW

참고) 1, 3번 규칙을 보니까 Follow(S) == Follow(S')다. 

Follow(S) = (First(S') - {ε}) ∪ Follow(S) = { e, $ }

Follow(S') = { e, $ }

Follow(C) = { t }

 

 

- 파싱 테이블을 작성한다.

만들어진 파싱 테이블을 보면, 규칙 2개 이상이 들어간 칸이 존재한다.

그러므로 input string은 LL문법이 아니다. 

즉, 결정적인 선택이 불가하다

 

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

 

1. S -> iCtSS'

2. S -> a

3. S' -> eS

4. S' -> ε

5. C -> b

 

 

<풀이과정>

* 일단 FIRST 먼저 보기

lhs가 S인 규칙 1,2를 보면 FIRST(S)에 i와 a가 포함된다. 그럼 M[S, i]=규칙1, M[S, a]=규칙2 넣으면 되겠다

lhs가 S'인 규칙 3,4를 보면 FIRST(S')에 e와 ε가 있다. nullable이 아닌 경우인 M[S', e]=규칙3 넣자.

반면 규칙 4를 보면 S'가 nullable하다는 것을 알 수 있다. 

그럼 FOLLOW(S')를 봐주면 되겠다.

lhs가 C인 규칙 5를 보면 FIRST(C)에 b가 포함된다. M[C, b]=규칙5 넣자.

* FIRST에서 nullable인 경우에 대해 FOLLOW를 보기

"규칙 4"에서 S'가 nullable임을 봤다. 그럼 FOLLOW(S')를 봐야 한다.

FOLLOW(S')={ e, $ }다.

그럼 M[S', e]와 M[S', $]에다가 "규칙 4를" 넣어주면 된다. 규칙4를!!

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

-- FIRST

First(S) = {i, a}

First(S') = {e, ε}

First(C) = {b}

 

-- FOLLOW

Follow(S) = (First(S') - {ε}) ∪ Follow(S) = { e, $ }

Follow(S') = { e, $ }

Follow(C) = { t }

 

 

 

---

오 근데 이런 파싱테이블을 파서가 어떻게 사용해서 구문분석한다는 건지

한번 쓱 보면 더 좋겠다 >.<

 

 

- 파서는 다음 액션을 반복하며 구문분석한다.

recall. 아까 perspective parser는 스택과 입력버퍼를 둔다고 했다.

- pop : 스택에서 pop 또는 입력버퍼에서 pop

- expand : 스택 탑이 Non-terminal이면 알맞은 생성규칙을 적용하여 pop & expand해간다.

                스택에 있는 Non-terminal을 생성규칙이 유도하는 걸로 바꿔치기하는 것이다.

그리고 구문분석이 끝나는 경우는 이러하다.

- accept : 입력 스트링이 올바름을 인식하여 구문분석 성공하거나

- error : 구문분석에 실패하거나 : 스택탑이 Non-terminal인데 유도불가한경우 (즉 적용할 규칙 존재 X)

 

 

- 예제

입력 스트링 : aabccd

생성규칙

1. S -> aS

2. S -> bA

3. A -> d

4. A -> ccA

 

	stack	input string	parsing action	parse
1	$S	aabccd$	expand 1	1
2	$Sa	aabccd$	pop & advance	1
3	$S	abccd$	expand 1	11
4	$Sa	abccd$	pop & advance	11
5	$S	bccd$	expand 2	112
6	$Ab	bccd$	pop & advance	112
7	$A	ccd$	expand 4	1124
8	$Acc	ccd$	pop & advance	1124
9	$Ac	cd$	pop & advance	1124
10	$A	d$	expand 3	11243
11	$d	d$	pop & advance	11243
12	$	$	accept	11243

 

Let ) 파싱 테이블 M이 다 마련되어 있다!

주의 ) 스택에 넣을 때 순서 유의! 먼저 봐야 할 문자를 당연히 위로 가게끔

 

맨 처음 스택에는 시작심볼 넣고 시작!

과정1: 파싱 테이블에서 M[S, a]를 찾아 규칙1을 적용 : expand 1

과정2: expand되었다! 엇 문자 a가 일치한다. 일치하는 문자열 a를 pop한다. 그리고 포인터를 다음 문자열로 옮긴다.

           즉 pop & advance

과정3: 파싱 테이블에서 M[S, a]를 찾아 규칙 1을 적용 : expand 1

과정4: pop & advance

과정5: 파싱 테이블에서 M[S, b]를 찾아 규칙 2를 적용 : expand 2

과정6: pop & advance

과정7: 파싱 테이블에서 M[A, c]를 찾아 규칙 4를 적용 : expand 4

과정8: pop & advance

과정9: pop & advance

과정10: 파싱 테이블에서 M[A, d]를 찾아 규칙 3을 적용 : expand 3

과정11: pop & advance

과정12: accept : 스택도 입력도 다 제거하고 $만 남았다. 구문분석 성공!

 

 

 

- 또다른 예제

문자열 (a,a)에 대해 파싱해보기!!

 

	stack	input string	parsing action	parse
1	$S	(a,a)$
2
3
4
5
6
7
8
9
10
11
12

 

---

이렇게..

 

Predictive Parser를 공부하면서

FIRST와 FOLLOW를 사용하여

파싱테이블을 직접 만들어보고

input string이 LL문법인지 아닌지까지 확인해보았다.