제6장 구문 분석 (syntax analysis)

컴파일러 구성론

강 승 식

6.1 구문 분석 방법

□ top-down parsing : 좌단 유도 이용

S □ ... □ [eqn: omega]  :  derivation 과정

□ bottom-up parsing : 우단 역유도 이용

S □ ... □ [eqn: omega]  :  reduce 과정

예1) top-down 파싱에 따라 abac의 구문분석 과정

1. S → XY

2. X → aX

3. X → b

4. Y → aY

5. Y → c

S □ XY	(1)

□ aXY	(12)

□ abY	(123)

□ abaY	(1234)

□ abac	(12345)

좌파스: 1 2 3 4 5

예2) [예1]의 문법에 따라 abac의 bottom-up 파싱 과정

S □ XY	(1)

□ XaY	(14)

□ Xac	(145)

□ aXac	(1452)

□ abac	(14523)

우파스: 3 2 5 4 1

6.2 구문 분석기의 출력 : parse tree

예3) id+id에 대한 좌단 유도와 우단 역유도 과정

1. E → E + T

2. E → T

3. T → T * F

4. T → F

5. F → (E)

6. F → id

좌단유도 과정

E □ E + T	(1)

□ T + T	(12)

□ F + T	(124)

□ id + T	(1246)

□ id + F	(12464)

□ id + id	(124646)

우단 역유도 과정

E □ E + T	(1)

□ E + F	(14)

□ E + id	(146)

□ T + id	(1462)

□ F + id	(14624)

□ id + id	(146246)

예4) (id+id)에 대한 parse tree를 구성하는 과정

1. E → E + E

2. E → E * E

3. E → (E)

4. E → -E

5. E → id

예5) [예4]의 문법에 따라 id+id*id에 대한 parse tree 구성

※ 구문 트리 ( AST : Abstract Syntax Tree )

- 코드생성 단계에서 필요한 정보만 갖는 tree

- nonterminal node : 의미있는 생성규칙의 이름

- terminal node : 의미있는 terminal symbol

예6) id+id*id에 대한 parse tree와 구문 트리

1. E → E + T	□ add

2. E → T

3. T → T * F	□ mul

4. T → F

5. F → (E)

6. F → id

예7) if 문에 대한 구문 트리의 예

if (a > b) then a = b + 1; else a = b - 2;

6.3 Top-down parsing

6.3.1 일반적인 top-down 방법

□ backtracking에 의하여 parsing하는 과정

1. start symbol의 첫번째 생성규칙을 적용한다.

2. 생성된 sentential form의 string과 input string을 차례로 비교한다.

3. 비교 과정에서 nonterminal이 생성된 string이 나오면 이 nonterminal의

첫번째 생성규칙을 적용하여 유도한다.

유도된 string과 input string이 같으면 2, 3을 반복한다.

4. 비교한 두 symbol이 같지 않으면, backtracking

□ 현재 적용된 생성규칙을 제거하고 다른 생성규칙 적용.

input symbol의 위치는 제거한 생성규칙에서 보았던 symbol의 수만큼

되돌림.

5. 위 과정을 반복하다가 유도된 string이 input string과 일치하면 accept,

더 이상 적용할 생성규칙이 없으면 reject.

예8) input string accd에 대한 top-down parsing 과정

1. S → aAd

2. S → aB

3. A → b

4. A → c

5. B → ccd

6. B → ddc

※ top-down parsing의 문제점

1. 생성규칙에 left-recursion(좌순환 규칙)이 존재하면 무한 loop에 빠진다.

2. backtracking overhead가 크다.

6.3.2 left-recursion

[정의 6.1] 직접(immediate) left-recursion : A □ A[eqn: alpha] 유형

*

[정의 6.2] 간접(indirect) left-recursion : A □ A[eqn: alpha] 유형

※ 좌순환 규칙을 우순환 규칙으로 변환

(1) A □ [eqn: A alpha] |[eqn: beta]가 생성하는 문장 유형은 [eqn: beta alpha^*]이고,

