##動機
CPythonのソースを読もうと思った動機のひとつに、文のブロックをどうやってインデントで実現しているのか、インタプリタのメカニズムはどうなっているかを解明したいというものがあった。やっと解明できたので、メモを書いておく。
リポジトリはここ： https://github.com/python/cpython
##字句解析(トーカナイザ）のひみつ
秘密は字句解析器にあった。Pythonのソースコードからトークンの切り出しをおこなう処理の、コアの部分は tok_get() という関数が行っている。ソースコードではこの部分。
字句解析は状態を持つステートフルな処理になっていて、状態を保持する重要な構造体 tok_state がある。この中にどのようなデータが保持されているか理解すると、字句解析の動きが理解できるようになる。
struct tok_state : githubへのリンク
インデント処理のための最も重要なデータは、この構造体tok_state のメンバである indstack というスタックである。このスタックには、処理するソースコードの最初の部分から、現在処理している部分までのインデントされたカラムの位置が積まれている。インデントが深くなるたびに、カラムの位置がpushされ、インデントが（正しく）浅くなると値がpopされる。
ちなみに、このスタックの上限はもちろん決まっていて、デフォルトは100である。よって101段以上のインデントをつけたソースコードは、エラーになる（はず）。またこの処理は巧妙に作られていて、ある部分のインデントはスペース4個、ある部分のインデントは空白2個といった、かなり変態的なソースコードでも処理でも正しく処理できる。（インデントを浅くなるとき、それまでのインデントと整合性がとれている必要がある）。次のようなソースでもエラーにはならない。
$ cat test_indent.py
def foo():
def bar(): # indent 2 spaces
pass # indent 8 spaces
def baz():
pass # indent 12 spaces
$ ./python.exe test_indent.py
$
字句解析器は、インデントが変化（深くなったり、浅くなったり）したときに、ソースコード上には存在しない仮想的トークン、INDENT や DEDENT というトークンを構文解析器に渡す。これにより、構文解析器の立場からからみたPythonの文法は、伝統的な言語のようなブロックを表すためのシンボル( { } begin end などなど)を持つ言語となんら変わらないものとなる。ソースコードは以下の部分。
仮想的トークン INDENT, DEDENT を返す処理 : githubへのリンク
参考までに、PEG (Parsing Expression Grammar) による block の具象構文の定義はこのようになっている。
block[asdl_seq*] (memo):
| NEWLINE INDENT a=statements DEDENT { a }
| simple_stmt
| invalid_block
なんとなく、NEWLINE(改行)の次にINDENTがきて、文が並び DEDENT が来ることがわかる。PEG は python 3.9 で採用された文法記述で詳細は PEP 617 を参照のこと。