정규식에서 파서까지: Lex와 Yacc로 작은 컴파일러 만들기

이 글은 개인 학습 아카이브에 보관된 컴파일러 강의 PDF·슬라이드·코드 예제를 교차 검토해 새로 구성한 학습 노트입니다. 오래된 표기, 오탈자, 실행되지 않는 예시는 본문에서 별도로 바로잡았으며 원본 파일이나 내부 경로는 공개하지 않습니다.

생성기는 정규식과 문법을 실행 가능한 table로 바꾼다

Lex 계열 도구는 regular expression과 action으로 scanner를 만들고, Yacc 계열 도구는 context-free grammar와 semantic action으로 LALR parser를 만든다.

source characters
  -> Lex/flex scanner: yylex()
  -> token kind + semantic value + source location
  -> Yacc/Bison parser: yyparse()
  -> shift/reduce + semantic actions
  -> AST, evaluated value, or IR

아카이브 강의는 전통적인 C interface와 output name을 사용한다. 개념은 여전히 유효하지만 실제 command, generated filename, global variable, runtime library는 구현과 option에 따라 달라진다. 이 글은 historical Lex/Yacc와 modern flex/Bison을 구분해 읽는다.

Lex regular expression dialect

대표 pattern은 다음과 같다.

"if"                     literal
\n                       escaped newline
(aa|bb)(a|b)*c?          grouping, alternation, repetition
[abxz]                   character class
[0-9]                    range
[^0-9abc]                negated class
.                        any character except newline

character class 안에서는 대부분의 metacharacter가 literal이 된다. [-+]나 [+-]는 둘 다 -와 + 중 한 글자를 뜻하도록 hyphen을 edge에 둔 형태다. archived 설명 중 [+-]가 “+부터 모든 문자”를 뜻한다는 부분은 잘못됐다.

^는 bracket 첫 위치에서 negation이고 bracket 밖에서는 beginning-of-line anchor다. 아카이브는 전자만 설명한다. 또 character-class 예제 문맥에서 [ab]* 대신 (ab)*를 적은 부분이 있는데 둘은 다르다. 전자는 a 또는 b의 임의 반복이고 후자는 정확히 문자열 ab의 반복이다.

named definition은 다음처럼 쓴다.

nat        [0-9]+
signedNat  ("+"|"-")?{nat}

설명식에서 nat = ...라고 쓸 수는 있지만 실제 Lex definitions section에는 =를 넣지 않는다.

.l 파일의 세 구역

%{
#include <stdio.h>
/* declarations copied into generated C */
%}

digit [0-9]

%%
{digit}+   { /* action */ }
%%

/* helper functions and optional main */

첫 구역에는 copied C code와 named regex definitions, 둘째에는 pattern/action rules, 셋째에는 helper routine을 둔다. archived delimiter %{ ... }%는 오탈자다. 닫는 delimiter는 %}다.

도구가 전통적으로 만드는 lex.yy.c에는 yylex, 현재 lexeme yytext, input/output stream yyin과 yyout, default output을 위한 ECHO 등이 들어 있다. reentrant flex scanner나 prefix option을 사용하면 이 global interface는 달라질 수 있다.

Longest match와 rule priority

Lex scanner의 핵심 우선순위는 다음과 같다.

1. 현재 위치에서 가장 긴 lexeme를 고른다.
2. 같은 길이면 source에서 먼저 선언한 rule을 고른다.
3. 아무 rule도 맞지 않으면 기본 동작으로 한 문자를 echo한다.

마지막 규칙을 잊으면 “매치되지 않은 문자는 버려진다”고 잘못 예상하기 쉽다. 명시적으로 skip하거나 error token을 반환하지 않으면 default ECHO가 살아 있다.

keyword rule을 identifier보다 먼저 두는 이유도 tie-break다.

"if"                 { return IF; }
[A-Za-z][A-Za-z]*    { return ID; }

if는 길이가 같아 keyword rule이 이기고, ifx는 identifier가 더 길어 ID가 된다.

세 개의 작은 scanner 예제를 검산하기

줄 번호 출력

%{
#include <stdio.h>
int lineno = 1;
%}
line .*\n
%%
{line} { printf("%5d %s", lineno++, yytext); }
%%
int main(void) {
    yylex();
    return 0;
}

pattern이 newline까지 포함하므로 마지막 줄에 newline이 없으면 이 rule은 그 줄을 match하지 않는다. archived smart quote는 C source에 쓸 수 없고, return type이 생략된 main() 대신 표준 signature를 써야 한다.

Decimal을 hexadecimal로 출력

