Flex (어휘분석기)

1. 개요

Flex는 C로 작성된 어휘 분석기 생성기로, 1987년경 번 팩슨이 개발했으며 반 제이콥슨의 아이디어를 기반으로 한다. Flex는 정규 표현식을 사용하여 문자 파싱 및 토큰화를 수행하며, C 및 C++ 코드를 생성할 수 있다. 하지만 유니코드 직접 지원, 재진입성, 유닉스 환경 의존성, 다른 언어와의 연동에 제한이 있으며, flex++는 C++용 어휘 분석기로서 임베디드 시스템과 같은 환경에서 유용하게 사용될 수 있다.

2. 역사

Flex는 번 팩슨(Vern Paxson)이 1987년경 C로 작성했으며, 반 제이콥슨(Van Jacobson)의 많은 아이디어와 영감을 받았다. 초기 버전은 제프 포스캔저(Jef Poskanzer)가 만들었으며, 빠른 테이블 표현은 반 제이콥슨이 설계하고 케빈 궝(Kevin Gong)과 번 팩슨이 구현했다.

2.1. 초기 개발

번 팩슨이 1987년경 C 언어로 Flex를 작성했으며, 반 제이콥슨의 많은 아이디어와 영감을 받았다. 제프 포스캔저가 초기 버전을 만들었다.

2.2. 핵심 구현

반 제이콥슨이 빠른 테이블 표현의 부분적인 구현을 설계했다. 이 구현은 케빈 궝(Kevin Gong)과 번 팩슨이 수행했다.

3. 예제

다음은 PL/0 프로그래밍 언어를 위한 Flex 스캐너의 예시이다. Flex를 사용하여 PL/0 언어의 어휘 분석을 수행하는 방법을 보여준다.

```c
%{
#include "y.tab.h"
%}

digit [0-9]
letter [a-zA-Z]

%%
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/" { return SLASH; }
"(" { return LPAREN; }
")" { return RPAREN; }
";" { return SEMICOLON; }
"," { return COMMA; }
"." { return PERIOD; }
":=" { return BECOMES; }
"=" { return EQL; }
"<>" { return NEQ; }
"<" { return LSS; }
">" { return GTR; }
"<=" { return LEQ; }
">=" { return GEQ; }
"begin" { return BEGINSYM; }
"call" { return CALLSYM; }
"const" { return CONSTSYM; }
"do" { return DOSYM; }
"end" { return ENDSYM; }
"if" { return IFSYM; }
"odd" { return ODDSYM; }
"procedure" { return PROCSYM; }
"then" { return THENSYM; }
"var" { return VARSYM; }
"while" { return WHILESYM; }
{letter}({letter}|{digit})* {
yylval.id = strdup(yytext);
return IDENT; }
{digit}+ { yylval.num = atoi(yytext);
return NUMBER; }
[ \t\n\r] /* skip whitespace */
. { printf("Unknown character [%c]\n",yytext[0]);
return UNKNOWN; }
%%

int yywrap(void){return 1;}

3.1. PL/0 스캐너 예제

다음은 PL/0 프로그래밍 언어를 위한 Flex 스캐너의 예시이다.

인식되는 토큰은 다음과 같다: '+', '-', '*', '/', '=', '(', ')', ',', ';', '.', ':=', '<', '<=', '<>', '>', '>=';
숫자: `0-9 {0-9}`; 식별자: `a-zA-Z {a-zA-Z0-9}` 및 키워드: `begin`, `call`, `const`, `do`, `end`, `if`, `odd`, `procedure`, `then`, `var`, `while`.

```c
%{
#include "y.tab.h"
%}

digit [0-9]
letter [a-zA-Z]

