컴파일러구성을위한대표적소프트웨어도구인 Lex( 또는 Flex) 와 Yacc( 또는 Bison) 입문 : Windows 환경에서 김도형 ( 성신여자대학교 IT 학부 ) 0. 소개 (1) Lex 와 Yacc 은무엇인가? 컴파일러의구성을도와주는대표적인소프트웨어도구들이다. 원래 UNIX의산실인벨연구소 (AT&T Bell Laboratories) 에서 UNIX 시스템의유틸리티 (utility) 로서개발되었다. 각각의개발자는 Lex는 Mark Lesk, Yacc은 Steve Johnson이다. 이후이도구들의유용성이확인되면서 Sun의 Solaris나 Linux와같은 UNIX 계열의운영체제는물론이고, Microsoft Windows 등의상이한운영체제에도이식 (porting) 되어서널리사용되고있다. (2) Lex 와 Yacc 을어떻게구하는가? 현재 UNIX 계열상용 ( 商用 ) 운영체제의경우 Lex와 Yacc은기본유틸리티의일부로서포함되어있다. 그러나 Lex와 Yacc의판권 (copyright) 은 Bell Laboratories( 현재 Lucent Technology) 가가지고있으므로, Linux와같은 FSF(Free Software Foundation) 의정신을표방하는운영체제의경우는각각 Lex와 Yacc의 GNU 버전 (version) 인 Flex와 Bison을기본유틸리티로서갖추고있다. 그외도여러운영체제를위한약간씩다른 Lex와 Yacc의버전들이있다. Windows 상에서 Cygwin 시스템을사용한다면처음설치할때 Flex와 Bison을선택하여사용하는것이가장 UNIX 계열운영체제와유사하게사용할수있을것이다. 이밖에도 Windows 환경에서 Lex와 Yacc 또는그에상응하는유틸리티를이용하기위한몇가지다른방법이있다. 원래의 Lex나 Yacc과는달리결과파일을 C 언어뿐만아니라 C++ 언어나 Java 언어로출력하는상용소프트웨어도시판되고있다. 또한 Cygwin 시스템과같이 UNIX 계열운영체제와유사한환경전체의설치가필요없는경우, GNU C 컴파일러 (gcc) 와 Flex, Bison만 Windows 운영체제에설치하여사용할수도있다. 이 Windows 운영체제용튜토리얼 (tutorial) 에서는가장간단한마지막방법에기반을두어설명하도록하겠다. ( 추후 Windows 운영체제를위한다른방법에대한내용을추가할계획이다.) - 1 -
(3) Windows 운영체제에 GNU C 컴파일러와 Flex, Bison 설치하기 적용된 Windows 운영체제는 32비트용 Windows 7이나, 다른버전에서도유사할것으로본다. 먼저 GNU C 컴파일러를설치한다. 이것을설치하는편한방법중하나가유명한무료 C/C++ 프로그램용통합개발환경 (IDE integrated development environment) 인 Bloodshed 사의 Dev-C++ 를설치하는것이다 ( 관련사이트링크 : http://www.bloodshed.net/devcpp.html). 원래 Dev-C++ 가 GNU C 컴파일러를기본으로하여그위에사용자편의를위한 IDE 인터페이스를뒤집어씌운것이기때문이다. Dev-C++ 를설치하면 ( 주의 : 이것이설치되는폴더 (folder) 까지이르는경로명 (path name) 에공백이없도록한다. 보통 C:\Dev-Cpp 에설치한다 ) 그설치디렉터리 (directory) 아래 bin 이라는하위디렉터리가만들어지고이안에 GNU C 컴파일러 ( gcc.exe ) 와 C++ 컴파일러 ( g++.exe ) 가설치된다. 그다음에는 Flex와 Bison을설치한다. ( 비록이렇게서술하지만이세프로그램 (GNU C 컴파일러, Flex, Bison) 의설치순서는바뀌어도상관없다.) Flex를다운로드받는다 ( 관련사이트링크 : http://gnuwin32.sourceforge.net/packages/flex.htm). 설치는매우간단하여다운로드받은설치파일을실행시킨후몇번 동의 또는 다음 버튼을누르기만하면된다 ( 주의 : Dev-C++ 와마찬가지로이것이설치되는폴더까지이르는경로명에공백이없도록한다. 보통 C:\GnuWin32 에설치한다 ). Bison도다운로드받아서 ( 관련사이트링크 : http://gnuwin32.sourceforge.net/packages/bison.htm) Flex 와같은요령으로설치한다 ( 주의 : 앞의두프로그램과마찬가지로이것이설치되는폴더까지이르는경로명에공백이없도록한다. 경로명에공백이있는경우실제 Bison을사용할때오류가발생하는것을확인했으니특히주의해야한다. 보통 Flex와함께 C:\GnuWin32 에설치한다 ). 세프로그램의설치를마치면시스템의환경변수들중 PATH 변수의값에 GNU C 컴파일러와 Flex, Bison의실행파일이있는경로를추가한다. 즉, 예컨대 C:\Dev-Cpp\binC:\GnuWin32\bin 을추가내지 ( PATH 변수가없었던경우 ) 새롭게등록하는것이다. 명령프롬프트 (command prompt) 창을연다 ( 모든프로그램 보조프로그램 명령프롬프트 메뉴를선택하여실행하거나실행창에서 cmd(.exe) 를입력하여바로실행시킨다 ). 이창에서 flex --version 을입력하여설치된 Flex의버전을확인한다 ( 최신버전은 2.5.4a). bison --version 을입력하여설치된 Bison의버전을확인한다 ( 최신버전은 2.4.1). gcc --version 을입력하여설치된 GNU C 컴파일러의버전을확인한다 ( 최신버전은 3.4.2이나 Dev-C++ 안정버전에포함된것은 3.3.1. 어느것이라도상관없다 ). 설치의마지막으로 Flex와 Bison이필요로하는라이브러리파일을 GNU C 컴파일러가찾을수있도록적절한디렉터리에복사한다. Flex와 Bison이설치된디렉터리 ( 예컨대 C:\GnuWin32 ) 에가면여러하위디렉터리가있는데, 그중 lib 속에 libfl.a 와 liby.a 가포함되어있고이것들이각각 Flex 와 Bison의라이브러리아카이브 (archive) 파일이다. 이것들을 GNU C 컴파일러의라이브러리디렉터리 ( 예컨대 C:\Dev-Cpp\lib ) 에복사한다. - 2 -
Flex 와 Bison 을사용하는일반적인형태는다음 C:\Users\JohnDoe> flex test.l C:\Users\JohnDoe> bison test.y 과같다. (Flex 입력파일의이름은 test.l, Bison 입력파일의이름은 test.y 라고가정한다.) 이렇게하면현재작업하는디렉터리에 Flex 와 Bison 의실행결과파일이만들어진다. 보다자세한설 명은뒤에서여러예제를직접보면서할것이다. - 3 -
1. Lex(Flex) 와 Yacc(Bison) 의작동 (1) Lex(Flex) 와 Yacc(Bison) 의역할 Lex(Flex) 와 Yacc(Bison) 모두사용자가작성한명세 (specification) 파일을처리하여각각기본적으로 C 언어로작성된어휘분석프로그램 (lexical analyzer 또는 scanner) 과구문분석프로그램 (syntax analyzer 또는 parser) 을만들어낸다 ( 이결과프로그램을 C++ 언어또는 Java로내는확장상용버전도있다 ). 사용자는이결과파일을컴파일하여단독으로, 또는컴파일러나다른용도의더큰프로그램의일부로사용하게된다. 그리중요한점은아니나, 오리지널 Lex와 Yacc 프로그램이결과로만들어내는파일의이름은각각 lex.yy.c' 와 y.tab.c 로고정되어있었다. 그러나 GNU 버전인 Flex와 Bison에서는입력파일의이름뒤에확장자로각각 yy.c 와 tab.c 를붙여서결과파일의이름을정할수있도록수정되었다. 각프로그램의입력으로들어가는명세파일의내용은그목적에비추어보면명백하게예상할수있다. 어휘분석기의경우, 입력으로기호 ( 대개문자 ) 들의스트림 (stream) 을받아그기호들로이루어진스트링 (string) 들의스트림을출력으로내보내므로 ( 이기호스트링을토큰 (token) 이라고도부르고, 이러한이유로 scanner를 tokenizer라고부르기도한다 ), Lex(Flex) 입력명세에는입력스트림으로부터한단위또는토큰으로모아야하는기호들의패턴들이규정되어있어야한다. 구문분석기의경우는기호스트링들의스트림을입력으로받아그스트링들이주어진문법에부합되는지의여부를판단하고부합할때는출력으로그스트링들의파스트리 (parse tree) 또는구문트리 (syntax tree) 를내보낸다 ( 출력은컴퓨터내부에서꼭명시적으로트리형태를가질필요는없으며, 구문분석과정에서묵시적으로구성되어이용될수도있다 ). 따라서 Yacc(Bison) 입력명세에는문법의생성규칙 (production rule) 들이규정되어있어야한다. (2) Lex(Flex) 와 Yacc(Bison) 의입력파일형식의얼개 두프로그램의입력파일모두크게세부분으로구성되어있으며, 각부분의역할도비슷하다. 첫번째부분은선언 (declaration) 이나정의 (definition) 가포함되며, 두번째부분은본론에해당하는것으로서각프로그램이수행하는일에대한규칙 ( 보통번역규칙 (translation rule) 이라고부른다 ) 을기술하고, 세번째부분은보조프로시저 (auxiliary procedure) 또는지원프로그램 (supporting routines) 을담고있다. 이세부분들중꼭있어야하는필수부분은두번째부분이고, 첫번째와세번째부분은필요없는경우생략이가능하다. 각부분은연속된두개의 % 기호로구분된다. 첫번째와세번째부분에대한설명은뒤에예제를통해하기로하고, 가장핵심이되는두번째부분에대해간략하게언급하고자한다. - 4 -
Lex(Flex) 의경우이두번째부분은아래 패턴 1 { 동작 1 패턴 2 { 동작 2 패턴 n { 동작 n 와같은형식을가지고있는데, 앞부분의패턴 (pattern) 이입력스트림에서발견되면뒷부분에있는동작 (action) 을실행하라는의미이다. 동작은 C 언어로된문장들로서, 하나의문장이면중괄호 (curly braces) 가필요없다. 패턴은스트링패턴을기술하는데보편적으로사용되는정규표현 (regular expression) 을 Lex에서확장한것을사용한다. Yacc(Bison) 의경우이두번째부분은아래 생성규칙 1 의좌변 : 의미동작이추가된생성규칙 1 의우변생성규칙 2 의좌변 : 의미동작이추가된생성규칙 2 의우변 생성규칙 n 의좌변 : 의미동작이추가된생성규칙 n 의우변 와같은형식을가지고있는데, 생성규칙의우변에있는문법기호 (grammar symbol) 들사이의필요한곳에중괄호에둘러싸인의미동작 (semantic action) 이삽입되어있는형태이다. 즉, 구문-인도번역 (syntax-directed translation) 의한종류인번역방략 (translation scheme) 형태인것이다. 의미동작은 Lex(Flex) 입력파일에서의동작과마찬가지로역시 C 언어로된문장들이다. - 5 -
2. 예제들을통한 Lex(Flex) 설명 (1) 첫번째예제 : 파일의줄번호붙이기 버전 1 %{ /* * line numbering 1 */ int lineno = 1 % \n { lineno++ ECHO ^.*$ printf("%d\t%s", lineno, yytext) 예제 1. 파일이름 ln1.l : 공백줄은건너뛰면서줄번호붙이기 먼저, 상기파일의경우 Lex 입력파일형식에서세번째부분이없고첫번째와두번째부분만있는상태이다. 세번째부분이없으므로, 두번째와세번째부분을구분하는두번째 은생략되어있다. 첫번째부분에서 %{ 와 % 에둘러싸인부분을볼수있는데, 이부분은 Lex(Flex) 에의해별다른처리가되지않고내용그대로 (in verbatim) 가결과파일인 lex.yy.c ( 이이름은 Flex의경우 -o 옵션과함께사용자가원하는대로지정하여바꿀수있다 ) 에포함된다 (being dumped). 결과적으로 lineno 란전역 (global) 변수를어휘분석기프로그램에서사용할수있게된다. 이변수는입력파일의줄번호를세는역할을하게된다. 두번째부분에는두개의패턴이규정되어있다. 첫째는 \n 인데, 글자그대로줄바꿈 (new line) 문자만이이패턴에부합한다. 그리고그패턴이입력에서인식되면해야될동작으로는 lineno 변수를 1 증가시키고 ECHO 란이름의매크로 (macro)( 이매크로는 Lex(Flex) 에의해정의되어있는데, 역할은지금패턴에부합한다고인식된토큰을출력하는것이다. 지금경우는그인식된토큰은 \n 이다. 따라서출력에서줄이바뀔것이다 ) 를호출하는것이다. 둘째는 ^.*$ 인데, 여러가지 Lex(Flex) 내의메타-문자 (meta-character) 가사용되고있다. 제일앞의 ^ 은입력파일의한줄에서제일앞을의미한다 ( 그렇지만제일앞에있는특정기호를의미하는것은아니다 ). 마지막에있는 $ 은반대로한줄의제일끝을의미한다 ( 역시제일끝에있는특정기호를의미하는것은아니다 ). 이들중간에있는.* 에서. 은 Lex(Flex) 에서줄바꿈문자를제외한임의의문자를의미한다. 그리고 * 은표준적인정규표현에서의의미그대로, 그앞에있는패턴에부합하는스트링 ( 기호는길이가 1인스트링이므로당연히포함 ) 이아예없든지아니면임의횟수반복될수있음을의미한다 (reflexive transitive closure). 결국이것들을종합하면, 둘째패턴은입력파일에서임의의한줄에서마지막에있는줄바꿈문자를제외한나머지줄전체와부합한다. 그리고그패턴이입력에서인식되면줄번호를담고있는 lineno 변수의값을출력하고이어서 yytext 를출력하는데, yytext - 6 -
는 Lex(Flex) 에서토큰을인식하는과정에서그것을임시로저장하는버퍼 (buffer) 로서문자배열 (character array) 이다. 결과적으로패턴에부합된다고인식된토큰을출력하는셈이다. ( 첫째패턴에서본 ECHO 와 printf("%s", yytext) 는동일한결과를만든다. 인식된토큰을출력하는이런일이워낙빈번하게사용되므로, Lex(Flex) 에서그것을위한축약형으로 ECHO 매크로를정의하여제공하는것이다.) 이제상기 Lex(Flex) 입력파일을사용해보도록하자. 다음 C:\Users\JohnDoe> flex ln1.l C:\Users\JohnDoe> gcc -o ln1 lex.yy.c -lfl 과같은순서로실행시킨다 ( 사용한플랫폼은 32비트 Windows 7이고, C:\Users\JohnDoe> 는명령프롬프트 (command prompt) 이다 ). Flex 프로그램을파일 ln1.l 을입력으로하여실행시킨다. 그결과로현재디렉토리 (directory) 에 lex.yy.c 파일이생긴다. 이 C 프로그램파일을컴파일한다. 이때주의할점은 Flex 라이브러리를컴파일할때링크시켜야 ( -lfl ) 무사히컴파일되어실행파일이만들어진다. 이렇게만들어진실행파일에아래 day := (1461*y) div 4 + (153*m+2) div 5 + d if a then c := 1 while (c) do c := c - 1 와같은입력파일 ( 파일이름 data.p. Pascal 프로그래밍언어의구문으로된간단한몇문장을포함 하고있다 ) 을다음 C:\Users\JohnDoe> ln1 < data.p 과같이실행시키면아래 1 day := (1461*y) div 4 + (153*m+2) div 5 + d 3 if a then c := 1 5 while (c) 6 do c := c - 1 와같은결과가나온다. 결과에서보듯이 \n 문자만으로이루어진빈줄에대해서는줄번호가없이 빈줄만출력된다. - 7 -
(2) 두번째예제 : 파일의줄번호붙이기 버전 2 Lex(Flex) 입력파일은다음 %{ /* * line numbering 2 */ int lineno = 0 % ^.*\n printf("%d\t%s", ++lineno, yytext) 예제 2. 파일이름 ln2.l : 공백줄을포함하여모든줄에줄번호붙이기 과같다. 예제 1과마찬가지로, Lex(Flex) 입력파일형식에서세번째부분은없는상태이다. 예제 1에서설명한내용만으로도예제 2를이해하는데는어려움이없을것이다. 예제 1에서처럼 Flex를실행시킨뒤만들어진 lex.yy.c 파일을컴파일하여만든실행파일에 data.p 파일을입력으로줘서실행시키면아래 1 day := (1461*y) div 4 + (153*m+2) div 5 + d 2 3 if a then c := 1 4 5 while (c) 6 do c := c - 1 와같은결과가나온다. 보다시피모든줄에줄번호가붙여져있다. - 8 -
(3) 세번째예제 : 파일의줄수, 단어수, 글자수세기 Lex(Flex) 입력파일은다음 %{ /* * word count */ int nchar, nword, nline % \n ++nchar, ++nline [^ \t\n]+ ++nword, nchar += yyleng. ++nchar int main(void) { yylex() printf("%d\t%d\t%d\n", nchar, nword, nline) return 0 예제 3. 파일이름 wc.l : 입력파일의줄수, 단어수, 글자수세기 과같다. 상기파일의경우 Lex(Flex) 입력파일형식의세부분을모두갖추고있음에유의하자. 먼저첫번째부분을보면, 각각글자수, 단어수, 줄수를저장하기위한세변수 nchar, nword, nline 이선언되어있다. 이선언은주석문과함께 %{, % 사이에위치하므로변경없이고스란히 Lex(Flex) 의결과파일인 lex.yy.c 에전역변수로포함된다. 두번째부분을보면세개의패턴과그에대한동작이규정되어있다. 첫째는 \n 으로서입력파일에포함되어있는줄바꿈문자만이부합한다. 따라서글자수와줄수가 1씩증가한다. 둘째는 [^ \t\n]+ 인데몇가지 Lex(Flex) 의메타-문자들이사용되고있다. 대괄호 ( [ 와 ] ) 는문자클래스 (character class) 를나타낸다. 예컨대패턴 [ab] 는스트링 a 나 b 가부합하고, 패턴 [ \t\n] 은스트링 ( 공백문자로이루어진스트링 ) 이나 \t 이나 \n 이부합한다. Lex(Flex) 에서 ^ 문자는줄의제일앞을나타내기도하나, 대괄호안에서사용되면 후속문자들을제외한다른문자들 이라는의미를가진다. 따라서패턴 [^ \t\n] 은공백문자와탭 (tab) 문자그리고줄바꿈문자를제외한다른임의의문자들이부합한다. 마지막으로 + 는거의표준적인정규표현으로서그앞에있는패턴에부합하는스트링이한번이상임의횟수반복될수있음을의미한다 (positive closure). 결국종합하면둘째패 - 9 -
턴은임의문자들로이루어진임의길이스트링 ( 중간에공백문자나탭문자나줄바꿈문자로끊어지지않은 ) 에부합한다. 곧 단어 라고볼수있다. 그러므로단어수를 1 증가시키고글자수는단어의길이만큼증가시켜야한다. 즉지금이패턴에부합된실제스트링의길이만큼 nchar 변수를증가시켜야하는것이다. Lex(Flex) 에서는명시된패턴에부합되어인식한입력스트링의길이를담고있는변수를미리제공하고있는데바로 yyleng 이다. 셋째는. 인데앞에서설명했듯이줄바꿈문자를제외한임의문자가부합하는패턴이다. 첫째패턴과둘째패턴에서부합되지않는입력은이제 와 \t 이다. 따라서글자수만 1 증가시켜주면된다. 세번째부분을보면 main 함수가정의되어있다. 우리가 Lex(Flex) 로부터만들어진 lex.yy.c 파일을열어보면어휘분석을담당하는함수로 yylex 가만들어져있다. C 프로그램실행에필수인 main 함수역시정의되어있는데, 이기본 (default) main 함수가하는일은단순히 yylex 함수를호출하는것이전부다. 이 yylex 함수가실행되면서입력의글자수, 단어수, 줄수등을두번째부분에서지시된대로계산할터이나, 기본 main 함수는그결과를출력조차하지않는다. 따라서이출력기능을추가한 main 함수를사용자가새롭게정의해야한다. 세번째부분의 main 함수는그역할을하는것이다. 이렇게사용자가정의한 main 함수가제공되는경우자동적으로 Lex(Flex) 의기본 main 함수는가려진다. 예제 1과 2에서처럼 Lex(Flex) 를실행시킨뒤만들어진 lex.yy.c 파일을컴파일하여만든실행파일에 data.p 파일을입력으로줘서실행시키면아래 92 25 6 와같은결과가나온다. ( 실습플랫폼이 UNIX 계열이라면, 이것이제대로된결과인지를확인하기위해굳이 data.p 파일의글자수, 단어수, 줄수를셀필요는없다. UNIX 시스템의기본명령중에 wc 가있는데이것이바로입력의글자수, 단어수, 줄수를세는기능을가지고있다. 물론 Linux 시스템에서도기본적으로지원된다. 이명령에인자로 data.p 파일을주고실행시키면결과는다음 $ wc data.p 6 25 92 data.p 과같다. 보다시피글자수, 단어수, 줄수의순서만바뀌었을뿐동일한결과를보여주고있다.) - 10 -
3. 예제들을통한 Yacc(Bison) 설명 (1) 첫번째예제 : 중위 (infix) 수식을후위 (postfix) 수식으로변환 버전 1 Yacc(Bison) 입력파일은다음 %{ #include <stdio.h> #include <ctype.h> % %token DIGIT line : expr '\n' { putchar('\n') expr : expr '+' term { putchar('+') expr '-' term { putchar('-') term term : DIGIT { printf("%d", yylval) int yylex() { int c while (1) { c = getchar() if (c == ' ' c == '\t') else if (isdigit(c)) { yylval = c - '0' return DIGIT else return c int main() { if (yyparse() == 0) printf(" 파싱성공!\n\n") else printf(" 파싱실패!\n\n") 예제 4. 파일이름 in2po-rec1.y : 단자리숫자로이루어진중위수식을후위수식으로변환 - 11 -
과같다. 이파일에는세부분이모두있다. 하나씩살펴보자. 첫번째부분에서 %{ 와 % 에둘러싸인부분은 Lex(Flex) 에서와마찬가지로 Yacc(Bison) 이변경하지않고그대로결과파일인 y.tab.c ( 오리지널 Yacc의경우 ) 에포함시킨다. 결과적으로 Yacc(Bison) 이만든파서프로그램에서 C 언어의표준헤더파일인 <ctype.h> 를포함시키는효과를내고그결과다양한문자판별술어함수 (predicate) 를사용할수있게된다. 첫번째부분의나머지에는 Yacc(Bison) 의키워드 (keyword) %token 을사용한선언이하나있는데, 두번째부분에서사용되는 DIGIT 이란기호가단말 (terminal) 기호란표시이다. 기본적으로 Yacc(Bison) 은두번째부분에서사용되는모든식별자 (identifier) 를비단말 (nonterminal) 기호라고간주한다. 단말기호로 Yacc(Bison) 이인식하게하려면, 홑따옴표 (single quote) 에둘러싸인문자이거나 Yacc 입력파일첫번째부분에서 %token 을사용해단말기호라고선언해야한다. 두번째부분에는단자리숫자들이 + 와 로엮어진중위수식을표현하기위한문법이기술되어있고, 거기에그중위수식을후위수식으로변환하기위한의미동작이추가되어있다. 곧번역방략이나와있다는뜻이다. 이번역방략의내용은자명하기에 ( 교재에서학습하기도한내용이라 ) 설명은생략하고, 문법의마지막생성규칙에추가된의미동작에서사용되고있는변수 yylval 에대해서만언급한다. 이변수는 Yacc(Bison) 에서미리정의되어있는데, 어휘분석기에서인식한토큰을 Yacc(Bison) 에의해만들어진파서쪽으로반환할때추가로반환할속성 (attribute) 값이있는경우그것을저장하여전달하는데사용된다. 주로 Yacc(Bison) 과 Lex(Flex) 를연동하여사용할때 Lex(Flex) 에서만든어휘분석기가토큰을인식하면서원하는값을저장한뒤 Yacc(Bison) 에서만들어진파서쪽으로복귀하는식으로이용되는게일반적이다. 세번째부분에는 main 함수와어휘분석기함수 yylex 가포함되어있다. Yacc(Bison) 에서만들어진파서함수 ( 이름은 yyparse 로고정되어있다 ) 는파싱과정에서필요할때마다어휘분석기에게토큰을요구하는데, 어휘분석기함수의이름이 yylex 라고무조건생각한다. 따라서 Lex(Flex) 를이용하여어휘분석기를만드는경우에는만들어진어휘분석기함수이름이저절로 yylex 로고정되어있으므로신경쓸필요없으나, 이예제처럼수동으로어휘분석기를만드는경우에도어휘분석기함수이름은무조건 yylex 로붙여야한다. 여기서수동으로작성된어휘분석기함수 yylex 의내용을보면, 공백문자와탭문자는그냥지나가고숫자는단자리로끊어서 DIGIT 이란토큰으로인식한다. 이 DIGIT 토큰의토큰값은자동으로 Yacc(Bison) 에의해정의되므로사용자는그냥 DIGIT 을반환하면 Yacc(Bison) 에서만들어진구문분석기가알아본다. 단자리숫자로이루어진 DIGIT 토큰의경우, 그단자리숫자의실제정수값을구해서토큰의추가속성값을저장하는변수 yylval 에넣은뒤아울러파서쪽으로복귀한다. 그외 + 나 - 나 \n 과같은한글자토큰은각문자의코드 ( 예컨대 ASCII) 값을토큰값으로반환하게된다. main 함수는파서함수인 yyparse 를호출하는것이주된임무이다. 호출된 yyparse 함수는필요할때마다 yylex 함수를불러토큰을받아파싱을진행한다. 입력에대해성공적으로파싱이완료되면 yyparse 함수는 0을반환한다. 이제상기 Yacc(Bison) 입력파일을사용해보자. 다음 C:\Users\JohnDoe> bison -y in2po-rec1.y C:\Users\JohnDoe> gcc -o in2po-rec1 y.tab.c -ly - 12 -
과같은순서로실행시킨다. Bison 프로그램을파일 in2po-rec1.y 를입력으로하여실행시킨다. 옵션 -y 는 Bison을오리지널 Yacc과같은모드 (mode) 로실행하라는뜻이다. 그결과로현재디렉토리에 y.tab.c 파일이생긴다. 이 C 프로그램파일을컴파일한다. 이때주의할점은 Yacc(Bison) 라이브러리를컴파일할때링크시켜야 ( -ly ) 무사히컴파일되어실행파일이만들어진다. 이렇게만들어진실행파일을다음 C:\Users\JohnDoe> in2po-rec1 9-5+2 95-2+ 파싱성공! 과같이사용한다. 보다시피단자리숫자를피연산자로하는중위수식을동일한의미의후위수식으로 변환한다 ( 출력할때피연산자들사이에공백을주지않아서붙어나오는바람에보기는다소불편하다 ). - 13 -
(2) 두번째예제 : 중위수식을후위수식으로변환 버전 2 첫번째예제에서한것과동일한일을 Lex(Flex) 와 Bison 을함께사용하여하고자한다. 먼저 Bison 입력파일은다음 %{ #include <stdio.h> #include <ctype.h> % %token DIGIT line : expr '\n' { putchar('\n') expr : expr '+' term { putchar('+') expr '-' term { putchar('-') term term : DIGIT { printf("%d", yylval) int main() { if (yyparse() == 0) printf(" 파싱성공!\n\n") else printf(" 파싱실패!\n\n") 예제 5. 파일이름 in2po-rec2.y : 단자리숫자로이루어진중위수식을후위수식으로변환 과같다. 보다시피동일한일을하는첫번째예제에서의 Yacc(Bison) 입력파일과거의동일하다. 다만 이제어휘분석기는 Lex(Flex) 에의해만들어질것이므로, 직접작성했던어휘분석기함수 yylex 부 분이삭제되었다. - 14 -
Lex(Flex) 입력파일은다음 %{ #include "in2po-rec2.tab.h" % [ \t]+ [0-9] { yylval = yytext[0] - '0' return DIGIT [+\-\n] return yytext[0] 예제 6. 파일이름 in2po-rec2.l : 단자리숫자로이루어진중위수식을후위수식으로변환 과같다. 세부분들중세번째부분은없는구조이다. 첫번째부분을보면 Lex(Flex) 의결과파일인 lex.yy.c 에그대로포함되는부분이있는데 in2po-rec2.tab.h 라는이름의헤더파일을포함시키는문장이다. 이파일은 Bison에의해만들어지는데 ( 뒤에서추가설명한다 ), Bison에의해정의된토큰의값이나타입을포함하고있다. 예를들면 Bison 입력파일에서비단말기호가아니라단말기호, 즉토큰으로선언된 DIGIT 의토큰값은 Bison 이자동으로배당하는데, 그정의가이파일에포함되어있는것이다. 이파일에서그정의가나오는근처부분을보면아래 /* Tokens. */ #ifndef YYTOKENTYPE # define YYTOKENTYPE /* Put the tokens into the symbol table, so that GDB and other debuggers know about them. */ enum yytokentype { DIGIT = 258 #endif 와같다. 보다시피 258 의값을가지는기호상수로정의되어있다. 이헤더파일을 Lex(Flex) 의결과파 일인 lex.yy.c 가포함시켜야 Lex(Flex) 입력파일의두번째부분에있는동작에서 DIGIT 을토큰 값으로사용할수있는것이다. 음 참고로 Bison 이아닌 Yacc 을동일입력파일에대해실행시켜만들어지는 y.tab.h 파일을보면다 #ifndef _yacc_defines_h_ #define _yacc_defines_h_ #define DIGIT 257 #define YYERRCODE 256 #endif - 15 -
과같다. Bison에비하면상당히간략하지만, 역시토큰 DIGIT 은 257의값을가지는기호상수로정의되어있다. 두번째부분은대부분이미설명된내용만으로이해에어려움이없겠지만, 셋째패턴에새롭게나타난 Lex(Flex) 의메타-문자가있다. \ 가그것인데, 이것은그바로뒤에나오는문자가 Lex(Flex) 의메타- 문자이면그의미를상실하고문자자체를나타내도록하는효과가있다. 즉, 일반적인 UNIX/C 커뮤니티의관례인이스케이프 (escape) 문자로서의백슬래쉬 (backslash) 의미그대로사용된다. 그러면왜 앞에백슬래쉬를썼는가하는점에설명이필요한데, 가문자클래스를나타내는대괄호사이에있으면문자들의범위 (range) 를뜻하는메타-문자로기능하기때문이다. 예컨대 [abcde] 와 [a e] 는동일한패턴을나타내는것이다. 이제이두 Lex(Flex) 입력파일과 Bison 입력파일을사용해보도록하자. 다음 C:\Users\JohnDoe> flex in2po-rec2.l C:\Users\JohnDoe> bison -d in2po-rec2.y C:\Users\JohnDoe> gcc -o in2po-rec2 lex.yy.c in2po-rec2.tab.c -lfl -ly 과같은순서로명령을실행하여실행파일을만든다. Lex(Flex) 를실행함으로써어휘분석기 yylex 를포함하고있는 lex.yy.c 파일이만들어진다. Yacc과 Bison은거의비슷하나, 만들어지는파일이름이차이가난다. Yacc은실행결과 y.tab.c 를만드나, Bison은실행결과파일이름이 Bison 입력파일의확장자앞부분 에확장자로 'tab.c 를붙여서만든것이된다. 예를들어 Bison 입력파일이름이이예제에서처럼 in2po-rec2.y 라고하면결과파일이름은 in2po-rec2.tab.c 가되는식이다. 또앞서말한 Yacc(Bison) 의정의를포함하고있는헤더파일은기본적으로만들어지는것이아니라, Yacc(Bison) 을실행시킬때 d 옵션 (option) 을줘야한다. 이옵션을가지고실행되면 y.tab.c (Yacc의경우 ) 나 in2po-rec2.tab.c (Bison의경우 ) 뿐만아니라, y.tab.h (Yacc의경우 ) 나 in2po-rec2.tab.h (Bison의경우 ) 도함께만들어낸다. 이헤더파일은우리 Lex(Flex) 입력파일에서규정된것처럼 lex.yy.c 에포함될것이다. 이렇게만들어진실행파일을다음 C:\Users\JohnDoe> in2po-rec2 9-5+2 95-2+ 파싱성공! 과같이사용한다. 보다시피단자리숫자를피연산자로하는중위수식을동일한의미의후위수식으로 변환한다. - 16 -
(3) 세번째예제 : 간단한단자리수계산기 단자리숫자들을피연산자로하고더하기와빼기만연산자로허용되는중위수식을받아들여그식의 결과값을계산하는계산기프로그램을 Yacc(Bison) 을이용해만들고자한다. Yacc(Bison) 입력파일은 다음 %{ #include <stdio.h> #include <ctype.h> % %token DIGIT line : expr '\n' { printf("%d\n", $1) expr : expr '+' term { $$ = $1 + $3 expr '-' term { $$ = $1 - $3 term term : DIGIT { $$ = $1 int yylex() { int c while (1) { c = getchar() if (c == ' ' c == '\t') else if (isdigit(c)) { yylval = c - '0' return DIGIT else return c int main() { if (yyparse() == 0) printf(" 파싱성공!\n\n") else printf(" 파싱실패!\n\n") 예제 7. 파일이름 calc1.y : 단자리숫자로이루어진중위수식의값을계산 - 17 -
과같다. 일단큰뼈대는예제 4 표에있는 Yacc(Bison) 입력파일과동일하다. 단지두번째부분에포함된의미동작들이다를뿐이다. 여기에서 $$ 또는 $1 이나 $2 등과같은표현이사용되고있는데이것은생성규칙에나타나는문법기호에첨부된속성값을나타낸다. $$ 는생성규칙의좌변에있는비단말기호에부착된속성값, $i (i = 1, 2, ) 는생성규칙의우변에있는 i-번째문법기호에부착된속성값을나타내는방식이다. 이표현을이용하면파싱이진행되면서문법기호들의속성값을사용한다양한응용이가능하다. Yacc(Bison) 은상향식 (bottom-up) 파싱알고리즘인 LALR(Lookahead LR) 기법을사용한다. 그러므로제일처음어휘분석단계에서인식된토큰에대해 yylval 변수를통해초기속성값을부여한다. 파스트리의잎노드 (leaf node) 에부착된속성값은이 $-표현을이용해서파스트리의중간노드 (interior node) 나루트노드 (root node) 까지전달될수있다. 이것만이해하면상기 Yacc(Bison) 입력파일을이해하는데는문제가없을것이다. 이제상기 Yacc(Bison) 입력파일을사용해보자. 다음 C:\Users\JohnDoe> bison -y calc1.y C:\Users\JohnDoe> gcc -o calc1 y.tab.c -ly 과같은순서로실행시켜실행파일을만든다. 이렇게만들어진실행파일을다음 C:\Users\JohnDoe>./calc1 9-5+2 6 파싱성공! 과같이사용한다. 이계산기에더하기와빼기이외에곱하기와나누기를연산기능에추가하거나, 연산의우선순위를바꿀수있는괄호를추가하는일은매우간단하다. 곱하기와나누기, 괄호를문법에반영하여번역방략을기계적으로확장하기만하면되기때문이다. Yacc(Bison) 입력파일은다음 - 18 -
%{ #include <stdio.h> #include <ctype.h> % %token DIGIT line : expr '\n' { printf("%d\n", $1) expr : expr '+' term { $$ = $1 + $3 expr '-' term { $$ = $1 - $3 term term : term '*' factor { $$ = $1 * $3 term '/' factor { $$ = $1 / $3 factor factor : '(' expr ')' { $$ = $2 DIGIT { $$ = $1 int yylex() { int c while (1) { c = getchar() if (c == ' ' c == '\t') else if (isdigit(c)) { yylval = c - '0' return DIGIT else return c int main() { if (yyparse() == 0) printf(" 파싱성공!\n\n") else printf(" 파싱실패!\n\n") 예제 8. 파일이름 calc2.y : 단자리숫자로이루어진중위수식의값을계산 ( 연산자추가 ) 과같다. 이제상기 Yacc(Bison) 입력파일을사용해보자. 다음 - 19 -
C:\Users\JohnDoe> bison -y calc2.y C:\Users\JohnDoe> gcc -o calc2 y.tab.c -ly 과같은순서로실행시켜실행파일을만든다. 이렇게만들어진실행파일을다음 C:\Users\JohnDoe>./calc2 (9 5) * 2 8 파싱성공! 과같이사용한다. 추가로, 한자리수가아닌여러자리로된수를피연산자로허용하도록기능을확장하는일도간단 하다. 상기 Yacc(Bison) 입력파일에서어휘분석을담당하고있는 yylex 함수만다음 int yylex() { int c while (1) { c = getchar() if (c == ' ' c == '\t') else if (isdigit(c)) { yylval = c - '0' c = getchar() while (isdigit(c)) { yylval = yylval * 10 + c - '0' c = getchar() ungetc(c, stdin) return DIGIT else return c 과같이변경하면된다. 그리고프로그램의실행에는아무차이가없으나, 이제는피연산자가한자리수가아니라여러자리수이므로피연산자를나타내는토큰의이름을 DIGIT으로부터 NUMBER로바꾸면보기에한결나을것이다. 여기에서한걸음더나아가, 우리가이미 Lex(Flex) 의사용법을알고있는이상굳이수동으로어휘분석기를만들필요가없다는생각이든다. 즉, 상기 Yacc(Bison) 입력의세번째부분에있는 yylex 함수를삭제하고동일한일을하는 Lex(Flex) 입력파일을만들수있겠다는것이다. Lex(Flex) 입력파일은다음 - 20 -
%{ #include <stdlib.h> #include "calc3.tab.h" % [ \t]+ [0-9]+ { yylval = atoi(yytext) return NUMBER [+\-\*\/\(\)\n] return yytext[0] 예제 9. 파일이름 calc3.l : 여러자리숫자로이루어진중위수식의값을계산 과같고 Yacc(Bison) 입력파일은다음 %{ #include <stdio.h> #include <ctype.h> % %token NUMBER line : expr '\n' { printf("%d\n", $1) expr : expr '+' term { $$ = $1 + $3 expr '-' term { $$ = $1 - $3 term term : term '*' factor { $$ = $1 * $3 term '/' factor { $$ = $1 / $3 factor factor : '(' expr ')' { $$ = $2 NUMBER { $$ = $1 int main() { if (yyparse() == 0) printf(" 파싱성공!\n\n") else printf(" 파싱실패!\n\n") 예제 10. 파일이름 calc3.y : 여러자리숫자로이루어진중위수식의값을계산 - 21 -
과같다. 이제이두 Lex(Flex) 입력파일과 Yacc(Bison) 입력파일을사용해보도록하자. 다음 C:\Users\JohnDoe> flex calc3.l C:\Users\JohnDoe> bison -d calc3.y C:\Users\JohnDoe> gcc -o calc3 lex.yy.c calc3.tab.c -lfl -ly 과같은순서로명령을실행하여실행파일을만든다. 이렇게만들어진실행파일을다음 C:\Users\JohnDoe> calc3 (53 13) * 12 + 20 500 파싱성공! 과같이사용한다. - 22 -
(4) 네번째예제 : 가상스택기계를위한어셈블리 (assembly) 코드로컴파일하기 컴파일러과목의표준적교재중하나인 Compilers: Principles, Techniques, and Tools (by Aho, Sethi, and Ullman) 의 2.8절에는가상스택기계 (Abstract Stack Machine) 라고부르는페이퍼머신 (paper machine) 이간략하게정의되어있다. 이제 Lex(Flex) 와 Yacc(Bison) 을이용해 Pascal 언어의간단한문장들을이가상스택기계의어셈블리코드로번역하는일을해보자. 이문장들을포함하고있는파일 ( 좀과장하자면 Pascal 프로그램파일 ) 이앞에서몇번사용된 data.p 이다. 아래에다시보였다. day := (1461*y) div 4 + (153*m+2) div 5 + d if a then c := 1 while (c) do c := c - 1-23 -
Lex(Flex) 입력파일은다음 %{ /* * 추상스택기계의목적코드생성예제 */ #include <string.h> #include "y.tab.h" % delim [ \t\n] ws {delim+ letter [A-Za-z] digit [0-9] id {letter({letter {digit)* number {digit+(\.{digit+)?(e[+\-]?{digit+)? {ws ":=" return(assign) div return(div) mod return(mod) if return(if) then return(then) while return(while) do return(do) {id { strcpy(yylval.lexeme, yytext) return(id) {number { strcpy(yylval.lexeme, yytext) return(num). return(yytext[0]) 예제 11. 파일이름 stack-m.l : 추상스택기계를위한 Pascal 컴파일러 Lex(Flex) 입력 과같다. 상기 Lex(Flex) 입력파일에대해서몇가지설명이필요할듯하다. 첫번째부분을보면여러가지이름 ( delim, ws 등 ) 을정의하는것이있는데, 보통정규정의 (regular definition) 이라고부른다. 이것은두번째부분에서패턴을기술할때사용함으로써패턴기술을알아보기쉽게만들기위한부분식 (subexpression) 정의라고볼수있다. 또새롭게나타난 Lex(Flex) 메타-문자가하나있는데,? 이다. 이문자도거의표준적정규표현에가까운데,? 앞의패턴에해당하는스트링이있을수도있고없을수도있다 (being optional) 는것을나타낸다. 상기파일에서는상수 (number) 패턴을기술하는데분수부분이나지수부분이있을수도있고없을수도있다는점을나타낸것이다. 토큰의추가속성값을전달하기위한변수 yylval 의기본타입은 int 이다. 만약다른타입의값을전달하고싶다면 Yacc(Bison) 의입력파일에서 %union 키워드를이용한다. 뒤의이예제를위한 Yacc(Bison) 입력파일에서보게되겠지만, 현재예제에서토큰의추가속성값타입은 10개의원소를 - 24 -
가진문자배열로선언되어있고그값에접근하기위한공용체 (union) 필드 (field) 이름은 lexeme 으로정의되어있다. 따라서상기 Lex(Flex) 입력파일을보면식별자나상수와같은토큰이입력에서인식되면, 그것이입력에서나타난실제스트링 (lexeme) 을 yylval.lexeme 에복사되어파서쪽으로전달하도록되어있다. 이예제를위한 Yacc(Bison) 입력파일은다음 %{ /* * 추상스택기계의목적코드생성예제 */ #include <stdio.h> #include <string.h> char *tmp_lbl1, *tmp_lbl2 % %union { char lexeme[10] %start list %token ID NUM DIV MOD ASSIGN IF THEN WHILE DO list : list '' stmt stmt stmt : ID ASSIGN { printf("\tlvalue\t%s\n", $1) expr { printf("\t:=\n") IF expr { tmp_lbl1 = new_lbl_no() printf("\tgofalse\t%s\n", tmp_lbl1) THEN stmt { printf("label\t%s\n", tmp_lbl1) WHILE { tmp_lbl1 = new_lbl_no() printf("label\t%s\n", tmp_lbl1) expr { tmp_lbl2 = new_lbl_no() printf("\tgofalse\t%s\n", tmp_lbl2) DO stmt { printf("\tgoto\t%s\n", tmp_lbl1) - 25 -
printf("label\t%s\n", tmp_lbl2) expr : expr '+' term { printf("\t+\n") expr '-' term { printf("\t-\n") term term : term '*' factor { printf("\t*\n") term '/' factor { printf("\t/\n") term DIV factor { printf("\tdiv\n") term MOD factor { printf("\tmod\n") factor factor : '(' expr ')' ID { printf("\trvalue\t%s\n", $1) NUM { printf("\tpush\t%s\n", $1) char* new_lbl_no(void) { static int lbl_no = 0 char buf[4] int i, quot char *lbl_header lbl_header = (char *)malloc(5) strcpy(lbl_header, "lbl_") buf[3] = '\0' quot = lbl_no++ for (i = 2 - (quot / 10) i >= 0 i--) { buf[i] = '0' + quot % 10 quot = quot / 10 return((char *)strcat(lbl_header, buf)) int main(void) { printf("\ncompilation for Abstract Stack Machine Started...\n\n") printf("\nassembly code for Abstract Stack Machine follows...\n\n") if (yyparse() == 0) printf("\n\ncompilation for Abstract Stack Machine Completed!\n") else printf("\n\ncompilation for Abstract Stack Machine Failed!\n") 예제 12. 파일이름 stack-m.y : 추상스택기계를위한 Pascal 컴파일러 Yacc(Bison) 입력 - 26 -
과같다. 상기파일의첫번째부분에나오는 %start 키워드는그다음에오는식별자가두번째부분에기술되어있는문법의시작기호 (start symbol) 라는점을선언하는것이다. 만약이게없으면문법의첫번째생성규칙의좌변에있는비단말기호를시작기호로 Yacc(Bison) 은생각한다. 세번째부분에정의되어있는 new_lbl_no 함수는과거만든레이블 (label) 과는다른새로운레이블을만들어서돌려주는함수이다. 상기 Lex(Flex) 입력파일과 Yacc(Bison) 입력파일을이용하여실행파일은다음 C:\Users\JohnDoe> flex stack-m.l C:\Users\JohnDoe> bison -yd stack-m.y C:\Users\JohnDoe> gcc -o stack-m lex.yy.c y.tab.c -lfl -ly 과같이만든다. 이렇게만들어진실행파일에입력으로앞에나온 data.p 파일을주고실행하여그 결과를 data.asm 이라는파일 ('asm' 이라는확장자는 assembly code 를나타내는뜻에서붙였다 ) 에다 음 C:\Users\JohnDoe> stack-m < data.p > data.asm 과같이저장한다. 이결과 ( data.p 파일에들어있는 Pascal 프로그램을추상스택기계의어셈블리코 드로번역한결과 ) 파일 data.asm 의내용은다음 - 27 -
Compilation for Abstract Stack Machine Started... Assembly code for Abstract Stack Machine follows... label label label lvalue day push 1461 rvalue y * push 4 div push 153 rvalue m * push 2 + push 5 div + rvalue d + := rvalue a gofalse lbl_000 lvalue c push 1 := lbl_000 lbl_001 rvalue c gofalse lbl_002 lvalue c rvalue c push 1 - := goto lbl_001 lbl_002 Compilation for Abstract Stack Machine Completed! 과같다. - 28 -
4. 맺는말 이상으로몇가지예제를이용하여컴파일러구성을보조하는대표적소프트웨어도구인 Lex(Flex) 와 Yacc(Bison) 의작동을살펴보았다. 넓게보면모든프로그램은정해진형식의입력을처리하여역시정해진형식의출력을내보낸다는측면에서일종의컴파일러이다. 이말은곧컴파일러구성에사용되는여러기법이다른분야의프로그램작성에도폭넓게적용될수있음을의미한다. 마찬가지로 Lex(Flex) 와 Yacc(Bison) 의응용범위도매우광범위하게미칠수있다. - 29 -