Flex and Bison Howto

1.1. 이 문서에서 할 수 없는 것

시중에는 이미 다양한 종류의 Lex와 Yacc를 주제로 하고 있는 좋은 책들이 나와 있다.(워낙에나 Flex/Bison과 비슷하기 때문에, 저들 책을 가지고 Flex와 Bison을 학습하기도 한다.) 비록 이 문서가 Bison과 Flex를 학습하는데 많은 도움을 주긴 하겠지만, 이들 책보다 더 낳은 정보를 제공해주긴 힘들 것이다. 이들 책은 대부분의 경우 책임감을 가지고 작성되었기 때문에 이 문서에서 제시하지 못한 다른 중요한 정보들을 가지고 있을 것이다. 이 문서는 Flex와 Bison을 좀더 쉽게 접할 수 있기 위한 입문서 정도로 활용을 해주길 바란다.

또한 이문서를 작성한 저자는 Flex/Bison 전문가가 아니며, 공부하면서 이 문서를 작성했다. 이점을 염두에 두고 이 문서를 읽기 바란다. 대부분의 예제들은 돌아가는지 확인하기 위한 간단한 수준에서 작성될 것이다. 좀더 현실감 있는 예제를 추가하길 원한 다면 언제든지 이 문서의 원본을 수정하는 정도로 참가할 수 있을 것이다.

1.2. 문서의 다운로드

1.3. Flex와 Bison

필자가 한살이던 1975년경 무렵 컴파일러를 작성하는 것은 사람의 애간장을 녹이는 인간의 인내력이 어디까지인가를 테스트하는 고도의 참을성과 집중력을 필요로 하는 작업이었다. 이러한 일련의 작업을 좀더 쉽게 하기위해서 Johnson과 Lesk란 사람들이 lex와 yacc라는 도구를 만들게 되었다. 이 도구는 컴파일러의 작성을 매우 간단하게 처리할 수 있는 훌륭한 기능을 가지고 있었으며 계속 발전을 해서 1986년경 지금 우리가 사용하는 현대적인 기능을 가진 lex와 yacc가 발표되게 되었다. lex와 yacc는 매우 훌륭한 도구 였기 때문에 아래와 같은 다른 많은 버젼들이 만들어지게 되었다.

1. Mortice Kern Systems(MKS), http://www.mks.com

2. (우리가 다루고자 하는)GNU flex, bison

3. Ming, http://www.mingw.org

4. 또다른 lex, yacc버젼, http://www.epaperpress.com

여기에서는 lex와 yacc의 원리에 대해 간단하게 소개하도록 할 것이다. 우리의 목적이 Flex와 Bison의 사용방법이긴 하지만 워낙에 lex와 yacc의 역사적 의미가 깊은 관계로 lex, yacc를 기준으로 했다. 그러나 도구의 이름이 틀리고 만들어내는 파일의 이름이 틀린 외에는 동일함으로 문제될건 없을 것이다.

lex는 어휘분석과 scanner를 위한 C코드를 생성한다. lex는 입력된 문자에서 매칭되는 문자열의 패턴을 이용해서 문자열을 토큰으로 변환한다. 토큰은 문법적으로 더이상 나눌 수 없는 기본적인 언어 요소를 말한다. 다음은 컴파일이 이루어지는 일반적인 과정이다. 토큰을 만들어내는 과정을 주의 깊게 보기 바란다.

심볼 테이블을 이용해서 lex는 입력되는 문자열의 특징을 가져온다. 심볼 테이블은 문자열이 숫자인지 단어인지와 같은 타입에 대한 정보와 어떤 변수를 통해 메모리에 접근할 수 있을 것인지 등을 정의 한다.

yacc -d bas.y                  # create y.tab.h, y.tab.c
lex bas.l                      # create lex.yy.c 
gcc lex.yy.c y.tab.c -o basc   # compile/link
			

마지막으로 gcc에 의해서 lexer와 parser이 컴파일 된후 링크되어서 basc실행파일을 만들게 된다. 작성된 컴파일러를 실행 시키면 main함수에서 yyparse를 호출하고 yyparse는 자동적으로 yylex를 호출해서 토큰을 얻어낸다.

2.1. 정규표현을 이용한 매칭

이번 예제는 아마도 매우 유용하게 응용할 수 있는 예제로 lex에서의 정규표현 지원에 대한 방법을 담고 있다.

%{
#include <stdio.h>
%}

%%
[0123456789]+           printf("NUMBER\n");
[a-zA-Z][a-zA-Z0-9]*    printf("WORD\n");
%%
			

[0123456789]+
			

[0-9]+
			

