경수

제가 접하는 많은 것들을 공유하고 싶습니다.

2 minute read

토큰화하는 방법

이전 장에서 토큰화가 무엇인지 알아봤다.

우리는 산업역군의 프로그래머이기 때문에 구현가능한 형태를 원한다. 예제: flex 를 이용해서 간단히 토큰화를 어떻게 하는지 살펴보겠다.

flex 가 무엇인지 살펴보면

flex는 《fast lexical analyzer generator》의 줄임말로 lex의 기능을 개선한 자유 소프트웨어이다. 주로 bison과 쌍을 이루어 구문 분석기를 만드는 데 사용된다. flex를 이용하면 C로 구문 문석 코드를 만들 수 있다. 한편 C++ 코드를 만들어 주는 비슷한 기능을 하는 프로그램으로 flex++가 있으며 flex와 함께 배포된다. 작성자는 “Vern Paxson”씨로 1987년도에 처음 만들어졌다.

앞 장에서 봤듯 입력된 문법이 적법한지 상관없이 어떤 종류의 문자열인가를 판단하는 1차 분류로 생각하면 된다.

%{
  Prologue
%} 
Bison declarations 
%%
Grammar rules
%% 
Epilogue

구조는 위와 같은데, 우리는 마지막 Epilogue 는 쓰지 않을 것이다. 처음 %{ … %} 사이에는 include 문들이 오고, Bison declarations 에는 flex 가 해당 문법파일을 어떻게 컴파일할것인지 옵션이 담긴다. 다음으로 Grammer Rules 에 우리가 분류해야 할 토큰 규칙들이 위치한다. 자세한 것은 인터넷 검색을 통해 해결하도록 하자. flex 에 대한 것들을 자세히 설명하기보다 바로 예제를 통해 이해하도록 한다.

예를 들어 보자.

%{
#include <iostream>
#include <cstdlib>
#include "scanner.h"
using namespace std;
#define yyterminate() 0;
%}
%option nodefault
%option noyywrap
%option c++
%option yyclass="Scanner"
%option yylineno
%%
[a-z][a-z0-9]* { 
    std::cout << yytext << std::endl;
    return 11;
} 
[0-9][0-9]* {
    std::cout << yytext << std::endl;
    return 12;
} 
= {
    std::cout << yytext << std::endl;
    return 13;
} 
[\n\t ] {
} 
. { 
} 
<<EOF>> { 
    std::cout << "EOF" << std::endl;
    return yyterminate(); 
} 
%%

%% 사이의 문법만 주목해서 보자. 정규식 { … } 형태로 기술되는데, 블록{} 사이에는 C/C++ 코드가 들어갈 수 있다.

이것만 기억하면 된다. 좌측에 정규식이 평가될 때 {} 사이의 코드가 실행된다.

// scanner.h
class Scanner : public yyFlexLexer {
    public:
        Scanner(std::istream *in) : yyFlexLexer(in) {} 
        virtual int yylex(); 
};

// lex.yy.cc
#define YY_DECL int Scanner::yylex() 
...
#include "scanner.h"
...
YY_DECL
{
	register yy_state_type yy_current_state;
	register char *yy_cp, *yy_bp;
	register int yy_act;
    ...
}

case 1:
YY_RULE_SETUP
#line 14 "scanner.l"
{ 
    std::cout << yytext << std::endl;
    return 11;
} 
	YY_BREAK
case 2:
YY_RULE_SETUP
#line 18 "scanner.l"
{
    std::cout << yytext << std::endl;
    return 12;
} 
	YY_BREAK
case 3:
YY_RULE_SETUP
#line 22 "scanner.l"
{
    std::cout << yytext << std::endl;
    return 13;
} 
	YY_BREAK
case 4:
/* rule 4 can match eol */
YY_RULE_SETUP
#line 26 "scanner.l"
{
} 
	YY_BREAK
case 5:
YY_RULE_SETUP
#line 28 "scanner.l"
{ 
} 
	YY_BREAK
case YY_STATE_EOF(INITIAL):
#line 30 "scanner.l"
{ 
    std::cout << "EOF" << std::endl;
    return yyterminate(); 
} 
	YY_BREAK

위 코드를 보면 scanner.l 이 flex를 이용하여 생성된 lex.yy.cc 파일에 블록 {} 사이의 코드가 그대로 들어간 모습을 볼 수 있다.

▾ tutorial1/
    main.cpp
    scanner.h
    scanner.l

$ cd tutorial1 
$ flex scanner.l && g++ lex.yy.cc main.cpp -std=c++11 && ./a.out

일부러 흐름을 잘 보여주기 위해 당분간은 CMake 를 쓰지 않겠다. 컴파일 되는 흐름을 잘 이해해야 한다. 먼저 flex 명령어를 통해 lex.yy.cc 가 생긴다. lex.yy.cc 안에는 %option yyclass="Scanner" 에 의해 YY_DECL 매크로가 정의된다.

또한, Scanner::yylex 가 overriding 으로 구현된다.

렉서파일에 scanner.h 를 쓰고 또 Scanner 클래스가 flex 를 쓰고, 생성된 파일(lex.yy.cc) 에서 scanner.h 를 쓰는 이상한 기분이지만 이 상호작용을 잘 이해하고 넘어가기 바란다.

// main.cpp
    std::istringstream is(R"(
    apple 5543 hello world =
    )"); 
    Scanner scanner(&is);
    while(1) {
        int t = scanner.yylex();
        if(t == 0) {
            break;
        }
        std::cout << t << std::endl;
    }

위 프로그램에 의해 flex 를 실행할 수 있다.

apple 5543 hello world = 입력된 문자열이 이와 같을 때 토큰 분류기는 11 12 11 11 13 과 같이 반환된다. 이렇게 토큰화를 통해 숫자형 배열에 담은 후 구문분석(Parsing)을 하게 된다.

동작하는 예제는 git clone https://github.com/hsnks100/dreampiler.git 의 tutorial1

Updated:

You May Also Enjoy