[루아1.1] lex.c 읽기

10 분 소요

Lex.c

Lua.lex를 읽고 나서 꽤나 찜찜했습니다. 호출하는 함수라든가 정의한 함수들이 없거나 쓰지 않았거든요. 쓰지 않는건 상관 없는데 호출하는 함수가 없으면 링커에서 에러가 납니다. 뭔가 이상하다 싶어서 봤더니 Lex.c라는 파일이 보입니다. 그리고 쭉 보니까, lexer만 따로 구현한것 같습니다. 그러니까 Lua.lex는 안쓴다는 말이지요. 그러면 이제 Lua.lex가 왜 아귀가 맞지 않는지 알 것 같습니다. 그리고 저는 쓰지 않는 Lua.lex를 열심히 읽은 셈이 되네요. 그렇다고 해서 무의미한 작업을 한 것은 아닙니다. Lex.c가 Lua.lex를 다시 구현한 것일테니까요.

루아 1.1 소스 코드에 보면 doc이란 디렉터리가 있습니다. 여기에 lua.ps 파일을 읽어보면 이런 내용이 나옵니다.

Code for compilation of extension programs can be built with standard tools, such as lex and yacc. The existence of good tools for compiler construction, which became widely available in the late seventies, was the main reason for the sprouting of several little languages, specially in Unix environments. Out implementation of Lua uses yacc for syntactical analysis. Initially, we wrote the lexical analyzer using lex. After performance profiles with production programs, we detected that this module was responsible for almost half of the time required for loading and executing extension programs. We then rewrote this module directly in C; the new lexcial analyzer is more that twice as fast as the old one.

늘 그렇듯 대충 후려쳐서 번역하면 이렇습니다. lex랑 yacc 써서 파서랑 낱말 분석기를 구현했다. 실행 시간의 절반을 로딩에서 까먹었다. 그래서 낱말 분석기(lexer)를 C로 다시 짰더니 두 배 넘게 빨라졌다. 이런 내용입니다. Lex.c가 C로 다시 짰다는 코드인가 봅니다.

그러면 Lex.c를 읽겠습니다. 다행히 짧네요. Lua.lex를 읽으면서 토큰이 어떤 종류가 있고 토큰별로 어떤 작업을 하는지 알고 있으므로 그 내용을 어떤식으로 구현 했는지만 보면 됩니다.

#include <ctype.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

#include "opcode.h"
#include "hash.h"
#include "inout.h"
#include "table.h"
#include "y.tab.h"

#define next() { current = input(); }
#define save(x) { *yytextLast++ = (x); }
#define save_and_next()  { save(current); next(); }

static int current;
static char yytext[256];
static char *yytextLast;

static Input input;

void lua_setinput (Input fn)
{
  current = ' ';
  input = fn;
}

char *lua_lasttext (void)
{
  *yytextLast = 0;
  return yytext;
}


static struct 
  {
    char *name;
    int token;
  } reserved [] = {
      {"and", AND},
      {"do", DO},
      {"else", ELSE},
      {"elseif", ELSEIF},
      {"end", END},
      {"function", FUNCTION},
      {"if", IF},
      {"local", LOCAL},
      {"nil", NIL},
      {"not", NOT},
      {"or", OR},
      {"repeat", REPEAT},
      {"return", RETURN},
      {"then", THEN},
      {"until", UNTIL},
      {"while", WHILE} };

#define RESERVEDSIZE (sizeof(reserved)/sizeof(reserved[0]))

Lex.c 파일의 초반부 코드입니다. #include 구문은 Lua.lex와 같습니다. 한번씩 대충 훑어본 파일들입니다. 그리고 이어서 매크로 세 개가 나옵니다. next(), save(), save_and_next()입니다. 이 매크로 세 개는 바로 아래 나오는 전역 정적 변수 세 개(current, yytext, yytextLast)를 사용하는 코드로 치환됩니다. 이름으로 추정해 보건데 current는 현재 낱말 분석 대상 문자, yytext는 낱말 분석 완료한 문자열, yytextLast는 yytext에 값을 한 글자씩 넣기 위한 문자열 포인터로 보입니다. yytext는 lex에서 쓰는 내부 변수 이름과 같으므로 역할도 같을 것으로 예상합니다.