[a-zA-Z][a-zA-Z0-9]* 
			

위의 정규표현에서 "+"와 "*"의 차이를 분명히 해둘필요가 있다. "+"는 하나 이상 발견되어야 하는걸 의미하며, "*"는 0개 이상 발견되어야 함을 의미한다.

위 Lex파일을 example2.l로 저장한다음 컴파일해서 실행시켜 보자.

# ./example1 
foo
WORD

bar
WORD

123
NUMBER

bar123
WORD

123bar
NUMBER
WORD
			

Flex를 제대로 다루기 위해서는 정규표현에 대한 어느정도의 지식을 가지고 있어야한다. 정규표현을 효과적으로 익히는 가장 좋은 방법은 Perl 언어를 이용해서 정규표현 관련 프로그램을 만들어 보는게 될것이다. 또한 시중의 많은 Perl관련 책들이 상당부분을 정규표현에 할애하고 있으므로 이들 책을 구입해서 학습하는 것도 좋은 방법이 될것이다.

2.2. 복잡한 문장의 파싱

이번에는 아래와 같은 좀더 복잡한 문장을 파싱해 보도록 하겠다.(bind를 위한 설정파일의 일부분이다)

logging {
	category lame-servers { null; };
	category cname { null; };
};

zone "." {
	type hint;
	file "/etc/bind/db.root";
};
			

Flex문을 확실히 작성하기 위해서 위의 분석문자열에서 사용되고 있는 토큰들에 대한 카테고리를 만들 필요가 있다.

• 'zone', 'type' 같은 문자열

• '/etc/bind/db.root' 같은 파일이름

