![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
[[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作成を読む]]を読んでいけば解決するのでしょう。
