Build a Lexer That Remembers Positions

Goal

You build a lexer that cuts Mini-language source into a list of tokens. Each token gets a kind, text, line, and column, and unknown characters, unclosed comments, and integers that are too large are reported at their start position.

Why it matters

Every later step inherits the positions the lexer gives. The parser's "a ; must come," semantic analysis's "no such name," and the run-time "division by zero" are all printed with this coordinate. If you count columns in bytes or from 0, every error on a line with a Korean comment points to the wrong place. And the lexer is the only stage that sweeps the whole input once, so if it is slow here, everything is slow.

The rules of a token

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  (그 숫자의 첫 칸)

Steps

1. Fill in Token, LexError(line, col, message), and Cursor(src) in /root/mini/lexer.py. The cursor carries src, i (the position of the next character), line, and col, and provides peek(ahead=0) (an empty character '' past the end), advance() (returns one character and moves the line and column), and at_end().
2. Fill in skip_trivia(cur) — it skips whitespace and comments and stops before the first character that is not a comment. An unclosed /* raises unterminated comment at its start position.
3. Fill in read_number(cur) and read_word(cur) — they are called when the cursor is on the first character of a number or a name, return a token, and move the cursor to its end. Also fill in KEYWORDS.
4. Fill in read_operator(cur) and TWO_CHAR and ONE_CHAR — look at two-character symbols first, and for an unknown character raise an error at that position.
5. Fill in tokenize(src) — skip whitespace, repeat choosing by the first character whether to read a number, a name, or a symbol until the end, and then attach EOF. The grader compares the token lists of the whole set of fixed programs.
6. On the error programs (/opt/fixtures/mini/errors/lex-*.mini), check that the error text matches the reference down to the last character. They include a column after a comment mixed with Korean and a Korean name (an unknown character because it is not ASCII).
7. The grader compares 300 random token soups (a mix of whitespace, newlines, \r\n, and Korean comments) against the reference.
8. The grader quadruples the input and measures the time. For a lexer that sweeps once, it should be around 4 times.

Notes

• With python3 /root/mini/mini.py tokens /opt/fixtures/mini/programs/hello.mini, you can see the tokens your lexer produced.
• Common mistakes: counting columns from 0, not returning the column to 1 after a newline, forgetting that str.isalnum() is true for Korean and é too, cutting letter into let, and putting the EOF position at (0, 0).
• The session starts at 60 minutes and you can extend it with the +time button, and when it ends /root/mini disappears.

A cursor that counts lines and columns

The cursor moves only one position number, i. In advance, if the character just passed is a newline, raise the line by one and set the column to 1; otherwise just raise the column by one. Python strings are already per character, so if you use len and indexing as they are, columns are counted in characters.

Skip whitespace and comments

Look at the current character and the next one (peek(1)) together. When you meet /*, first write down the line and column at that spot and walk until you find */. If you reach the end, raise the error at the position you wrote down. A lone '/' is not a comment, so stop.

Integers, names, and keywords

Write down the start position and advance while the condition holds. For a name, read to the end and then check whether it is in KEYWORDS. To exclude Korean and é, use isascii() and isalnum() together. For an integer, if int(text) is greater than 2 ** 63 - 1, it is an error at the first column.

Cut the longest symbol first

If peek() + peek(1) is in the list of two-character symbols, advance twice. If not, look at the one-character list. If neither, report it as "unexpected character %r", wrapping the character with repr (a lone & and a lone | are also unknown characters).

Tie it together with tokenize

At each repetition, call skip_trivia first, and at the end attach EOF and return. If the first character is an ASCII digit, read_number; if it is an ASCII letter or _, read_word; anything else is read_operator. The position of EOF is the spot where skip_trivia stopped.

Print errors in place

There is no new code. If it fails, look at the line:column in the message. If the column shifts after a Korean comment, you are counting in bytes, and if you accept a Korean name, you are looking only at isalpha.

Compare with random token soup

There is no new code. The random inputs have \r\n newlines mixed in. \r is not a newline but whitespace that takes up one column — if you raise the line on \r, the line number shows up doubled.

Measure whether it sweeps only once

There is no new code. If the time grows close to 16 times when the input is 4 times, somewhere you are copying all the remaining characters for every character (src[i:]) or recounting from the beginning (src[:i].count('\n')).