• 파일이름을 감싸는데 사용하는 쿼터(") 문자

• {, 중괄호 열기

• }, 중괄호 닫기

• ;, 세미콜론

다음은 위의 카테고리를 만족시키는 Lex파일이다. 파일명은 example3.l로 하자.

%{
#include <stdio.h>
%}

%%
[a-zA-Z][a-zA-Z0-9]*    printf("WORD ");
[a-zA-Z0-9\/.-]+        printf("FILENAME ");
\"                      printf("QUOTE ");
\{                      printf("OBRACE ");
\}                      printf("EBRACE ");
;                       printf("SEMICOLON ");
\n                      printf("\n");
[ \t]+                  /* ignore whitespace */;
%%
			

# ./example3 < test.txt
WORD OBRACE 
WORD FILENAME OBRACE WORD SEMICOLON EBRACE SEMICOLON 
WORD WORD OBRACE WORD SEMICOLON EBRACE SEMICOLON 
EBRACE SEMICOLON 

WORD QUOTE FILENAME QUOTE OBRACE 
WORD WORD SEMICOLON 
WORD QUOTE FILENAME QUOTE SEMICOLON 
EBRACE SEMICOLON 
			

2.3. flex에 미리 정의된 변수들

지금까지의 내용을 보면 몇개 flex에서 정의해서 사용하는 변수와 함수들이 보일 것이다. 이것들을 표로 정리해 두었으니 참고하기 바란다.

2.4. 지금까지 다룬 내용들

지금까지의 내용들을 통하여 Lex는 임의의 입력을 받아들여서 각각의 부분을 의미를 결정할 수 있음을 알았다. 이러한 것을 'Tokenizing'라고 한다.

3.1. 간단한 온도 조절기

Bison의 용도를 확인하기 위해서 간단한 온도 조절기를 위한 언어를 만드는 과정을 예로 들어 보겠다. 온도 조절기를 만들기 위해서는 다음과 같이 3개의 세션이 필요할 것이다.

heat on
	Heater on !
heat off
	Heater off !
target temperature 22
	New temperature set !
			

위의 토큰을 분리하기 위해서 다음과 같은 lex 파일을 작성하고 example4.l로 저장하도록 한다.

%{
#include <stdio.h>
#include "example4.tab.h"
%}
%%
[0-9]+                  return NUMBER;
heat                    return TOKHEAT;
on|off                  return STATE;
target                  return TOKTARGET;
temperature             return TOKTEMPERATURE;
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%
			

bison 코드는 크게 3가지 부분으로 이루어진다.

... 정의(definitions) ...
%%
... 규칙(rules) ...
%%
... 함수들(subroutines) ...
			

example4.tab.h에 대해서 우리가 신경쓸 필요는 없다. bison문법파일을 규칙대로 작성해주고나서 bison를 돌리면 example4.tab.h는 자동적으로 생성되기 때문이다. 다음은 위의 토큰의 정보를 처리할 수 있도록 작성된 bison 문법 파일이다.

commands: /* empty */
        | commands command
        ;

command:
        heat_switch
        |
        target_set
        ;

heat_switch:
        TOKHEAT STATE
        {
                printf("\tHeat turned on or off\n");
        }
        ;

target_set:
        TOKTARGET TOKTEMPERATURE NUMBER
        {
                printf("\tTemperature set\n");
        }
        ;
			

두번째 룰에서는 command에 대해서 정의하고 있다. 여기에서는 heat_switch와 target_set두개의 명령만을 정의한다. 이들 명령을 선언하는데 '|'이 사용되고 있는데, 이는 command가 heat_switch 또는 target_set를 구성요소로 가지고 있음을 의미한다.

heat_switch는 HEAT token에 대한 처리를 담당하는 구성요소로 'heat'와 state 토큰이 올 경우 이를 실행하도록 했다. 이는 히터를 키고 켤때 2개의 토큰으로 이루어지기 때문이다.

온도를 설정하는 명령은 'target'과 target으로 지정할 '객체', 그리고 '값'의 3개의 객체로 이루어진다. 이를 위해서 3개의 토큰이 만족할 때 target_set이 실행되도록 룰을 만들었다.

%{
#include <stdio.h>
#include <string.h>
 
void yyerror(const char *str)
{
	fprintf(stderr,"error: %s\n",str);
}
 
int yywrap()
{
	return 1;
} 
  
main()
{
	yyparse();
} 
%}

%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE
%%
commands: /* empty */
	| commands command
	;

command:
	heat_switch
	|
	target_set
	;

heat_switch:
	TOKHEAT STATE
	{
		printf("\tHeat turned on or off\n");
	}
	;

target_set:
	TOKTARGET TOKTEMPERATURE NUMBER
	{
		printf("\tTemperature set\n");
	}
	;
				

# flex example4.l
# bison -d example4.y
# gcc lex.yy.c example4.tab.c -o example4
				

# ./example4 
heat on
        Heat turned on or off
heat off
        Heat turned on or off
target temperature 10
        Temperature set
target humidity 20
error: parse error
				

3.2. 온도조절 프로그램의 업그레이드

어쨋든 우리는 문장을 파싱해서 원하는 루틴을 실행가능한 프로그램을 만들어 냈다. 그러나 좀더 완벽하게 작동하기 위해서는 단지 "무엇을 파싱 했다"가 아닌 "파싱한 정보가 무엇"이다라는 값을 얻어 올 수 있어야 한다. 예를 들자면 'heat'는 온도조절기를 켜거나 끄는데, 이를 위해서는 heat 토큰 다음의 'on', 'off' 토큰을 가져올 수 있어야 한다.

또한 온도 설정을 위한 target temperature의 경우 온도 값을 읽어올 수 있어야 한다.

Flex는 매칭된 단어의 문자열을 'yytex'라는 변수에 저장한다. 또한 'yylval'에 리턴값을 되돌려줄 수도 있다. 이를 이용하면 패턴매칭의 결과를 넘길 수가 있다. 아래와 같이 작성하고 example5.l 로 저장하자.

%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+                  yylval=atoi(yytext); return NUMBER;
heat                    return TOKHEAT;
on|off                  yylval=!strcmp(yytext,"on"); return STATE;
target                  return TOKTARGET;
temperature             return TOKTEMPERATURE;
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%
			

이제 Bison 코드에서 yylval을 통해서 넘어온 값을 이용해서 어떤 작업을 가능하도록 코딩해 주기만 하면 된다. 다른 부분은 모두 동일하니 아래의 부분만 수정하면 된다.

heat_switch:
    TOKHEAT STATE
    {
        if($2)
            printf("\tHeat turned on\n");
        else
            printf("\tHeat turned off\n");
    }
    ;

target_set:
    TOKTARGET TOKTEMPERATURE NUMBER
    {
        printf("\tTemperature set %d\n", $3);
    }
    ;
			

tatget_set 역시 동일한 방법으로 수정했다. 온도 값은 NUMBER 토큰값으로 넘어옴으로 $3를 이용해서 받아서 이를 출력했다.

컴파일 테스트를 하면 다음과 같은 결과를 확인할 수 있을 것이다.

# ./example5
heat on
  Heat turned on
heat off
  Heat turned off
target temperature 50
			

3.3. 계산기를 만들어 보자

이번에는 계산기 프로그램을 만들어 보도록 하자. 앞서의 예제처럼 flex와 bison의 작동방식도 함께 설명하도록 하겠다.

계산기 프로그램은 사칙연산을 하는데, "()"도 처리를 할 것이다. 또한 값을 변수에 저장하는 기능까지를 추가할 것이다. 아시겠지만 계산기 프로그램을 작성함에 있어서 ()처리를 한다는게 그리 간단한게 아니라는걸 이해 할것이다. 그러나 이 예제를 통해서 flex와 bison을 쓴다면 그리 어렵지 않게 작성 가능하다는 것을 알 수 잇을 것이다.

계산기 프로그램에서는 토큰으로 INTEGER와 VARIABLE를 선언한다. INTEGER은 피연산자에 대한 토큰을 만났을 때 사용하는 토큰값이며, VARIABLE는 변수를 만났을 때 사용할 토큰 값이다. 여러분이 bison를 실행 시킨다면 cal.tab.h 파일을 볼 수 있을 건데, 다음과 같은 코드를 포함하고 있을 것이다.

#ifndef YYSTYPE
#define YYSTYPE int
#endif
#define INTEGER 258
extern YYSTYPE yylval;
			

[0-9]+     {
               yylval = atoi(yytext);
               return INTEGER;
           }
			

이제 연산자들과 ()에 대한 토큰을 얻어와야 한다.

[-+()=/*\n]   {return *yytext;}
			

[a-z]  {
          yylval = *yytext - 'a';
          return VARIABLE  
       }
			

bison 문법에서의 핵심은 각 연산자에 맞도록 연산을 실행하고, 괄호를 만났을 경우 우선 연산할 수 있어야 한다는 점이다.

expr:
		INTEGER
		| VARIABLE       { $$ = sym[$1]; }
		| expr '+' expr  { $$ = $1 + $3; }
		| expr '-' expr  { $$ = $1 + $3; }
		| expr '*' expr  { $$ = $1 + $3; }
		| expr '/' expr  { $$ = $1 / $3; }
		| '(' expr ')'   { $$ = $2; }
		;
			

()를 만났을 경우 이 연산은 우선적으로 이루어 져야 한다. 그러므로 ()안에 있는 연산들 자체를 스택의 가장 아래로 밀어 넣어야 할 것이다. 이를 위해서 '(' expr ')' {$$ = $2;}가 사용하고 있다.

다음은 flex와 bison의 완전한 코드로 파일이름은 cal.l, cal.y로 하며, 위에서 빠진 몇가지 내용들은 주석을 통해서 설명하도록 하겠다.

예제 : cal.l

%{
#include <stdlib.h>
void yyerror(char *);
#include "mycal.tab.h"
%}

%%
 /* 변수명을 위한 VARIABLE 토큰을 되돌려 준다 */
 /* 변수명은 a-z 까지 사용될 수 있다.         */ 
 /* 리턴된 값은 cal.y에서 sym테이블을 만들기 위해서 사용된다. */ 
[a-z]   {
          yylval = *yytext - 'a';
          return VARIABLE;
        }
 
 /* 숫자를 만났을 때 */
[0-9]+  {
          yylval = atoi(yytext);
          return INTEGER;
        }
 /* 연산자를 만났을 때 */
[-+()=/*\n] {return *yytext;}

[ \t]   ;     /* 무시한다 */

.       yyerror("invalid character");
%%

int yywrap(void)
{
  return 1;
}
			

%token INTEGER VARIABLE
%left '+' '-'
%left '*' '/'

%{
  void yyerror(char *);
  int yylex(void);
  int sym[26];
%}

%%

program:
    program statement '\n'
    |
    ;

 /* 변수를 만났을 경우                                */
 /* 변수명의 토큰값을 이용해서 심볼릭 테이블을 만든다 */ 
 /* 만약 변수명이 'a'라면 토큰값은 0이 리턴되고       */
 /* sym[0] 에 연산결과가 들어가게 된다.               */   
statement:
    expr                  { printf("계산결과 %d\n", $1); }
    | VARIABLE '=' expr   { sym[$1] = $3; }
    ;

expr:
    INTEGER
    | VARIABLE            { $$ = sym[$1]; }
    | expr '+' expr       { $$ = $1 + $3; }
    | expr '-' expr       { $$ = $1 - $3; }
    | expr '*' expr       { $$ = $1 * $3; }
    | expr '/' expr       { $$ = $1 / $3; }
    | '(' expr ')'        { $$ = $2; }
    ;

%%
void yyerror(char *s)
{
  printf("%s\n", s);
  return 0;
}

int main(void)
{
  yyparse();
  return 0;
}
			

# ./cal 
a=5*(10+20)
a
계산 결과 150
a=10+5+2 +(2*10)
a
계산 결과 37
(10*12)/(3*2)
계산 결과 20
b=((52+32)/(2*1)+(16*3))+(22*2)
b
계산 결과 134