Chapter 13 렉스와야크
01 렉스와야크 02 렉스와야크의입력파일형식 03 플렉스와바이슨설치방법 04 플렉스사용법 05 바이슨사용법
렉스와야크의개념에대해이해할수있다. 렉스의입력파일형식과야크의입력파일형식에대해이해할수있다. 플렉스와바이슨의설치방법에대해이해할수있다. 플렉스사용법에대해이해할수있다. 바이슨사용법에대해이해할수있다.
13.1 렉스와야크 프로그래밍언어와컴퓨터구조가다양해짐에따라 n 개의언어를 m 개의기계에구현하려면 n m 개의컴파일러가필요 그런데하나의컴파일러를만들때에도많은시간과노력이들기때문에컴파일러를만드는데도움을주는시스템이필요. 이러한시스템을컴파일러자동화도구라하고컴파일러 - 컴파일러 (compiler-compiler) 또는컴파일러생성기 (compiler generator) 라일컫는다. 어떤입력을주면출력으로컴파일러를자동으로생성해주는컴파일러 - 컴파일러 : PQCC(Production-Quality Compiler Compiler) 팀과 ACK(Amsterdam Compiler Kit) 팀에의해만들려고시도했으나만족할만한결과를얻지는못함. 반면에어휘분석, 구문분석, 코드생성등컴파일러의한단계 (phase) 를자동으로생성해주는번역기제작시스템 (translator writing system) 은실제로제작되었다. 이가운데가장성공적인도구는유닉스 (UNIX) 시스템에서사용되는렉스 (Lex) 와야크 (YACC, Yet Another Compiler Compiler) 이다. 4
13.1 렉스와야크 렉스 : 렉스는어휘분석기를자동으로생성해주는어휘분석기생성기 (scanner generator) 1975 년벨연구소의레스크 (Richard Mike Lesk) 와슈미트 (Eric Emerson Schmidt) 가개발 렉스는사용자가정의한토큰에대한표현인정규표현과수행코드를입력받아일반범용언어인 C 로작성된어휘분석기를출력 어휘분석기는입력프로그램에서정규표현에해당하는토큰을찾았을때, 거기에결합된수행코드를수행하여토큰을구분해내는일을한다. 5
13.1 렉스와야크 현재사용하고있는 C 언어에서식별자를구분하기위한어휘분석기를만들고싶다 가장먼저해야할일은렉스의입력을만드는것 - 입력형태는 2 절에서자세히설명 식별자에대해서첫자는영문소문자 대문자또는밑줄문자로시작하고, 둘째자부터영문소문자 대문자, 숫자및밑줄문자가온다. 식별자의길이에제한이없다고하면다음과같이간단하게렉스의입력을작성할수있다. Letter [a-za-z_] Digit [0-9] Ident {Letter}({Letter} {Digit})* 이문법을렉스의서술형태에맞게작성하고확장자는 ~.l 로저장 그다음렉스를불러서실행하면출력이생성되는데 lex.yy.c 가어휘분석기 이어휘분석기는 C 언어로작성된프로그램이므로, 실행하기위해컴파일을하고실행하면서테스트프로그램을주면어휘분석기가테스트프로그램에서식별자를구분해낼것이다. 6
13.1 렉스와야크 야크 : 야크는구문분석기를자동으로생성해주는구문분석기생성기 (parser generator) 1975 년벨연구소의존슨 (Steve Johnson) 이주축이되어개발한 LALR(1) 구문분석기생성기로, 문법규칙에대한수행코드를 C 언어로기술하도록만들어졌다. [ 그림 13-2] 에야크의역할을나타냈다. 7
13.1 렉스와야크 야크를사용하려면야크에대한입력을작성해야한다. 문법을야크의형태에맞게서술하고, 확장자는 ~.y 로저장 그런다음야크를불러실행하면출력이생성된다. 출력중에 y.tab.c 가구문분석기인데, 구문분석기는파싱표와수행코드로구성되고 C 언어로작성되어있다. 따라서컴파일하고테스트프로그램을입력으로주면문법에맞는문장인지아닌지를알려줄것이다. 이구문분석기는 LR 파서이다. 8
13.2 렉스와야크의입력파일형식 렉스의입력파일형식 렉스는 [ 그림 13-1] 과같이렉스의입력을먼저작성하며입력프로그램은파일확장자가 ~.l 이어야한다. 렉스의입력은다음과같이정의부분 (definition part), 변환규칙부분 (translation rules part), 사용자부프로그램부분 (user subprogram part) 으로구성된다. 각부분은 %% 로구분된다. 정의부분과사용자부프로그램부분은생략할수있지만변환규칙부분은생략이불가능하다. 9
13.2 렉스와야크의입력파일형식 정의부분은이름과일련의표현식으로구성되는데, 이름이식별자이고표현식은이름에해당하는정규표현이다. 변환규칙부분은표현식과일련의수행코드로구성된다. 이때표현식은정규표현으로나타내고, 수행코드는표현식을나타낸정규표현과매칭되었을때수행될일련의코드로서 C 언어로작성된다. 사용자부프로그램부분에서는토큰에대한기호표처리루틴 (symbol table handling routine) 등과같이변환규칙부분에서사용되는부프로그램이사용자에의해작성된다. 정의부분은자료구조나변수및상수에대한정의를포함하며, 내용을 %{ 와 %} 사이에기술하면렉스가생성하는 lex.yy.c 의앞부분에그대로삽입된다. 그러나 %{ %} 의외부에서코멘트를사용할때는반드시하나이상의화이트스페이스 (white space)( 스페이스, 탭, 줄바꿈문자 (new line) 등화면상에는나타나지않는문자 ) 로행이시작되어야한다. 10
13.2 렉스와야크의입력파일형식 정의부분은다음과같이구성된다. 11
13.2 렉스와야크의입력파일형식 변환규칙부분은정규표현과수행코드의쌍으로구성된다. 변환규칙부분의구성은다음과같다. 여기서 %% 는정의부분과변환규칙부분을구분하는구분자이다. 그리고규칙 n 은인식하고자하는토큰을나타내는정규표현이고, 수행 n 은토큰이인식되었을때어휘분석기가처리할수행코드이다. 12
13.2 렉스와야크의입력파일형식 [ 예제 13-1] 렉스의입력으로식별자를정의하고식별자가나타나면토큰값리턴하기 렉스의입력으로식별자를정의하고, 식별자가나타나면식별자에대한토큰값을리턴하는입력을작성해보자. 단, 식별자는 C 언어에대한식별자이다. [ 풀이 ] Letter [a-za-z_] Digit [0-9] %% {Letter}({Letter} {Digit})* return tident [ 예제 13-2] 변환규칙부분작성하기 입력문자열에서숫자를만나면 found integer number 를출력하는변환규칙부분을작성해보자. [ 풀이 ] [0-9]+ printf( found integer number\n ); 13
13.2 렉스와야크의입력파일형식 변환규칙부분에서토큰을표현하려면정규표현으로패턴을정의해야하는데, 정규표현에는 [ 표 13-1] 과같은메타기호를사용한다. 14
13.2 렉스와야크의입력파일형식 다음은메타기호를이용하여자주사용되는예이다. a * b : 문자열 a*b 를나타낸다. 문자열 a*b 는정규표현 a*b 와같다. a\*b : 문자열 a*b 를나타내는정규표현이다. [abc] : a, b, c 중의한문자를나타낸다. [a-z] : 문자 a 부터 z 중하나, 즉소문자를나타낸다. [0-9] : 숫자 0 부터 9 중하나, 즉범위를나타낸다. [^+] : + 를제외한모든문자, 즉여집합을나타낸다. [\t\n] : 공백, 탭, 줄바꿈문자중의하나를나타낸다. [a-za-z][a-za-z0-9]* : 첫자는영문자이고둘째자부터영문자나숫자로구성된문자열이다. a+ : 문자 a 가한번이상반복되는것을나타낸다. ab c : ab 혹은 c 를나타낸다. ^ab : 행의시작에문자열 ab 가나타나는경우에만토큰으로 ab 를처리한다. ab$ : 행의끝에문자열 ab 가나타나는경우에만토큰으로 ab 를처리한다. ab/cd : ab 다음에 cd 가이어서나타날때만 ab 가토큰으로처리된다. 15
13.2 렉스와야크의입력파일형식 렉스입력의마지막인사용자부프로그램부분은렉스에서사용될부프로그램을정의하는부분으로렉스에서어떤처리없이그대로렉스의출력인 lex.yy.c 에복사된다. 렉스에서는여러정보를제공하고복잡한기능을수행할수있도록하기위해다양한함수와전역변수를제공한다. 이러한함수와전역변수는 [ 표 13-2] 와같다. 16
13.2 렉스와야크의입력파일형식 토큰값이필요한경우에변수 yytext 의내용을사용하여해결할수있다. 예를들어매칭된문자열을출력할때다음과같이작성한다. [a-z]+ printf( %s, yytext); 이것은입력에서소문자로이뤄진단어를찾으면그단어를 yytext 에저장하고그내용을그대로출력하라는의미이다. 이와동일한기능을하는렉스의함수로 ECHO 가있는데, 다음과같이작성하면똑같은결과를얻을수있다, [a-z]+ ECHO; yytext[yyleng-1] 이라고하면매칭된문자열의마지막문자를출력한다. 렉스의출력인 lex.yy.c 에는스캐너역할을하는함수 yylex( ) 가포함되어있다. 이함수는렉스의입력에서명시한정규표현과일치하는토큰을찾을때까지한문자씩계속읽어들인다. 그리고토큰이매칭되면해당정규표현과결합된수행코드가실행되고, 함수 yylex( ) 의복귀값 return value 이바로토큰번호에해당된다. 또한 yylex( ) 를호출한함수가토큰값을요구할때는외부변수 yytext 의내용을복사하여필요로하는함수에전달한다. 함수 yylex( ) 는입력파일의끝에도달할때까지토큰을생성한다. 파일의끝에도달하면 yylex( ) 는함수 yywrap( ) 를호출한후 0 으로복귀한다. 그러므로모든토큰을처리한후실행할일이더있는경우 yywrap( ) 내에서처리하면된다. 17
13.2 렉스와야크의입력파일형식 야크의입력파일형식 야크의입력은문법규칙과각규칙에대한수행코드이며다음과같이선언부분 (declation part), 변환규칙부분 (translation rules part), 사용자프로그램부분 (user program part) 으로구성된다. 각부분은 %% 로구분되는데, % 기호는야크의표현에서에스케이프 (escape) 문자로사용된다. 선언부분은생략할수있으며, 만약사용자프로그램부분이생략되는경우두번째 %% 기호도생략가능하다. 선언부분에서는문법규칙의토큰에대해선언하고변환규칙부분과프로그램부분에서사용될임시변수에대해선언한다. 18
13.2 렉스와야크의입력파일형식 시작기호는다음과같이정의한다. %start %{ 와 %} 사이에내용을기술하며, 어휘분석기에서반환되는모든토큰에대한정의를 %token 으로정의한다. 관례적으로모든토큰의이름은대문자로하고토큰이외의다른이름은소문자로한다. 변환규칙부분에서는문법의규칙을정의한다. 변환규칙부분에대한표현은일련의문법규칙으로구성되고, 각규칙은왼쪽부분 (left hand side) 과몸체 (body) 의형태를취한다. 여기서왼쪽부분은논터미널의이름이고, 몸체는문법규칙의오른쪽부분에나오는기호로이름이나상수문자가될수있다. 야크의각규칙에대한수행코드는 C 언어로기술되며, 수행코드는각규칙이감축될때실행된다. 사용자프로그램부분은야크를보조하는 C 루틴으로서오류처리루틴등이첨가된다. 19
13.2 렉스와야크의입력파일형식 [ 예제 13-3] 규칙을야크로표현하기 BNF로표현된규칙을야크로표현해보자. <expr> ::= <expr> + <term> [ 풀이 ] 이를야크로표현하면다음과같다. expr : expr + term 사용자는각생성규칙및그생성규칙이파서에의해인식되었을때호출되는수행코드를작성해야한다. 생성규칙에해당하는수행코드를작성해보자. expr : expr + term { printf( addition expr detected \n );}; 야크에서는생성규칙에있는문법기호에대한값을정의할수있도록의사변수 (pseudo variable) 를제공한다. 변수 $1 과 $2 는각각오른쪽부분의첫번째기호와두번째기호의값을의미한다. 생성규칙의왼쪽부분에있는기호는의사변수 $$ 로치환문을통해다른문법규칙에값을전달한다. 다음은의사변수를사용하여수행코드를기술한예이다. expr : expr + term {$$ = $1 + $3} expr - term {$$ = $1 - $3} 20
13.2 렉스와야크의입력파일형식 5 장과 6 장에서모호한문법에대한해결방법을다루었는데, 6 장에서는모호한문법을사용하여파싱표에서충돌이발생했을때그충돌을우선순위와결합법칙을이용해서해결했다. 같은방법으로모호한문법에대해야크를통해파싱표를만든다고해도충돌이발생한다. 이를해결하기위해야크에서는우선순위를제공하는데가장낮은우선순위인터미널부터정의하며, 왼쪽결합법칙인경우에는 LEFT 로표기하고오른쪽결합법칙인경우에는 RIGHT 로표기한다. [ 예제 13-4] 야크의입력에서연산순서알아보기 다음과같은야크의입력을보고식 a = c * d - e + f / g 에대한연산순서를알아보자. %right = %left + - %left * / %% expr : expr = expr expr + expr expr - expr expr * expr expr / expr 21
13.2 렉스와야크의입력파일형식 [ 풀이 ] 식 a = c * d - e + f / g 에대한야크의입력을보면연산자우선순위는 = < +, - < *, / 의순이며, = 은오른쪽결합법칙을취하고 +, -, *, / 는왼쪽결합법칙을취한다. 그러므로괄호를이용하여표기하면다음과같다. (a = (((c * d) - e) + (f / g))) 22
13.3 플렉스와바이슨설치방법 렉스와야크는유닉스시스템의유틸리티로개발되었고, 유용성이확인되면서선의솔라리스나리눅스와같은유닉스계열의운영체제를비롯해마이크로소프트의윈도등다른운영체제에도이식되어사용되었다. 리눅스와같은운영체제의경우렉스와야크의 GNU(Gnu s Not Unix) 버전인플렉스 (Flex) 와바이슨 (Bison) 을사용할수있다. 윈도에서는 PCLex와 PCYacc도사용되지만현재사용하는방법중유닉스계열운영체제와가장유사하게사용할수있는것은역시플렉스와바이슨이다. 윈도상에서시그윈 (Cygwin) 시스템과같이유닉스계열운영체제와유사한환경을사용한다면처음설치할때플렉스와바이슨을선택하여사용하는것이좋다. 만약시그윈시스템과같이유닉스계열운영체제와유사한환경전체의설치가필요없는경우에는 GNU C 컴파일러 (gcc) 와플렉스, 바이슨만을윈도에설치하면된다. 다음과같은순서로윈도에 GNU C 컴파일러 (gcc) 와플렉스, 바이슨을설치한다. 단, GNU C 컴파일러, 플렉스, 바이슨의설치순서는바뀌어도무관하다. 23
13.3 플렉스와바이슨설치방법 1 GNU C 컴파일러를설치한다. GNU C 컴파일러를설치하는방법중하나는무료 C/C++ 프로그램용통합개발환경 (IDE) 인블러드셰드 (Bloodshed) 사의 Dev-C++ 를설치하는것이다 (http://www.bloodshed.net/devcpp.html 에서내려받는다 ). 원래 Dev-C++ 는 GNU C 컴파일러를기본으로하여그위에사용자편의를위한통합개발환경인터페이스를덮어씌운것이다. Dev-C++ 를설치할때는설치폴더에이르기까지경로명에공백이없어야한다. 설치가끝나면그디렉터리아래에 bin 이라는하위디렉터리가만들어지고, 그안에 GNU C 컴파일러 (gcc.exe) 와 C++ 컴파일러 (g++.exe) 가설치된다. 2 플렉스와바이슨을설치한다. 플렉스는 http://gnuwin32.sourceforge.net/packages/flex.htm 에서내려받아설치한다. 설치는매우간단하다. Dev-C++ 와마찬가지로경로명에공백이없도록해야하며보통은 C:\GnuWin32 에설치한다. 바이슨은 http://gnuwin32.sourceforge.net/packages/bison.htm 에서내려받아같은방법으로설치한다. 역시경로명에공백이없도록해야하며, 일반적으로플렉스와함께 C:\GnuWin32 에설치한다. 24
13.3 플렉스와바이슨설치방법 3 시스템속성에서환경변수중 PATH 변수의값에경로를추가한다. GNU C 컴파일러, 플렉스, 바이슨의설치를마치면시스템속성에서환경시스템의환경변수중 PATH 변수의값에 GNU C 컴파일러와플렉스, 바이슨의실행파일이있는경로를추가한다. 예를들어 PATH 변수가있으면 C:\Dev-Cpp\bin; C:\GnuWin32\bin 을추가하고, PATH 변수가없다면새롭게등록한다. 4 제대로설치되었는지확인한다. GNU C 컴파일러와플렉스, 바이슨이제대로설치되었는지확인하기위해명령프롬프트창을연다. 명령프롬프트는 [ 모든프로그램 ] [ 보조프로그램 ] [ 명령프롬프트 ] 메뉴를선택하여실행하거나실행창에서 cmd.exe 를입력하여바로실행시킨다. 이창에서 flex-version 을입력하여설치된플렉스의버전을확인하고, bison-version 을입력하여설치된바이슨의버전을확인한다. 마지막으로 gcc-version 을입력하여설치된 GNU C 컴파일러의버전을확인한다. 이과정에서버전이모두나타난다면문제없이제대로깔린것이다. 25
13.3 플렉스와바이슨설치방법 5 플렉스와바이슨이필요로하는라이브러리파일을 GNU C 컴파일러디렉터리에복사 한다. 마지막으로플렉스와바이슨이필요로하는라이브러리파일을 GNU C 컴파일러디렉터리에복사한다. 플렉스와바이슨이설치된디렉터리인 C:\GnuWin32 에는여러하위디렉터리가있다. 그중 lib 속에 libfl.a 와 liby.a 가포함되어있는데이것들은각각플렉스와바이슨의라이브러리아카이브 (archive) 파일이다. 이것들을 GNU C 컴파일러의라이브러리디렉터리인 C:\Dev-Cpp\lib 에복사한다. 플렉스입력파일의이름을확장자가 l 인 test.l 이라하고바이슨입력파일의이름을확장자가 y 인 test.y 라고하면플렉스와바이슨을사용하는일반적인형태는다음과같다. C:\Users\ex> flex test.l C:\Users\ex> bison test.y 26
13.4 플렉스사용법 [ 예제 13-5] 플렉스를이용하여글자개수, 단어개수, 문장개수를계산하는어휘분석기 플렉스를이용하여글자의개수 ( 빈칸도하나의글자로계산 ), 단어의개수, 문장의개수를계산하는어휘분석기를만들어보자. [ 풀이 ] 1. 플렉스의입력파일을만든다. 입력파일의이름은 WordCount.l 이라고하자. %{ /* word count */ unsigned charcount=0, wordcount=0, linecount=1; %} word [^ \t\n]+ eol \n %% {word} {wordcount++; charcount+=yyleng; printf("word : %s\n", yytext);} {eol} {charcount++; linecount++;}. charcount++; %% main() { yylex(); printf("number of character : %d \n", charcount); printf("number of word : %d \n", wordcount); printf("number of line %d \n", linecount); } 27
13.4 플렉스사용법 2. 실행순서 실행하고자하는테스트파일은다음과같은 datafile2.txt 이다. The token descriptions that lex uses are known as regular expressions, extended versions of the familiar patterns used by the grep and egrep commands. A lex lexer is almost always faster than a lexer that you might write in C by hand. 맨먼저다음을실행한다. C:\ > flex WordCount.l C:\ > gcc -o WordCount lex.yy.c -lfl C:\ > WordCount < datafile2.txt 3. 실행결과 다음도스화면은실행순서와실행결과를보여주는데 235 개의문자, 42 개의단어, 1 개의행이나타난다. 28
13.4 플렉스사용법 29
13.5 바이슨사용법 [ 예제 13-7] 플렉스와바이슨을이용하여파싱표와구문분석기만들기 다음문법에대해바이슨을이용하여 SLR 파싱표와구문분석기를만들어보자. 이문법은 [ 예제 6-30] 에서 SLR 방법으로, [ 예제 6-34] 에서 CLR 방법으로, [ 예제 6-38] 에서 LALR 방법으로파싱표를만들었다. S L = R S R L *R L id R L [ 풀이 ] 1. 플렉스입력파일작성 ( 파일명 : TT.L) %{ #include "y.tab.h %} letter [A-Za-z] digit [0-9] id {letter}({letter} {digit})* %% /* 토큰정의규칙 */ "=" return(yytext[0]); "*" return(yytext[0]); {id} return(id); 30
13.5 바이슨사용법 2. 바이슨입력파일작성 ( 파일명 : TT.Y) %{ %} %token ID %% S:L '=' R R; L:'*'R ID; R:L; %% main() { if(yyparse()==0) { printf("the Parsing Complete \n"); } else { printf("syntax error \n"); } } 31
13.5 바이슨사용법 3 실행순서 C:\ > flex tt.l /* lex.yy.c 어휘분석기생성과정 */ C:\ > bison -yd -v tt.y C:\ > gcc -o tt lex.yy.c y.tab.c -lfl ly 32
13.5 바이슨사용법 4. 파싱표 33
13.5 바이슨사용법 34