CPythonのパーサーのしくみ

はじめに

CPythonの動作の背後では複雑な処理が行われており、特にソースコードの解析に関わるパースプロセスはCPythonの実行を支える重要な要素です。本稿ではCPythonにおけるパースプロセスの概要、具体的なパーサーの実装や工夫、エラーハンドリングについて解説します。

本稿で解説する内容はCPython 3.11を対象としています。

パースプロセスの概要

パースとは、文字列として記述されたソースコードを解析し、ソースコードの構造を理解するプロセスを指します。パースの主な目的は、プログラムの構文を正しく解釈し、後続の処理（たとえばコンパイルや実行）に必要な情報を抽出することです。CPythonのパーサーは以下のステップを経てソースコードを解析し、抽象構文木（Abstract Syntax Tree, AST）を生成します。ASTはプログラムの論理的な構造を表現するツリー状のデータ構造であり、CPythonの実行において重要な役割を果たします。

1. トークナイズ: ソースコードをトークンと呼ばれる最小単位に分割する
2. パース: トークンがPythonの文法規則に従って正しく組み合わされているかを検証し、ASTを生成する

 source                       token                                                      AST
+-----------+                +--------------------------------------------+             +-------------------------------+
| 1 + 2 + 3 | -> tokenize -> | 0,0-0,0:            ENCODING       'utf-8' | -> parse -> | BinOp(                        |
+-----------+                | 1,0-1,1:            NUMBER         '1'     |             |   left=BinOp(                 |
                             | 1,2-1,3:            PLUS           '+'     |             |     left=Constant(value=1),   |
                             | 1,4-1,5:            NUMBER         '2'     |             |     op=Add(),                 |
                             | 1,6-1,7:            PLUS           '+'     |             |     right=Constant(value=2)), |
                             | 1,8-1,9:            NUMBER         '3'     |             |   op=Add(),                   |
                             | 1,9-1,10:           NEWLINE        '\n'    |             |   right=Constant(value=3))    |
                             | 2,0-2,0:            ENDMARKER      ''      |             | )                             |
                             +--------------------------------------------+             +-------------------------------+

構成要素の整理

重要な構成要素となるトークンとASTについて整理しておきましょう。

トークン

トークンとは、ソースコードを構成する最小単位のことです。パーサーがソースコードを解析する際の基礎となる要素であり、各トークンはタイプと値を持ちます。CPythonのトークナイザーはソースコードを逐次的に読み取りトークンに分割します。トークンのタイプは、CPythonのリポジトリ内の Grammar/Tokens に定義されています。

https://github.com/python/cpython/blob/v3.11.5/Grammar/Tokens#L1-L68

Python 3.11.5でトークンに分割する具体例を示します。対象となるPythonコードは次のとおりです。

def func():
    a = 1 + 2
    return a

このコードをmain.pyとして保存し、Pythonの標準ライブラリである tokenize モジュールを使用します。

$ python -m tokenize -e main.py

すると次のような出力が得られます。各行は 開始位置-終了位置: トークンタイプ 値 の形式で表示されます。括弧や演算子だけでなく、改行やインデントもトークンとして認識されています。

0,0-0,0:            ENCODING       'utf-8'        
1,0-1,3:            NAME           'def'          
1,4-1,8:            NAME           'func'         
1,8-1,9:            LPAR           '('            
1,9-1,10:           RPAR           ')'            
1,10-1,11:          COLON          ':'            
1,11-1,12:          NEWLINE        '\n'           
2,0-2,4:            INDENT         '    '         
2,4-2,5:            NAME           'a'            
2,6-2,7:            EQUAL          '='            
2,8-2,9:            NUMBER         '1'            
2,10-2,11:          PLUS           '+'            
2,12-2,13:          NUMBER         '2'            
2,13-2,14:          NEWLINE        '\n'           
3,4-3,10:           NAME           'return'       
3,11-3,12:          NAME           'a'            
3,12-3,13:          NEWLINE        '\n'           
4,0-4,0:            DEDENT         ''             
4,0-4,0:            ENDMARKER      ''             

AST

