字句解析

字句解析

執筆済 コンピュータ言語

文字列をトークンの列に分ける。 lexing、tokenizing。

"if (x >= 10) return;"
  ↓
IF, LPAREN, IDENT(x), GE, NUM(10), RPAREN, RETURN, SEMI

空白とコメントはここで捨てる。

正規表現と有限オートマトン#

各トークンの形を正規表現で書く。

トークン 正規表現
識別子 [a-zA-Z_][a-zA-Z0-9_]*
整数 [0-9]+
浮動小数 [0-9]+\.[0-9]+

正規表現は有限オートマトンに変換でき、 入力を 1 文字ずつ読んで状態遷移するだけで認識できる。

正規表現→NFA→DFA→表駆動の走査

計算量は入力長に線形。 lex / flex はこの変換を自動化する道具。

最長一致#

>= を > と = に分けてはいけない。 候補のうち最も長く一致するものを選ぶのが標準的な規則。

同じ長さで複数一致する場合は、 先に書かれた規則を優先する。 これにより if を IDENT ではなく IF と解釈できる。

難しい例#

  • C の a*b … a が型なら宣言、変数なら乗算。 字句だけでは決まらない（lexer hack）
  • C++ の >> … 右シフトかテンプレートの閉じか
  • Python のインデント … 空白が意味を持つので、 字句解析器が INDENT / DEDENT トークンを生成する

理論上きれいに分かれる層が、 実際の言語では相互に依存することがある。

参考文献#

  • Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed. Pearson, 2006.
  • Robert Nystrom. Crafting Interpreters. Genever Benning, 2021.（全文公開） https://craftinginterpreters.com/