[컴개/CI] Top-Down 구문 분석, 구문분석기 만들기

지금까지 알아보았던 LL(1)파싱 방법을 통해 파서를 만들 수 있다.

LL 파서는 두 가지 방법으로 만들 수 있다.

1. Recursive descent parser

2. Predictive parser

 

이제 각 방법의 특징과 어떻게 파서를 만들 수 있는지 설명하겠다.

 

Recursive descent parser

recursion을 이용하고, 각 non-terminal마다 하나의 procedure를 둔다.

직관적이고, 쉽다는 장점이 있지만, 

생성 규칙이 바뀌면 구문 분석기를 고쳐야 한다는 점에서 융통성이 떨어진다는 단점이 있다.

 

모든 terminal 심볼 a에 대한 파서 코드

 

모든 non-terminal 심볼 A에 대한 파서 코드

 

아래는 위 로직을 코드로 구현한 예시이다.

/* S -> aAb
 * A -> aS | b */

/* Terminal Symbol */
void pa() {
	if (nextSymbol == ta) {
    	nextSymbol = get_nextSymbol();
    } else error();
}

void pb() {
	if (nextSymbol == tb) {
    	nextSymbol = get_nextSymbol();
    } else error();
}

/* Non-terminal Symbol */
void pS() {
	if (nextSymbol == ta) {
    	pa(); pA(); pb();
    }
}

void pA() {
	switch(nextSymbol) {
    	case ta: pa(); pS(); break;
        case tb: pb(); break;
    }
}

/* 참고: get_nextSymbol()은 getToken()이다.
 * nextSymbol()은 전역 변수이다. */

 

Predictive parser

이론적으로 PDA(Push Down Automata)에 기반하였다.

생성 규칙이 바뀌어도 구문 분석기는 고치지 않으며,

구문 분석기의 행동을 나타내는 파싱 테이블만 수정하면 된다는 장점이 있다.

 

테이블로 파싱

LL(1)은 lookahead에 따라 적용할 생성규칙이 unique하게 결정되기 때문에

주어진 문자열에 대해 기계적으로 파싱할 수 있다.

아래의 예시를 보자.

 

생성 규칙이 사진과 같을 때 입력 문자열로 'aabccd'가 들어왔다고 하자.

우리는 위와 같은 테이블을 이용하여 문자열을 파싱할 수 있는데,

그 결과는 아래와 같다.

 

파싱 테이블 만들기

그렇다면 우리는 위와 같은 파싱 테이블을 어떻게 만들 수 있을까?

 

파싱테이블은 non-terminal X terminal = 적용될 규칙의 형태이다.

파싱테이블의 구성 원칙은 아래와 같다.

1. 모든 a ∈ FIRST(α)에 대하여, M[A, a] := A -> α로 채운다.

2. 만일 ε ∈ FIRST(α)이면, 모든 b ∈ FOLLOW(A)에 대하여,

    M[A, b] := A -> α로 채운다.

 

아래 예제를 보자.

위 사진은 생성규칙과, 각 non-terminal에 대해 FIRST와 FOLLOW를 구한 모습이다.

이때, 각 규칙 별로 번호가 메겨져 있고 각 규칙에 대해 표를 채우면 아래와 같다.

 

모호성과 테이블

파싱 테이블 한 칸에 두 개 이상의 생성 규칟이 들어갈 수 있는 경우

LL(1)이 아니므로 결정적 선택이 불가능하다.

 

기계적 파서 구조

생성 규칙이 바뀌더라도 구문 분석기를 고치지 않고, 파싱 테이블만 수정한다.

Push Down Automata에 기반하여 CFG와 동일한 표현력을 가졌다.

이는 스택을 통해 구현이 가능하다.

 

구문 분석기의 동작

pop(제거)

stack의 top는 입력 심볼이다.

stack의 top 심벌은 stack에서 제거하고, 현재 입력 심벌은 입력 스트링에서 제거한다.

 

expand(확장)

stack의 top이 non-terminal인 경우로 생성 규칙을 적용하여 확장한다.

예를 들어, M[A, a] = {A -> XYZ}일 때, A를 스택에서 제거하고 ZYX를 차례로 스택에 넣는다.(이렇게 해야 pop할 때 순서가 올바르다.)

 

accept(인식)

stack의 top 심벌과 현재 심벌 모두 $인 경우 주어진 입력이 올바른 문자열임을 알린다.

 

error(오류)

stack의 top 심벌이 non-terminal 심벌인 경우이다.

그 심벌로부터 현재 보고 있는 입력 심벌을 유도할 수 없다.

 

예시를 보자.

위의 생성 규칙에 입력 문자열로 'aabccd'가 들어왔다.

구문 분석기는 위와 같이 구문을 분석할 수 있다.