[컴개/CI] 어휘 분석기 만들기

이번에는 가장 전통적으로 유명한 도구를 이용하여

어휘 분석기를 직접 만들어 보자.

오래 되었지만, 다른 도구들도 이 도구를 기반하여 만들어졌다.

 

어휘 분석기 도구

Lex

전통적인 방법으로 C 언어가 기반이다.

구문 분석기인 yacc과 밀접한 관련이 있으며

발전된 버전인 flex를 더 많이 사용한다.

 

ANTLR

java 기반으로, 구문 분석 시 다시 언급하겠다.

 

기타 도구로는 JavaCC, SableCC가 있다.

 

Lex(렉스)

렉스는 1975년 레스크에 의해 발표된 어휘분석기 생성기이다.

이때 주의할 점은 어휘 분석기가 아니라 어휘 분석기 "생성기"라는 것이다.

사용자가 정의한 프로그램의 정규표현과 실행코드를 입력받아

C언어로 쓰여진 프로그램(어휘분석기)을 출력한다.

 

어휘 분석기의 생성 및 동작

어휘 분석기는 lex를 입력하면 lex.yy.c파일을 출력하는데,

이 파일은 cc(lex library)를 거치면 어휘 분석기 실행 파일이 된다.

 

lex의 선택 규칙

이전 포스트에서 토큰이 두 가지 이상으로 해석될 여지가 있다면

어휘분석기는 각자의 방법으로 토큰을 인식한다고 하였다.

lex는 토큰의 길이가 가장 긴 토큰을 우선으로 한다.

인식될 수 있는 토큰의 길이가 같은 경우 먼저 나타난 규칙의

정규 표현으로 인식한다.

 

lex의 입력

lex의 입력은 크게 3가지로 나뉘는데, 입력 형식은 아래와 같다.

 

<정의 부분>

