Yacc와 Lex 시작하기

Yacc와 Lex 시작하기

 Lex와 Yacc 소개

 Lex와 Yacc는 UNIX에 있어서 매우 중요하고 강력한 툴이다. Lex와 Yacc에 능숙해지면 실제로 FORTRAN이나 C 컴파일러를 쉽게 작성할 수 있다. Ashish Bansal은 사용자가 자신의 언어와 그 컴파일러를 작성할 수 있을 만큼 이 툴들을 자세하게 설명한다. Ashish Bansal은 정규식, 선언, 매칭 패턴, 변수, Yacc 문법 및 파싱 코드를 다룬다. 마지막에는 Lex와 Yacc의 연결 방법을 설명한다.

Lex는 Lexical Analyzer, 그리고 Yacc는 Yet Another Compiler Compiler의 약자이다. 우선 Lex부터 시작한다.

 Lex

 Lex는 스캐너를 만들 수 있는 툴이다. 스캐너는 텍스트의 어휘 패턴(lexical patterns)을 인식하는 프로그램이다.

일치되는 정규식은 관련된 작동을 가지며, 여기에는 토큰의 반환도 포함될 수 있다. Lex가 파일이나 텍스트 형식으로 입력을 받으면, Lex는 텍스트를 정규식과 대조 시킨다. Lex는 한 번에 한 문자씩 받아서 패턴이 일치될 때까지 계속 반복한다. 패턴이 일치되면 Lex는 관련된 작동(토큰의 반환 등)을 실행한다. 이와 반대로 일치되는 정규식이 없으면, Lex은 더 이상의 처리를 중단하고 오류 메시지를 뿌린다.

Lex와 C는 밀접한 관계에 있다. .lex 파일(Lex에서 파일의 확장자는 .lex이다)이 Lex 유틸리티를 통과하면, C에 출력 파일이 생성된다. 이 파일들을 컴파일하면 Lexical Analyzer의 실행 프로그램을 만들 수 있다.

 

Lex에서의 정규식

정규식은 메타 언어를 사용한 패턴의 기술(description)을 말한다. 하나의 수식은 기호들로 구성되어 있다. 기호들은 보통 문자와 숫자이다. 그러나 Lex에서 특별한 의미를 지니는 기호들이 있다. 다음 두 표는 Lex에서 사용되는 여러 기호를 규정하고 있으며 약간의 전형적인 예제를 제시한다.

Lex에서의 레귤러 표현 규정

문자	의미
A-Z, 0-9, a-z	패턴의 일부를 구성하는 문자와 숫자.
.	\n을 제외한 어느 문자와도 일치.
-	범위를 표시할 때 사용. 예: A-Z은 문자 A부터 Z까지를 의미.
[ ]	문자 클래스. 괄호 안의 어느 문자와도 일치. 첫 문자가 ^이면 부정 패턴을 나타냄. 예: [abC]는 a,b 혹은 C와 일치.
*	선행 패턴의 발생이 0 이상.
+	선행 패턴의 발생이 1 이상.
?	선행 패턴의 발생이 0 또는 1 일 때 일치.
$	패턴의 마지막 문자가 행 종료일 때 일치.
{ }	패턴이 나타날 수 있는 횟수를 표시. 예: A{1,3}은 A가 1회나 3회 표시 가능을 의미.
\	메타 문자를 피하기 위해 사용. 또한 이 표에 규정된 문자의 특별한 의미를 제거하는데 사용.
^	부정.
|	수식의 논리합.
"<some symbols>"	문자 그대로의 의미. 메타 문자 보류.
/	표현이 계속되는 경우에 한하여 선행 패턴과 일치. 예: A0/1은 A01이 입력일 경우에 한하여 A0와 일치.
( )	일련의 정규식을 그룹화.

 

레귤러 표현의 예제

