어휘 분석기를 직접 만드는 법: 정규식에서 maximal munch와 토큰 스트림까지

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

공백으로 나누는 것은 lexer가 아니다

a = b + 3;처럼 공백이 친절한 문장은 단어 분리기로도 그럴듯해 보인다. 하지만 a=b+3;, count++, "a b", /* comment */를 만나면 단순 split은 무너진다. programming-language lexer는 다음 계약을 동시에 지켜야 한다.

• 어떤 문자 열이 하나의 token인가
• 겹치는 후보 중 어느 것을 고르는가
• token에 속하지 않는 lookahead를 소비할 것인가
• 숫자 값·identifier text·원본 위치를 어떻게 전달할 것인가
• 잘못된 문자와 끝나지 않은 literal을 어디에서 진단할 것인가

아카이브의 splitWord 계열 예제는 space로 자르고 일부 문장부호만 따로 떼는 좋은 반례다. 인접 연산자, string, comment, maximal munch를 처리하지 못하므로 단어 분리기이지 lexer가 아니다.

token kind, lexeme, value

세 용어를 분리하면 parser와의 인터페이스가 선명해진다.

a = b + 3;

교육용 구현은 이를 (ID,a) (ASSIGN) (ID,b) (PLUS) (INT,3) (SEMI)처럼 반환할 수 있다. token의 숫자 enum 값 자체는 언어 의미가 아니라 scanner와 parser 사이의 구현 계약이다.

먼저 token 언어를 고정한다

자료에는 서로 다른 시점의 Mini-C 규칙이 섞여 있다. 어떤 문서는 identifier를 letter(letter|digit)*로, 다른 문서는 underscore까지 포함한 (letter|_)(letter|digit|_)*로 둔다. 이것은 어느 한쪽이 보편적으로 맞는 문제가 아니다. lexer가 구현할 언어 명세를 먼저 정해야 한다.

이 글의 작은 예제는 다음을 사용한다.

identifier  [A-Za-z_][A-Za-z0-9_]*
decimal     0|[1-9][0-9]*
hex         0[xX][0-9A-Fa-f]+
whitespace  [ \t\r\n]+

keyword는 identifier와 같은 모양이므로 먼저 긴 identifier를 읽은 뒤 if, else, while, return table에서 다시 분류한다. 반면 operator와 delimiter는 fixed lexeme로 직접 연결할 수 있다.

literal과 comment의 경계

강의 자료의 숫자 automaton은 decimal, leading-zero octal, 0x hexadecimal을 구분하고, 실수는 대략 다음 부분집합을 다룬다.

digits+ "." digits+ ("e" [+-]? digits+)?

이 규칙은 .5, 1., 대문자 E, suffix, digit separator를 포함하지 않는다. “실수의 정의”가 아니라 그 수업 언어가 선택한 숫자 문법이다. 현대 언어를 구현한다면 overflow, 잘못된 0x, 08의 의미까지 명세에서 결정해야 한다.

string은 여는 quote 이후 ordinary character나 escaped character를 반복하다 닫는 quote를 만난다. 그러나 newline 허용 여부, 지원 escape, EOF까지 닫히지 않은 경우는 추가 오류 상태가 필요하다. /* ... */ 같은 중첩하지 않는 block comment는 finite automaton으로 처리할 수 있지만, EOF 전에 */가 없으면 “계속 읽기”가 아니라 unterminated-comment 진단으로 끝나야 한다.

겹치는 연산자와 lookahead

+, ++, +=가 함께 있을 때 첫 +만 보고는 token을 확정할 수 없다. 두 번째 문자를 확인해 더 긴 후보가 있으면 계속 읽고, 없으면 첫 token을 반환하면서 다음 문자는 남겨 둔다.

input: count+++1
tokens: ID(count), PLUS_PLUS, PLUS, INT(1)

다른 강의 예제의 :/:=, </<=/<>는 Pascal 계열이고, Mini-C 자료의 =/==, !/!=와는 다른 token set이다. 두 언어의 예를 한 scanner에 무심코 합치면 명세가 아니라 예제 모음이 된다.

maximal munch 알고리즘

identifier 한 종류만 스캔할 때는 구분자를 만나면 반환해도 된다. 여러 규칙을 합친 DFA에서는 accepting state를 지나 더 읽었다가 실패할 수 있으므로 가장 최근 accepting 지점을 기억한다.

start = cursor
state = initial
lastAccept = none

while transition(state, classify(peek())) exists:
    state = transition(...)
    consume one character
    if state is accepting:
        lastAccept = (state, cursor)

if lastAccept exists:
    rewind cursor to lastAccept.cursor
    emit token selected by lastAccept.state
else:
    report the unknown character at start

가장 긴 길이가 같으면 rule priority를 적용한다. generator에서는 보통 먼저 선언한 rule이 이긴다. keyword rule을 identifier보다 먼저 두거나, identifier를 읽은 뒤 keyword lookup을 하는 두 방식 모두 가능하다.

