レキサーが位置を覚えている理由

一言でいうと

レキサーは、文字の並びをトークン(種類のついた単語)の並びに変えながら空白とコメントを取り除き、トークンごとにどこから来たのか(行・桁)を付けておきます。パーサーはそのおかげで、文字ではなく意味のある断片を見ることができ、あとのすべてのエラーメッセージは、その位置を受け継ぎます。

なぜ必要なのか

パーサーが文字を直接読むとしましょう。let x=10;とlet x = 10 ;とlet x /* 설명 */ = 10;は同じ文なのに、パーサーのすべての規則が、空白とコメントを読み飛ばすコードをそれぞれ持たなければなりません。<=に出会うたびに「次の文字が=か」を規則ごとに確認する必要があり、letterがキーワードletで始まるという事実にも、規則ごとに気をつけなければなりません。

レキサーは、この仕事を1か所に集めます。パーサーが見るのは、let、IDENT(x)、=、INT(10)、;、EOFの6つだけです。そして、もう1つあります。位置を覚えておきます。ユーザーに「何かが間違っています」ではなく「3行目17桁目の@を知りません」と伝えられるのは、いちばん最初の段階が文字を数えるときに、行と桁をいっしょに数えているからです。この座標は、パーサーの「;が必要です」、意味解析の「宣言されていない名前」、実行中の「0で除算」まで、すべて同じ座標系を使います。

どう動くのか

レキサーは、カーソル1つで文字を1回だけ走査します。1歩ごとに今の文字を見て、どのトークンが始まるのかを決め、そのトークンが終わるまで読み進めます。

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

守るべき規則が4つあります。

いちばん長いものから切る(最長一致、maximal munch)。<=が読めるなら、<と=には切りません。2文字の記号を先に確認し、だめなら1文字に降ります。名前も同じです。letterは、文字を最後まで読んでからキーワードかどうかを見ます。先頭の3文字がletだからと先に切ると、letとterになってしまいます。

桁は文字で数えます。ファイルはUTF-8のバイトですが、人が見る桁は文字です。/* 한글 */ xのxは10番目の文字ですが、14番目のバイトです。バイトで数えると、ハングルのコメントがある行のすべてのエラー位置がずれます。改行を過ぎたら、桁は1に戻ります。

エラーは、その開始位置で知らせます。閉じられていない/*が見つかるのはファイルの末尾ですが、知らせるべき位置はコメントが始まったところです。末尾の位置を知らせると、ユーザーはファイルの末尾で迷います。64ビットに収まらない整数も、その数字の最初の桁で知らせます。

終わりもトークンにします。最後には必ずEOFトークンを置きます。パーサーが「トークンがまだあるか」を別に確認しなくてよくなり、「}が必要なのにファイルが終わった」というエラーも、EOFの位置(最後の文字の直後)で正確に示せます。

1回だけ走査することも大切です。残りの文字をsrc = src[1:]のようにそのたびに切り取って新しく作ると、1文字読むたびにファイル全体をコピーすることになり、ファイルが2倍になると時間が4倍になります。カーソルは、位置の番号を1つ動かすだけでなければなりません。

現場での姿

コンパイラーのエラー表示の下線。clang・rustcがエラーの行を見せ、その下に^の印でちょうどその桁を指すのは、レキサーが残した位置のおかげです。位置が間違っているコンパイラーは、エラーメッセージが合っていても使いづらくなります。
エディターの桁番号の事故。言語サーバープロトコル(LSP)は、桁をUTF-16のコード単位で数えると決めています。サーバーがバイトで、エディターがUTF-16で数えると、ハングルや絵文字がある行で赤い下線が見当違いの場所に引かれます。「桁を何で数えるのか」は些細に見えますが、実際のツール同士がずれる代表的な場所です。
レキサージェネレーターと手書きのレキサー。flexのようなツールは、正規表現の一覧からレキサーを作ってくれます。便利ですが、「いちばん長いものから」と「先に書いた規則が勝つ」という2つの規則が同時に働くので、キーワードと名前の優先順位を正規表現の順序で合わせようとして混乱することがよくあります。そのため、GCC・Clang・rustc・Goはレキサーを手で書きます。行と桁を正確に数え、エラーメッセージを磨き、1回だけ走査することを自分で制御するためです。このラボのレキサーも、その方式です。
Pythonのtokenizeモジュール。Pythonも同じことをしています。python3 -m tokenize 파일.pyを実行すると、トークンごとに(行、桁)の範囲が出力されます(プレースホルダーはファイル名です)。インデントに意味がある言語なので、INDENT・DEDENTというトークンまでレキサーが作る点だけが違います。

次のラボですること

ミニ言語のレキサーを、lexer.pyに5つの部品として作ります。行と桁を数えるカーソル、空白とコメントの読み飛ばし、整数と名前・キーワード、いちばん長いものから切る記号、そしてこれらをつなぐtokenizeです。採点ツールは、トークン1つ1つの行・桁まで基準のレキサーと突き合わせ、ハングルが混じったコメント・64ビットを超える整数・閉じられていないコメントではエラーの文字列まで同じかを確認し、最後に入力を4倍にして、時間が線形に増えるかを測ります。