%%
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/" { return SLASH; }
"(" { return LPAREN; }
")" { return RPAREN; }
";" { return SEMICOLON; }
"," { return COMMA; }
"." { return PERIOD; }
":=" { return BECOMES; }
"=" { return EQL; }
"<>" { return NEQ; }
"<" { return LSS; }
">" { return GTR; }
"<=" { return LEQ; }
">=" { return GEQ; }
"begin" { return BEGINSYM; }
"call" { return CALLSYM; }
"const" { return CONSTSYM; }
"do" { return DOSYM; }
"end" { return ENDSYM; }
"if" { return IFSYM; }
"odd" { return ODDSYM; }
"procedure" { return PROCSYM; }
"then" { return THENSYM; }
"var" { return VARSYM; }
"while" { return WHILESYM; }
{letter}({letter}|{digit})* {
yylval.id = strdup(yytext);
return IDENT; }
{digit}+ { yylval.num = atoi(yytext);
return NUMBER; }
[ \t\n\r] /* skip whitespace */
. { printf("Unknown character [%c]\n",yytext[0]);
return UNKNOWN; }
%%

int yywrap(void){return 1;}

4. 내부 구조

Flex는 결정적 유한 오토마타(DFA)를 사용하여 문자 파싱 및 토큰화를 수행한다. DFA는 정규 언어를 인식하는 이론적인 기계이며, 튜링 기계 집합의 부분 집합이자 읽기 전용 오른쪽 이동 튜링 기계와 동등하다. 구문은 정규 표현식을 기반으로 한다. 비결정적 유한 오토마타(NFA)도 참고할 수 있다.

4.1. 결정적 유한 오토마타 (DFA)

결정적 유한 오토마타(DFA)는 정규 언어를 인식하는 이론적인 기계이다. 이 기계는 튜링 기계 집합의 부분 집합이며, 읽기 전용 오른쪽 이동 튜링 기계와 동등하다. Flex는 DFA를 사용하여 문자 파싱 및 토큰화를 수행하며, 구문은 정규 표현식을 기반으로 한다. 비결정적 유한 오토마타(NFA)도 참고할 수 있다.

5. 문제점 및 한계

Flex는 몇 가지 문제점과 한계를 가지고 있다.

시간 복잡도

Flex는 일반적으로 입력 길이에 대해 $O(n)$의 시간 복잡도를 갖지만, `REJECT` 매크로를 사용하면 비선형 성능의 스캐너를 생성할 수 있다. `REJECT` 기능은 기본적으로 활성화되어 있지 않으며, 성능에 미치는 영향 때문에 Flex 매뉴얼에서 사용을 권장한다.

재진입성 (Reentrancy)

기본적으로 Flex에 의해 생성된 스캐너는 재진입 가능하지 않아, 여러 스레드에서 사용하는 프로그램에 문제를 야기할 수 있다. Flex는 재진입성을 위한 옵션을 제공하며, 자세한 내용은 Flex 매뉴얼에서 확인할 수 있다.

유닉스 환경 의존성

생성된 스캐너는 유닉스 특정 unistd.h 헤더 파일을 참조하는 경우가 있다. 이를 피하려면 `%option nounistd`를 사용해야 한다. 또한, 생성된 코드에서 isatty (유닉스 라이브러리 함수) 호출 문제가 발생할 수 있는데, `%option never-interactive`를 통해 해결할 수 있다.

다른 언어와의 연동

Flex는 C와 C++ 코드만 생성 가능하다. 다른 언어에서 사용하려면 SWIG와 같은 언어 바인딩 도구가 필요하다.

유니코드 지원

Flex는 1바이트(8비트) 바이너리 값 일치로 제한되어 유니코드를 직접 지원하지 않는다. RE/flex 등 다른 도구들은 유니코드 일치를 지원한다.

5.1. 시간 복잡도

Flex는 일반적으로 입력 길이에 대해 $O(n)$의 시간 복잡도를 갖는다. 즉, 각 입력 기호에 대해 상수 횟수의 연산을 수행한다. 이 상수는 상당히 낮다. GCC는 DFA 매치 루프에 대해 12개의 명령어를 생성한다. 이 상수는 토큰의 길이, 정규 표현식의 길이 및 DFA의 크기와 무관하다는 점에 유의해야 한다.