hardwired와 table-driven scanner

작은 scanner는 switch(state)와 조건문으로 transition을 직접 적기 쉽다. 큰 scanner나 generator 출력은 row=state, column=character class인 table이 편하다.

             LETTER  DIGIT  UNDERSCORE  OTHER  EOF
START        IN_ID   ERROR  IN_ID       ERROR  EOF
IN_ID        IN_ID   IN_ID  IN_ID       ACCEPT ACCEPT

table-driven 방식에서는 최소한 다음 데이터의 indexing 계약이 같아야 한다.

• transition table
• accepting/token-kind table
• 입력을 소비할지 나타내는 advance policy
• character-class enum

자료의 교육용 표에는 S_in_less와 S_less 이름 불일치, accepting row 중복, whitespace·other·EOF 열 누락이 있다. 표는 코드보다 자동으로 안전한 것이 아니다. state 이름을 enum으로 통일하고 dimensions를 검증하는 test가 필요하다.

token을 내보내는 accepting action

function finishIdentifier(lexeme: string, span: Span): Token {
  const keyword = keywordKinds.get(lexeme);
  if (keyword !== undefined) return { kind: keyword, lexeme, span };
  return { kind: "IDENTIFIER", lexeme, span };
}

오래된 예제는 identifier를 symbol table에 즉시 intern하고 index를 token value로 돌려준다. 가능한 설계지만 필수는 아니다. 현대 compiler는 lexer가 text와 span만 반환하고 semantic phase가 scope-aware symbol table을 관리하기도 한다. 어느 쪽이든 lexer 단계의 table은 “같은 철자”를 다루며, 선언의 scope와 type을 해결하는 symbol table과 책임을 혼동하지 않아야 한다.

source span은 부가 기능이 아니다

최소 token 구조는 다음처럼 잡을 수 있다.

interface Token {
  kind: TokenKind;
  lexeme: string;
  value?: number | string;
  span: {
    startOffset: number;
    endOffset: number;
    line: number;
    column: number;
  };
}

offset은 원본 slice와 IDE 연동에, line/column은 사람에게 보이는 오류에 필요하다. CRLF, UTF-8 byte offset, Unicode code point와 JavaScript string index처럼 서로 다른 단위를 섞지 않도록 한 기준을 명시한다.

아카이브 C/C++ 예제에서 배울 디버깅 사례

자료의 코드는 transition 아이디어를 보여주지만 그대로 재사용하면 안 된다.

• void main()과 제거된 gets 대신 표준 int main()과 길이가 제한된 입력을 쓴다.
• error state를 -1로 둔 뒤 AcceptingTable[-1]에 접근하지 않는다. sentinel 검사를 배열 접근보다 먼저 한다.
• isalpha와 isdigit에는 EOF를 넘기지 않고, 음수 signed char 대신 unsigned char 값으로 변환한다.
• fixed lexeme buffer에는 bounds와 null termination이 필요하다.
• int[128][64]에 strcpy를 쓰거나 loop 첫 불일치에서 즉시 return -1하는 symbol-table 예는 type과 탐색 로직이 모두 잘못됐다.
• raw pointer, malloc, owning array를 섞기보다 std::string, std::vector, std::unordered_map과 RAII를 사용한다.

이 결함 목록은 옛 코드를 조롱하기 위한 것이 아니다. 상태 머신이 맞아도 memory safety와 cursor invariant가 틀리면 scanner 전체가 틀린다는 사례다.

최소 구현의 의사 코드

function nextToken(source: string, cursor: Cursor): Token {
  skipTrivia(source, cursor);
  const start = cursor.snapshot();
  const ch = cursor.peek();

  if (ch === EOF) return token("EOF", "", start, cursor.snapshot());
  if (isIdentifierStart(ch)) return scanIdentifier(source, cursor, start);
  if (isDigit(ch)) return scanNumber(source, cursor, start);
  if (ch === '"') return scanString(source, cursor, start);

  const fixed = scanLongestFixedToken(source, cursor);
  if (fixed) return fixed;

  cursor.advance();
  return errorToken("UNKNOWN_CHARACTER", source.slice(start.offset, cursor.offset), start);
}

production scanner에서는 trivia를 token으로 보존할지 버릴지도 목적에 따라 다르다. compiler는 대개 버리지만 formatter와 source-to-source 도구는 comment와 whitespace를 별도 channel에 남겨야 한다.

테스트 매트릭스

각 case는 token kind만이 아니라 lexeme, value, start/end span, diagnostic, next cursor를 함께 assert해야 한다. whitespace split에서 lexer로 넘어가는 결정적 변화는 정규식을 쓰는 것이 아니라 명세와 커서 상태를 검증 가능한 계약으로 만드는 것이다.