Flex (어휘분석기)

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 스캐너 예제

4. 내부 구조

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

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

5. 문제점 및 한계

Flex는 몇 가지 문제점과 한계를 가지고 있다.
시간 복잡도Flex는 일반적으로 입력 길이에 대해 $O(n)$의 시간 복잡도를 갖지만, `REJECT` 매크로를 사용하면 비선형 성능의 스캐너를 생성할 수 있다. `REJECT` 기능은 기본적으로 활성화되어 있지 않으며, 성능에 미치는 영향 때문에 Flex 매뉴얼에서 사용을 권장한다.<sup>[12]</sup>
재진입성 (Reentrancy)기본적으로 Flex에 의해 생성된 스캐너는 재진입 가능하지 않아, 여러 스레드에서 사용하는 프로그램에 문제를 야기할 수 있다. Flex는 재진입성을 위한 옵션을 제공하며, 자세한 내용은 Flex 매뉴얼에서 확인할 수 있다.<sup>[13]</sup>
유닉스 환경 의존성생성된 스캐너는 유닉스 특정 ''unistd.h'' 헤더 파일을 참조하는 경우가 있다. 이를 피하려면 `%option nounistd`를 사용해야 한다. 또한, 생성된 코드에서 isatty (유닉스 라이브러리 함수) 호출 문제가 발생할 수 있는데, `%option never-interactive`를 통해 해결할 수 있다.<sup>[14]</sup>
다른 언어와의 연동Flex는 C와 C++ 코드만 생성 가능하다. 다른 언어에서 사용하려면 SWIG와 같은 언어 바인딩 도구가 필요하다.
유니코드 지원Flex는 1바이트(8비트) 바이너리 값 일치로 제한되어 유니코드를 직접 지원하지 않는다.<sup>[15]</sup> RE/flex 등 다른 도구들은 유니코드 일치를 지원한다.

5. 1. 시간 복잡도

5. 2. 재진입성 (Reentrancy)

5. 3. 유닉스 환경 의존성

5. 4. 다른 언어와의 연동

5. 5. 유니코드 지원

6. Flex++

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

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

6. 1. 특징

6. 2. 생성 클래스

참조

<sub>[1]</sub> 서적 flex & bison https://books.google[...] O'Reilly Media 2009-08
<sub>[2]</sub> 서적 lex & yacc https://books.google[...] O'Reilly
<sub>[3]</sub> 서적 lex & yacc https://books.google[...] O'Reilly
<sub>[4]</sub> 서적 flex & bison http://oreilly.com/c[...] O'Reilly Media 2009-08
<sub>[5]</sub> 웹사이트 src/usr.bin/lex/ http://bxr.su/o/usr.[...] 2015-12-11
<sub>[6]</sub> 웹사이트 flex(1) http://mdoc.su/-/fle[...]
<sub>[7]</sub> 웹사이트 yacc(1) http://mdoc.su/-/yac[...]
<sub>[8]</sub> 웹사이트 bison-3.0.4 – GNU parser generator http://ports.su/deve[...] 2015-11-15
<sub>[9]</sub> 웹사이트 Is flex GNU or not? https://westes.githu[...]
<sub>[10]</sub> 웹사이트 Flex - a scanner generator - Table of Contents - GNU Project - Free Software Foundation (FSF) https://ftp.gnu.org/[...] 2019-12-05
<sub>[11]</sub> 웹사이트 Flex, version 2.5 A fast scanner generator Edition 2.5, March 1995 https://www.cs.princ[...] 2019-04-20
<sub>[12]</sub> 웹사이트 Performance - Lexical Analysis With Flex, for Flex 2.5.37 https://westes.githu[...] Flex.sourceforge.net 2013-02-25
<sub>[13]</sub> 웹사이트 Reentrant - Lexical Analysis With Flex, for Flex 2.5.37 https://westes.githu[...] Flex.sourceforge.net 2013-02-25
<sub>[14]</sub> 웹사이트 Code-Level And API Options - Lexical Analysis With Flex, for Flex 2.5.37 https://westes.githu[...] Flex.sourceforge.net 2013-02-25
<sub>[15]</sub> 웹사이트 Why you should not use (f)lex, yacc and bison https://tomassetti.m[...] 2022-10-26