Lex & Yacc(소개와 예제 중심으로)박 성구 byosmosis@yahoo.com1997년 11월 1일이 글은... 언젠가 누군가를 위해 리포트를 대신 해주느라고 작성했었던 문서입니다. ^^; 텍스트에서 볼 수 있도록 바꾸어서 게시합니다. lex & yacc을 배워보세요. :) Lex와 Yacc는 입력구문의 검색과 분석을 용이하게 하기 위하여 개발되었다. 입력에 대한 어떤 패턴을 갖어야 하는 응용 프로그램을 만들 때 좀더 빠르고 정확하게 그리고 약간의 수정으로 유지보수가 쉽게 되는 것이 lex와 yacc의 특징이다. Lex와 Yacc가 쓰이는 예로는 숫자와 연산자를 구별해줘야 하는 계산기, 컴파일러나 인터프리터 언어의 문장 검색, 문법 분석을 위한 것이나, 데이타 베이스에서의 SQL언어의 문법을 체크하는 것, lex만을 이용한 구분 분석 등의 여러가지 경우에 이용된다. 여기서는 lex와 yacc의 전반적인 소개와 lex와 yacc를 이용하는 법 그리고 약간의 lex와 yacc의 응용 등에 대해서 소개하고자 한다. 1. Lex & Yacclex와 yacc는 벨연구소(Bell Laboratories)에서 70년대에 개발되었고, 후에 이것들은 유닉스의 표준 유틸리티로 선정이 되어 System V와 초기 BSD 버전은 원래의 AT&T 버전이 이용되고 있으며 새로운 BSD버전으로는 flex나 Berkely yacc이 나와 이용되고 있다. 또 FSF(Free Software Foundation)의 GNU 프로젝트의 bison이라 불리는 것은 yacc에 비해 좀더 향상된 기능을 가졌으며 BSD와 GNU 프로젝트의 flex(Fast Lexical Analyzer Generator)외에도 여러 운영체제하에서 여러 가지 다른 이름으로 lex와 yacc의 변형이 지원되고 있다. ※ MS-DOS나 OS/2 등의 OS상에서도 이용할 수 있는 lex와 yacc를 만든 곳으로 MKS(Mortice Kern Systems Inc.)가 있다. 1.1 Lex의 사용(Lex를 이용한 간단한 프로그램)예제) Lex는 아래와 같이 %%와 %%사이에는 lex가 기술되고 그 이후에는 C가 기술된다. 위는 표준입력을 표준출력으로 내보내는 가장 간단한 lex 프로그램으로 정규 표현 .와 \n으로 표시되는 문자가 들어왔을 시 그대로 에코해준다. (실제로 lex에서 위의 내용은 default이다.) 유용한 다른 간단한 예로 다음과 같은 위의 소스를 simple.l이라고 하면(밑줄 표시는 사용자 입력) 위와 같이 되어 UNIX의 cat과 유사한 프로그램이 완성된다.(인자가 없는 cat 명령의 사용시 실제로 위의 프로그램과 같다) ※ lex의 구성은 다음 세가지 definitions, rules, user code section으로 이루어진다.
예제) 또 %%와 %%사이에 lex를 기술하기 이전에 C를 기술하기를 원할시에는 %{와 %}로 C의 기술이라는 표시를 하고 그 사이에 기술할 수 있다.
yytext는 lex에서 사용되는 입력 텍스트에 대한 global character pointer이다. 위의 소스를 simple.l과 같은 방법으로 컴파일하여 실행시켜 보면
위에 나타난 수행결과의 출력과 같이 처리하기를 원하는 패턴에 대해서 처리가 이루어진다. love7의 경우에는 love에 대한 처리를 해주고 7은 알파벳이 아니므로 다음줄에 에코가 된다. 또 결과중 바로 위의 'love story'는 love를 인식하고 whitespace로 빈칸을 인식하고 다음에 story를 인식한 것이다. 따라서 love에 대한 처리와 빈칸에 대한 아무 처리없음과 story에 대한 처리가 결과 내용이 될 것이다. 위의 예로서 loveyou라고 입력을 했다면 love 다음에 you를 따로 보는 것이 아니라 하나의 패턴으로 보아 distress와 같은 결과가 나올 것임을 예상할 수 있다. 예제) 다음은 전의 예제와 같은 간단한 형식으로 다만 숫자에 대한 C의 enum형식으로 선언하여 심볼 테이블의 값을 이용하는 예를 보여준다.
위의 마지막 'two two'는 two에 대한 처리를 해주고 ' '의 빈칸은 다음 줄에 단순히 에코해주고 다음줄로 넘어가지 않고 다음의 two가 처리되어 나타난 결과이다. 따라서 두 번째의 two에는 앞에 빈칸이 하나 더 있다. 그리고 oneone이라는 패턴이 존재할 때에는 one의 패턴이 아닌 oneone의 패턴을 따르는 것은 긴 문자열이 우선순위를 가지기 때문이다.(정규 표현식 참조) 예제) 다음은 lex의 위에 제시한 것보다 약간 복잡한 숫자와 연산자와 변수를 인식하는 예제로서 조금만 개선시키면 완전한 계산기 프로그램이 될 수 있다. 이 예제는 단순히 숫자인지, 연산자인지, 예약어 또는 변수로서 사용될 값인지를 출력하여 나타내도록 하는 예제이다.
위의 예에서 yyin에 대한 지정은 입력을 커맨드 라인상의 첫인자가 가리키는 파일의 내용을 처리할 것이지 화면에서 표준입력을 받아 처리할 것인지에 대한 처리를 할 수 있게 한다. 1.2 Lex와 Yacc의 관계(Lex scanner, Yacc parser)Lex scanner와 Yacc parser는 같이 구현하는 경우가 대부분인데, Yacc가 Lex의 상위에서 구현된다. Lex는 입력문자열에 대한 일차적인 검색을 하고 실제적인 분석은 Yacc가 하는 것이다. Yacc는 입력에 대한 토큰(token)이 필요하면, Lex에서 제공하는 yylex()함수를 호출하여, 입력된 토큰들의 배열이 주어진 문법에 맞는지를 체크하면서 그 조건에 맞는 실행을 하게 된다. 다르게 표현하면, Lex와 Yacc을 사용 동시에 사용할 시에는 yacc 기술파일의 main()함수에서 yyparse()함수라는 yacc에 의해 만들어지는 구문분석기를 부르고, yyparse()함수는 yylex()라는 lex가 만들어 주는 해석기(lexer)를 이용해서 입력열에서 처리단위의 토큰을 뽑아오게 된다. 예를 들어 lex에서 '[\t ]+'로 표시되었던 공백이나 탭과 같은 whitespace문자는 대부분의 프로그램에서 실제로 처리하기를 원치 않는다. 따라서 위와 같은 의미 없는 문자나 처리할 필요가 없는 문자열에 대해서는 그 내용을 parser에게 넘겨줄 필요가 없다. 그리고 다음에 오는 처리할 문자가 있을 경우 그 내용(토큰)을 yacc parser에게 넘기면 그 처리를 할 것이다. 이런 경우가 lex와 yacc를 같이 쓰게 되는 간단한 예로 생각될 수 있을 것이다. ※ MS-DOS나 OS/2 등의 OS상에서도 이용할 수 있는 lex와 yacc를 개발했던 MKS(Mortice Kern Systems Inc.)가 WWW과 관련하여 Netscape의 Fasttrack이나 Microsoft의 IIS에 대한 검색 엔진 등에 이용할 수 있게도 하였다. 1.3 Yacc의 사용Yacc는 Yet Another Compiler Compiler의 약자로, 컴파일러 생성을 위한 프로그램을 compiler-generator 또는 compiler-compiler라고 부르는데, Yacc가 BNF와 같은 형식의 rules의 항목들로부터 parser를 만들어내는 프로그램이다.(Yacc 입력은 BNF를 간단하게 만든 버전이다.) Yacc를 이용한 프로그램들은 portable C 컴파일러, APL, Pascal, Ratfor, tbl, eqn 등이 있다. 다음은 Yacc의 구조이며, Yacc는 Lex와 비슷한 구조를 가지고 있는데 실제로는 Lex가 Yacc의 구조를 본따 쓴 것이다.
예제) yacc의 이해를 위한 간단한 단지 덧셈과 뺄셈만이 가능한 아주 간단한 기능을 가진 계산기를 만든다고 할 때 그것의 실제 실행 예를 보이면 아래와 같다.
yacc가 lex를 호출하면(=yylex()를 호출하면) NAME, NUMBER, 그리고 +, -, =의 형태로 토큰을 넘겨 받는다.(정규식 표현에 의해서 ' '안에 놓여진 문자는 그 문자 그 자체로 본다) 또 y_calc.y를 보면, $1, $2, $3는 각각 입력받은 토큰의 위치에 해당하는 값을 가지고 있고, 이 값은 yacc에서 yylval가 type int, 정수로 처리가 되어 %d로 정수를 출력한다.(y_calc.l에서 사용하고 있는 yylval이라는 변수는 union으로 선언되어 있다. 이것을 lex에서 외부변수로 만들어 이용하여 yyparse()함수를 호출하는 yacc가 처리하도록 값을 전달하게 되는 것임) 그리고 $2의 경우에 해당하는 것은 연산자에 해당하는 문자가 들어가기 때문에 expression의 RHS의 { } 안에서 +, 와 -로 이용하고 있다. 그리고 $$는 LHS의 값, expression의 값이 된다. yacc를 실제로 사용하기 위해서 example.y라는 yacc파일이 작성되면 yacc를 이용하여, yyparse()라는 구문분석기 함수를 가진 y.tab.c라는 C언어 화일을 만들기 위해서 'yacc example.y'를 실행하고 C컴파일러를 이용해서, y.tab.o라는 오브젝트 화일을 만든 후에, 코드생성기나 다른 프로그램과 링크하여 원하는 결과를 만든다. 위의 프로그램(y_calc.y와 y_calc.l)을 컴파일하여 실행한 결과는 아래와 같다. 여기서는 y.tab.h를 lexer에서 include하기 때문에, yacc에서 만들어주기 위해 -d 스위치를 이용하였다. lex를 이용하여, lex.yy.c를 만들고, yacc을 이용하여, y.tab.c를 만들어서 liby.a와 libl.a를 링크하여 원하는 실행화일을 만들게 된다. ※ Yacc에서의 모호성 - 다음과 같은 예제를 생각해보자.
위와 같이 기술하게 되면, + - * / = 의 우선순위는 + - 가 가장 낮고, * /가 그것보다 높고, 대입연산자 = 이 높고, 부호연산자인 -가 가장 높은 우선순위를 가진다는 것을 보여주고 있다. 또한 +나 -, *, /는 왼쪽으로 결합법칙을 가지고, 대입연산자 =는 우측으로 결합법칙을 따른다.
※ 또다른 Yacc의 모호성, LALR(1)이 아닌 문법의 예 다음과 같은 문법을 살펴보자.
위의 예는 들어, HORSE AND CART 라는 입력이 들어왔을 경우에, HORSE를 cart_animal로 reduce해야 하는지, work_animal로 reduce해야 하는지 알려면, HORSE를 보고, AND를 보고, CART를 보고 나서야 알 수가 있게 된다. Yacc가 처리할 수 없는 이 문제는, yacc가 구문 분석을 하는데 사용하는 기술은 LALR(1)인데 LALR은 LookAhead Left Recursive, 즉, 한 개의 단어를 더 보고 맞는 문법을 결정할 수 있다는 것이기 때문이다. 따라서, HORSE 다음에 2개의 단어를 더 읽어야 하는 경우인데, 이 경우 LALR(2)문법이며, yacc는 한 개의 lookahead만을 볼 수 있는 문법인 LALR(1)에 해당하므로, 위의 문법은 처리할 수 없다. 따라서 위의 문법은 다음과 같이 LALR(1)문법으로 바꾸어 주어야 한다.
위의 문법은 HORSE를 보고, 바로 뒤의 한 단어인 CART만을 보면 cart_animal로 reduce할지, work_animal로 reduce해야할지를 알게 된다. 예제) 다음과 같이 변수 처리가 가능한 탁상 계산기를 구현하려고 한다. 위와 같은 기능을 수행하려면 기본적으로 기억장소로 사용될 수 있는 심볼테이블을 유지하고, 심볼테이블에 변수의 이름과 값을 유지해야 한다. 다음은 변수이름이 영문의 알파벳만을 가진다고 가정한 그러한 예를 보인 것이다.
변수이름이 영문의 알파벳만을 가진 26개의 원소를 가진 배열인 vbltable[26]을 선언해서 변수의 값을 유지하도록 한다. 위에서 %union은 lexer에서 받는 token인 NAME과 NUMBER를 NAME은 vbltable[]의 한 인덱스를 지칭하게 하여, 0부터 25의 값을 가지게 하는 반면에, NUMBER는 실수의 값을 가지도록 한다. 따라서, 같은 token이라고 하더라도, 가지는 값이 다르게 되는데, 가지는 값은 달라도, 한 순간에는 오직 한 개의 token만이 인식되기 때문에, 같은 기억장소를 유지하도록 위와 같이 %union으로 선언하게 된다. 그리고 %union문은 실제, y.tab.c안에서 C의 union으로 변환되어 처리된다. ``%type <dval> expression'' 문장은 역시, token뿐이 아니라 token으로 정해지지 않은 LHS의 경우에도 알맞은 타입으로 설정이 가능하다는 것을 보여준다. ``NAME '=' expression { vbltable[$1] = $3; }''의 문장은 왼편의 문법으로 reduce될 때 오른편의 action부를 실행하게 되는데, 의미는 $1 즉 NAME의 값(0부터 25사이의 값을 yylex()로부터 받았다)으로 vbltable의 한 원소에 $3 즉 expression의 값을 넣는 것이다. 예를 들어 x = 2.0 + 3.2이었으면 x에 대한 $1은 23이 되며 vbltable[23] = 5.2의 의미를 가진다. ``'-' expression %prec UMINUS { $$ = -$2; }''의 문장은 -2와 같은 단어가 들어왔을 때 -는 2-3에서의 -가 아니라 %prec에 의해 부호연산자인 -로 우선 순위를 두어 연산이 이루어짐을 의미한다. ``NAME { $$ = vbltable[$1]; }''은 만약 y라는 변수이름이 주어지면 $1의 값이 0부터 25사이의 값 중에서 24번째 해당되므로 vbltable[24]의 값을 스택에 저장하게 된다.
위의 lex화일을 보면, yylval.dval로 표현한 것이 있는 데, 이것은 yylval가 union타입으로 선언이 되어있으므로, NUMBER형이면, 값을 넣을때에도, yylval.dval식으로 하여, 넣으라는 것을 나타낸다. 또한 변수가 영문 알파벳만을 가정하기 때문에, 단순히 0부터 25사이의 값으로 vbltable을 인덱싱하게 되는데, lex에서의 yylval.vblno = yytext[0] - 'a'는 yylval에 0부터 25사이의 값을 넣게 된다. 위의 프로그램(variable.l 과 variable.y)을 컴파일하여 실행한 결과는 아래와 같다.
1.4 Lex와 Yacc의 이용다음은 실제로 Lex와 Yacc를 동시에 결합하여 사용한 예이다.
verb, noun 등에 대해서 state를 이용하여, 줄이 끝나기 전까지 나오는 단어들을 심볼테이블에 등록하게 되는 것이 add_word()함수이고 그 등록된 단어를 살펴보는 함수가 lookup_word()이다. 다음은 yacc화일 example.y화일의 내용이다. 위의 yacc화일에서 "%token NOUN PRONOUN VERB ADVERB ADJECTIVE PREPOSITION CONJUNCTION"문은 입력 기본단위인 토큰으로 처리한다는 것을 의미하고 여기서는 lexer에게서 넘겨받는 것이 된다. 즉, yyparse()가 매번 yylex()를 부르면, 그 결과는 NOUN이나 PRONOUN 등의 token으로 오게 되는 것이다. 따라서, yyparse는 그러한 토큰의 나열이 문법에 맞는지를 분석하여, 맞으면 옆에 주어진, action인 C언어 문장을 수행하게 된다. yacc의 입력은 yyin이라는 화일에서 들어오게 되고, 출력은 yyout이라는 화일로 쓰게 된다. 기본적으로는 yyin과 yyout은 stdin과 stdout, 즉 표준 입,출력으로 설정이 되어있으므로, 키보드와 화면을 통해 입출력이 이루어지게 된다. 이를 바꾸어주는 것은 앞에서 제시하였었다. yyparse()는 yacc가 만들어주는 구문분석기(parser)이고, yyerror()는 구문분석 중에 에러가 생겼을 때 부르는 함수이다. 다음은 앞에서 설명한 lex화일(example.l)과 yacc화일(example.y)을 실제 컴파일하여 수행한 결과이다.
1.5 Makefile의 이용컴파일 절차를 간소화하고, 프로그램 보수를 쉽게 하기 위해서 다음과 같이 makefile를 정의하여 편리하게 컴파일을 수행할 수 있다.
2. 참고도서
|
   
|