digit  [0-9]
number {digit}+
%%
{number} {
    errno = 0;
    char *end = NULL;
    unsigned long n = strtoul(yytext, &end, 10);
    if (errno == ERANGE || end == yytext || *end != '\0')
        fprintf(stderr, "invalid decimal: %s", yytext);
    else
        printf("%lx", n);
}

이 action은 definitions 영역에서 errno.h, stdio.h, stdlib.h를 포함한다고 가정한다. archived action은 atoi로 모든 decimal lexeme를 다시 출력하면서 값이 9보다 클 때만 “replacement count”를 올린다. 09처럼 text는 바뀌지만 value가 9인 경우 count가 늘지 않으므로 이름과 측정이 맞지 않는다. atoi에는 overflow report도 없다. 실제 도구라면 conversion error와 range를 검사한다.

a로 시작하거나 끝나는 줄

ends_with_a    .*a\n
begins_with_a  a.*\n
%%
{ends_with_a}    ECHO;
{begins_with_a}  ECHO;
.*\n             ;

두 pattern이 같은 전체 줄을 match하면 먼저 선언한 rule이 이긴다. 그 밖의 newline-terminated line은 empty action으로 사라진다. 하지만 newline 없는 마지막 줄은 fallback rule까지 맞지 않아 default action으로 character가 echo될 수 있다. “나머지는 모두 삭제”하려면 EOF 직전 줄도 다루는 rule이 필요하다.

TINY scanner의 token contract

archived example은 다음 definition을 사용한다.

digit       [0-9]
number      {digit}+
letter      [a-zA-Z]
identifier  {letter}+
newline     \n
whitespace  [ \t]

keyword if, then, else, end, repeat, until, read, write를 먼저 선언하고, :=, =, <, +, -, *, /, 괄호, semicolon을 token으로 반환한다. 그 뒤 number와 identifier, newline count, whitespace skip, 마지막 . error rule이 온다.

이 identifier는 letter만 허용하므로 foo2와 _name을 하나의 ID로 읽지 못한다. 잘못이라기보다 해당 teaching language의 제한이지만 현대 identifier 문법과 혼동하면 안 된다.

brace comment action은 }가 나올 때까지 input()을 반복한다. EOF check가 없어 닫는 brace가 없으면 EOF 값을 계속 받으며 무한 loop가 될 수 있다. nested comment도 지원하지 않는다. 최소한 다음 상태를 나눠야 한다.

closing delimiter -> finish comment
newline           -> update location
EOF               -> unterminated-comment error
other             -> continue

wrapper는 yylex() 뒤 yytext를 token buffer로 복사한다. archived strncpy는 최대 길이를 복사한 뒤 explicit NUL을 쓰지 않아 긴 lexeme가 terminated string이 아닐 수 있다. modern scanner는 std::string 또는 length-aware slice와 source span을 반환하는 편이 안전하다.

Lex build command도 구현별로 다르다

archived command는 generated scanner에 -lm을 link한다. -lm은 math library이지 Lex runtime library가 아니다. classic Lex는 흔히 -ll, flex는 -lfl을 사용하거나 %option noyywrap 또는 직접 yywrap을 제공한다.

flex scanner.l
cc -o scanner lex.yy.c -lfl

실제 project에서는 generated source name과 runtime option을 build system에 명시해야 한다.

Yacc grammar와 semantic action

Yacc는 “compiler compiler”라는 역사적 이름을 가진 LALR(1) parser generator다. .y file도 세 구역을 사용한다.

definitions and token declarations
%%
grammar rules and semantic actions
%%
helper routines, yylex, yyerror, main

전통 output은 y.tab.c, y.tab.h, y.output이지만 modern Bison은 option과 input name에 따라 parser.tab.c, parser.tab.h, parser.output 등을 만든다. 특정 filename을 보편 규칙처럼 외우지 않는 편이 좋다.

calculator grammar는 grammar structure 자체로 multiplication precedence와 left associativity를 만든다.

%token NUMBER
%%
command
    : exp              { printf("%d\n", $1); }
    ;

exp
    : exp '+' term     { $$ = $1 + $3; }
    | exp '-' term     { $$ = $1 - $3; }
    | term             { $$ = $1; }
    ;

term
    : term '*' factor  { $$ = $1 * $3; }
    | factor           { $$ = $1; }
    ;

factor
    : NUMBER           { $$ = $1; }
    | '(' exp ')'      { $$ = $2; }
    ;

$1, $2, $3는 RHS symbol의 semantic value이고 $$는 LHS value다. production application과 value computation이 reduction 시점에 연결된다.

Token kind, lexeme, yylval을 분리한다

아카이브는 yylval을 lexeme과 같다고 설명하지만 세 항목은 다르다.

scanner는 token kind를 return하고 semantic value를 yylval에 넣는다. location interface를 사용하면 line/column span도 함께 전달한다. parser action은 lexeme text와 parsed value를 필요에 따라 구분해 사용한다.

