做一个记住位置的词法分析器

한국어 원문으로 표시합니다.

목표

미니 언어의 소스를 토큰 목록으로 자르는 렉서를 만듭니다. 토큰마다 종류·글자·줄·칸을 붙이고, 모르는 글자·닫히지 않은 주석·너무 큰 정수는 시작 위치로 알립니다.

왜 중요한가

뒤의 모든 단계는 렉서가 준 위치를 물려받습니다. 파서의 "; 이 와야 한다", 의미 분석의 "없는 이름", 실행 중의 "0 으로 나눔" 이 전부 이 좌표로 찍힙니다. 칸을 바이트로 세거나 0부터 세면, 한글 주석이 있는 줄의 모든 오류가 엉뚱한 곳을 가리킵니다. 그리고 렉서는 입력 전체를 한 번 훑는 유일한 단계라, 여기서 느리면 전부가 느립니다.

토큰의 규칙

Token(kind, text, line, col)   namedtuple. line·col 은 1부터, col 은 글자(코드 포인트) 단위.
                               탭도 한 칸, \r 도 한 칸. 줄바꿈(\n)을 지나면 줄 +1, 칸 1.
공백      ' ' '\t' '\r' '\n' 은 버린다
주석      // 부터 줄 끝까지 · /* 부터 */ 까지(겹치지 않는다: /* /* */ 에서 끝난다)
정수      ASCII 숫자 하나 이상. kind "INT", text 는 쓴 그대로("007"). 2^63-1 을 넘으면 오류
이름      ASCII 글자나 _ 로 시작, 그 뒤 ASCII 글자·숫자·_. 키워드면 kind 가 그 키워드, 아니면 "IDENT"
키워드    let fn return if else while print true false
기호      두 글자 == != <= >= && || 를 먼저 보고, 한 글자 + - * / % ^ ( ) { } , ; = < > !
끝        마지막에 늘 Token("EOF", "", 줄, 칸) — 마지막 글자 바로 뒤의 위치
오류      LexError(줄, 칸, 메시지). str() 은 "줄:칸: 메시지"
          unexpected character '@'   (repr 로 감싼 그 글자, 그 글자의 위치)
          unterminated comment       (그 /* 의 위치)
          integer literal too large  (그 숫자의 첫 칸)

단계

/root/mini/lexer.py 의 Token·LexError(line, col, message)·Cursor(src) 를 채웁니다. 커서는 src·i(다음 글자 자리)·line·col 을 들고, peek(ahead=0)(끝을 넘으면 빈 글자 ''), advance()(글자 하나를 돌려주며 줄·칸을 옮김), at_end() 를 제공합니다.
skip_trivia(cur) 를 채웁니다 — 공백과 주석을 건너뛰고 주석이 아닌 첫 글자 앞에서 멈춥니다. 닫히지 않은 /* 는 그 시작 위치로 unterminated comment 를 냅니다.
read_number(cur) 와 read_word(cur) 를 채웁니다 — 커서가 숫자·이름의 첫 글자에 있을 때 불리고, 토큰을 돌려주며 커서를 그 끝으로 옮깁니다. KEYWORDS 도 채웁니다.
read_operator(cur) 와 TWO_CHAR·ONE_CHAR 를 채웁니다 — 두 글자 기호를 먼저 보고, 모르는 글자는 그 자리로 오류를 냅니다.
tokenize(src) 를 채웁니다 — 공백을 건너뛰고, 첫 글자로 숫자·이름·기호 중 무엇을 읽을지 고르기를 끝까지 되풀이한 뒤 EOF 를 붙입니다. 채점기가 고정 프로그램 전체의 토큰 목록을 대조합니다.
오류 프로그램(/opt/fixtures/mini/errors/lex-*.mini)에서 오류 글자가 기준과 한 글자까지 같은지 확인합니다. 한글이 섞인 주석 뒤의 칸, 한글 이름(ASCII 가 아니므로 모르는 글자)이 들어 있습니다.
채점기가 무작위 토큰 수프 300편(공백·줄바꿈·\r\n·한글 주석 섞임)을 기준과 대조합니다.
채점기가 입력을 네 배로 늘려 시간을 잽니다. 한 번 훑는 렉서라면 4배 안팎이어야 합니다.

참고

python3 /root/mini/mini.py tokens /opt/fixtures/mini/programs/hello.mini 로 여러분의 렉서가 낸 토큰을 볼 수 있습니다.
흔한 실수: 칸을 0부터 세는 것, 줄바꿈 뒤 칸을 1로 되돌리지 않는 것, str.isalnum() 이 한글·é 도 참이라는 것을 잊는 것, letter 를 let 으로 자르는 것, EOF 위치를 (0, 0) 으로 두는 것.
세션은 60분에 시작해 ＋시간으로 늘릴 수 있고, 끝나면 /root/mini 가 사라집니다.

줄과 칸을 세는 커서

커서는 자리 번호 i 하나만 옮깁니다. advance 에서 방금 지난 글자가 줄바꿈이면 줄을 하나 올리고 칸을 1로, 아니면 칸만 하나 올립니다. 파이썬 문자열은 이미 글자 단위라 len·인덱스를 그대로 쓰면 칸이 글자로 세어집니다.

공백과 주석을 건너뛴다

지금 글자와 다음 글자(peek(1))를 함께 봅니다. /* 를 만나면 그 자리의 줄·칸을 먼저 적어 두고 */ 를 찾을 때까지 걷습니다. 끝에 닿으면 적어 둔 위치로 오류를 냅니다. '/' 하나만 있으면 주석이 아니니 멈춥니다.

정수와 이름, 그리고 키워드

시작 위치를 적어 두고 조건이 맞는 동안 advance 합니다. 이름은 끝까지 읽은 뒤에 KEYWORDS 에 있는지 봅니다. 한글·é 를 막으려면 isascii() 와 isalnum() 을 함께 씁니다. 정수는 int(text) 가 2 ** 63 - 1 보다 크면 첫 칸으로 오류입니다.

가장 긴 기호부터 자른다

peek() + peek(1) 이 두 글자 기호 목록에 있으면 두 번 advance 합니다. 아니면 한 글자 목록을 봅니다. 둘 다 아니면 "unexpected character %r" 로 그 글자를 repr 로 감싸 알립니다(& 하나, | 하나도 모르는 글자입니다).

tokenize 로 잇는다

되풀이마다 skip_trivia 를 먼저 부르고, 끝이면 EOF 를 붙여 돌려줍니다. 첫 글자가 ASCII 숫자면 read_number, ASCII 글자나 _ 면 read_word, 그 밖은 read_operator 입니다. EOF 의 위치는 skip_trivia 가 멈춘 그 자리입니다.

오류를 제자리에 찍는다

새 코드는 없습니다. 떨어진다면 메시지의 줄:칸을 보세요. 한글 주석 뒤에서 칸이 밀리면 바이트로 세고 있는 것이고, 한글 이름을 받아들인다면 isalpha 만 보고 있는 것입니다.

무작위 토큰 수프로 대조한다

새 코드는 없습니다. 무작위 입력에는 \r\n 줄바꿈이 섞여 있습니다. \r 은 줄바꿈이 아니라 한 칸을 차지하는 공백입니다 — \r 에서 줄을 올리면 줄 번호가 두 배로 뜁니다.

한 번만 훑는지 잰다

새 코드는 없습니다. 입력이 4배일 때 시간이 16배에 가깝게 늘면, 어딘가에서 글자 하나마다 남은 글자 전체를 복사하거나(src[i:]) 처음부터 다시 세고(src[:i].count('\n')) 있는 것입니다.