오토마타와 컴파일러 07 - 하향식 파싱

파싱이란 무엇인가

렉서가 소스 코드를 토큰 스트림으로 변환했다면, 이제 그 토큰들이 언어의 문법 규칙에 맞게 배열되어 있는지를 검증하고 구조를 파악해야 한다. 이것이 파싱(Parsing)의 역할이다. 파싱은 본질적으로 유도(Derivation)의 역과정이다. 문법이 시작 기호에서 출발하여 문자열을 생성하는 과정이 유도라면, 파서는 주어진 문자열에서 출발하여 시작 기호에 도달하는 경로를 찾아내는 것이다.

파싱 방법은 크게 두 가지로 나뉜다. 시작 기호에서 출발하여 입력 문자열을 향해 내려가는 하향식(Top-Down) 방법과, 입력 문자열에서 출발하여 시작 기호를 향해 올라가는 상향식(Bottom-Up) 방법이다. 이번 포스트에서는 하향식 파싱을 다룬다.

재귀 하강 파서

하향식 파싱에서 가장 직관적인 구현 방식이 재귀 하강 파서(Recursive Descent Parser)이다. 문법의 각 비단말 기호에 대해 하나의 함수를 작성하고, 이 함수들이 서로를 재귀적으로 호출하면서 입력을 분석하는 것이다.

다음과 같은 간단한 수식 문법을 생각해 보자.

E → T + E | T
T → ( E ) | id | num

이 문법에 대한 재귀 하강 파서는 다음과 같은 형태가 된다.

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        if self.pos < len(self.tokens):
            return self.tokens[self.pos]
        return None

    def consume(self, expected_type):
        token = self.peek()
        if token and token[0] == expected_type:
            self.pos += 1
            return token
        raise SyntaxError(f'Expected {expected_type}')

    def parse_E(self):
        node = self.parse_T()
        if self.peek() and self.peek()[0] == 'PLUS':
            self.consume('PLUS')
            right = self.parse_E()
            return ('ADD', node, right)
        return node

    def parse_T(self):
        token = self.peek()
        if token[0] == 'LPAREN':
            self.consume('LPAREN')
            node = self.parse_E()
            self.consume('RPAREN')
            return node
        elif token[0] == 'IDENT':
            return self.consume('IDENT')
        elif token[0] == 'NUMBER':
            return self.consume('NUMBER')
        raise SyntaxError('Unexpected token')

각 문법 규칙이 하나의 함수로 대응되므로 구조가 명확하고 디버깅이 쉽다. 실제로 GCC, Clang, Go 컴파일러 등 많은 프로덕션 컴파일러가 재귀 하강 방식을 채택하고 있다. 파서 생성기에 의존하지 않고도 유연한 오류 처리와 정교한 제어가 가능하기 때문이다.

예측 파싱과 LL(1)

재귀 하강 파서가 올바르게 동작하려면 현재 토큰만 보고 어떤 문법 규칙을 적용할지 결정할 수 있어야 한다. 과연 하나의 토큰만으로 항상 올바른 선택이 가능한 것일까? 모든 문법에 대해서는 그렇지 않다. 하지만 LL(1) 문법이라고 불리는 부류에서는 가능하다.

LL(1)이라는 이름은 세 가지 의미를 담고 있다. 첫 번째 L은 입력을 왼쪽에서 오른쪽으로(Left-to-right) 읽는 것, 두 번째 L은 최좌단 유도(Leftmost derivation)를 생성하는 것, 그리고 1은 결정에 필요한 선행 토큰이 하나라는 것이다.

LL(1) 파서가 올바른 규칙을 선택하기 위해서는 두 가지 집합을 미리 계산해야 한다. FIRST 집합과 FOLLOW 집합이다.

FIRST와 FOLLOW

FIRST(α)는 문자열 α에서 유도할 수 있는 모든 문자열의 첫 번째 단말 기호의 집합이다. α가 빈 문자열(ε)을 유도할 수 있다면 ε도 FIRST(α)에 포함된다.

FOLLOW(A)는 비단말 기호 A 바로 뒤에 나올 수 있는 단말 기호의 집합이다. 시작 기호의 FOLLOW에는 입력의 끝을 나타내는 $가 포함된다.

예를 들어 다음 문법을 보자.

E  → T E'
E' → + T E' | ε
T  → F T'
T' → * F T' | ε
F  → ( E ) | id

이 문법에서 FIRST와 FOLLOW를 계산하면 다음과 같다.

기호	FIRST	FOLLOW
E	{ (, id }	{ $, ) }
E'	{ +, ε }	{ $, ) }
T	{ (, id }	{ +, $, ) }
T'	{ *, ε }	{ +, $, ) }
F	{ (, id }	{ *, +, $, ) }