레귤러 표현	의미
joke[rs]	jokes 혹은 joker와 일치.
A{1,2}shis+	AAshis, Ashis, Aashi, Ashi와 일치.
(A[b-e])+	A의 발생이 없거나 한 번 이상이고 b에서 e까지의 어느 한 문자가 이어질 경우에 일치 .

Lex에서의 토큰은 C의 변수명 같이 선언된다. 토큰은 모두 관련된 수식을 가지고 있다. (다음 표에 토큰과 수식의 예가 나와 있다.) 표를 예로 들어 워드 카운트(단어의 개수를 세는) 프로그램을 작성할 것이다. 첫번째 일은 토큰이 선언되는 방식을 제시하는 것이다.

 

토큰 선언 예제

토큰	관련 수식	의미
number	([0-9])+	숫자가 1회 이상 발생
chars	[A-Za-z]	임의 문자
blank	" "	1개의 블랭크 스페이스
word	(chars)+	chars가 1회 이상 발생
variable	(chars)+(number)*(chars)*( number)*

 

Lex를 이용한 프로그래밍

Lex를 이용한 프로그래밍은 세 단계로 구분된다 :

1. Lex가 이해할 수 있는 형식으로 패턴 관련 작동을 지정한다.
2. Lex를 이 파일에 실행하여 스캐너용 C 코드를 작성한다.
3. C 코드를 컴파일 및 링크하여 실행 가능한 스캐너를 생성한다.

주: 스캐너가 Yacc로 개발한 parser의 일부라면, 단계 1 및 2만 수행해야 한다. 이 문제에 대해서 도움이 필요하면 Yacc 및 Lex와 Yacc을 함께 사용하기 섹션을 검토하는 것이 좋다.

이제 Lex가 이해하는 프로그램 포맷의 종류를 살펴본다. Lex 프로그램은 3개의 섹션으로 구분된다: 첫째 섹션은 전역 C와 Lex 선언, 둘째 섹션은 패턴(C로 코딩 된) 그리고 셋째 섹션은 추가 C 함수들을 포함하고 있다. 예를 들면, main()은 3번째 섹션에서 찾아볼 수 있다. 각 섹션은 %%로 구분된다. 이제 Lex 워드 카운팅 프로그램으로 돌아가서 여러 가지 프로그램 섹션의 구성을 검토한다.

 

글로벌 C 와 Lex 선언들

이 섹션에 C 변수 선언을 추가할 수 있다. 우리는 이곳에서 워드의 숫자를 저장하는 정수형 변수를 선언할 것이다. 또한 Lex의 토큰 선언을 수행할 것이다.

워드 카운팅 프로그램을 위한 선언 (Declarations for the word-counting program)

