오토마타와 컴파일러 08 - 상향식 파싱

아래에서 위로

이전 포스트에서 다룬 하향식 파싱은 시작 기호에서 출발하여 입력 문자열을 향해 내려가는 방식이었다. 상향식 파싱(Bottom-Up Parsing)은 그 반대이다. 입력 문자열의 토큰들에서 출발하여 문법 규칙을 역으로 적용하면서 시작 기호까지 올라가는 것이다. 이 과정에서 파서는 최우단 유도(Rightmost Derivation)의 역순을 추적한다.

과연 방향을 뒤집는 것만으로 의미 있는 차이가 생기는 것일까? 그렇다. 상향식 파서는 하향식 파서보다 훨씬 넓은 부류의 문법을 처리할 수 있다. LL(1)으로 표현할 수 없었던 많은 문법이 LR 파싱에서는 자연스럽게 처리되며, 좌재귀 같은 문제도 별도의 변환 없이 다룰 수 있다. 이것이 상향식 파싱이 파서 생성기의 표준 방식으로 자리 잡은 이유이다.

시프트-리듀스 파싱

상향식 파싱의 핵심 메커니즘은 시프트-리듀스(Shift-Reduce) 파싱이다. 파서는 스택과 입력 버퍼를 사용하며, 두 가지 동작을 반복한다.

• 시프트(Shift): 입력에서 다음 토큰을 읽어 스택에 푸시한다.
• 리듀스(Reduce): 스택 최상위의 기호열이 어떤 문법 규칙의 우변과 일치하면, 그것을 규칙의 좌변(비단말 기호)으로 교체한다.

id + id * id를 파싱하는 과정을 다음 문법으로 추적해 보자.

E → E + T | T
T → T * F | F
F → id

스택           입력              동작
                id + id * id $
id              + id * id $    시프트
F               + id * id $    리듀스 (F → id)
T               + id * id $    리듀스 (T → F)
E               + id * id $    리듀스 (E → T)
E +             id * id $      시프트
E + id          * id $         시프트
E + F           * id $         리듀스 (F → id)
E + T           * id $         리듀스 (T → F)
E + T *         id $           시프트
E + T * id      $              시프트
E + T * F       $              리듀스 (F → id)
E + T           $              리듀스 (T → T * F)
E               $              리듀스 (E → E + T)

최종적으로 스택에 시작 기호 E만 남으면 파싱이 성공한 것이다. 이 과정에서 리듀스가 적용되는 순서를 뒤집으면 최우단 유도가 된다는 점이 중요하다.

핵심적인 질문은 언제 시프트하고 언제 리듀스할 것인가이다. 이 결정을 자동화한 것이 LR 파싱이다.

LR 파싱의 원리

LR 파서는 유한 오토마타와 파싱 테이블을 결합하여 시프트-리듀스 결정을 자동으로 수행한다. LR이라는 이름은 입력을 왼쪽에서 오른쪽으로(Left-to-right) 읽으면서 최우단 유도의 역순(Rightmost derivation in reverse)을 생성한다는 뜻이다.

LR 파서의 핵심은 아이템(Item)과 상태(State)의 개념이다. LR(0) 아이템은 문법 규칙 내에서 파싱이 어디까지 진행되었는지를 나타내는 표기법이다. 점(·)이 현재 위치를 표시한다.

E → ·E + T    (아직 아무것도 인식하지 못한 상태)
E → E·+ T     (E를 인식한 상태)
E → E +·T     (+를 인식한 상태)
E → E + T·    (전체를 인식한 상태, 리듀스 가능)

같은 시점에 가능한 여러 아이템을 모아 하나의 상태를 구성하고, 이 상태들 사이의 전이를 정의하면 LR 오토마톤이 만들어진다. 이 오토마톤으로부터 파싱 테이블의 시프트, 리듀스, GOTO 동작이 결정되는 것이다.

LR 파서의 종류

LR 파서는 테이블 구성 방식에 따라 여러 변종이 있으며, 각각 처리할 수 있는 문법의 범위와 테이블 크기에서 차이를 보인다.

LR(0)는 선행 토큰 없이 상태만으로 결정하므로 처리할 수 있는 문법이 극히 제한적이다. SLR(1)은 FOLLOW 집합을 이용하여 리듀스 시점을 결정하지만, FOLLOW 집합은 모든 문맥에서의 가능성을 합산한 것이므로 불필요한 충돌이 발생할 수 있다.

