[[Pythonを読む]]
 
 #contents
 
 *PyParser_ParseFileObject (Parser/parsetok.c) [#l2c3f89c]
 
 ファイルを指定したときに呼び出されるPyParser_ParseFileObject からスクリプト解析を見ていきます。(ファイルを指定しないでpythonコマンドを起動したときも呼ばれる)
 
 #code(C){{
 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) [#rdce3b52]
 
 parsetok関数は長いです。エラー処理をばさっと削ると以下のような感じ。
 
 #code(C){{
 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) [#bbe749ea]
 
 #code(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) [#be144651]
 
 PyParser_AddTokenではトークンと現在の状態(どの文法要素を解析中か)からノードを構築しています。書いてある処理ははっきり言って難解です。普通のDFAの遷移処理に加え解析を高速化するための処理も入っているのでそれを理解して読まないと何が書いてあるかわかりません。こういう場合はそもそも何の解析をしているのかを考え、実装の詳細はあまり気にしないほうがいいです。とりあえず、
 
 -非終端記号の場合はpush
 -終端記号に来たらshift
 -受理状態のままの場合はpopしてスタックが空になったらOK
 
 という構文解析の基本が行われていると思っておけばよいです。
 
 pushでは現在のスタックトップのノードに子ノードを追加して追加した子ノードを次にノードが追加される場合の親ノードとしています。(書いてるとややこしい)
 
 #code(C){{
 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は行われないので現在のスタックトップにノードが追加されていくことになります。
 
 #code(C){{
 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;
 }
 }}
 
 *構文解析してみる [#i3c050f6]
 
 静的にコードを眺めるだけだとよくわからないので例によってノードを作ってみましょう。解析対象となるコードは以下。
 
 #code(Python){{
 [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
                                                 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)
                                                 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
 
 長いわ!演算子の優先順位の都合でかなり深いノードになっています。
 
 *おわりに [#j1b37ae4]
 
 というわけでスクリプト解析まで来ました。シンプルなスクリプトなのにかなり深いノードになっています。Rubyの場合こんなに深くならなかったけど、yaccが演算子優先順位を処理してくれるからか。その代わり、Rubyではかっこ省略とかができる関係でparse.yの文法記述がノード作成処理込みで4000行以上になっていますね(2.3.0の場合)。慣れてるからRubyの方がよくない?と感じてますがたぶん構文解析処理的にはPythonの方がシンプルですね。ノードが深い問題は[[この後>Python/AST作成を読む]]を読んでいけば解決するのでしょう。

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS