구문 분석 : 하향식 구문 분석

구문 분석

- 주어진 입력이 올바른 프로그램인가를 검사하고 다음 단계에서 필요한 정보를 구성하는 과정

- 스캐너에 의해 생성된 토큰을 입력으로 받아 주어진 문법에 맞는지를 검사하고, 문법에 맞으면 파스 트리를 생성하고 맞지 않으면 에러를 내는 단계

- 구문 분석을 담당하는 도구를 구문 분석기(Syntax analyzer) 혹은 파서(parser)라고 함

 

방법: 파스 트리를 어떤 순서로 만들어 가느냐에 따라 분류

하향식 구문 분석

- 입력 문자열을 한 번에 한 심볼씩 좌에서 우로 검사, 루트 노드에서 시작하여 터미널 노드로 만들어 나가는 방법

- 시작기호 S로부터 문법의 규칙을 적용하여 좌단 유도에 의해 주어진 문장을 찾아가는 방법

- 좌단 유도에 의한 좌파스가 생성됨

 

상향식 구문 분석

- 입력 문자열을 한 번에 한 심볼씩 좌에서 우로 검사, 터미널 노드에서 시작하여 루트 노드로 감축해 나가는 방법

- 입력된 문장에서 감축에 의해 시작 기호를 찾아가는 방법으로 우단 유도의 역순이 됨

- 우단 유도의 역순에 의한 우파스가 생성

 

---

 

하향식 구문 분석

구현이 간단하여 학습 시엔 자주 사용하나 역추적 문제 때문에 상업적 용도로는 잘 사용하지 않음

여러 방법 중 하나

1. 시작 기호에 대해 생성 규칙을 적용, 이때 생성 규칙이 여러 개 존재하면 첫번째 생성 규칙부터 적용. 생성 규칙 적용 시마다 부분 파스 트리를 구성해 나감

2. 생성된 문장 형태의 문자열과 입력 기호를 차례로 비교

3. 만약 유도된 문자열과 입력 기호가 같으면 계속 비교해 나감

4. 비교한 두 기호가 같지 않으면 생성 규칙을 잘못 적용한 것으로, 현재 적용된 생성 규칙을 제거하고 다른 생성 규칙을 적용함. 이때 입력 기호의 위치는 제거한 생성 규칙에서 보았던 기호의 개수만큼 뒤로 이동하는데 이를 역추적(backtracking)이라 함

5. 과정을 반복하다 더 이상 적용할 생성 규칙이 없으면 주어진 문장을 주어진 문법에 올바르지 않은 문장으로 인식하고 에러 메시지를 출력. 만약 생성된 문자열이 주어진 문자열과 일치하면 올바른 문장으로 인식하고 파스 트리를 출력으로 내보냄

 

ex. cabdd 파스 트리 구성

S -> cDd

D -> a

D -> aE

E -> bb

E -> bd

 

트리를 그리긴 시간이 걸리니 만들어지는 문자열만 쓰면..

S

cDd  // 입력이 같으니 오른쪽으로 이동 (c에서 D로)

cad   // 입력 기호와 맞지 않음, 적용된 생성 규칙을 제거하고 새로..

caEd   // 생성된 기호가 일치하니 입력 위치를 오른쪽으로 이동

cabbd // 첫 b가 맞아서 오른쪽으로 이동.. 하니 안맞음. 제거 후 다시 적용

cabdd // d 일치, 오른쪽 이동, 다시 일치. 생성된 기호가 입력 기호와 일치하게 됨

 

---

 

역추적이 시간이 많이 쓰여서 실제 컴파일러의 구문 분석 알고리즘으론 부적합

- 역추적을 하지 않고 결정적으로 구문 분석을 할 수 있는 방법이 필요

 

하향식에서 문법에 어떤 제약 조건을 걸어서 결정적인 구문 분석이 가능한데,

- 이러한 조건을 LL 조건이라 함

LL 조건을 만족하는 문법 : LL 문법

- LL 문법으로 하향식 구문 분석기를 만들어 구문 분석을 하는 방법을 LL 구문 분석이라 함