%{

    실행 코드를 C언어로 기술할 때 필요한 자료 구조, 변수, 상수

    (예: #include)

}%

이름 정의 부분: 특정한 정규 표현을 하나의 이름으로 정의하여 그 형태의 정규표현이 필요할 때만 쓸 수 있도록 해주는 부분

 

%%

<규칙 부분>

: 토큰의 형태를 표현하는 정규 표현과 그 토큰이 인식 되었을 때 처리할 행위를 기술하기 위한 부분인 실행코드.

 

%%

<사용자 부 프로그램 부분>

: 렉스의 입력 작성 시 사용되는 부 프로그램들을 정의

 

예제

%{  /* file name : word.lex
    * 이 프로그램은 파일이름을 입력받고 파일에 들어있는 문장의 라인수 단어수 
    * 문자수를 계산하고 파일이름과 같이 출력한다. */
    unsigned long charCount=0, wordCount=0, lineCount=0;
}%

%%
[^ \t\n]+    {wordCount++; charCount+=yyleng;}  /*  space, \t, \n 제외 모든 문자  */
\n           {charCount++; lineCount++;}  /*  문자 개수 +1, 라인 개수 +1  */
  .          {charCount++;}  /*  default, 모든 경우  */
  
%%
void main() { 
    FILE *file;
    char fn[20];
    printf("Type a input file Name:");
    scanf("%s",fn);
    file=fopen(fn, "r");
    if (!file) {
        fprintf(stderr,"file '%s' could not be opened. \n",fn);
        exit(1);
    }
    yyin=file;
    yylex();
    printf("%d %d %d %s \n", lineCount, wordCount, charCount,fn);
}
yywrap() { return 1; /* 처리의 종료 */ }

위와 같은 파일을 아래로 바꿀 수 있다.

 

%{  /* file name : word.lex
    * 이 프로그램은 파일이름을 입력받고 파일에 들어있는 문장의 라인수 단어수 
    * 문자수를 계산하고 파일이름과 같이 출력한다. */
    unsigned long charCount=0, wordCount=0, lineCount=0;
}%
word [^ \t\n]+
eol  \n

%%
{word}       {wordCount++; charCount+=yyleng;}  /*  space, \t, \n 제외 모든 문자  */
{eol}        {charCount++; lineCount++;}  /*  문자 개수 +1, 라인 개수 +1  */
  .          {charCount++;}  /*  default, 모든 경우  */
  
%%
void main() { 
    FILE *file;
    char fn[20];
    printf("Type a input file Name:");
    scanf("%s",fn);
    file=fopen(fn, "r");
    if (!file) {
        fprintf(stderr,"file '%s' could not be opened. \n",fn);
        exit(1);
    }
    yyin=file;
    yylex();
    printf("%d %d %d %s \n", lineCount, wordCount, charCount,fn);
}
yywrap() { return 1; /* 처리의 종료 */ }

위에서 변수를 정의해주어, [^ \t\n]대신 {word}를 사용했음을 볼 수 있다.

 

렉스의 정규 표현

• * : 0번 이상 반복을 의미([a-zA-Z][a-zA-Z0-9]*: 변수 인식)
• + : 1번 이상 반복을 의미 ([a-z]+: 모든 소문자열 인식)
• ? : 선택을 의미 (ab?c: abc 또는 ac)
• | : 택일을 위한 연산자 ((ab|cd): ab 또는 cd)
• [] : 문자들의 클래스를 정의하는 데 사용 ([abc]: a, b, c 중 한 문자)
  • - : 범위를 나타내는 연산자 문자 ([a-z]: a부터 z사이 문자 중 1)
  • ^ : 여집합을 표현 ([^*]: *을 제외한 모든 문자)
• " : "사이에 있는 모든 문자는 텍스트로 취급 (a'*'b != a*b)
• \ : [] 밖에서는 한 개의 문자를 escape하기 위해 사용 (XYZ"++" == "XYZ++" == XYZ\+\+)
  • [] 안에서는 C언어의 escape 문자열로 간주함 ([ \t\n]: 공백, 탭, 줄바꿈 중 1)
• ^ : 라인의 시작을 인식 (^abc: 라인의 시작에서 abc가 있을 때만 토큰으로 처리)
• $ : 라인의 끝에서만 인식
• / : 접미 문맥을 명시할 때 사용 (ab/cd: ab 다음에 cd가 이어서 있을 때만 ab를 토큰으로 처리)
• . : newline 문자를 제외한 모든 문자들 ("--".*: --부터 라인의 끝까지)
• {} : 정의된 이름을 치환식으로 확장할 때 사용

 

렉스 실행코드 내의 총괄 변수와 함수

- yyleng: 매칭된 토큰의 문자열의 길이를 저장하고 있는 변수

- yytext: 매칭된 토큰의 문자열을 담은 변수

- yylval: 매칭된 토큰값을 담은 변수

- yywarp(): 렉스가 입력의 끝을 만났을 때 호출하는 함수, 정상적인 경우 호출값은 1이다.

 

또 다른 예제를 보겠다.

%{
    /* calc.lex */
#include "global.h"
#include "calc.h"
#include <stdlib.h> 
%}
white [ \t]+
digit [0-9]
integer {digit}+
exponent [eE]([+-])?{integer}
real {integer}("."{integer})?({exponent})? 

%%
{white} {}
{real} { yylval=atof(yytext);
return(NUMBER); }
"+" { return(PLUS); }
"-" { return(MINUS);}
"*" { return(TIMES); }
"/" { return(DIVIDE); }
"^" { return(POWER); }
"(" { return(LEFT_PARENTHESIS); } 
")" { return(RIGHT_PARENTHESIS); }
"\n" { return(END); } 

%%
int yywrap(void) { 
    return 1;
}

위 예제는 앞서 나왔던 wordcount와 어떤 차이점이 있을까?

return문이 많다는 점과, 구문 분석이 main문이 된다는 점,

getToken() 역할을 yylex가 한다는 점이 차이점이 될 수 있겠다.