Flex and Bison Howto
Flex and Bison Howto
윤상배
고친 과정 | ||
---|---|---|
고침 0.890.88 | 2004년 07월 25일 13시2004년 07월 25일 04시 | |
오타 수정계산기 예제 추가 | ||
고침 0.85 | 2004년 07월 22일 09시 | |
번역에서 문서 참고 스타일 변경 | ||
고침 0.82 | 2004년 07월 21일 09시 | |
lex/yacc를 flex/bision 기반으로 변경, 4장 추가 | ||
고침 0.81 | 2004년 07월 20일 09시 | |
번역시작 1-3장 | ||
고침 0.8 | 2002년 04월 20일 19시 | |
원본 문서작성 |
- 차례
- 1. 소개
- 1.1. 이 문서에서 할 수 없는 것
- 1.2. 문서의 다운로드
- 1.3. Flex와 Bison
- 2. Flex
- 2.1. 정규표현을 이용한 매칭
- 2.1.1. 꼭 필요한 정규표현
- 2.2. 복잡한 문장의 파싱
- 2.3. flex에 미리 정의된 변수들
- 2.4. 지금까지 다룬 내용들
- 3. Bison
- 3.1. 간단한 온도 조절기
- 3.1.1. 완전한 Bison 파일
- 3.2. 온도조절 프로그램의 업그레이드
- 3.3. 계산기를 만들어 보자
1. 소개
문서의 많은 부분은 Lex, Yacc Howto와 Compact Guide to Lex & Yacc를 참고하고 있습니다.
만약 당신이 오랜시간동안 유닉스 환경에서 프로그래밍을 해왔다면 LEX와 YACC라는 이름의 다소 신비스러운 느낌을 주는 프로그램에 대해서 들어 봤을 것이다. 혹 당신이 GNU/Linux에 더 친숙하다면 Flex와 Bison이라는 프로그램에 대해서도 몇번 정도는 들어 봤을 것이다. Flex는 Vern Paxon에 의해서 만들어진 lex(12)의 확장 도구격인 프로그램이며, Bison은 YACC의 GNU버젼격인 프로그램이다. 여기에서는 Lex와 yacc(12)의 화갖어전이라고 할수 있는 Bison과 Flex에 대해서 다룰 것이다. 원조격인 Yacc와 Lex와의 차이점이 거의 없으므로 호환에 문제가 생기지는 않을 것이다. 어쨋든 GNU환경에서의 개발은 GNU툴은 Bison과 flex가 좀더 자연스럽다.
이들 프로그램은 당신이 매우 중요하게 사용하는 C 컴파일러와 같은 프로그램의 작성에 중요하게 사용되는데, 그 중요성에 비해서 man 페이지는 썩 훌륭하지 못해서 이것만 을 가지고는 이들 도구를 사용할 수가 없다. 여기에서는 이들 도구를 실질적으로 사용할 수 있도록 좀더 실용적 관점에서 다룰 것이다.
1.1. 이 문서에서 할 수 없는 것
시중에는 이미 다양한 종류의 Lex와 Yacc를 주제로 하고 있는 좋은 책들이 나와 있다.(워낙에나 Flex/Bison과 비슷하기 때문에, 저들 책을 가지고 Flex와 Bison을 학습하기도 한다.) 비록 이 문서가 Bison과 Flex를 학습하는데 많은 도움을 주긴 하겠지만, 이들 책보다 더 낳은 정보를 제공해주긴 힘들 것이다. 이들 책은 대부분의 경우 책임감을 가지고 작성되었기 때문에 이 문서에서 제시하지 못한 다른 중요한 정보들을 가지고 있을 것이다. 이 문서는 Flex와 Bison을 좀더 쉽게 접할 수 있기 위한 입문서 정도로 활용을 해주길 바란다.
또한 이문서를 작성한 저자는 Flex/Bison 전문가가 아니며, 공부하면서 이 문서를 작성했다. 이점을 염두에 두고 이 문서를 읽기 바란다. 대부분의 예제들은 돌아가는지 확인하기 위한 간단한 수준에서 작성될 것이다. 좀더 현실감 있는 예제를 추가하길 원한 다면 언제든지 이 문서의 원본을 수정하는 정도로 참가할 수 있을 것이다.
1.3. Flex와 Bison
필자가 한살이던 1975년경 무렵 컴파일러를 작성하는 것은 사람의 애간장을 녹이는 인간의 인내력이 어디까지인가를 테스트하는 고도의 참을성과 집중력을 필요로 하는 작업이었다. 이러한 일련의 작업을 좀더 쉽게 하기위해서 Johnson과 Lesk란 사람들이 lex와 yacc라는 도구를 만들게 되었다. 이 도구는 컴파일러의 작성을 매우 간단하게 처리할 수 있는 훌륭한 기능을 가지고 있었으며 계속 발전을 해서 1986년경 지금 우리가 사용하는 현대적인 기능을 가진 lex와 yacc가 발표되게 되었다. lex와 yacc는 매우 훌륭한 도구 였기 때문에 아래와 같은 다른 많은 버젼들이 만들어지게 되었다.
Mortice Kern Systems(MKS), http://www.mks.com
(우리가 다루고자 하는)GNU flex, bison
Ming, http://www.mingw.org
또다른 lex, yacc버젼, http://www.epaperpress.com
여기에서는 lex와 yacc의 원리에 대해 간단하게 소개하도록 할 것이다. 우리의 목적이 Flex와 Bison의 사용방법이긴 하지만 워낙에 lex와 yacc의 역사적 의미가 깊은 관계로 lex, yacc를 기준으로 했다. 그러나 도구의 이름이 틀리고 만들어내는 파일의 이름이 틀린 외에는 동일함으로 문제될건 없을 것이다.
lex는 어휘분석과 scanner를 위한 C코드를 생성한다. lex는 입력된 문자에서 매칭되는 문자열의 패턴을 이용해서 문자열을 토큰으로 변환한다. 토큰은 문법적으로 더이상 나눌 수 없는 기본적인 언어 요소를 말한다. 다음은 컴파일이 이루어지는 일반적인 과정이다. 토큰을 만들어내는 과정을 주의 깊게 보기 바란다.
심볼 테이블을 이용해서 lex는 입력되는 문자열의 특징을 가져온다. 심볼 테이블은 문자열이 숫자인지 단어인지와 같은 타입에 대한 정보와 어떤 변수를 통해 메모리에 접근할 수 있을 것인지 등을 정의 한다.
Yacc는 구문분석과 파서를 위한 C코드를 생성한다. yacc는 lex로 부터 토큰을 받아들이고 이것을 문법룰에 넣고 돌려서 구문트리(syntax tree)를 생성한다. 구문트리는 토큰구조체의의 계층적인 구조를 만들게 된다. 위의 그림을 보면 연산자와 값에 따라 계층 구조를 볼 수 있을 것이다. 다음 단계에서 코드를 생성(code generator)하게 된다. 코드 생성은 깊이 우선으로 이루어지게 된다. 만들어지는 코드는 시스템의 어셈블러가 해석가능한 어셈블리코드 혹은 기계어 코드가 된다. 위의 그림은 lex와 yacc에 의해서 사용되는 파일 이름의 규칙이다. 예를 들어 BASIC 컴파일러를 만든다고 가정해 보자. 먼저 우리는 패턴매칭 규칙을 가진 bas.i라는 lex파일을 만들 것이다. 그리고 문법규칙을 위해서 basy.y라는 yacc파일을 만들 것이다. 그리고 마지막으로 gcc를 이용해서 basc 라는 컴파일러를 만들게 된다.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. Flex
Flex의 원조는 Lex로 흔히 Lex generate라고 하며 'Lexer'라고 부르기도 한다. GNU버젼은 여기에 F(Fast)를 붙여서 이전 버젼의 Lex와 구분하고 있다. 주로 문자열을 받아들이고 문자열중에서 원하는 형식의 문자의 조합이 있는지 확인해서 어떤 함수(작업)를 실행시키는 일을 한다. 다음은 간단한 예제이다.
%{ #include <stdio.h> %} %% stop printf("Stop command receive\n"); start printf("Start command receive\n"); %% |
다음 섹션은 %%를 구분자로 해서 시작되는데, 첫번째는 'stop'이라는 문자열을 키로 시작하고 있다. 이것은 문자열의 입력중에 'stop'문자열을 대면할 경우 뒤에 있는 printf()를 실행하라는 의미를 가진다.
stop과 마찬가지로 'start'에 대해서도 printf()문을 실행하라고 선언되어 있다.
위의 문법은 lex에서 사용될 수 있는 문법으로, 이걸 실제 사용하기 위해서는 C가 인식할 수 있는 문법으로 변경시켜줘야 한다. 이러한일 역시 lex가 담당한다. 일종의 선처리기 라고 할 수 있다.
# flex example1.l # gcc lex.yy.c -o example1 -lfl |
참고: 만약 flex대신에 lex를 사용하길 원한다면 -lfl 대신 -ll을 사용하면 된다.
# ./example1 start program Start command receive program stopped Stop command receive ped ^D |
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.1.1. 꼭 필요한 정규표현
정규표현은 매우 광범위한 주제임으로 여기에서는 반드시 필요한 정규표현 규칙에 대해서만 간단히 정리하기로 하겠다. 정규표현에 대한 자세한 정보는 정규표현을 참고하기 바란다.
flex를 제대로 사용하기 위해서는 위의 표에 정리된 자주사용되는 패턴매칭의 내용들은 기본적으로 숙지하고 있어야 한다. 두번째 표에 있는건 패턴매칭의 사용예이다.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.4. 지금까지 다룬 내용들
지금까지의 내용들을 통하여 Lex는 임의의 입력을 받아들여서 각각의 부분을 의미를 결정할 수 있음을 알았다. 이러한 것을 'Tokenizing'라고 한다.
3. Bison
Bison의 원조격인 YACC에 대해서 먼저 알아보기로 하자. YACC는 Yet Another Compiler Compiler의 약자로 컴파일러를 생성을 위한 프로그램 이다. compiler-generator 혹은 compiler-compiler이라고 부르기도 한다. yacc는 lex에 의해서 얻어진 token들의 관계를 구성하는 "구문분석기"를 생성하는 툴이다. yacc가 내부적으로 token을 얻기 위해서 lex를 사용하는데, lex와 yacc, flex와 bison을 한 묶음으로 해서 다루는 이유가 된다. lex를 호출하기 때문에 lex의 상위에 위치하게 된다. Bison은 이러한 일을 하는 YACC의 GNU버젼이며, 하는일 옵션등에 있어서 거의 동일하다.
Bison(yacc)는 BNF (Backus Naur Form)을 이용해서 필요한 일을 수행한다. 이 기술은 John Backus 와 Peter Naur에 의해서 만들어 졌으며 ALGOL60 언어를 제작하는데 사용되었다. BNF 문법은 자유로운 문맥(context-free) 언어를 표현하는데 유용하게 사용할 수 있다. 현대의 대부분의 프로그래밍 언어는 BNF를 이용해서 문맥을 표현하고 있다.
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이 실행되도록 룰을 만들었다.
3.1.1. 완전한 Bison 파일
다음은 이상의 모든 내용을 종합한 Bison 파일이다.
%{ #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"); } ; |
yywrap()는 다른 파일로 부터 계속적으로 읽기를 수행하고자 할때 사용한다.
main함수가 호출되었다. main함수는 단지 yyparse만을 호출하지만 우리가 지금까지 만들었던 룰을 이용해서 입력되는 문자열을 이용해서 작업을 수행한다.
마지막으로 우리가 사용하게될 토큰을 선언하였다. 지금까지의 모든내용은 yacc 를 -d 옵션을 주고 실행함으로써, y.tab.h에 쓰여지게 된다.
컴파일은 아래와 같이 이루어진다.
# 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 |
댓글