[컴파일러] - 구문 분석 (Syntax Analysis) II

1. 하향식 파싱 (Top-down parsing)

하향식 파싱은 root node에서 시작하여 파스 트리의 노드들을 전위 순서 (preorder)에 따라 생성하는 것이다 [그림 1]. 따라서, 하향식 파싱은 항상 문자열의 가장 왼쪽 nonterminal부터 유도가 이루어지기 때문에 하향식 파싱은 입력 문자열에 대한 최좌단 유도 (leftmost derivation)을 찾는 것과 같다.

[그림 1] 하향식 파싱 (top-down parsing)을 통한 파스 트리 (parse tree)의 생성

하향식 파싱에는 가장 일반적인 형태인 재귀적 하강 파싱 (recursive descent parsing)과 재귀가 필요없는 예측 파싱 (predict parsing) 등이 있다.

2, 재귀적 하강 파싱 (Recursive descent parsing)

재귀적 하강 파싱은 하향식 파싱의 한 종류이며, nonterminal 당 하나의 프로시저가 작성된다. 재귀적 하강 파싱에서 각 nonterminal에 대해 작성되는 프로시저의 의사코드 (pseudocode)는 아래의 [코드 1]과 같다.

// X is the current symbol
 
void E() {
    select production rule of the nonterminal E
    
    for(i = 1;i < NUM_PRODUCTION_RULES;) {
        if(X == NONTERMINAL) {
            call X()
        }
        else if(X == TERMINAL) {
            read next symbol
        }
        else {
            print error
        }
}

[코드 1] 재귀적 하강 파싱의 nonterminal $E$에 대한 프로시저

다음과 같은 문법이 있다.

입력 문자열이 $abec$일 때, 재귀적 하강 파싱은 시작 기호인 $S$의 프로시저를 호출한 다음, nonterminal $A$를 만나면 $A$의 프로시저를 호출한다. Nonterminal $A$는 $S$와 다르게 생성규칙을 두 개 갖고 있기 때문에 재귀적 하강 파싱은 $A$가 갖고 있는 생성규칙을 하나씩 실행하면서 출력 문자열이 입력 문자열과 일치하는지를 검사한다. 아래의 과정은 재귀적 하강 파싱의 알고리즘을 글로 서술한 것이다.

1) 현재 nonterminal의 현재 생성규칙을 적용한다.

2) 생성된 문자열에서 다음 nonterminal이 나타나기 전 부분까지를 입력 문자열과 비교한다.

3-1) 생성된 문자열과 입력 문자열이 불일치한다면, [과정 4]로 이동한다.

3-2) 생성된 문자열과 입력 문자열이 일치한다면, [과정 5]로 이동한다.

4-1) 현재 nonterminal에 적용할 다음 생성규칙이 존재하면, 현재까지의 실행을 모두 취소하고 현재 nonterminal의 다음 생성규칙을 현재 생성규칙으로 설정하고, [과정 1]로 이동한다.

4-2) 현재 nonterminal에 적용할 다음 생성규칙이 존재하지 않는다면, 파싱이 실패했음을 알린다.

5-1) 생성된 문자열에 nonterminal이 존재하지 않으면, 파싱을 종료한다.

5-2) 생성된 문자열에 아직 nonterminal이 존재하면, 다음 nonterminal을 현재 nonterminal로 설정하고, [과정 1]로 이동한다.

예를 들어, $A$의 프로시저에서는 먼저 $A$가 $bd$가 되는 생성규칙을 실행한다. 그 다음, 입력 문자열에서 $S$에 의해 이미 올바르게 생성된 $ab$부분을 제외한 $e$부분과 $A$에 의해 생성된 문자열의 첫 번째 기호인 $b$를 비교한다. 입력 문자열에서는 현재 $e$를 읽었지만, $A$의 프로시저에 의해 생성된 문자열의 첫 번째 기호는 $b$이므로 파서는 자신이 올바르게 생성규칙을 적용하지 못 한 것을 인지한다. 파서는 현재 $A$의 프로시저가 수행한 행동을 모두 취소하고, 다시 이전 상태로 회귀하여 $A$가 $e$가 되는 생성규칙을 적용한다. 재귀적 하강 파싱은 이러한 수행을 반복하여 출력 문자열과 입력 문자열이 완벽히 일치하면, 파싱이 성공했음을 알린다.

재귀적 하강 파싱은 매우 간단하면서도 이해하기 쉽다. 그러나 재귀적 하강 파싱은 최악의 경우 nonterminal의 생성규칙이 $N$개일 때, $N$번의 생성규칙 실행과 $N-1$번의 생성규칙의 실행을 취소하여 이전 상태로 복원하는 역추적 (backtracking)을 수행해야 한다. 이러한 재귀적 하강 파싱의 문제점을 해결하는 방법으로는 LL(1) 문법과 이를 파싱할 수 있는 LL(1) 파서가 있다.

3. LL(1) 파서

재귀적 하강 파싱의 단점을 보완하기 위해 고안된 LL(1) 파서는 하향식 파서의 한 종류이다. LL(1)에서 첫 번째 L은 left scanning을, 두 번째 L은 leftmost derivation을 의미한다. 즉, LL(1) 파서는 입력 문자열을 왼쪽에서 오른쪽으로 읽어가며, 최좌된 유도를 수행한다. 마지막으로, LL(1)의 괄호에 표기된 숫자 1은 파싱 동작을 결정하는 각 단계에서 한 개의 입력 기호를 미리 읽는다는 것을 나타낸다. 각 단계에서 미리 읽는 입력 기호를 선견항목(lookahead)라고 한다.

[그림 2] LL(1) 파서의 구조

재귀적 하강 파싱에서는 일단 생성규칙을 적용하고, 출력된 문자열과 입력된 문자열을 비교하였다. 그러나 LL(1) 파서는 한 개의 입력 기호를 미리 읽고, 스택 (stack)에 저장된 현재 nonterminal의 생성규칙들 중에서 미리 읽은 입력 기호와 매칭되는 생성규칙을 선택하는 것이 차이점이다 [그림 2].

각 nonterminal과 입력 기호가 매칭되어 선택되는 생성규칙에 대한 정보는 FIRST와 FOLLOW라는 연산을 통해 테이블의 형태로 정의된다. 이 글에서는 LL(1) 파서의 개념만 설명할 것이기 때문에 LL(1) 파서에서 이용되는 파싱 테이블을 생성하는 과정은 따로 설명하지 않는다.