ASTは、ソースコードの論理的な構造をツリー状に表現したデータ構造です。ASTはノードとエッジから構成され、各ノードはプログラムの構成要素（たとえば関数定義や条件文や演算子など）を表します。ノードは階層的に配置され、親ノードと子ノードはエッジによって結ばれます。エッジはノード間の関係を示し、プログラムのネスト構造や制御フローを明確に表現します。ASTは後続のコンパイラで利用され、効率的なコード実行とエラーチェックのための基盤となります。
Pythonの標準ライブラリである ast モジュールを使って生成されるASTを見てみましょう。たとえば、1 + 2 + 3 をASTに変換すると次のようになります。

>>> import ast
>>> tree = ast.parse("1 + 2 + 3")
>>> print(ast.dump(tree.body[0].value, indent=2))
BinOp(
  left=BinOp(
    left=Constant(value=1),
    op=Add(),
    right=Constant(value=2)),
  op=Add(),
  right=Constant(value=3))

BinOpノードは二項演算を表し、leftとrightには左右のオペランド、opには演算子が格納されます。Constantノードはリテラル値を表し、Addノードは加算演算子を示します。上記の例ではBinOpノードがネストしていて、1つ目のBinOpノードのleftに1 + 2を表すBinOpノードが渡されています。この構造により、はじめに1 + 2を計算しその結果に+3をすることが表現できています。
もう少し複雑なASTを見てみましょう。for と if を組み合わせたPythonコードをASTに変換すると次のようになります。

>>> tree = ast.parse("""
... for i in range(5):
...     if i % 2 == 0:
...         print("even")
...     else:
...         print("odd")
... """)
>>> print(ast.dump(tree.body[0], indent=2))
For(
  target=Name(id='i', ctx=Store()),
  iter=Call(
    func=Name(id='range', ctx=Load()),
    args=[
      Constant(value=5)],
    keywords=[]),
  body=[
    If(
      test=Compare(
        left=BinOp(
          left=Name(id='i', ctx=Load()),
          op=Mod(),
          right=Constant(value=2)),
        ops=[
          Eq()],
        comparators=[
          Constant(value=0)]),
      body=[
        Expr(
          value=Call(
            func=Name(id='print', ctx=Load()),
            args=[
              Constant(value='even')],
            keywords=[]))],
      orelse=[
        Expr(
          value=Call(
            func=Name(id='print', ctx=Load()),
            args=[
              Constant(value='odd')],
            keywords=[]))])],
  orelse=[])

このASTの構造を言葉で説明すると、以下のようになります。

• Forノード
  • For.target: iterから取り出した値を格納するNameノード
  • For.iter: range関数を呼び出すCallノード
  • For.body: 繰り返し実行されるIfノード
    • If.test: 条件を表すCompareノード
    • If.body: Trueのときに実行されるExprノード
      • Expr.value: print関数を呼び出すCallノード
    • If.orelse: Falseの時に実行されるExprノード
      • Expr.value: print関数を呼び出すCallノード

パーサーの実装

CPythonのパーサーは非常に大規模で複雑な実装となっています。そのため文法規則を定義したファイル Grammar/python.gram からC言語による実装である Parser/parser.c を自動生成するアプローチをとっています。自動生成には以下のメリットがあります。

• 定めた文法規則とその実装が一貫したものとなる
• 実装を手動で管理すると発生するミスを減らし効率的な開発が可能となる

python.gram

python.gramに定義された各文法規則は、左辺の非終端記号と右辺の生成規則から構成されています。例として関数定義の文法規則を見てみましょう。

https://github.com/python/cpython/blob/v3.11.5/Grammar/python.gram#L265-L270

関数定義が正しく記述されているかを順番にチェックし、全てのチェックをパスできた場合に _PyAST_FunctionDef によってASTノードが生成されます。

1. 'def' の確認
2. 関数名の取得
3. '(' の確認
4. 関数のパラメータの解析
5. ')' の確認
6. 戻り値の型解釈の解析（オプション）
7. コロンの確認
8. 型コメントの解析（オプション）
9. 関数ブロックの解析
10. _PyAST_FunctionDef に解析結果を渡してASTノードを生成

python.gramはCPythonの言語仕様を定義する重要なファイルであり、新しい構文を追加したり既存の構文を変更する際に編集されます。

parser.c

parser.cは自動生成されたC言語のコードであり、Pythonのソースコードを解析してASTを生成する役割を担います。CPython 3.9以降ではPEG（Parsing Expression Grammar）パーサーを採用しており、従来のLL(1)パーサーよりも強力な構文解析が可能になっています。PEGパーサー導入により、文法規則の定義が簡潔になり、新しい構文の導入が容易になりました。
parser.cには各文法規則に対応するパース関数が実装されていて、パース関数はトークンを受け取って対応するASTノードを構築します。たとえば、関数定義のパース関数を確認すると、python.gramで定義した文法規則がC言語で具体的に実装されていることがわかります。

