位置を覚えるレキサーを作る

目標

ミニ言語のソースをトークンの一覧に切るレキサーを作ります。トークンごとに種類・文字列・行・桁を付け、知らない文字・閉じられていないコメント・大きすぎる整数は、開始位置で知らせます。

なぜ重要なのか

あとのすべての段階は、レキサーが渡した位置を受け継ぎます。パーサーの「;が必要です」、意味解析の「存在しない名前」、実行中の「0で除算」が、すべてこの座標で示されます。桁をバイトで数えたり、0から数えたりすると、ハングルのコメントがある行のすべてのエラーが、見当違いの場所を指します。そして、レキサーは入力全体を1回走査する唯一の段階なので、ここが遅ければ全体が遅くなります。

トークンの規則

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()(文字を1つ返しながら行・桁を進める)、at_end()を提供します。
skip_trivia(cur)を埋めます。空白とコメントを読み飛ばし、コメントではない最初の文字の手前で止まります。閉じられていない/*は、その開始位置でunterminated commentを出します。
read_number(cur)とread_word(cur)を埋めます。カーソルが数字や名前の最初の文字にあるときに呼ばれ、トークンを返しながらカーソルをその終わりへ進めます。KEYWORDSも埋めます。
read_operator(cur)とTWO_CHAR・ONE_CHARを埋めます。2文字の記号を先に見て、知らない文字はその位置でエラーを出します。
tokenize(src)を埋めます。空白を読み飛ばし、最初の文字で数字・名前・記号のどれを読むかを選ぶことを最後まで繰り返してから、EOFを付けます。採点ツールが、固定プログラム全体のトークン一覧を突き合わせます。
エラープログラム(/opt/fixtures/mini/errors/lex-*.mini)で、エラーの文字列が基準と1文字まで同じかを確認します。ハングルが混じったコメントのあとの桁と、ハングルの名前(ASCIIではないので、知らない文字)が入っています。
採点ツールが、ランダムなトークンスープ300個(空白・改行・\r\n・ハングルのコメントが混ざっています)を基準と突き合わせます。
採点ツールが、入力を4倍にして時間を測ります。1回だけ走査するレキサーなら、4倍前後になるはずです。

参考

python3 /root/mini/mini.py tokens /opt/fixtures/mini/programs/hello.miniで、自分のレキサーが出したトークンを見られます。
よくある間違いは、桁を0から数える、改行のあとで桁を1に戻さない、str.isalnum()がハングルやéでも真になることを忘れる、letterをletで切ってしまう、EOFの位置を(0, 0)にしてしまう、の5つです。
セッションは60分で始まり、＋時間で延ばせます。終わると/root/miniが消えます。

行と桁を数えるカーソル

カーソルは、位置の番号iを1つ動かすだけです。advanceで、今通り過ぎた文字が改行なら行を1つ上げて桁を1に、そうでなければ桁だけを1つ上げます。Pythonの文字列はすでに文字単位なので、lenとインデックスをそのまま使えば、桁が文字で数えられます。

空白とコメントを読み飛ばす

今の文字と次の文字(peek(1))をいっしょに見ます。/に出会ったら、その位置の行・桁を先に控えておき、/が見つかるまで進みます。終端に着いたら、控えておいた位置でエラーを出します。'/'が1つだけならコメントではないので、止まります。

整数と名前、そしてキーワード

開始位置を控えておき、条件が合うあいだadvanceします。名前は、最後まで読んでからKEYWORDSにあるかを見ます。ハングルやéを弾くには、isascii()とisalnum()をいっしょに使います。整数は、int(text)が2 ** 63 - 1より大きければ、最初の桁でエラーです。

いちばん長い記号から切る

peek() + peek(1)が2文字の記号の一覧にあれば、advanceを2回します。なければ、1文字の一覧を見ます。どちらにもなければ、"unexpected character %r"で、その文字をreprで包んで知らせます(&が1つだけ、|が1つだけも、知らない文字です)。

tokenizeでつなぐ

繰り返しのたびに、まずskip_triviaを呼び、終端ならEOFを付けて返します。最初の文字がASCIIの数字ならread_number、ASCIIの文字か_ならread_word、それ以外はread_operatorです。EOFの位置は、skip_triviaが止まったその位置です。

エラーを正しい位置に出す

新しいコードはありません。落ちるなら、メッセージの行:桁を見てください。ハングルのコメントのあとで桁がずれるなら、バイトで数えています。ハングルの名前を受け入れるなら、isalphaだけを見ています。

ランダムなトークンスープで突き合わせる

新しいコードはありません。ランダムな入力には、\r\nの改行が混ざっています。\rは改行ではなく、1桁を占める空白です。\rで行を上げると、行番号が2倍になります。

1回だけ走査しているかを測る

新しいコードはありません。入力が4倍のときに時間が16倍に近く増えるなら、どこかで1文字ごとに残りの文字全体をコピーしているか(src[i:])、最初から数え直しているか(src[:i].count('\n'))のどちらかです。