- LL은 입력 문자열을 왼쪽(L)에서 오른쪽으로 읽어가며 좌파스(L)를 생성하기 때문에 붙은 이름

 

LL 방법은 주어진 문자열과 같은 문장을 생성하기 위해 현재의 입력 기호를 보고 적용될 생성 규칙을 결정적으로 선택하여 유도

그리고 현재의 입력 기호와 생성된 터미널 기호가 같지 않으면 주어진 문장을 틀린 문장으로 간주

 

LL 조건은 유도 과정에서 나타난 문장 형태에서 논터미널을 대체하는 생성 규칙을 결정적으로 선택하기 위해

FIRST와 FOLLOW를 이용

---

 

FIRST

- 문법 G가 문맥 자유 문법일 때, 논터미널 기호 A에 대한 FIRST는 다음과 같다

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

- 즉, 논터미널 기호 A로부터 유도되어 첫번째로 나타날 수 있는 터미널 기호의 집합

 

예시

S -> C | D

C -> aC | b

D -> cD | d

 

논터미널 기호는 S, C, D이므로 이것들에 대한 FIRST를 구하면 됨

S => C => aC로 유도되는 a는 S의 FIRST

S => C => b

S => D => cD

S => D => d

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

 

같은 방식으로 하면

FIRST(C) = {a, b}

FIRST(D) = {c, d}

 

 

nullable

- 논터미널 A가 ε을 유도할 수 있으면 A를 nullable하다고 부름

- 즉 A =>* ε 이면 널러블하다.

 

ring sum ⊕

- 앱실론의 포함 여부에 따라 다르게 동작하는 집합 연산

- 1. ε ∉ A, then A ⊕ B = A

- 2. ε ∈ A, then A ⊕ B = (A − {ε}) ∪ B

 

FIRST(A1A2...An)

- == FIRST(A1) ⊕ FIRST(A2) ⊕ FIRST(A3) ⊕ ...  ⊕ FIRST(An)- 어떤 문자열의 퍼스트는 가장 왼쪽 기호로부터 유도되는 터미널 기호를 찾는 것- 즉, 문자열의 첫번째 기호가 널러블하면 그 문자열 다음 기호의 FIRST도 해당 문자열의 FIRST에 속함- nullable이 아닐 때까지 기호들의 FIRST를 합집한 것이 문자열의 FIRST

 

FIRST(X) 계산 규칙

1. 만약 X가 하나의 터미널 기호이면 {X}는 FIRST(X)에 포함된다

2. 만약 X가 하나의 논터미널 기호이고 X -> aβ의 생성 규칙이 존재하면 터미널 기호인 {a}는 FIRST(X)에 속함

3. 만약 X -> ε의 생성 규칙이 존재하면 { ε }도 FIRST(X)에 속함

4. 만약 X -> Y1Y2...Yk의 생성 규칙이 존재하면 FIRST(X) = FIRST(X) ∪ FIRST(Y1Y2....Yk)

 

예시E -> TE'E' -> +TE' | ε T -> FT'T' -> *FT' | ε F -> (E) | id

 