%{         int wordCount = 0;         %}         chars [A-za-z\_\'\.\"]         numbers ([0-9])+         delim [" "\n\t]         whitespace {delim}+         words {chars}+         %%

 

더블 퍼센트 심볼은 이 섹션의 마지막과, 세 개의 섹션으로 구성되어 있는 Lex 프로그래밍의 두 번째 섹션의 시작을 나타낸다.

 

패턴 일치를 위한 Lex의 규칙

일치시키고자 하는 토큰을 기술하는 Lex 규칙을 살펴보기로 하자. (C는 토큰이 일치시킬 때 필요한 작업을 규정하기 위해 사용한다) 토큰과 일치되는 규칙을 살펴보자.

워드 카운팅 프로그램을 위한 Lex 규칙(Lex rules for the word-counting program)

{words} { wordCount++; /*         increase the word count by one*/ }         {whitespace} { /* do         nothing*/ }         {numbers} { /* one may         want to add some processing here*/ }         %%

 

C code

Lex 프로그래밍의 마지막인 세번째 섹션에서는 C 함수 선언(main 함수 포함)을 다룬다. 이 섹션에 yywrap() 함수가 포함되는 것을 유의해야 한다. Lex에는 사용자가 이용 가능한 일련의 함수와 변수가 있다. 그 중의 하나가 yywrap이다. 전형적으로 yywrap()는 아래 예의 경우처럼 규정된다. 이 문제를 Advanced Lex에서 탐구할 것이다.

워드 카운팅 프로그램용 C code 섹션(C code section for the word-counting program)

void main()         {         yylex(); /* start the         analysis*/         printf(" No of words:         %d\n", wordCount);         }         int yywrap()         {         return 1;         }

 

이전의 섹션에서 간단한 Lex 프로그램 작성을 돕는 Lex 프로그래밍의 기본 원리를 검토했다. Advanced Lex의 섹션에서는 Lex가 제공하는 기능성을 다룬다. 그러면 모든 사용자가 복잡한 프로그램을 작성할 수 있다.

 

최종 작업

.lex 파일은 Lex의 스캐너로서 Lex 프로그램에 다음과 같이 사용한다::

$ lex <file name.lex>

 

lex.yy.c 파일이 생성되는데 이 파일은 C 컴파일러로의 컴파일이 가능하다. 또한 파서로 실행 파일을 생성하거나 옵션 2로 링크 단계에 라이브러리를 포함할 수 있다.

다음은 몇 가지 Lex 플래그이다:

• -c는 C 작동을 가리키며 기본값이다.
• -t는 표준 출력과는 다른 방식으로 .lex.yy.c 프로그램을 작성한다.
• -v는 통계를 두 행으로 요약한다.
• -n은 -v 요약을 인쇄하지 않는다.

Advanced Lex

Lex는 여러 정보를 제공하고 복잡한 기능을 수행하는 프로그램 작성할 수 있는 다양한 함수와 변수를 포함한다. 이들 변수와 함수의 일부는 그 사용법과 함께 다음의 표에 나타나 있다. 리스트를 자세히 검토하려면 Lex 또는 Flex 매뉴얼(참고자료)을 참조하는 것이 좋다.

Lex의 변수

yyin	FILE* 유형과 관련이 있으며, lexer가 구문 해석 중인 현재 파일을 가리킨다.
yyout	FILE* 유형과 관련 있으며, lexer의 출력이 작성될 위치를 가리킨다. 기본값으로, yyin과 yyout는 표준 입력과 출력을 가리킨다.
yytext	일치 패턴의 텍스트가 이 변수에 저장된다.(char*)
yyleng	일치 패턴의 길이를 제공한다.
yylineno	현재 행 숫자의 정보를 제공한다. (lexer가 지원할 수도 있고 안 할 수도 있다.)

Lex의 함수

yylex()	분석 시작하는 함수. Lex가 자동으로 생성.
yywrap()	이 함수는 파일( 혹은 입력)의 끝에 호출된다. 이 기능이 1을 반환하면 구문 해석(파싱)은 정지한다. 따라서 이 함수는 다중 파일의 파싱에 사용될 수 있다. 코드는 세번째 섹션에서 작성되어 다중 파일이 파싱된다. 말하자면 모든 파일이 파싱될 때까지 yyin 파일 포인터가 상이한 파일을 가리킨다는 전략이다. 마지막에 yywrap()가 구문 해석의 종료를 가리키기 위하여 1을 반환한다.
yyless(int n)	이 함수는 판독 토큰의 'n' 문자를 제외한 모든 것을 밀어낸다.
yymore()	이 함수는 Lexer에게 현재의 토큰에 다음 토큰을 부가하도록 지시한다.

이것으로 Lex에 관한 토론은 종료되었다. Yacc로 이동한다...

 

Yacc

Yacc는 Yet Another Compiler Compiler의 약자이다. Yacc에 상응하는 GNU 프로그램은 Bison이다. 이것은 언어를 표기하는 모든 문법을 해당하는 파서로 번역하는 툴로서 Backus Naur Form(BNF)로 작성된다. 관례적으로 Yacc 파일은 접미사 .y를 가진다. 다음 컴파일 행을 이용하면 Yacc 컴파일러가 호출된다. :

$ yacc <options>         <filename ending with .y>

 

먼저 문법의 정의에 대해 검토하겠다. 전의 섹션에서 Lex가 순차적 입력에서의 토큰을 인식하는 것을 보았다. 토큰의 순서를 주시할 경우, 이 순서 발생에 따라 적절한 작동을 수행하고 싶을 수 있다. 그 경우에 유효한 순서를 지정한 것을 문법이라고 한다. Yacc 문법 파일에 이러한 문법이 지정되어 있다. 즉, 순서가 일치될 경우 어떻게 해야 할지 나타낸다.

분명한 개념을 위해서 영어 문법을 예로 들어 본다. 토큰은 명사, 동사 및 형용사 등이 될 수 있다. 이 토큰으로 문법적으로 정확한 문장을 만들기 위해서는, 특정 규칙과 일치하도록 구성해야 한다. 간단한 한 문장은 명사 동사 또는 명사 동사 명사일 수 있다.

따라서 토큰 자체는 언어(Lex)에서 나오고, 이들 토큰에 허용된 순서(문법)는 Yacc에 지정된다.

 

Yacc로 컴파일러를 작성하기 위해서는 4 단계가 필요하다.:

1. 문법 파일을 통해 Yacc를 실행하여 Yacc에서 파서를 생성한다.
2. 문법을 지정한다:
   • .y 파일에 문법을 작성한다.
   • 인풋을 처리하고 토큰을 파서로 전달할 렉시컬 애널라이저를 작성한다. 이때 Lex를 사용할 수 있다.
   • yyparse()를 호출하여 파싱을 시작하는 함수를 작성한다.
   • 에러 처리 루틴(yyerror())을 작성한다.
3. Yacc과 다른 관련 소스파일에서 만들어진 코드를 컴파일 한다.
4. 객체 파일을 실행파일 파서용 라이브러리에 링크한다.

단말기호 및 비단말기호(Terminal and non-terminal symbols)

단말기호(Terminal symbol):

구문상으로 동등한 토큰 클래스를 나타낸다. 단말기호에는 세 가지 유형이 있다:

Named token: %token 식별자에 의하여 규정된다. 관례적으로 이것들은 모두 대문자다.

Character token: C의 경우와 동일한 포맷으로 작성된 문자 상수. 예로 '+'는 Character token 이다.

Literal string token: C의 문자열 상수처럼 작성된다. 예로 <<는 Literal string token이다.

Lexer은 Named token을 반환한다.

 

비단말기호(Non-terminal symbol):

비단말기호와 단말기호의 그룹을 구성하는 기호이다. 관례적으로 모두 소문자이다. 예제에서 보면 NAME이 단말기호인 반면 file은 비단말기호이다.

 

Yacc에서 문법 작성하기

이 세 절은 선언, 문법 규칙 그리고 C 코드이다. 문법 지정을 설명하기 위하여 포맷명=년 단위의 기간(age) 파일을 파싱하는 예를 사용할 것이다. 우리는 파일이 각각 공백문자(space)로 분리되어 있는 여러 이름과 기간(age)을 가지고 있다고 전제한다. 또한 Yacc 프로그램의 각 섹션을 보면서, 실례를 위한 문법 파일을 작성할 것이다.

 

C와 Yacc에서의 선언

C 선언은 매크로 및 작동에서 사용되는 유형과 변수를 규정할 수 있으며, 또한 헤더 파일이 포함될 수 있다. Yacc 선언 부분의 각자는 단말기호와 비단말기호(토큰들)명을 선언하며, 또한 연산자 우선순위와 여러 기호의 데이터 유형을 기술할 수 있다. 일반적으로 lexer(Lex)는 이 토큰을 반환한다. 그러한 모든 토큰은 Yacc 안에서 선언되어야 한다.

 

파일 파싱 선언의 예(Declarations for the file-parsing example)

%         #typedef char* string; /*         to specify token types as char* */         #define YYSTYPE string /*         a Yacc variable which has the value of returned token */         %}         %token NAME EQ AGE         %%

 

YYSTYPE은 다소 이상하게 보일 수 있다. 그러나 Lex 처럼 Yacc 또한 사용자가 기능 확장할 수 있는 일련의 변수와 함수를 포함한다. YYSTYPE는 lexer 값을 파서나 Yacc로 복사하는데 사용하는 yylval 유형(또 다른 Yacc 변수)을 정의한다. 기본 유형은 int이다. 문자열이 lexer에서 복사되므로 이 유형은 char*로 재정의된다. Yacc 변수에 대한 상세한 것은 Yacc 매뉴얼을 검토한다(참고자료)

 

Yacc 문법 규칙

Yacc 문법 규칙은 일반적으로 다음 형식을 취한다 :

result: components { /*         action to be taken in C */ }         ;

 

예제에서 결과는 규칙이 기술하는 비단말기호이다. 구성 요소는 규칙에 의해 결합된 다양한 단말 및 비단말 기호이다. 특정 순서가 일치하면 구성 요소 뒤에 작동이 수행될 수 있다. 다음 예제를 검토한다.:

param : NAME EQ NAME {         printf("\tName:%s\tValue(name):%s\n", $1,$3);}             | NAME EQ VALUE{             printf("\tName:%s\tValue(value):%s\n",$1,$3);}         ;

 

위의 예제에서 NAME EQ NAME 순서가 일치되면 이에 대응해서 { } 괄호 안의 작동이 취해진다. 또 한 가지 유용한 것은 NAME과 NAME의 토큰 값(또는 두 번째 행의 VALUE)을 참조하는 $1과 $3의 사용이다. Lexer는 yylval이라 불리는 Yacc 변수를 통해 이들 값을 반환한다. NAME 토큰에 대한 Lex 코드는 다음과 같다:

char [A-Za-z]         name {char}+         %%         {name} { yylval = strdup(yytext);         return NAME; }

 

파일 파싱(file-parsing) 예제의 규칙 섹션은 다음과 같다 :

파일 파싱의 문법(Grammar for the file-parsing)

file : record file         | record         ;         record: NAME EQ AGE {         printf("%s is now %s years old!!!", $1, $3);}         ;         %%

 

추가 C 코드

이제 문법 파일의 최종 섹션인 추가 C 코드에 대해 검토해 보겠다.(이 섹션은 선택 섹션으로 스킵하여도 상관없다: ) main() 같은 함수는 yyparse() 함수를 호출한다 (Lex의 yylex()에 상응하는 Yacc의 함수). 일반적으로 Yacc는 파서가 에러에 직면할 때마다 호출될 yyerror(char msg)에 대한 코드도 필요로 할 것이다. 에러 메시지는 매개 변수로서 파싱된다. 간단한 yyerror(char*)는 다음과 같다.:

int yyerror(char* msg)         {         printf("Error: %s         encountered at line number:%d\n", msg, yylineno);         }

 

yylineno는 행 번호에 대한 정보를 제공한다.

파일 파싱 예제의 main 함수 또한 이 섹션에 포함된다.:

추가 C 코드(Additional C code)

void main()         {             yyparse();         }         int yyerror(char* msg)         {         printf("Error: %s         encountered \n", msg);

 

다음 명령으로 코드를 생성한다.:

$ yacc _d <filename.y>

 

이렇게 해서 출력 파일 y.tab.h와 y.tab.c가 작성되며 UNIX의 표준 C 컴파일러(예를 들면 gcc)를 사용해서 컴파일 할 수 있다.

 

명령 행에 사용 가능한 또 다른 일반적인 옵션

• '-d' ,'-defines' : 문법에 규정된 토큰 유형명, 의미상의 값 유형인 YYSTYPE 그리고 약간의 외부 변수 선언에 대해 매크로 규정을 포함하는 여분의 출력 파일을 작성한다. 파서 출력 파일이 'name.c'라고 명명되면, '-d' 파일은 'name.h'로 명명된다. 분리된 원시 파일에 yylex 규정을 입력할 경우 'name.h'가 필요하다. 그 이유는 yylex는 yylval 변수는 물론, 토큰 유형 코드를 참조하기 때문이다.
• '-b file-prefix' ,'--file-prefix=prefix' : Yacc의 모든 출력 파일명에 사용할 접두사를 지정한다. 마치 출력 파일명이 'prefix.c'인 것처럼 명명을 선택한다.
• '-o outfile' ,--output-file=outfile' : 파서 파일을 위해 출력 파일명을 지정한다. 다른 출력 파일명은 'd' 옵션에서 기술한대로 출력 파일에서 구성된다.

Yacc 라이브러리는 보통 컴파일 단계에 자동적으로 포함된다. 그러나 컴파일 단계 과정에 -ly 옵션을 지정해서 분명하게 포함시킬 수도 있다. 이 경우 컴파일 명령 행은 다음과 같다:

$ cc <source file         names> -ly

 

Lex와 Yacc을 함께 사용하기

지금까지는 Lex와 Yacc를 따로 설명하였다. 이제 이 둘을 함께 사용할 수 있는 방법에 대해 살펴보겠다.

일반적으로 프로그램이 토큰을 반환할 때마다 yylex() 함수를 호출한다. 이러한 호출은 파일의 끝이나 부정확한 토큰이 발생할 때 중지된다.

Yacc에서 생성된 파서는 토큰을 얻기 위하여 yylex()를 호출한다. Yylex()는 Lex로 생성시키거나 직접(scratch) 작성할 수 있다. Lex에서 생성된 lexer를 Yacc와 함께 사용하기 위해서는 패턴이 Lex에 일치될 때마다 토큰을 반환 시켜야 한다. 따라서 Lex에 패턴을 일치시키는 작동의 일반적인 형식은 다음과 같다.:

{pattern} { /* do smthg*/         return TOKEN_NAME; }

 

이렇게 해서 Yacc는 반환된 토큰을 얻는다. Yacc가 -d 옵션으로 .y 파일을 컴파일하면 헤더 파일이 작성되며, 이 헤더 파일은 토큰 각각에 대하여 #define을 가진다. Lex와 Yacc를 같이 사용한다면, 헤더 파일은 Lex의 .lex 파일에 상응하는 C 선언 섹션을 포함해야 한다.

명명과 기간(age)의 파일 파싱 예제로 돌아가서, Lex와 Yacc 파일의 코드를 살펴보자.

Name.y-문법 파일(Name.y - The grammar file)

%         typedef char* string;         #define YYSTYPE string         %}         %token NAME EQ AGE         %%         file : record file         | record         ;         record : NAME EQ AGE {         printf("%s is %s years old!!!\n", $1, $3); }         ;         %%         int main()         {         yyparse();         return 0;         }         int yyerror(char *msg)         {         printf("Error         encountered: %s \n", msg);         }

Name.lex-파서를 위한 Lex 파일(Name.lex - Lex file for the parser )

%{         #include "y.tab.h"                 #include <stdio.h>         #include <string.h>         extern char* yylval;         %}         char [A-Za-z]         num [0-9]         eq [=]         name {char}+         age {num}+         %%         {name} { yylval = strdup(yytext);         return NAME; }         {eq} { return EQ; }         {age} { yylval = strdup(yytext);         return AGE; }         %%         int yywrap()         {         return 1;         }

 

Yacc가 생성한 헤더 파일인 y.tab.h에 참조용 리스트를 기술한다.

y.tab.h-Yacc 생성 헤더 (y.tab.h - Yacc-generated header)

# define NAME 257         # define EQ 258         # define AGE 259

 

이상 Lex와 Yacc에 관한 것은 마무리한다. 어떤 언어든지 컴파일을 해보기 바란다