lua_setinput() 함수는 current 변수를 비우고 input 변수에 함수 포인터를 저장합니다. 함수 포인터는 어디서 올까요? lua_setinput() 함수는 두 군데서 호출합니다.

int lua_openfile (char *fn)
{
 lua_linenumber = 1;
 lua_setinput (fileinput);
 fp = fopen (fn, "r");
 if (fp == NULL) return 1;
 if (lua_addfile (fn)) return 1;
 return 0;
}

int lua_openstring (char *s)
{
 lua_linenumber = 1;
 lua_setinput (stringinput);
 st = s;
 {
  char sn[64];
  sprintf (sn, "String: %10.10s...", s);
  if (lua_addfile (sn)) return 1;
 }
 return 0;
}

루아 코드를 파일이나 문자열에서 컴파일러로 넘길 수 있는가 봅니다. 파일에서 루아 코드를 받을 때는 fileinput() 함수의 함수 포인터를 넘기고 문자열에서 루아 코드를 받을 때는 stringinput() 함수의 함수 포인터를 넘깁니다. fileinput() 함수와 stringinput() 함수는 Inout.c 파일에 있습니다.

/*
** Function to get the next character from the input file
*/
static int fileinput (void)
{
 int c = fgetc (fp);
 return (c == EOF ? 0 : c);
}

/*
** Function to get the next character from the input string
*/
static int stringinput (void)
{
 st++;
 return (*(st-1));
}

결국 입력 수단(파일, 문자열)에 상관없이 한 글자씩 입력 받아 오려고 만든 인터페이스가 Input 함수 포인터였네요. 그래서 위에서 읽었던 next() 매크로를 쓰면 fileinput() 함수와 stringinput() 함수 둘 중 하나가 실행되면서 current 정적 전역 변수에 입력 데이터에서 한 글자를 읽어 저장합니다.

소박하지만 이렇게 루아 구현 중 한 흐름을 파악했습니다. 뿌듯하군요.

이어서 나오는 이름 없는 구조체는 예약어 토큰 종류를 이름과 매치해 놓은 정적 전역 변수 입니다. 그래서 변수 이름도 reserved입니다. 아마 나중에 패턴 매칭 코드 쉽게 짜려고 미리 만들어 둔것일겁니다. RESERVEDSIZE 상수는 흔한 태크닉입니다. 구조체 배열이 아이템이 몇개 인지 미리 계산해 두는 것이지요.

이후로 함수 딱 두 개가 있습니다. 하나는 짧고 하나는 길군요. 짧은 것 먼저 보겠습니다.

int findReserved (char *name)
{
  int l = 0;
  int h = RESERVEDSIZE - 1;
  while (l <= h)
  {
    int m = (l+h)/2;
    int comp = strcmp(name, reserved[m].name);
    if (comp < 0)
      h = m-1;
    else if (comp == 0)
      return reserved[m].token;
    else
      l = m+1;
  }
  return 0;
}

간단합니다. 바로 위에 있던 예약어 구조체 배열에서 예약어를 찾아 토큰을 리턴하는 함수 입니다.

"local"					return LOCAL;
"if"					return IF;
"then"					return THEN;
"else"					return ELSE;
"elseif"				return ELSEIF;
"while"					return WHILE;
"do"					return DO;
"repeat"				return REPEAT;

Lua.lex에 있던 위와 같은 패턴 코드를 구현한 것이지요. 간단합니다.

Lex.c 파일의 핵심은 yylex() 함수입니다. yylex() 함수는 원래 yacc과 lex가 서로 약속으로 정해 놓은 함수 이름입니다. lex 파일을 lex 툴에 돌려서 C 파일을 만들면 내부에 yylex() 함수를 만듭니다. 그러면 yacc 툴이 만든 yyparse() 함수에서 토큰이 필요할 때마다 yylex() 함수를 호출하는 식이지요. 이들 관계는 lex와 yacc 관련 자료를 인터넷에서 찾으면 많이 나옵니다.