https://github.com/python/cpython/blob/v3.11.5/Parser/parser.c#L4434-L4464

実装における工夫

CPythonのパーサーは複雑な文法規則を効率的かつ正確に解析するために工夫が施されています。その中でも特に重要なのがメモ化による左再帰の回避です。ここでは、具体的な文法規則を例に取りながらメモ化について解説します。

左再帰の問題

左再帰とは、文法規則が自身を左側で再帰的に呼び出す構造を指します。以下に左再帰を含む文法規則を示します。

https://github.com/python/cpython/blob/v3.11.5/Grammar/python.gram#L751-L754

この例では、sum が自身を左側で再帰的に呼び出しています。具体的には sum が sum '+' term または sum '-' term の形で定義されています。CPythonのパーサーは、左再帰を含む文法規則を解析する際に、メモ化という技術を用いて無限ループを回避しています。

メモ化による回避

メモ化とは、解析位置に対する解析結果をキャッシュしておき、同じ位置に対する解析が発生した場合にキャッシュを利用する技術です。このキャッシュのしくみにより左再帰による無限ループを回避し、正しい解析を行うことができます。CPythonのパーサーでは、このメモ化はパース関数の戻り値と解析位置をキーとしたテーブルを用いて実現されています。これにより、一度解析した結果を再利用できるため、パースの効率も向上します。
以下に簡易的な文法規則 expr を定義し、メモ化の動作を理解するための例を示します。

expr:
  | expr '+' NUMBER
  | NUMBER

expr は左側で自身を呼び出しているので左再帰です。この expr の定義を使って 1 + 2 を解析する際にメモ化がどのように機能するのかを具体的にみてみましょう。

1 + 2 解析のステップ

1. 解析位置0において expr の解析中であることをメモし、expr の解析を始める
2. 第一の選択肢 expr '+' NUMBER の expr を試みるが既に解析中であるためスキップ
3. 第二の選択肢 NUMBER に成功し、解析位置0における結果 Number(value=1) をメモする
4. 解析位置0に戻って expr の解析を始める
5. 第一の選択肢 expr '+' NUMBER の expr の結果をメモから取得
6. 解析位置2に進んで expr '+' NUMBER の '+' に成功
7. 解析位置4に進んで expr '+' NUMBER の NUMBER に成功し Number(value=2) を得る
8. expr '+' NUMBER に成功し、以下の結果を得る

Expr(
  left=Number(value=1),
  op=Add(),
  right=Number(value=2),
)

エラーハンドリング

すべての文法規則の適用に失敗した場合、CPythonのパーサーはもう一度パースします。このときパーサーは invalid_rule を適用しエラーの詳細情報を提供します。この二度目のパースでは、エラーの原因となった位置や期待されたトークンなどの情報を収集し、ユーザーに対して具体的なエラーメッセージを生成します。特に SyntaxError や IndentationError などの具体的な例外を発生させることで、コードを修正しやすくしています。エラーハンドリングは以下のように実装されています。

https://github.com/python/cpython/blob/v3.11.5/Parser/pegen.c#L834-L852

当てはまる文法規則が見つからなかった（コード上では res == NULL）場合、reset_parser_state_for_error_pass によってパーサーの状態をリセットし、エラー特定モードをオンにして再度パースを実行しています。invalid_rule がどのような定義になっているか invalid_def_raw を例に見てみましょう。

https://github.com/python/cpython/blob/v3.11.5/Grammar/python.gram#L1307-L1309

コロン、改行のあとにインデントがなかったら RAISE_INDENTATION_ERROR を呼び出すよう定義されています。インデントを入れずに関数を定義してみましょう。

def foo():
return 1

これをmain.pyに保存して実行してみます。

$ python main.py
  File "main.py", line 2
    return 1
    ^
IndentationError: expected an indented block after function definition on line 1

期待する IndentationError が出ることが確認できました。このように失敗の文法規則を定義することで詳細なエラー情報を提供しています。

おわりに

本稿では、CPythonのパーサーのしくみを解説してきました。CPythonの内部動作に対する理解を深めることができていれば嬉しいです。次回は後続の処理となるコンパイラについて書こうと思います。