Parsing in Practice — 실전 파싱

📌단원 개요

앞에서 배운 LL(1)·LR(1) grammar 이론을 실제로 적용해, 간단한 expression language용 동작하는 parser를 만든다. 이 장이 다음 장의 B-Minor parser 작성의 토대가 된다.

Bison으로 만드는 3가지 프로그램 유형

5.1The Bison Parser Generator

LALR parser는 손으로 구현하기 비현실적이므로, grammar 명세로부터 table과 code를 자동 생성하는 도구를 쓴다.

%{
    (C preamble code)
%}
    (declarations)
%%
    (grammar rules)
%%
    (C postamble code)

문법 규칙(rule)의 형태

expr : expr TOKEN_ADD expr
     | TOKEN_INT
     ;

non-terminal expr는 expr TOKEN_ADD expr 또는 단일 terminal TOKEN_INT를 생성할 수 있다.

생성되는 함수: yyparse() · yylex()

예시 grammar (Figure 5.1 — Validator용)

parser.bison

%token TOKEN_INT  TOKEN_PLUS TOKEN_MINUS TOKEN_MUL TOKEN_DIV
%token TOKEN_LPAREN TOKEN_RPAREN TOKEN_SEMI TOKEN_ERROR
%%
program : expr TOKEN_SEMI ;

expr : expr TOKEN_PLUS  term
     | expr TOKEN_MINUS term
     | term ;

term : term TOKEN_MUL factor
     | term TOKEN_DIV factor
     | factor ;

factor: TOKEN_MINUS factor
      | TOKEN_LPAREN expr TOKEN_RPAREN
      | TOKEN_INT ;
%%

빌드 절차 (Figure 5.3)

bison --defines=token.h --output=parser.c parser.bison

• --defines=token.h : %token 선언으로부터 token.h 자동 생성 → parser와 scanner가 같은 정보 공유
• --output=parser.c : 알아보기 힘든 기본 파일명 yy.tab.c 대신 parser.c로 출력

state 9
    2 expr: expr . TOKEN_PLUS expr
    2     | expr TOKEN_PLUS expr .

  TOKEN_PLUS   shift, and go to state 7
  TOKEN_PLUS   [reduce using rule 2 (expr)]   ← 억제됨
  $default     reduce using rule 2 (expr)

5.2Expression Validator

Figure 5.1의 명세는 입력이 원하는 grammar와 일치하는지만 평가한다 → 이런 프로그램이 validator.

extern int yyparse();
int main() {
    if(yyparse()==0) printf("Parse successful!\n");
    else             printf("Parse failed.\n");
}

5.3Expression Interpreter

단순 검증을 넘어서려면 grammar 안에 semantic action을 심어야 한다.

Figure 5.4 = 완전한 interpreter. main이 yyparse()를 호출하고, 성공 시 결과가 전역변수 parser_result에 저장된다.

Figure 5.4 — Interpreter

prog : expr TOKEN_SEMI          { parser_result = $1; } ;

expr : expr TOKEN_PLUS  term    { $$ = $1 + $3; }
     | expr TOKEN_MINUS term    { $$ = $1 - $3; }
     | term                     { $$ = $1; } ;

term : term TOKEN_MUL factor    { $$ = $1 * $3; }
     | term TOKEN_DIV factor    { $$ = $1 / $3; }
     | factor                   { $$ = $1; } ;

factor : TOKEN_MINUS factor            { $$ = -$2; }
       | TOKEN_LPAREN expr TOKEN_RPAREN { $$ = $2; }
       | TOKEN_INT                     { $$ = atoi(yytext); } ;

5.4Expression Trees (AST)

파싱 도중 즉시 계산하는 방식의 한계를 해결하기 위해, 값을 바로 계산하지 않고 abstract syntax tree(AST) 자료구조를 만든다.

AST 자료구조 (Figure 5.5)

typedef enum {
    EXPR_ADD,
    EXPR_SUBTRACT,
    EXPR_DIVIDE,
    EXPR_MULTIPLY,
    EXPR_VALUE
} expr_t;

struct expr {
    expr_t kind;
    struct expr *left;
    struct expr *right;
    int value;   // leaf용
};

// 모든 종류의 노드 생성
struct expr * expr_create(
    expr_t kind,
    struct expr *left,
    struct expr *right);

// 특별히 EXPR_VALUE leaf 노드 생성
struct expr * expr_create_value(int value);

AST 손으로 만들기 — 예: (10+20)*30

struct expr *e =
  expr_create(EXPR_MULTIPLY,
    expr_create(EXPR_ADD,
      expr_create_value(10),
      expr_create_value(20)),
    expr_create_value(30));

Bison으로 AST 자동 생성 (Figure 5.6)

각 element가 인식될 때마다 새 노드를 만들고, 위로 전달(pass up)해 알맞은 자리에 연결한다. bottom-up이므로 leaf 먼저 생성 후 parent에 연결.

%{
#include "expr.h"
#define YYSTYPE struct expr *      // ★ semantic type 지정
struct expr * parser_result = 0;
%}

prog : expr TOKEN_SEMI   { parser_result = $1; } ;

expr : expr TOKEN_PLUS  term { $$ = expr_create(EXPR_ADD,$1,$3); }
     | expr TOKEN_MINUS term { $$ = expr_create(EXPR_SUBTRACT,$1,$3); }
     | term                  { $$ = $1; } ;

term : term TOKEN_MUL factor { $$ = expr_create(EXPR_MULTIPLY,$1,$3); }
     | term TOKEN_DIV factor { $$ = expr_create(EXPR_DIVIDE,$1,$3); }
     | factor                { $$ = $1; } ;

factor : TOKEN_MINUS factor
           { $$ = expr_create(EXPR_SUBTRACT, expr_create_value(0), $2); }
       | TOKEN_LPAREN expr TOKEN_RPAREN { $$ = $2; }
       | TOKEN_INT { $$ = expr_create_value(atoi(yytext)); } ;

5.4+AST 순회: 평가 & 출력

AST를 만든 뒤에는 이를 계산·출력 등 여러 연산의 기반으로 쓴다.

int expr_evaluate(struct expr *e){
  if(!e) return 0;            // ★ null 체크
  int l = expr_evaluate(e->left);
  int r = expr_evaluate(e->right);
  switch(e->kind){
    case EXPR_VALUE:    return e->value;
    case EXPR_ADD:      return l+r;
    case EXPR_SUBTRACT: return l-r;
    case EXPR_MULTIPLY: return l*r;
    case EXPR_DIVIDE:
      if(r==0){ printf("error: divide by zero\n");
                exit(1); }   // ★ divide-by-zero 명시 체크
      return l/r;
  }
  return 0;
}

void expr_print(struct expr *e){
  if(!e) return;             // ★ null 체크
  printf("(");
  expr_print(e->left);
  switch(e->kind){
    case EXPR_VALUE:    printf("%d",e->value); break;
    case EXPR_ADD:      printf("+"); break;
    case EXPR_SUBTRACT: printf("-"); break;
    case EXPR_MULTIPLY: printf("*"); break;
    case EXPR_DIVIDE:   printf("/"); break;
  }
  expr_print(e->right);
  printf(")");
}

5.5Exercises (연습문제)

5.6Further Reading

YACC는 최초의 컴파일러 도구는 아니지만 지금도 널리 쓰이며, 다양한 언어·문법 클래스를 다루는 유사 도구들을 파생시켰다.

⭐핵심 정리 / 시험 포인트

📋한눈에 보기 — Cheat Sheet