[eqn: alpha^*]는 우반복 규칙으로 A' □ [eqn: alpha A']|[eqn: epsilon] 로 기술된다.

A □ [eqn: beta]A'

A' □ [eqn: alpha A'] |[eqn: epsilon]

(2) A □ [eqn: A alpha_1] |[eqn: A alpha_2] | □ |[eqn: A alpha_m] |[eqn: beta_1] | [eqn: beta_2] | □ |[eqn: beta_n]에 대하여

A □ [eqn: beta_1 A']|[eqn: beta_2 A']| □ |[eqn: beta_n A']

A' □ [eqn: alpha_1 A']|[eqn: alpha_2 A']| □ |[eqn: alpha_m A']|[eqn: epsilon]

예9) 다음 문법의 left-recursion을 제거

E → E + T | T

T → T * F | F

F → (E) | id

nonterminal E 에 대해

E → TE'

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

nonterminal T 에 대해

T → FT'

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

left-recursion이 제거된 문법

E → TE'

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

T → FT'

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

F → (E) | id

※ 간접 left-recursion의 제거 방법(알고리즘 6.1)

1. nonterminal들을 순서화한다 ( 정의를 먼저하고 사용을 나중에 하도록 )

2. 간접 순환이 발생한 생성규칙에 대입(substitution) 기법을 이용하여 직접 순환으로 변환.

예10) 간접 left-recursion의 제거

S □ Aa | b

A □ Ac | Sd | e

6.3.3 Left-factoring

□ 공통된 prefix를 새로운 nonterminal을 도입하여 인수 분해한다.

A □ [eqn: alpha beta~ |` alpha gamma]

□

A □ [eqn: alpha A']

A' □ [eqn: beta~|` gamma]

예11) 다음 문법에 대하여 left-factoring

S □ iCtS | iCtSeS | a

C □ b

□

S □ iCtSS' | a

S' □ eS | [eqn: epsilon]

C □ b

6.3.4 No-backtracking의 조건

□ left-recursion을 제거하고 left-factoring을 한 후에도 top-down 파서는

주어진 string을 결정적(deterministic)으로 parsing할 수 있는 것은 아니다.

□ Top-down 방법에서 정의된 문법이 결정적(deterministic)으로 parsing할 수 있도록 제약 조건을 줄 수 있다. 이를 LL 조건이라 하고, 이 조건을 만족하는 문법을 LL 문법이라 한다.

※ FIRST와 FOLLOW 이용   □□□  chapter 7

FIRST : 어떤 nonterminal이 확장되었을 때 첫번째 terminal들의 집합

FOLLOW : 어떤 nonterminal의 다음에 올 수 있는 terminal들의 집합

6.4 Bottom-up 방법

□ top-down parsing

start symbol로부터 확장(expand)에 의해 input string을 생성해 나가는 과정

□ bottom-up parsing

input string으로부터 start symbol로 축약(reduce)되어 가는 과정

6.4.1 Reduce

[정의 6.3] reduce의 정의

*

S □[eqn: alpha beta omega] 이고 A □[eqn: beta]의 생성규칙이 존재할 때,

sentential form [eqn: alpha beta omega]에서 [eqn: beta]를 A로 대치하는 것.

즉, 생성규칙의 RHS와 같은 부분을 그 생성규칙의 LHS로 대치.

예12) 다음 문법으로 input string abbcde를 reduce하는 과정

1. S → aAcBe

2. A → Ab

3. A → b

4. B → d

Reduce 과정

abbcde	==> aAbcde	(reduce 3)

==> aAcde	(reduce 2)

==> aAcBe	(reduce 4)

==> S	(reduce 1)

[정의 6.4] handle의 정의

*

S □[eqn: alpha A omega] □[eqn: alpha beta omega] 의 유도과정이 있을 때, [eqn: beta]를 [eqn: alpha beta omega]의 handle이라 한다.

즉, 어떤 sentential form의 reduce되는 부분을 handle이라 한다.