생성 규칙 형태에 따라 2번을 적용하면..FIRST(E) = { }FIRST(E') = { + }

FIRST(T) = { }

FIRST(T') = { * }

FIRST(F) = { (, id }

 

3번 규칙 적용..

FIRST(E) = { }

FIRST(E') = { +, ε }

FIRST(T) = { }

FIRST(T') = { *, ε }

FIRST(F) = { (, id }

 

4번, 1번 규칙 적용

FIRST(E)

= FIRST(E) ∪ FIRST(TE')

= FIRST(E) ∪ ( FIRST(T) ⊕ FIRST(E') )

= FIRST(E) ∪ FIRST(T)      // T가 널러블하지 않음

 

FIRST(T)

= FIRST(T) ∪ FIRST(FT')

= FIRST(T) ∪ ( FIRST(F) ⊕ FIRST(T') )

= FIRST(T) ∪ FIRST(F) 

= { (, id }

 

결과적으로

FIRST(E) = { (, id }

FIRST(E') = { +, ε }

FIRST(T) = { (, id }

FIRST(T') = { *, ε }

FIRST(F) = { (, id }

 

 

FOLLOW(A)

- 문법 G가 문맥 자유 문법일 때 논터미널 기호 a의 FOLLOW(A)는 다음과 같음

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

- 어떤 문장 형태에서 논터미널 기호 A 다음에 나오는 터미널 기호들의 집합

- $는 입력 문자열의 끝을 나타내는 기호, 시작 기호에 대한 FOLLOW는 $임

 

예시

E -> TE'    .. 1

E' -> +TE' | ε    .. 2

T -> FT'    .. 3

T' -> *FT' | ε    .. 4

F -> (E) | id   .. 5

 

FOLLOW(E)

- 시작 기호이므로 입력 문자열의 끝에 $, 또한 5번 생성 규칙에서 E 다음에 )

- FOLLOW(E) = { $, ) }

 

FOLLOW(E')

- E -> TE'에서 E' 다음에 나오는 기호는 E 다음에 나오는 기호임을 알 수 있음

- FOLLOW(E) ⊆ FOLLOW(E'), 이외의 FOLLOW(E') 은 없음

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

 

FOLLOW(T)

- E -> TE'에서 FIRST(E') ⊆ FOLLOW(T)

- 또한 2번 생성 규칙에 따라 E' -> ε가 되니 E -> T가 가능, FOLLOW(E) ⊆ FOLLOW(T)

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

 

FOLLOW(T')

- 3번 생성 규칙 T -> FT', FOLLOW(T) ⊆ FOLLOW(T')

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

 

FOLLOW(F)

- 3번, FIRST(T') ⊆ FOLLOW(F), 단 ε은 제외

- 4번에서 T -> F가 되니, FOLLOW(T) ⊆ FOLLOW(F)

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

 

 

FOLLOW(A) 계산 규칙

1. 만약 A가 시작 기호이면 $은 FOLLOW(A)에 속한다

2. 만약 B → αAβ, β ≠ ε인 생성 규칙이 존재하면 A의 FOLLOW에 ε을 제외한 FIRST( β ) 추가

3. 만약 B → αA 이거나  B → αAβ에서 β =>* ε이면 B의 FOLLOW 전체를 A의 FOLLOW에 추가

 

예제

E -> TE'  

E' -> +TE' | ε   

T -> FT'  

T' -> *FT' | ε    

F -> (E) | id   

 

1번 규칙

FOLLOW(E) = {$}

 

2번 규칙, E' -> +TE',  T' -> *FT', F -> (E)  

FOLLOW(T) ⊇ FIRST(E') = { + }, ( ε은 제외 )

FOLLOW(F) ⊇ FIRST(T') = { * }, ( ε은 제외 )

FOLLOW(E) ⊇ FIRST( ) ) = { ) }

 

3번 규칙, E -> TE', T -> FT'

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

FOLLOW(T') ⊇ FOLLOW(T) = { + }

 

3번 규칙, E -> TE', E' ->  ε  이고 T -> FT',  T' -> ε 이니..

FOLLOW(T) ⊇ FOLLOW(E) = { $, ) }

FOLLOW(F) ⊇ FOLLOW(T) = { + }

 

결과적으로

FOLLOW(E) = { $, ) }

FOLLOW(E') = { $, ) }

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

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

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

 

---

 

LL 조건

- 임의의 생성 규칙 A -> α | β ∈ P 에 대해..

- FIRST( α ) ∩ FIRST( β ) = ø

- if ε ∈ FIRST( α ) then FOLLOW(A) ∩ FIRST( β ) = ø

 

예시

E -> TE'  

E' -> +TE' | ε   

T -> FT'  

T' -> *FT' | ε    

F -> (E) | id   

일때

 

FIRST(E) = { (, id }

FIRST(E') = { +, ε }

FIRST(T) = { (, id }

FIRST(T') = { *, ε }

FIRST(F) = { (, id }

 

FOLLOW(E) = { $, ) }

FOLLOW(E') = { $, ) }

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

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

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

 

조건이 여러 개인건 E', T', F이니

E' -> +TE' | ε  에서 FIRST(+TE') ∩ FOLLOW(E') = {+} ∩ {$, )} = ø

T' -> *FT' | ε 에서 FIRST(*FT') ∩ FOLLOW(T) = {*} ∩ { $, ), + } = ø

F -> (E) | id 에서 FIRST((E)) ∩ FIRST(id) = {(} ∩ {id} = ø

LL 조건을 만족하며, 이 문법은 LL 문법

 

 

LL 방법을 실제로 파싱으로 사용하는 구문 분석기

- 재귀적 하강 구문 분석 (Recursive-descent parsing)

- 예측 구문 분석(Predict parsing)

 

재귀적 하강 구문 분석

- LL 방법의 일종

- 주어진 입력 문자열을 구문 분석하기 위해 재귀적 프로시저를 사용

- 재귀적 프로시저는 각 논터미널에 해당하는 것으로 논터미널에 대한 유도를 재귀적 프로시저 호출로 처리하는 방법

 

재귀적 하강 구문 분석기를 구현하는 방법

- 각 논터미널 기호에 대한 프로시저를 작성하고, 터미널 기호에 대한 프로시저를 작성한 다음 이를 통합함으로써 구현 가능

- 터미널 기호에 대한 프로시저는 생성 규칙에 있는 터미널 기호와 입력 기호가 같은지 비교하여 만일 같은 경우 다음 입력기호를 읽게 하면 됨

- 논터미널 기호의 경우 현재의 입력 기호를 생성할 수 있는 적절한 생성 규칙이 선택되도록 프로시저를 작성

 

재귀적 하강 구문분석

- 주어진 문자열에 대한 구문 분석은 현재의 입력 기호를 보고 시작 기호에 대한 프로시저를 호출

- 마지막에는 현재의 입력기호가 입력의 끝을 나타내는 $이면 accept, 아니면 에러

- 문법으로부터 재귀적 프로시저를 이용하여 구문 분석기를 빠르게 구성할 수 있으며 오류 발생 가능성이 적다는 것이 장점

- 프로시저를 부르는 시간이 많이 걸려서 속도가 느리고 구문 분석기의 크기가 커진다는 단점

- 결정적인 구문 분석이 되지 않아 역추적이 필요할 수 있음

- 생성 규칙이 바뀔 때마다 구문 분석기 전체를 다시 고쳐야 함

 

재귀적 하강 구문 분석기를 만들고 구문 분석하기

S -> aAb

A -> aS

A -> b

에 대해 만들고 aaabbb$ 구문 분석하기

 

먼저 각 터미널 기호와 논터미널 기호에 대한 프로시저 작성

1. 터미널 기호에 대한 프로시저

procedure pa:
    begin
        if nextsymbol = qa then get_nextsymbol
        else error

procedure pb:
    begin
        if nextsymbol = qb then get_nextsymbol
        else error
    end

pa는 현재 입력이 a면 consume, 아니면 error

pb는 현재 입력이 b면 consume, 아니면 error

소비해서 없앤다고 보면 됨

 

2. 논터미널 기호에 대한 프로시저

procedure PS:
    begin
        if nextsymbol = qa then begin pa; PA; pb; end;
        else error
    end
    
procedure PA:
    begin
        case nextsymbol
            qa: begin pa; PS; end
            qb: qb
            otherwise error
    end

PS: a를 소비하고 A를 호출, b를 소비

PA: a가 다음 심볼이면 a를 소비, S 호출

      b가 다음 심볼이면 b소비

 

3. 주 프로그램에 대한 프로시저

begin
    get_nextsymbol
    PS
    if nextsymbol = q$ then accept else error
end

 

이 경우 aaabbb$의 구문 분석을 하면

1. get_nextsymbol에 의해 nextsymbol a

2. PS 호출, pa PA pb -> a소비(aabbb$) A호출(a 소비 후(abbb$) S호출(bbb$ -> bb$ b$)), 이후 b소비 ($)

3. 남은게 $가 끝 accept

 

 

예측 구문분석

- 생성 규칙이 바뀌더라도 전체 구문 분석기를 고치지 않고 단지 구문 분석기의 행동을 제어하는 파싱 테이블만 수정해서 구문 분석기를 구현하는 방법

- 스택을 이용하여 구현하며 입력과 스택, 파싱 테이블, 출력으로 구성

- 입력은 구문 분석이 될 입력 문자열과 $을 저장하고 스택은 문장 형태에서 입력 문자열과 아직 매칭되지 않은 부분을 유지하며 bottom marker로 역시 $을 가짐

- 출력은 파스 트리나 구문 분석 시 적용된 일련의 생성 규칙 번호(좌파스)가 될 수 있음

 

구문 분석기는 주어진 입력 문자열을 왼쪽에서 오른쪽으로 읽고 현재 입력 기호와 스택의 톱 기호에 따라 파싱표에서 주어진 행동을 취하며 구문 분석. 예측 구문 분석기의 행동은 제거, 확장, 인식, 에러 등

- 제거(pop): 스택의 톱과 현재의 입력 기호가 같은 경우, 스택의 톱 기호를 제거하고 현재의 입력 기호를 입력 문자열에서 제거. (현재의 입력 기호를 입력 문자열에서 제거한다는 것은 입력 버퍼의 제어가 오른쪽으로 한 자리 이동하고 다음 기호를 본다는 의미)

- 확장(expand): 스택의 톱이 논터미널 기호인 경우, 생성 규칙을 적용하여 확장

- 인식(accept): 스택의 톱과 현재의 입력 기호가 모두 $인 경우, 입력 문자열이 올바른 문자열임. (구문 분석 시 스택의 초기 상태는 $S, 입력 문자열은 w$)

- 에러(error): 스택의 톱이 논터미널인 경우에 그 기호로부터 현재 보고 있는 기호를 유도할 수 없음

 

예측 파싱표 구성 방법

입력: LL 문법

출력: 예측 파싱표 M

방법:

begin
    for each A -> α ∈ P do
        begin
            for a ∈ FIRST(α) do M[A, a] = A -> α
            if α =>* ε then
                for b ∈ FOLLOW(A) do M[A, b] = A -> α
        end
end

예측 파싱 표 M[A, a] : A를 보고 a가 다음 입력이면 어떤 생산 규칙을 써야 하는가?

 

핵심 원리

1. FIRST(α)에 있는 입력 a를 보면 A -> α를 써야 함

- A -> α를 적용하면 α가 시작되는 기호는 FIRST(α)에 있는 어떤 터미널이니까

 

2. α가 ε로 될 수 있으면 FOLLOW(A)에 대해서도 채움

- ε 되버리면 뒤에 나오는 것들이 FOLLOW(A)니까

 

예시

생성 규칙	FIRST	FOLLOW
E -> TE'   E' -> +TE' | ε    T -> FT'   T' -> *FT' | ε     F -> (E) | id	FIRST(E) = { (, id } FIRST(E') = { +, ε } FIRST(T) = { (, id } FIRST(T') = { *, ε } FIRST(F) = { (, id }	FOLLOW(E) = { $, ) } FOLLOW(E') = { $, ) } FOLLOW(T) = { $, ), + } FOLLOW(T') = { $, ), + } FOLLOW(F) = { $, ), +, * }

이 규칙으로 표를 만들면

	id	+	*	(	)	$
E	E -> TE'			E -> TE'
E'		E' -> +TE'			E' -> ε	E' -> ε
T	T -> FT'			T -> FT'
T'		T' -> ε	T' -> *FT'		T' -> ε	T' -> ε
F	F -> id			F -> (E)

 

입력 문자열: id+id*id$, 시작 기호 E

* 스택이라 변환 그대로 안들어가고 뒤집어져서 들어감

스택의 내용	입력 문자열	적용될 생성 규칙
$E	id+id*id$	E -> TE'
$E'T	id+id*id$	T -> FT'
$E'T'F	id+id*id$	F -> id
$E'T'id	id+id*id$
$E'T'	+id*id$	T' -> ε
$E'	+id*id$	E' -> +TE'
$E'T+	+id*id$
$E'T	id*id$	T -> FT'
$E'T'F	id*id$	F -> id
$E'T'id	id*id$
$E'T'	*id$	T' -> *FT'
$E'T'F*	*id$
$E'T'F	id$	F -> id
$E'T'	$	T' -> ε
$E'	$	E' -> ε
$	$