CLR(1)은 각 아이템에 정확한 룩어헤드 토큰을 부착하여 가장 넓은 범위의 문법을 처리할 수 있지만, 테이블 크기가 지수적으로 증가할 수 있다. LALR(1)은 CLR(1)에서 동일한 코어를 가진 상태를 합치는 방식으로 테이블 크기를 줄이면서도 대부분의 실용적인 프로그래밍 언어 문법을 처리할 수 있다. 이것이 LALR(1)이 실용적인 최적점으로 널리 채택되는 이유이다.

충돌 해결

LR 파싱 테이블을 구성할 때 하나의 칸에 두 가지 이상의 동작이 들어가는 경우가 있다. 이를 충돌(Conflict)이라 하며, 두 가지 종류가 있다.

시프트-리듀스 충돌(Shift-Reduce Conflict): 같은 상태에서 시프트와 리듀스 모두 가능한 경우이다. 앞서 언급한 dangling else 문제가 대표적이다. if E then if E then S · else S에서 else를 시프트하면 안쪽 if에 매칭되고, 리듀스하면 바깥쪽 if에 매칭된다. 대부분의 파서 생성기는 이 경우 시프트를 기본으로 선택하여 else를 가장 가까운 if에 연결한다.

리듀스-리듀스 충돌(Reduce-Reduce Conflict): 같은 상태에서 두 가지 다른 규칙으로 리듀스가 가능한 경우이다. 이 충돌은 일반적으로 문법 자체의 모호함을 나타내므로, 문법을 재설계하여 해결하는 것이 바람직하다.

실용적인 파서 생성기에서는 연산자 우선순위와 결합 방향을 별도로 지정하여 충돌을 해결하는 메커니즘을 제공한다. 예를 들어 +가 좌결합이고 *가 +보다 우선순위가 높다는 선언만으로, 수식 문법의 시프트-리듀스 충돌을 자동으로 해결할 수 있는 것이다.

파서 생성기: Yacc과 Bison

렉서에 Lex/Flex가 있듯이, 파서에는 Yacc과 Bison이 있다. 이들은 문법 명세를 입력으로 받아 LALR(1) 파서 코드를 자동으로 생성해 주는 도구이다.

Yacc/Bison의 입력 파일은 문법 규칙과 각 규칙이 리듀스될 때 실행할 액션으로 구성된다.

%token NUMBER IDENTIFIER
%left '+' '-'
%left '*' '/'

%%
expr : expr '+' expr   { $$ = $1 + $3; }
     | expr '-' expr   { $$ = $1 - $3; }
     | expr '*' expr   { $$ = $1 * $3; }
     | expr '/' expr   { $$ = $1 / $3; }
     | '(' expr ')'    { $$ = $2; }
     | NUMBER           { $$ = $1; }
     ;
%%

%left와 %right 선언으로 결합 방향을 지정하고, 선언 순서로 우선순위를 결정한다. 나중에 선언된 것이 더 높은 우선순위를 갖는다. 이 선언들이 시프트-리듀스 충돌을 해결하는 데 사용되는 것이다.

내부적으로 파서 생성기는 문법에서 LR 오토마톤을 구성하고, 상태를 합병하여 LALR(1) 테이블을 만들고, 충돌을 우선순위 규칙으로 해결하고, 최종적으로 테이블 구동 파서 코드를 출력한다. 오토마타 이론이 다시 한번 실전 도구로 구현되는 셈이다.

하향식과 상향식의 비교

두 접근법을 정리하면 다음과 같다.

실무에서는 양쪽 접근법이 모두 활발하게 사용된다. 수동 제어와 정교한 오류 메시지가 중요하면 재귀 하강 파서를, 복잡한 문법의 자동 처리가 중요하면 LR 파서 생성기를 선택하는 것이 일반적이다.

어떤 방식을 선택하든 파서의 최종 산출물은 구문 트리(Parse Tree)이다. 하지만 구문 트리를 그대로 사용하기에는 불필요한 정보가 많다. 다음 포스트에서는 구문 트리에서 불필요한 요소를 제거하고 핵심 구조만 남긴 추상 구문 트리(AST)를 살펴본다.