간단한 scanner도 boundary를 조심해야 한다.

int yylex(void) {
    int c;
    do {
        c = getchar();
    } while (c == ' ' || c == '\t');

    if (c != EOF && isdigit((unsigned char)c)) {
        ungetc(c, stdin);
        if (scanf("%d", &yylval) != 1)
            return 0;
        return NUMBER;
    }

    if (c == '\n' || c == EOF)
        return 0;
    return c;
}

archived version은 EOF를 isdigit에 넘길 수 있고 space만 건너뛰며, newline 하나를 parser 종료 token 0으로 사용한다. 한 줄 calculator에는 가능하지만 general language scanner의 규칙은 아니다. void yyerror(...) 안에서 return 0을 하는 예도 return type과 맞지 않는다.

Header와 report option

bison -d parser.y
bison -v parser.y

-d는 token definition을 공유할 header를 만들고 -v는 item states와 conflict를 볼 report를 만든다. 실제 include에는 quotes가 필요하다.

#include "parser.tab.h"

archived #include y.tab.h는 C syntax error다. output name은 tool과 option에 맞춰야 한다.

LALR state report 읽기

calculator의 augmented rule을 포함한 numbering은 다음처럼 볼 수 있다.

0 $accept -> command $end
1 command -> exp
2 exp -> exp '+' term
3 exp -> exp '-' term
4 exp -> term
5 term -> term '*' factor
6 term -> factor
7 factor -> NUMBER
8 factor -> '(' exp ')'

한 archived report는 15 states를 만든다.

• initial state: NUMBER와 (를 shift하고 command, exp, term, factor로 GOTO
• completed factor -> NUMBER .: rule 7 reduce
• exp -> exp . + term과 exp -> exp . - term: operator shift
• term -> term . * factor: multiplication shift
• completed parenthesized factor: rule 8 reduce
• augmented accept state: end marker에서 accept

다른 report는 같은 automaton의 state number를 다르게 배치한다. state ID는 generator version, rule order, construction order에 따라 달라질 수 있으므로 숫자 자체가 semantics는 아니다.

오래된 report의 8/127 terminals, 15/1000 states, fixed memory counters도 당시 generator의 static table limit를 보여 줄 뿐 현대 parser의 language property가 아니다.

또한 default reduce는 table compression과 error behavior를 구분해서 읽어야 한다. generator는 한 state의 대부분 token에서 같은 reduction을 할 때 default action으로 압축하고 formal error cell에서도 먼저 reduce할 수 있다. language recognition은 유지되더라도 syntax error 발견 시점은 늦어질 수 있다.

실제 table 오탈자 하나를 검산하기

state가 다음 completed item을 가진다고 하자.

exp -> exp '+' term .

이 state는 +, -, ), end marker에서 rule 2로 reduce하고, *에서는 factor를 더 읽기 위해 shift한다. archived 최종 table의 해당 state는 end marker에 r3를 적었지만 같은 자료의 state listing과 grammar에 따르면 r2가 맞다.

이런 검산은 단순 오탈자 찾기 이상이다. item, rule number, ACTION entry가 서로 같은 statement를 말하는지 확인하는 parser-generator debugging 방법이다.

현대적인 end-to-end build

작은 project의 전형적인 흐름은 다음과 같다.

flex scanner.l
bison -d -o parser.tab.c parser.y
cc -o tiny parser.tab.c lex.yy.c -lfl

scanner는 generated header의 token kind를 include하고, yylex가 token과 semantic value를 전달한다. yyparse는 LALR table에 따라 shift/reduce하며 action에서 AST나 IR을 만든다. production code에서는 다음도 함께 설계한다.

• reentrant scanner/parser와 explicit context
• typed semantic-value union 또는 variant
• source location
• lexical and syntax error recovery
• ownership과 destructor
• pure 또는 testable semantic action
• generated artifacts의 reproducible build

마무리

Lex와 Yacc를 쓰면 DFA와 LALR table을 손으로 적지 않아도 된다. 그렇다고 correctness가 generator 안으로 사라지는 것은 아니다. longest match와 rule order, token kind와 yylval의 contract, EOF와 unterminated comment, grammar precedence, conflict report, semantic action의 type과 ownership이 모두 language implementation의 경계다.

아카이브의 오래된 command와 C code는 도구의 핵심 아이디어를 잘 드러내지만, 잘못된 regex, 뒤집힌 delimiter, EOF loop, NUL termination, header syntax, table rule number 같은 오류도 함께 품고 있다. generated code를 신뢰하려면 input specification과 generated automaton을 둘 다 읽을 수 있어야 한다.