파서 제네레이터 활용하기

이 문서에서는 컴파일러 프론트엔드 구축을 돕기 위해 파서 제네레이터를 어떻게 사용할 수 있는지 설명합니다. 논의 기반으로 LALR 파서 제네레이터인 Yacc를 사용하며, 이는 이전 섹션에서 다룬 개념들을 구현한 것입니다. Yacc는 "또 다른 컴파일러-컴파일러"라는 의미로, 1970년대 초반에 S. C. Johnson에 의해 만들어졌습니다.

Yacc란?

Yacc를 이용하여 번역기를 생성하는 과정은 다음과 같습니다. 우선 translate.y와 같은 파일을 준비합니다. UNIX 시스템 명령어

yacc translate.y

는 translate.y를 Algorithm 4.63에서 설명된 LALR 방법에 따라 y.tab.c C 프로그램으로 변환합니다. y.tab.c는 사용자가 작성한 기타 C 루틴과 함께 LALR 파서를 나타내는 C 코드입니다. Section 4.7에서 설명된 방식으로 LALR 파싱 테이블이 압축됩니다. 다음 명령어로 컴파일하면 a.out이라는 객체 프로그램을 얻게 됩니다:

cc y.tab.c -ly

Yacc 소스 프로그램 구조

Yacc 소스 프로그램은 세 부분으로 구성됩니다:

선언
%%
번역 규칙
%%
지원 C 루틴

간단한 계산기 예제

다음 문법을 기반으로 한 간단한 계산기를 만들어 보겠습니다:

E -> E + T | T 
T -> T * F | F 
F -> ( E ) | 숫자

숫자는 0에서 9 사이의 단일 숫자를 의미합니다. 이 문법을 바탕으로 만든 Yacc 계산기는 아래와 같습니다:

%{ 
#include <ctype.h>
%}
%token NUMBER

%%

line   : expr '\n' { printf("%d\n", $1); }
       ;

expr   : expr '+' term { $$ = $1 + $3; }
       | term
       ;

term   : term '*' factor { $$ = $1 * $3; }
       | factor
       ;

factor : '(' expr ')' { $$ = $2; }
       | NUMBER
       ;

%%

yylex() {
    int c;
    c = getchar();
    if(isdigit(c)) {
        yylval = c - '0';
        return NUMBER;
    }
    return c;
}

선언부

Yacc 프로그램의 선언부에는 두 가지 섹션이 있습니다. 첫 번째 섹션에서는 일반적인 C 선언을 %{와 %} 사이에 포함시킵니다. 여기에는 번역 규칙이나 절차에서 사용되는 임시 변수들의 선언을 포함시킬 수 있습니다. 위 예제에서는 ctype.h 헤더 파일만 포함되어 있습니다. 두 번째 섹션에서는 문법 토큰을 선언합니다. 예제에서 %token NUMBER는 NUMBER를 토큰으로 선언합니다.

번역 규칙

첫 번째 %% 이후에는 번역 규칙을 작성합니다. 각 규칙은 문법 생성과 연관된 의미론적 동작으로 구성됩니다. 예를 들어:

expr   : expr '+' term { $$ = $1 + $3; }
       | term
       ;

위 규칙은 expr 노드가 expr와 term을 합친 결과를 반환하도록 합니다.

지원 C 루틴

세 번째 부분에서는 지원 C 루틴을 작성합니다. 반드시 제공해야 하는 렉서리얼 분석기는 yylex() 함수입니다. Lex를 사용해 yylex()를 생성할 수도 있습니다.

오류 복구

Yacc는 error이라는 예약어를 사용해 오류 복구를 처리합니다. 예를 들어:

lines : lines expr '\n' { printf("%g\n", $2); }
      | lines '\n'
      | /* empty */
      | error '\n' { yyerror("재입력 필요:");
                     yyerrok; }
      ;

위 예제에서는 오류 발생 시 입력 줄을 재입력하도록 요구합니다.