Python/スクリプト解析を読む

PyParser_ParseFileObject (Parser/parsetok.c)
parsetok (Parser/parsetok.c)
- PyParser_New (Parser/parser.c)
- PyParser_AddToken (Parser/parser.c)
構文解析してみる
おわりに

PyParser_ParseFileObject (Parser/parsetok.c) †

ファイルを指定したときに呼び出されるPyParser_ParseFileObject からスクリプト解析を見ていきます。（ファイルを指定しないでpythonコマンドを起動したときも呼ばれる）

 
 
 
 
 
-
|
|
|
|
|
-
|
|
!
|
|
|
|
|
!

node *
PyParser_ParseFileObject(FILE *fp, PyObject *filename,
                         const char *enc, grammar *g, int start,
                         const char *ps1, const char *ps2,
                         perrdetail *err_ret, int *flags)
{
    struct tok_state *tok;
 
    if (initerr(err_ret, filename) < 0)
        return NULL;
 
    if ((tok = PyTokenizer_FromFile(fp, enc, ps1, ps2)) == NULL) {
        err_ret->error = E_NOMEM;
        return NULL;
    }
#ifndef PGEN
    Py_INCREF(err_ret->filename);
    tok->filename = err_ret->filename;
#endif
    return parsetok(tok, g, start, err_ret, flags);
}

↑

parsetok (Parser/parsetok.c) †

parsetok関数は長いです。エラー処理をばさっと削ると以下のような感じ。

 
 
 
-
|
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-
-
|
|
!
|
!
!
|
-
|
|
!
|
|
|
|
|
|
|
!

static node *
parsetok(struct tok_state *tok, grammar *g, int start, perrdetail *err_ret,
         int *flags)
{
    parser_state *ps;
    node *n;
 
    ps = PyParser_New(g, start);
    for (;;) {
        char *a, *b;
        int type;
        size_t len;
        char *str;
        int col_offset;
 
        type = PyTokenizer_Get(tok, &a, &b);
        len = b - a; /* XXX this may compute NULL - NULL */
        str = (char *) PyObject_MALLOC(len + 1);
        if (len > 0)
            strncpy(str, a, len);
        str[len] = '\0';
 
        if (a >= tok->line_start)
            col_offset = Py_SAFE_DOWNCAST(a - tok->line_start,
                                          Py_intptr_t, int);
        else
            col_offset = -1;
 
        if ((err_ret->error =
             PyParser_AddToken(ps, (int)type, str,
                               tok->lineno, col_offset,
                               &(err_ret->expected))) != E_OK) {
            if (err_ret->error != E_DONE) {
                PyObject_FREE(str);
                err_ret->token = type;
            }
            break;
        }
    }
 
    if (err_ret->error == E_DONE) {
        n = ps->p_tree;
        ps->p_tree = NULL;
    }
 
    PyParser_Delete(ps);
 
done:
    PyTokenizer_Free(tok);
 
    return n;
}

パーサを作り、トーカナイザからトークンを取得して追加、終わりまで来たらループ終了、（エラーがなかったら）ノードができているのでそれを返すということをしています。

↑

PyParser_New (Parser/parser.c) †

 
-
|
|
|
|
|
|
|
|
|
|
!

PyParser_New(grammar *g, int start)
{
    parser_state *ps;
 
    if (!g->g_accel)
        PyGrammar_AddAccelerators(g);
    ps = (parser_state *)PyMem_MALLOC(sizeof(parser_state));
    ps->p_grammar = g;
    ps->p_tree = PyNode_New(start);
    s_reset(&ps->p_stack);
    (void) s_push(&ps->p_stack, PyGrammar_FindDFA(g, start), ps->p_tree);
    return ps;
}

DFAとあります。つまり、スクリプトからノードに変換するにはオートマトンを使っているようです。yaccを使っていないのはインデントが意味を持っているから？

grammer、その実体は_PyParser_GrammarはPython/graminit.cに定義されています。もっともDFAを表現したデータが格納されているだけなのでこれだけ見てもよくわかりません。graminit.c（とInclude/graminit.h）はParserにあるpgenを用いて生成されているようです。また、pgen自体の入力ファイルはGrammar/Grammarです。これを見るとPythonの文法が書かれています。

↑

PyParser_AddToken (Parser/parser.c) †

PyParser_AddTokenではトークンと現在の状態（どの文法要素を解析中か）からノードを構築しています。書いてある処理ははっきり言って難解です。普通のDFAの遷移処理に加え解析を高速化するための処理も入っているのでそれを理解して読まないと何が書いてあるかわかりません。こういう場合はそもそも何の解析をしているのかを考え、実装の詳細はあまり気にしないほうがいいです。とりあえず、