이 집합들을 이용하면 예측 파싱 테이블을 구성할 수 있다. 현재 비단말 기호 A와 다음 입력 토큰 a가 주어졌을 때, A의 어떤 생성 규칙 A → α를 적용할지는 다음과 같이 결정된다. a가 FIRST(α)에 속하면 해당 규칙을 선택한다. α가 ε을 유도할 수 있고 a가 FOLLOW(A)에 속하면 A → ε 규칙을 선택한다. 이 방식으로 테이블의 모든 칸이 최대 하나의 규칙만 갖는다면 해당 문법은 LL(1)인 것이다.

좌재귀 제거

하향식 파서에서 반드시 해결해야 하는 문제가 좌재귀(Left Recursion)이다. 다음과 같은 문법 규칙을 생각해 보자.

E → E + T | T

재귀 하강 파서에서 parse_E를 호출하면 가장 먼저 parse_E를 다시 호출하게 되어 무한 루프에 빠진다. 이 문제를 해결하기 위해 좌재귀를 우재귀로 변환해야 한다.

변환 방법은 다음과 같다. A → Aα | β 형태의 좌재귀 규칙은 다음과 같이 변환된다.

A  → β A'
A' → α A' | ε

앞의 수식 문법에 적용하면 다음과 같다.

E  → T E'
E' → + T E' | ε

변환 후에는 좌재귀가 제거되어 재귀 하강 파서가 올바르게 동작한다. 다만, 이 변환은 파스 트리의 구조를 변화시킨다. 원래 문법에서 왼쪽 결합이었던 연산이 변환 후에는 오른쪽 결합처럼 보이게 되므로, 추상 구문 트리를 구성할 때 이를 적절히 보정해야 한다.

좌인수분해

또 다른 문제는 공통 접두사이다. 다음 문법을 보자.

S → if E then S else S
S → if E then S

두 규칙이 if E then S라는 공통 접두사를 가지므로, 첫 번째 토큰 if만 보고는 어떤 규칙을 선택해야 할지 결정할 수 없다. 좌인수분해(Left Factoring)를 적용하면 공통 접두사를 분리할 수 있다.

S  → if E then S S'
S' → else S | ε

이제 if를 보면 S의 유일한 규칙을 선택하고, else가 나타나면 S'에서 else 분기를 선택하면 된다. 하지만 이 변환도 모호함을 완전히 해소하지는 못한다. 이른바 dangling else 문제가 남아 있으며, 보통은 else를 가장 가까운 if에 매칭시키는 규칙을 별도로 적용한다.

예측 파싱 테이블 구동 파서

재귀 하강 대신 명시적인 스택과 파싱 테이블을 사용하는 방식도 있다. 이 방식에서는 스택의 최상위와 다음 입력 토큰을 보고 파싱 테이블에서 적용할 규칙을 결정한다.

스택: [E, $]    입력: id + id $

1. 스택 최상위 E, 입력 id → 테이블에서 E → T E' 선택
   스택: [T, E', $]

2. 스택 최상위 T, 입력 id → 테이블에서 T → F T' 선택
   스택: [F, T', E', $]

3. 스택 최상위 F, 입력 id → 테이블에서 F → id 선택
   스택: [id, T', E', $]

4. 스택 최상위 id, 입력 id → 매칭, 팝
   스택: [T', E', $]    입력: + id $

... (계속 진행)

이 방식은 재귀 함수 호출 대신 명시적인 루프와 스택을 사용하므로 호출 스택 깊이의 제약을 받지 않는다. 다만, 오류 처리의 유연성에서는 재귀 하강 방식이 더 유리하다.

하향식 파싱의 한계

하향식 파싱은 직관적이고 구현이 쉽다는 장점이 있지만, 근본적인 한계도 존재한다. LL(1) 문법으로 표현할 수 없는 언어 구조가 상당히 많다는 것이다. 좌재귀 제거와 좌인수분해를 아무리 적용해도 LL(1)으로 변환이 불가능한 문법이 있으며, 이런 경우 더 많은 선행 토큰을 보는 LL(k)나 백트래킹을 도입해야 한다.

실용적인 관점에서 보면, 재귀 하강 파서는 문법을 코드로 직접 작성하기 때문에 문법 규칙 너머의 문맥 의존적인 처리를 삽입하기 쉽다. C 언어에서 typedef 이름과 변수 이름을 구별하는 것처럼 문법만으로는 표현할 수 없는 규칙을 파서 내부에서 처리할 수 있는 것이다. 이런 유연성이 많은 프로덕션 컴파일러가 재귀 하강 방식을 선택하는 이유이기도 하다.

반면, 더 넓은 부류의 문법을 자동으로 처리할 수 있는 방법이 필요하다면 상향식 파싱을 고려해야 한다. 다음 포스트에서는 상향식 파싱, 특히 LR 파싱을 살펴본다.