Why a Lexer Remembers Positions

In one line

A lexer turns a line of characters into a line of tokens (words with a kind attached), filtering out whitespace and comments and attaching to each token where it came from (line and column). Thanks to that, the parser looks at meaningful pieces rather than characters, and every error message later inherits that position.

Why this was needed

Suppose the parser read characters directly. let x=10;, let x = 10 ;, and let x /* 설명 */ = 10; are the same statement, but every rule of the parser would need its own code to skip whitespace and comments. Each time it meets <=, every rule would have to check "is the next character =?", and every rule would have to be careful about the fact that letter starts with the keyword let.

The lexer gathers this work in one place. All the parser sees is six things: let, IDENT(x), =, INT(10), ;, and EOF. And it does one more thing — it remembers position. The reason you can tell the user not "something is wrong" but "I do not know the @ at column 17 of line 3" is that the very first stage counted lines and columns together as it counted characters. This coordinate is used in the same coordinate system all the way from the parser's "a ; must come," to semantic analysis's "undeclared name," to the run-time "division by zero."

How it works

A lexer sweeps through the characters once with a single cursor. At each step, it looks at the current character, decides which token starts, and swallows it until that token ends.

 let  x1 <= 007 ; // 끝
 ^^^  ^^ ^^ ^^^ ^
 let  IDENT  <=  INT  ;   (주석과 공백은 버리고) EOF
 1:2  1:7  1:10 1:13 1:17                        1:23

There are four rules to keep.

Longest first (maximal munch). If it can read <=, it does not cut it into < and =. It checks two-character symbols first and falls back to one character if that does not work. Names are the same — for letter, it reads the characters to the end and only then checks whether it is a keyword. If you first cut because the first three characters are let, you get let + ter.

Count columns in characters. A file is UTF-8 bytes, but the columns a person sees are characters. In /* 한글 */ x, x is the 10th character but the 14th byte. If you count by bytes, every error position on a line with a Korean comment shifts. After passing a newline, the column returns to 1.

Report errors at their start position. An unclosed /* is discovered at the end of the file, but the position to report is where the comment started. If you report the end position, the user wanders around the end of the file. An integer that does not fit in 64 bits is also reported at the first column of that number.

Make the end a token. At the end there is always an EOF token. The parser does not have to check separately for "are there more tokens," and an error such as "a } must come but the file ended" is pinpointed exactly at the position of EOF (right after the last character).

Sweeping only once is also important. If you cut the remaining characters and build a new string each time, as in src = src[1:], you copy the entire file for every character you read, so when the file doubles, the time quadruples. A cursor must only move a single position number.

What it looks like in the field

• The underline in compiler errors. That clang and rustc show the error line and point to the exact column with a ^ mark beneath it is thanks to the position the lexer left behind. A compiler with wrong positions is painful to use even when its error messages are right.
• Column number incidents in editors. The Language Server Protocol (LSP) specifies that columns are counted in UTF-16 code units. If the server counts in bytes and the editor in UTF-16, the red underline is drawn in the wrong place on lines with Korean or emoji. "What do you count columns in" looks trivial, but it is a typical point where real tools disagree with one another.
• Lexer generators and hand-written lexers. A tool like flex builds a lexer from a list of regular expressions. It is convenient, but the two rules "longest first" and "the earlier rule wins" run together, and it is common to get confused while matching the priority of keywords and names by regex order. That is why GCC, Clang, rustc, and Go write their lexers by hand — to count lines and columns exactly, polish error messages, and control the single sweep themselves. This lab's lexer takes the same approach.
• Python's tokenize module. Python does the same job. If you run python3 -m tokenize 파일.py (the placeholder is the file), the (line, column) range is printed for each token. The only difference is that, because indentation carries meaning in the language, the lexer even produces tokens called INDENT and DEDENT.

What you will do in the next lab

You build the Mini language's lexer in lexer.py in five pieces — a cursor that counts lines and columns, skipping whitespace and comments, integers and names and keywords, symbols cut longest first, and tokenize, which ties them together. The grader compares down to the line and column of each token against the reference lexer, checks whether even the error text is the same for comments mixed with Korean, integers beyond 64 bits, and unclosed comments, and finally quadruples the input and measures whether the time grows linearly.