非終端記号の場合はpush
終端記号に来たらshift
受理状態のままの場合はpopしてスタックが空になったらOK

という構文解析の基本が行われていると思っておけばよいです。

pushでは現在のスタックトップのノードに子ノードを追加して追加した子ノードを次にノードが追加される場合の親ノードとしています。（書いてるとややこしい）

 
 
-
|
|
|
|
|
|
|
|
|
!

static int
push(stack *s, int type, dfa *d, int newstate, int lineno, int col_offset)
{
    int err;
    node *n;
    n = s->s_top->s_parent;
    assert(!s_empty(s));
    err = PyNode_AddChild(n, type, (char *)NULL, lineno, col_offset);
    if (err)
        return err;
    s->s_top->s_state = newstate;
    return s_push(s, d, CHILD(n, NCH(n)-1));
}

shiftではpushは行われないので現在のスタックトップにノードが追加されていくことになります。

 
 
-
|
|
|
|
|
|
|
!

static int
shift(stack *s, int type, char *str, int newstate, int lineno, int col_offset)
{
    int err;
    assert(!s_empty(s));
    err = PyNode_AddChild(s->s_top->s_parent, type, str, lineno, col_offset);
    if (err)
        return err;
    s->s_top->s_state = newstate;
    return 0;
}

↑

構文解析してみる †

静的にコードを眺めるだけだとよくわからないので例によってノードを作ってみましょう。解析対象となるコードは以下。

[n for n in range(10) if n * n > 10]

次のような感じになるはずです。

 single_input
   simple_stmt
     small_stmt
       expr_stmt
         testlist_star_expr
           test
             or_test
               and_test
                 not_test
                   comparison
                     expr
                       xor_expr
                         and_expr
                           shift_expr
                             arith_expr
                               term
                                 factor
                                   power
                                     atom_expr
                                       atom
                                         testlist_comp
                                           test
                                             or_test
                                               and_test
                                                 not_test
                                                   comparison
                                                     expr
                                                       xor_expr
                                                         and_expr
                                                           shift_expr
                                                             arith_expr
                                                               term
                                                                 factor
                                                                   power
                                                                     atom_expr
                                                                       atom
                                                                         NAME(n)
                                           comp_for
                                             exprlist
                                               expr
                                                 xor_expr
                                                   and_expr
                                                     shift_expr
                                                       arith_expr
                                                         term
                                                           factor
                                                             power
                                                               atom_expr
                                                                 atom
                                                                   NAME(n)
                                             or_test
                                               and_test
                                                 not_test
                                                   comparison
                                                     expr
                                                       xor_expr
                                                         and_expr
                                                           shift_expr
                                                             arith_expr
                                                               term
                                                                 factor
                                                                   power
                                                                     atom_expr
                                                                       atom
                                                                         NAME(range)
                                                                       trailer
                                                                         arglist
                                                                           argument
                                                                             test
                                                                               or_test
                                                                                 and_test
                                                                                   not_test
                                                                                     comparison
                                                                                       expr
                                                                                         xor_expr
                                                                                           and_expr
                                                                                             shift_expr
                                                                                               arith_expr
                                                                                                 term
                                                                                                   factor
                                                                                                     power
                                                                                                       atom_expr
                                                                                                         atom
                                                                                                           NUMBER(10)
                                             comp_iter
                                               comp_if
                                                 test_nocond
                                                   or_test
                                                     and_test
                                                       not_test
                                                         comparison
                                                           expr
                                                             xor_expr
                                                               and_expr
                                                                 shift_expr
                                                                   arith_expr
                                                                     term
                                                                       factor
                                                                         power
                                                                           atom_expr
                                                                             atom
                                                                               NAME(n)
                                                                       *
                                                                       factor
                                                                         power
                                                                           atom_expr
                                                                             atom
                                                                               NAME(n)
                                                           comp_op
                                                             >
                                                           expr
                                                             xor_expr
                                                               and_expr
                                                                 shift_expr
                                                                   arith_expr
                                                                     term
                                                                       factor
                                                                         power
                                                                           atom_expr
                                                                             atom
                                                                               NUMBER(10)
     NEWLINE

長いわ！演算子の優先順位の都合でかなり深いノードになっています。

↑

おわりに †

というわけでスクリプト解析まで来ました。シンプルなスクリプトなのにかなり深いノードになっています。Rubyの場合こんなに深くならなかったけど、yaccが演算子優先順位を処理してくれるからか。その代わり、Rubyではかっこ省略とかができる関係でparse.yの文法記述がノード作成処理込みで4000行以上になっていますね（2.3.0の場合）。慣れてるからRubyの方がよくない？と感じてますがたぶん構文解析処理的にはPythonの方がシンプルですね。ノードが深い問題はこの後を読んでいけば解決するのでしょう。