그러나 매우 긴 토큰과 일치할 가능성이 있는 스캐너에서 `REJECT` 매크로를 사용하면 Flex가 비선형 성능의 스캐너를 생성할 수 있다. 이 기능은 선택 사항이다. 이 경우 프로그래머는 이미 일부 입력을 일치시킨 후 "다시 시도"하도록 Flex에 명시적으로 지시한 것이다. 이렇게 하면 DFA가 다른 수락 상태를 찾기 위해 백트래킹하게 된다. `REJECT` 기능은 기본적으로 활성화되어 있지 않으며, 성능에 미치는 영향 때문에 Flex 매뉴얼에서 사용을 권장하지 않는다.

5.2. 재진입성 (Reentrancy)

기본적으로 Flex에 의해 생성된 스캐너는 재진입 가능하지 않다. 이는 생성된 스캐너를 서로 다른 스레드에서 사용하는 프로그램에 심각한 문제를 야기할 수 있다. 이러한 문제를 해결하기 위해 Flex는 재진입 가능성을 달성하기 위한 옵션을 제공한다. 이러한 옵션에 대한 자세한 설명은 Flex 매뉴얼에서 찾을 수 있다.

5.3. 유닉스 환경 의존성

일반적으로 생성된 스캐너는 유닉스에 특정한 unistd.h 헤더 파일에 대한 참조를 포함한다. unistd.h를 포함하는 코드가 생성되는 것을 피하려면, %option nounistd를 사용해야 한다. 또 다른 문제는 생성된 코드에서 발견될 수 있는 isatty(유닉스 라이브러리 함수)에 대한 호출이다. %option never-interactive는 flex가 isatty를 사용하지 않는 코드를 생성하도록 강제한다.

5.4. 다른 언어와의 연동

Flex는 C와 C++에 대한 코드만 생성할 수 있다. Flex가 생성한 스캐너 코드를 다른 언어에서 사용하려면 SWIG와 같은 언어 바인딩 도구를 사용할 수 있다.

5.5. 유니코드 지원

Flex는 1바이트(8비트) 바이너리 값 일치로 제한되어 있어 유니코드를 직접 지원하지 않는다. RE/flex 및 다른 대안들은 유니코드 일치를 지원한다.

6. Flex++

flex++는 C++용 어휘 분석기로, flex 패키지에 포함되어 있다. 생성된 코드는 입력 자체에 종속되지 않는 한, 메모리 할당기(malloc 또는 사용자가 제공한 대안)를 제외하고는 어떠한 런타임이나 외부 라이브러리에도 의존하지 않는다. 이는 기존의 운영체제나 C 런타임 기능을 사용할 수 없는 임베디드 시스템 및 유사한 상황에서 유용할 수 있다.

flex++로 생성된 C++ 스캐너는 `FlexLexer.h` 헤더 파일을 포함하며, 이 헤더 파일은 두 개의 C++ 생성 클래스의 인터페이스를 정의한다.

6.1. 특징

flex++는 C++용 어휘 분석기로, flex 패키지에 포함되어 있다. 생성된 코드는 (입력 자체에 종속되지 않는 한) 메모리 할당기(malloc 또는 사용자가 제공한 대안)를 제외하고는 어떠한 런타임이나 외부 라이브러리에도 의존하지 않는다. 이는 기존의 운영체제나 C 런타임 기능을 사용할 수 없는 임베디드 시스템 및 유사한 상황에서 유용할 수 있다.

flex++로 생성된 C++ 스캐너는 `FlexLexer.h` 헤더 파일을 포함하며, 이 헤더 파일은 두 개의 C++ 생성 클래스의 인터페이스를 정의한다.

6.2. 생성 클래스

flex++로 생성된 C++ 스캐너는 `FlexLexer.h` 헤더 파일을 포함하며, 이 헤더 파일은 두 개의 C++ 생성 클래스의 인터페이스를 정의한다.