writer: unidev

먼저 Flex / Bison에 대한 설명을 해보자면, Flex는 문자열을 분석하여 토큰 단위로 나누고, Bison은 yacc의 기능을 개선한 GNU 파서를 생성해주는 파서 생성기라고 말할 수 있습니다. 또, Flex, Bison의 개념들을 잘 이해하고 있으면 응용하여 컴파일러도 만들 수 있습니다.

Flex, Bison 의 개념을 이해하기 위하여 기본적인 예제인 계산기를 만들어 볼 것인데, 예제 소스는 아래 링크를 참고하면 됩니다.

https://github.com/smakerdev/flex_bison

fb1-5.l

%%
"+"	{ return ADD; }
"-"	{ return SUB; }
"*"	{ return MUL; }
"/"	{ return DIV; }
"|"     { return ABS; }
"("     { return OP; }
")"     { return CP; }
[0-9]+	{ yylval = atoi(yytext); return NUMBER; }

\n      { return EOL; }
"//".*  
[ \t]   { }
.	{ yyerror("Mystery character %c\n", *yytext); }
%%

위 코드를 보면 입력되는 문자열의 패턴을 검증하여, 그 패턴에 매칭되면 일련의 행동을 취하는 코드이다. 예를 들어 "3 + 2"가 입력이 되면, 먼저, "3", "2"이라는 숫자가 "[0-9]+"에 매칭이 될 것이다. 또, "+"는 "+"에 매칭이 되어 ADD를 반환하게 된다.

fb5-1.y

exp: factor
 | exp ADD exp { $$ = $1 + $3; }
 | exp SUB factor { $$ = $1 - $3; }
 ;

계산기의 기본 기능인 덧셈, 뺄셈 규칙을 정의한 부분이다. Bison은 규칙을 정의하고, 정의된 규칙에 매칭이 되었다면 자동적으로 파싱을 해줘서 C code에서 각각의 symbol이 값과 연관 되도록 한다. 위 코드와 비슷한 방식으로 곱셈, 나눗셈 부분도 규칙을 정의할 수 있다. (Github 코드 참고)

빌드 과정

  • 컴파일 방법 (Makefile)
fb1-5: fb1-5.l fb1-5.y
       bison -d fb1-5.y
       flex fb1-5.l
       cc -o $@ fb1-5.tab.c lex.yy.c -lfl

11

먼저, Bison으로 컴파일되면 "fb1-5.tab.c", "fb1-5.tab.h" 두 개의 파일을 생성하게 된다. "fb1-5.tab.h"에는 Bison에서 선언한 token에 대한 value 정보가 들어있고 yylval도 선언되어있다. 이 때문에 flex 코드에서 이 헤더파일을 include 하게 된다. 그 후 flex가 "lex.yy.c"를 만들게 된다. "lex.yy.c" 파일과 "fb1-5.tab.c" 파일을 함께 컴파일한 후 실행해본다.

$ ./fb1-5
2 + 3 * 4
= 14
2 * 3 + 4
= 10
20 / 4 - 2
= 3
20 - 4 / 2
= 18
  • Reference
    • O'REILLY Flex & Bison