<그림1>
컴파일을 할때 일단 string으로 적혀 있는 어떤 컴퓨터 언어의 어휘 분석을하여 의미 단위인 토큰을 추출하고(flex), 그 토큰들의 관계가 어떻게 되는지를 따져서 실제로 그런 관계가 되도록 하는 Parsing(bison) 단계가 있다. 그렇게 되면 C코드가 만들어지고 그것을 가지고 어셈블리어를 만들게 되고 이후에 실행가능 파일로 만들게 된다. <그림1>에서 Lexical Analyzer 가 flex고, Parser가 bison이 하는 역할이다.
역으로 flex와 bison을 알게되면 새로운 컴퓨터 언어를 창조할 수 있다는 이야기! (어차피 C코드로만 만들게 되면 나머지는 해결)
자 그럼 계산기 예제를 만들어 보면서 flex와 bison이 어떤 일을 하는 지 알아보자. 먼저 flex예제부터 보자.
fb1-4.1l 예제
//선언부
%{
enum yytokentype { //token에게 값을 부여해보자. 원래는 자동으로 부여된다.
NUMBER = 258, //token은 자동적으로 258부터 시작하지만 일단 예제이므로 직접 작성해본다.
ADD = 259,
SUB = 260,
MUL = 261,
DIV = 262,
ABS = 263,
EOL = 264
};
int yylval; //token의 return값을 담을 변수
%}
//pattern
%%
"+" { return ADD; } //각 부호 마다 맞는 token을 return한다.
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"|" { return ABS; }
[0-9]+ { yylval = atoi(yytext); return NUMBER; } //숫자는 int 타입으로 yylval에 저장하고 token을 return한다.
\n { return EOL; } //newline 이면 EOL을 return한다.
[ \t] { /* ignore whitespace */ } //공백 무시
. { printf("Mystery character %c\n", *yytext); }
//C code
%%
main(int argc, char **argv)
{
int tok; //token값 임시 저장 변수
while(tok = yylex()) { //token의 return값이 있는 경우
printf("%d", tok); //token의 value를 출력
if(tok == NUMBER) printf(" = %d\n", yylval); //만약 token이 NUMBER라면 yylval의 value도 출력
else printf("\n");
}
}
//결과
$ flex fb1-4.l
$ cc lex.yy.c -lfl
$ ./a.out
a / 34 + |45
Mystery character a
262
258 = 34
259
263
258 = 45
264
결과를 보면 token의 value가 출력되는 것을 알 수 있다. 즉 string 으로 입력된 code들을 scan해서 의미가 있는 단위로 추출했다는 것이다.
또한 yylval 은 scanner 가 token을 return 할때 token의 값이 들어있는 것이다.
그런데 이제 이 token을 가지고 이들의 관계를 지정해 줘야한다. 밑에 <그림2>을 보자.
<그림2>
예를들어 1 * 2 + 3 * 4 + 5 라는 계산식이 있을 때 우선적으로 계산되어야 하는 것이 있다. 즉 token마다 의미가 있고 관계가 있다.
위의 <그림2> 처럼 트리를 만들어서 parser가 사용하도록 해줘야하는데 그럴때 쓰는 언어가 바로 context-free grammar(CFG) 이다.
그 중에서 standard form 은 Backus-Naur Form (BNF)이다. 우리가 쓸 bison은 BNF가 기반이다.
예를 들어 1 * 2 + 3 * 4 + 5 라는 것이 있을 때 아래와 같이 표현한다.
<exp> ::= <factor>
| <exp> + <factor>
<factor> ::= NUMBER
| <factor> * NUMBER
각 라인은 parse tree 의 branch를 어떻게 생성할지에 대한 규칙이다. 이때 기호는 아래와 같이 해석한다.
::= 은 is a 나 become 으로 해석
| 는 or 로 해석
규칙의 왼쪽에 있는 이름은 symbol 혹은 term이다. 자 이제 해석하는 방법으 알아보자.
첫번째 규칙을 보면 exp는 factor 이거나 exp는 exp + factor 형태이다. 그렇담 여기서 factor란 무엇인가? 그것은 두번째 규칙에 있다.
두번째 규칙에서 factor는 NUMBER이거나 factor는 factor * NUMBER형태이다.
위 규칙에 의하면 곱하기가 된 것 혹은 숫자들이 factor가 되고 그것들을 더하거나 그 자체가 exp가 된다. 즉 곱하기를 먼저하고 더하기를 하게 되는 것이다.
아래의 간단한 사칙연산 계산기 bison 예제를 보자.
fb1-5.y 예제
/* simplest version of calculator */
//선언부
%{
#include <stdio.h>
%}
/* declare tokens */
%token NUMBER
%token ADD SUB MUL DIV ABS
%token EOL
%%
//rules
calclist: /* nothing 아무것도 안함 */ //matches at beginning of input
| calclist exp EOL { printf("= %d\n", $2); } //EOL is end of an expression //결과 출력
;
//더하기, 빼기 규칙
exp: factor //default $$ = $1
| exp ADD factor { $$ = $1 + $3; }
| exp SUB factor { $$ = $1 - $3; }
;
//곱하기, 나누기 규칙
factor: term //default $$ = $1
| factor MUL term { $$ = $1 * $3; }
| factor DIV term { $$ = $1 / $3; }
;
//숫자, 절대값 숫자 규칙
term: NUMBER //default $$ = $1
| ABS term { $$ = $2 >= 0? $2 : - $2; }
;
%%
//C code
main(int argc, char **argv)
{
yyparse();
}
yyerror(char *s)
{
fprintf(stderr, "error: %s\n", s);
}
flex와 마찬가지로 3개의 part로 나뉘어져있다. (선언, 규칙, C code)
BNF와 달리 bison 은 ::= 대신 : 을 사용한다. 그리고 ; 은 rule 의 끝을 의미한다.
Bison은 rule이 match됐다면 자동적으로 parsing을 해줘서 C code에서 각각의 symbol이 값과 연관 되도록 한다.
맨 처음의 rule의 왼쪽 symbol은 start symbol이라고 한다.
각 symbol 마다 값을 가지고 있는데 target symbol은 action code에서 $$으로 표현된다.
오른쪽에 있는 값들은 차레대로 $1, $2... 순으로 표현된다.
예를들자면!
exp: factor -> exp = $$, factor = $1
| exp ADD factor { $$ = $1 + $3; } -> exp = $1, ADD = $2, factor = $3
| exp SUB factor { $$ = $1 - $3; } -> exp = $1, SUB = $2, factor = $3
;
이런식으로 각각 $$과 $1, $2... 들이 매치되는 것이다.
자 이제 flex로 만든 예제파일과 bison으로 만든 예제파일을 하나로 합쳐서 계산기를 만들어 보자.
합치기 전에 parser가 불러올 수 있도록 fb1-4.1l 예제를 약간 수정해야 한다.
특히 우리가 token의 value를 직접 정의하는 것보다 bison이 token number와 yylval의 정의를 생성해주는 헤더파일을 include 하도록 한다.
parser가 scanner를 호출할 것이기 때문에 우리는 scanner의 세번째 section에 있는 main routine을 제거하도록 한다.
수정결과는 아래와 같다.
fb1-4.l을 수정한 fb1-5.l 예제
//선언부
%{
#inclue "fb1-5.tab.h" //헤더파일 include
%}
//pattern
%%
"+" { return ADD; } //각 부호 마다 맞는 token을 return한다.
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"|" { return ABS; }
[0-9]+ { yylval = atoi(yytext); return NUMBER; } //숫자는 int 타입으로 yylval에 저장하고 token을 return한다.
\n { return EOL; } //newline 이면 EOL을 return한다.
[ \t] { /* ignore whitespace */ } //공백 무시
. { printf("Mystery character %c\n", *yytext); }
%%
이때 makefile 의 내용은 아래와 같다.
# part of the 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
<그림3>
설명하자면 이렇다. 처음에 bison이 -d 옵션(for "definitions" file)에 의해 fb1-5.tab.c와 fb1-5.tab.h를 생성한다.
이때 fb1-5.tab.h에는 bison에서 선언한 token에 대한 value 정보가 들어있고 yylval도 선언되어있다. 그렇기 때문에 flex 코드에서 이 헤더파일을 include하여 쓰게 된다.
그리고 flex가 lex.yy.c를 만들도록 한다. 그 후에 flex library와 함께 컴파일을 한다.
그 후에 실행해본다.
$ ./fb1-5
2 + 3 * 4
= 14
2 * 3 + 4
= 10
20 / 4 - 2
= 3
20 - 4 / 2
= 18
결과는... 잘 된다!!
우리가 계산기를 만들었다!
출처 :
flex_bison_O'Reilly
댓글 없음:
댓글 쓰기