yylex() 함수는 뺑뺑이 도는 큰 switch-case 구문으로 구현되 있습니다. 상태 머신(state machine) 구현하고 비슷하게 만든 것 같네요. 코드가 기니까, 조각 조각 짤라서 읽어보겠습니다.

int yylex ()
{
  while (1)
  {
    yytextLast = yytext;
    switch (current)
    {
      case '\n': lua_linenumber++;
      case ' ':
      case '\t':
        next();
        continue;

무한 루프로 뺑뺑이 도는 함수 입니다. 토큰 찾을 때까지 루프 돌다가 토큰 찾으면 리턴하는 식으로 구현됐습니다. 리턴 코드는 다음에 나올 겁니다. 위 코드는 Lua.lex의 상단에 있던 규칙하고 같군요. 줄바꿈이 나오면 lua_linenumber 변수를 하나 증가합니다. 공백이나 탭이 나오면 next() 매크로를 호출해서 한 글자 입력받고 yytext를 초기화 합니다. continue가 동작해서 while 루프 시작 위치로 돌아가면 yytextLast = yytext가 실행됩니다. 토큰의 값은 아마 포인터를 늘리면서 yytextLast 변수에 넣을 것이기 때문에 yytextLast 변수를 yytext 문자열 배열의 주소로 초기화하는 것은 토큰 값을 초기화하는 것과 같은 의미입니다.

추가로 yytext는 256바이트 문자 타입 배열이기 때문에 루아는 256자가 넘어가는 토큰은 처리하지 못합니다.

      case '$':
	next();
	while (isalnum(current) || current == '_')
          save_and_next();
        *yytextLast = 0;
	if (strcmp(yytext, "debug") == 0)
	{
	  yylval.vInt = 1;
	  return DEBUG;
        }
	else if (strcmp(yytext, "nodebug") == 0)
	{
	  yylval.vInt = 0;
	  return DEBUG;
        }
	return WRONGTOKEN;

case 구문으로 처음 비교하는 문자가 $입니다. 딱 보자마자 Lua.lex에서 봤던 $debug, $nodebug가 떠오르네요. 아마 이 둘을 찾는 코드일겁니다. 현재 글자가 $면 다음 글자를 봐야겠지요. $ 다음에 알파벳이나 숫자 혹은 _가 나오면 yytext에 저장합니다. 그리고 null terminate해서 yytext 문자열을 완성합니다. 이어서 debug가 나오면 yylval.vInt에 1넣고 DEBUG 토큰 리턴, nodebug가 나오면 yylval.vInt에 0넣고 DEBUG 토큰 리턴합니다. 위 조건이 아니면 WRONGTOKEN을 리턴합니다. 그래서 $abc123debug면 yytext에는 “abc123”이 들어가고 DEBUG 토큰을 리턴하는 코드로 보입니다. 물론 $_a_323_bb_debug 이런 토큰도 허용하고요.

      case '-':
        save_and_next();
        if (current != '-') return '-';
        do { next(); } while (current != '\n' && current != 0);
        continue;
  
      case '<':
        save_and_next();
        if (current != '=') return '<';
        else { save_and_next(); return LE; }
  
      case '>':
        save_and_next();
        if (current != '=') return '>';
        else { save_and_next(); return GE; }
  
      case '~':
        save_and_next();
        if (current != '=') return '~';
        else { save_and_next(); return NE; }

이어서 나오는 case 구문은 같은 패턴으로 4개가 연속해서 나옵니다. 그래서 하나만 읽고 이해하면 되겠네요. 맨 위만 보죠. -가 나오면 일단 yytext에 저장하고 다음 글자가 -인지 봅니다. 다음 글자가 -가 아니면 -를 리턴하고 끝냅니다. 그러면 yacc은 -을 전달 받습니다. 만약 -또 나오면, 즉, –이 나오면 다음 줄바꿈이 나오거나 문자열 끝까지 그냥 쭉 next()하면서 지나갑니다. 왜냐면 –는 주석이니까요. 그 아래도 비슷합니다. < 다음에 =가 나오면 LE 토큰을 리턴하고 그렇지 않으면 그냥 < 자체를 리턴하고 끝냅니다. 같은 패턴으로 GE, NE도 처리합니다.

      case '"':
      case '\'':
      {
        int del = current;
        next();  /* skip the delimiter */
        while (current != del) 
        {
          switch (current)
          {
            case 0: 
            case '\n': 
              return WRONGTOKEN;
            case '\\':
              next();  /* do not save the '\' */
              switch (current)
              {
                case 'n': save('\n'); next(); break;
                case 't': save('\t'); next(); break;
                case 'r': save('\r'); next(); break;
                default : save('\\'); break;
              }
              break;
            default: 
              save_and_next();
          }
        }
        next();  /* skip the delimiter */
        *yytextLast = 0;
        yylval.vWord = lua_findconstant (yytext);
        return STRING;
      }

위 구문은 문자열을 처리합니다. 일단 문자열이니까 따옴표가 나와야 겠지요. 루아는 쌍따옴표와 홑따옴표를 둘 다 문자열로 처리합니다. 그래서 쌍따옴표나 홑따옴표를 시작으로 인식하면 문자열 처리를 시작합니다. 그리고 다시 문자열이 나오기 전까지 모든 글자는 yytext에 저장합니다. 문자열은 중간에 개행을 허락하지 않습니다. 그래서 문자열 중간에 개행이 들어가면 WRONGTOKEN을 리턴합니다. 문자열을 다 걸러내서 yytext에 저장하고 나면 lua_findconstant() 함수에 yytext을 넘겨서 어떤 숫자를 리턴받습니다. 그리고 STRING 토큰을 리턴합니다. lua_findconstant() 함수가 어떻게 생겼는지 보겠습니다.

int lua_findconstant (char *s)
{
 int i;
 for (i=0; i<lua_nconstant; i++)
  if (streq(s,lua_constant[i]))
   return i;
 if (lua_nconstant >= MAXCONSTANT-1)
 {
  lua_error ("lua: constant string table overflow"); 
  return -1;
 }
 {
  char *c = calloc(strlen(s)+2,sizeof(char));
  c++;		/* create mark space */
  lua_constant[lua_nconstant++] = strcpy(c,s);
 }
 return (lua_nconstant-1);
}

lua_findconstant() 함수 구현을 구체적으로 보지 않아도 뭐하는 함수인지 알겠습니다. 딱 봐도 문자열을 배열에 저장하고 있다가 배열에 저장되 있는 문자열하고 똑같은 문자열이 파라메터로 오면 배열 인덱스를 리턴하고 아니면 배열에 새로 추가하는 함수입니다. lua_nconstant는 당연히 배열 마지막 인덱스를 기록하는 변수입니다. lua_constant가 문자열 배열인데요. 선언을 보겠습니다.

#ifndef MAXCONSTANT
#define MAXCONSTANT	256
#endif
/* pre-defined constants need garbage collection extra byte */ 
static char tm[] = " mark";
static char ti[] = " nil";
static char tn[] = " number";
static char ts[] = " string";
static char tt[] = " table";
static char tf[] = " function";
static char tc[] = " cfunction";
static char tu[] = " userdata";
static char  	       *constantbuffer[MAXCONSTANT] = {tm+1, ti+1,
						       tn+1, ts+1,
						       tt+1, tf+1,
						       tc+1, tu+1
                                                      };
char  	      	      **lua_constant = constantbuffer;

위 코드를 보면 루아는 문자열을 최대 256개까지만 처리할 수 있습니다. 그리고 기본값으로 문자열 8개를 배열에 미리 넣어 둡니다. 미리 넣어두는 문자열이 예약어와 같은 문자열인데 왜 인지는 모르겠습니다. 나중에 알게 되겠지요.

그럼 다시 Lex.c 파일로 가서 마져 읽겠습니다.

      case 'a': case 'b': case 'c': case 'd': case 'e':
      case 'f': case 'g': case 'h': case 'i': case 'j':
      case 'k': case 'l': case 'm': case 'n': case 'o':
      case 'p': case 'q': case 'r': case 's': case 't':
      case 'u': case 'v': case 'w': case 'x': case 'y':
      case 'z':
      case 'A': case 'B': case 'C': case 'D': case 'E':
      case 'F': case 'G': case 'H': case 'I': case 'J':
      case 'K': case 'L': case 'M': case 'N': case 'O':
      case 'P': case 'Q': case 'R': case 'S': case 'T':
      case 'U': case 'V': case 'W': case 'X': case 'Y':
      case 'Z':
      case '_':
      {
        int res;
        do { save_and_next(); } while (isalnum(current) || current == '_');
        *yytextLast = 0;
        res = findReserved(yytext);
        if (res) return res;
        yylval.pChar = yytext;
        return NAME;
      }

알파벳이나 _로 시작하는 글자가 오면 일단 NAME 토큰으로 간주하고 검사를 시작합니다. 그래서 알파벳이나 숫자 혹은 _가 아닐 때까지 계속 글자를 넘기면서 yytext에 저장하다가, 그것이 아닌 글자가 나오면 스캔을 중단하고 yytext가 예약어인지 검사합니다. 만약 예약어라면 어떤 예약어인지 인덱스를 리턴합니다. 아마 yacc 쪽에서 처리를 할 것 같습니다. yacc에 예약어 토큰의 문자열 포인터를 넘겨 주고 NAME 토큰을 리턴합니다.

      case '.':
        save_and_next();
        if (current == '.') 
        { 
          save_and_next(); 
          return CONC;
        }
        else if (!isdigit(current)) return '.';
        /* current is a digit: goes through to number */
        goto fraction;

.이 나오면 이게 문자열 붙이는 ..인지 소수점 표시하는 것인지 구분해야 합니다. 그래서 .다음에 .이 또 나오면 CONC 토큰을 리턴합니다. 그게 아니면 일단 다음 글자가 숫자인지 검사해보고 숫자가 아니면 그냥 .자체를 리턴하고 숫자면 fraction 레이블로 점프합니다. 오! goto가 나왔네요.

여담으로, 요즘도 그렇게 가르치는지 모르겠는데, 제가 C언어를 공부할 때만해도 goto를 쓰지 말라고 배웠습니다. 아예 책에 써 있었어요. 그런데 경력이 십년 넘게 쌓이고 실무에서 이런저런 문제를 해결하는 코드를 많이 작성하다 보니까, goto도 적절하게 필요할 때 잘 쓰면 훌륭한 도구라는 것입니다. 무조건 배척할 건 아니죠.

      case '0': case '1': case '2': case '3': case '4':
      case '5': case '6': case '7': case '8': case '9':
      
        do { save_and_next(); } while (isdigit(current));
        if (current == '.') save_and_next();
fraction: while (isdigit(current)) save_and_next();
        if (current == 'e' || current == 'E')
        {
          save_and_next();
          if (current == '+' || current == '-') save_and_next();
          if (!isdigit(current)) return WRONGTOKEN;
          do { save_and_next(); } while (isdigit(current));
        }
        *yytextLast = 0;
        yylval.vFloat = atof(yytext);
        return NUMBER;

      default: 		/* also end of file */
      {
        save_and_next();
        return *yytext;      
      }

이제 마지막입니다. 딱 봐도 숫자 처리네요. 소수점과 지수 표기법을 모두 처리합니다. 음수도 처리하는 군요. 그리고 숫자를 다 스캔하고 나면 atof() 함수로 문자열을 정수형으로 바꾼다음 yacc로 전달합니다. 토큰은 NUMBER입니다.

댓글남기기