예13) a + a * a의 우단 역유도에서 handle의 예

1. E → E + T

2. E → T

3. T → T * F

4. T → F

5. F → (E)

6. F → a

a + a * a ==> F + a * a	(6)

==> T + a * a	(64)

==> E + a * a	(642)

==> E + F * a	(6426)

==> E + T * a	(64264)

==> E + T * F	(642646)

==> E + T	(6426463)

==> E	(64264631)

예14) id+id*id의 bottom-up 파싱 과정

※ handle을 어떻게 찾을 것인가, handle에 적용할 생성규칙을 어떻게 결정?

FOLLOW와 LOOKAHEAD  □□□  see chapter 8

6.4.2 Shift-reduce 파싱

□ stack과 input buffer를 사용하여 구현하는 bottom-up 파서 : [그림 6.3]

□ Shift-reduce 파서의 동작

shift   : 현재의 input symbol을 stack으로 move

reduce : stack의 top에 있는 handle을 생성규칙의 lhs로 대치

accept : input string을 accept

error  : input string을 reject

예15) [예13]의 a+a*a 에 대한 Shift-reduce 파싱 예 : 5장 [예28]과 동일

1. E → E + T

2. E → T

3. T → T * F

4. T → F

5. F → (E)

6. F → a

a + a * a ==> F + a * a	(6)

==> T + a * a	(64)

==> E + a * a	(642)

==> E + F * a	(6426)

==> E + T * a	(64264)

==> E + T * F	(642646)

==> E + T	(6426463)

==> E	(64264631)

입력 스트링 a + a * a 의 구문 분석 과정

Step	Stack	Input buffer	Action
1 2 3 4 5 6 7 8 9 10 11 12 13 14	$ $a $F $T $E $E + $E + a $E + F $E + T $E + T * $E + T * a $E + T * F $E + T $E	a + a * a$ + a * a$ + a * a$ + a * a$ + a * a$ a * a$ * a$ * a$ * a$ a$ $ $ $ $	shift a reduce F → a reduce T → F reduce E → T shift + shift a reduce F → a reduce T → F shift * shift a reduce F → a reduce T → T * F reduce E → E + T accept

6.4.3 트리 생성

Shift action -- terminal node 생성

BUILD_NODE(a) : terminal a를 단말 노드로 만든다.

Reduce action -- subtree 생성

BUILD_TREE(n) : 생성규칙 번호 n에 해당하는 subtree 생성

예16) 스트링 a,a를 파싱하고 그 결과를 파스 트리로 구성

1. LIST → LIST , ELEMENT

2. LIST → ELEMENT

3. ELEMENT → a

Step	Stack	Input buffer	Action	Parse Tree
1 2 3 4 5 6 7 8	$ $a $ELEMENT $LIST $LIST , $LIST , a $LIST , ELEMENT $LIST	a , a$ , a$ , a$ , a$ a$ $ $ $	shift a reduce 3 reduce 2 shift , shift a reduce 3 reduce 1 accept	BUILD_NODE(a) BUILD_TREE(3) BUILD_TREE(2) BUILD_NODE(,) BUILD_NODE(a) BUILD_TREE(3) BUILD_TREE(1) return tree

예17) [예16]의 문법에 따라 스트링 a,a를 파싱하고 그 결과를 AST 구성

0. ACCEPT → LIST

1. LIST → LIST , ELEMENT

2. LIST → ELEMENT

3. ELEMENT → a

Step	Stack	Input buffer	Action	Parse Tree
1 2 3 4 5 6 7 8 9	$ $a $ELEMENT $LIST $LIST , $LIST , a $LIST , ELEMENT $LIST $ACCEPT	a , a$ , a$ , a$ , a$ a$ $ $ $ $	shift a reduce 3 reduce 2 shift , shift a reduce 3 reduce 1 reduce 0 accept	BUILD_NODE(a) BUILD_NODE(a) BUILD_TREE(0) return tree

연습문제 풀이