Як влаштований парсер Python, і як втричі зменшити споживання ним пам'яті

кожен, хто вивчав пристрій мов програмування, приблизно уявляє, як вони працюють: парсер згідно з формальною граматикою ЯП перетворює вхідний текст в деякий подання, з якою працюють наступні етапи (семантичний аналіз, різні трансформації, і генерація коду).

КДПВ

В Python все трохи складніше: парсерів два. Перший парсер керується граматикою, заданої у файлі
<a href="https://hg.python.org/cpython/file/default/Grammar/Grammar">Grammar/Grammar</a>
у вигляді регулярних виразів (з не зовсім звичайним синтаксисом). По цій граматиці за допомогою
Parser/pgen
під час компіляції
python
генерується цілий набір кінцевих автоматів, розпізнають задані регулярні вирази — по одному КА для кожного нетерминала. Формат получающегося набору КА описаний в
<a href="https://hg.python.org/cpython/file/default/Include/grammar.h">Include/grammar.h</a>
, а самі КА задаються в
<a href="https://hg.python.org/cpython/file/default/Python/graminit.c">Python/graminit.c</a>
, у вигляді глобальної структури
_PyParser_Grammar
. Термінальні символи визначені в
<a href="https://hg.python.org/cpython/file/default/Include/token.h">Include/token.h</a>
, і їм відповідають номери 0..56; номери нетерминалов починаються з 256.

Проілюструвати роботу першого парсера простіше всього на прикладі.
Нехай у нас є програма
if 42: print("Hello world")


Ось частина граматики, відповідна розбору нашої програмиsingle_input: NEWLINE | simple_stmt | compound_stmt NEWLINE
compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | with_stmt | funcdef | classdef | decorated | async_stmt
if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]
suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT
simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE
small_stmt: expr_stmt | del_stmt | pass_stmt | flow_stmt | import_stmt | global_stmt | nonlocal_stmt | assert_stmt
expr_stmt: testlist_star_expr (annassign | augassign (yield_expr|testlist) | ('=' (yield_expr|testlist_star_expr))*)
testlist_star_expr: (test|star_expr) (',' (test|star_expr))* [',']
test: or_test ['if' or_test 'else' test] | lambdef
or_test: and_test ('or' and_test)*
and_test: not_test ('and' not_test)*
not_test: 'not' not_test | comparison
comparison: expr (comp_op expr)*
expr: xor_expr ('|' xor_expr)*
xor_expr: and_expr ('^' and_expr)*
and_expr: shift_expr ('&' shift_expr)*
shift_expr: arith_expr (('<<'|'>>') arith_expr)*
arith_expr: term (('+'|'-') term)*
term: factor (('*'|'@'|'/'|'%'|'//') factor)*
factor: ('+'|'-'|'~') factor | power
power: atom_expr ['**' factor]
atom_expr: [AWAIT] atom trailer*
atom: '(' [yield_expr|testlist_comp] ')' | '[' [testlist_comp] ']' | '{' [dictorsetmaker] '}' |
NAME | NUMBER | STRING+ | '...' | 'None' | 'True' | 'False'
trailer: '(' [arglist] ')' | '[' subscriptlist ']' | '.' NAME
arglist: argument (',' argument)* [',']
argument: test [comp_for] | test '=' test | '**' test | '*' test

А ось так визначено цікаві нам частині структури _PyParser_Grammar в Python/graminit.c
static arc arcs_0_0[3] = {
{2, 1},
{3, 1},
{4, 2},
};
static arc arcs_0_1[1] = {
{0, 1},
};
static arc arcs_0_2[1] = {
{2, 1},
};
static state states_0[3] = {
{3, arcs_0_0},
{1, arcs_0_1},
{1, arcs_0_2},
};

//...

static arc arcs_39_0[9] = {
{91, 1},
{92, 1},
{93, 1},
{94, 1},
{95, 1},
{19, 1},
{18, 1},
{17, 1},
{96, 1},
};
static arc arcs_39_1[1] = {
{0, 1},
};
static state states_39[2] = {
{9, arcs_39_0},
{1, arcs_39_1},
};

//...

static arc arcs_41_0[1] = {
{97, 1},
};
static arc arcs_41_1[1] = {
{26, 2},
};
static arc arcs_41_2[1] = {
{27, 3},
};
static arc arcs_41_3[1] = {
{28, 4},
};
static arc arcs_41_4[3] = {
{98, 1},
{99, 5},
{0, 4},
};
static arc arcs_41_5[1] = {
{27, 6},
};
static arc arcs_41_6[1] = {
{28, 7},
};
static arc arcs_41_7[1] = {
{0, 7},
};
static state states_41[8] = {
{1, arcs_41_0},
{1, arcs_41_1},
{1, arcs_41_2},
{1, arcs_41_3},
{3, arcs_41_4},
{1, arcs_41_5},
{1, arcs_41_6},
{1, arcs_41_7},
};

//...

static dfa dfas[85] = {
{256, "single_input", 0, 3, states_0,
"\004\050\340\000\002\000\000\000\012\076\011\007\262\004\020\002\000\300\220\050\037\102"},

//...

{270, "simple_stmt", 0, 4, states_14,
"\000\040\200\000\002\000\000\000\012\076\011\007\000\000\020\002\000\300\220\050\037\100"},

//...

{295, "compound_stmt", 0, 2, states_39,
"\000\010\140\000\000\000\000\000\000\000\000\000\262\004\000\000\000\000\000\000\000\002"},
{296, "async_stmt", 0, 3, states_40,
"\000\000\040\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000"},
{297, "if_stmt", 0, 8, states_41,
"\000\000\000\000\000\000\000\000\000\000\000\000\002\000\000\000\000\000\000\000\000\000"},
// ^^^

//...

};
static label labels[176] = {
{0, "EMPTY"},
{256, 0},
{4, 0}, // №2
{270, 0}, // №3
{295, 0}, // №4

//...

{305, 0}, // №26
{11, 0}, // №27

//...

{297, 0}, // №91
{298, 0},
{299, 0},
{300, 0},
{301, 0},
{296, 0},
{1, "if"}, // №97

//...

};
grammar _PyParser_Grammar = {
86,
dfas,
{176, labels},
256
};
(За нижченаведеним описом роботи парсера зручно було б стежити за цим лістингу — наприклад, відкривши його в сусідній вкладці.)

Парсер починає розбір з КА
single_input
; цей КА заданий масивом
states_0
з трьох станів. З початкового стану виходять три дуги (
arcs_0_0
), що відповідають вхідним символам
NEWLINE
(мітка №2, символ №4),
simple_stmt
(мітка №3, символ №270) та
compound_stmt
(мітка №4, символ №295). Вхідний термінал
"if"
(символ №1, мітка №97) входить у безліч
d_first
,
compound_stmt
, а не
simple_stmt
— йому відповідає біт \002 у 13-те байті множини. (Якщо під час розбору виявляється, що черговий термінал входить у безлічі
d_first
відразу для декількох вихідних дуг, то парсер виводить повідомлення про те, що граматика неоднозначна, і відмовляється продовжувати розбір.) Отже, парсер переходить по дузі
{4, 2}
в стан №2, і одночасно перемикається до КА
compound_stmt
, заданому масивом
states_39
. У цьому КА з початкового стану виходять відразу дев'ять дуг (
arcs_39_0
); вибираємо серед них дугу
{91, 1}
, відповідну вхідного символу
if_stmt
(№297). Парсер переходить в стан №1 і переключається до КА
if_stmt
, заданому масивом
states_41
. Із початкового стану цього КА виходить лише одна дуга
<nobr>{97, 1}</nobr>
, що відповідає нашому вхідного терміналу
"if"
. По ній парсер переходить в стан №1, звідки знову виходить єдина дуга
{26, 2}
, відповідна нетерминалу
test
(№305). По цій дузі парсер переходить в стан №2 і переключається до КА
test
, і так далі. Після довгого-предолгого перетворення числа
42
в нетерминал
test
, парсер повернеться в стан №2, з якого виходить єдина дуга
{27, 3}
, відповідна терміналу
COLON
(символ №11) і продовжить розбір нетерминала
if_stmt
. В якості результату його розбору парсер створить вузол конкретного синтаксичного дерева (структура
<a href="https://hg.python.org/cpython/file/default/Include/node.h">node</a>
), у якого буде тип вузла №297, і чотири дитини — типів №1 (
NAME
), №305 (
test
), №11 (
COLON
) і №304 (
suite
). У стані №4 створення сайту для
if_stmt
завершиться, парсер повернеться в стан №1 КА
compound_stmt
, і новостворений сайт
if_stmt
стане єдиною дитиною вузла, відповідного
compound_stmt
. Цілком КОД нашої програми буде виглядати так, як показано праворуч. Зауважте, як коротка програма із семи терміналів
NAME NUMBER COLON NAME LPAR STRING RPAR
перетворилася в «бамбук» — величезна, майже неветвящееся дерево розбору з аж 64 вузлів! Якщо вважати в байтах, то вихідна програма займає 27 байт, а її КСД — на два порядки більше: півтора кілобайта на 32-бітної системі, і три — на 64-бітної! (64 сайту за 24 або 48 байтів кожен). Саме із-за нестримно растягивающегося КОД спроби пропустити через
python
вихідні файли розміром всього в декілька десятків мегабайт призводять до фатальної
MemoryError
.

Для роботи з КОДУ в Python є стандартний модуль
<a href="https://docs.python.org/3.7/library/parser.html">parser</a>
:
$ python 
Python 3.7.0a0 (default:98c078fca8e0, Oct 31 2016, 08:33:23) 
[GCC 4.7.3] on linux
Type "help", "copyright", "credits" або "license" for more information.
>>> import parser
>>> parser.suite('if 42: print("Hello world")').tolist()
[257, [269, [295, [297, [1, 'if'], [305, [309, [310, [311, [312, [315, [316, [317, [318, [319, [320, [321, [322, [323, [324, [2, '42']]]]]]]]]]]]]]]], [11, ':'], [304, [270, [271, [272, [274, [305, [309, [310, [311, [312, [315, [316, [317, [318, [319, [320, [321, [322, [323, [324, [1, 'print']], [326, [7, '('], [334, [335, [305, [309, [310, [311, [312, [315, [316, [317, [318, [319, [320, [321, [322, [323, [324, [3, '"Hello world"']]]]]]]]]]]]]]]]]], [8, ')']]]]]]]]]]]]]]]]]]], [4, "]]]]]], [4, "], [0, "]]
>>> 

У його вихідному коді (
<a href="https://hg.python.org/cpython/file/80d1faa9735d/Modules/parsermodule.c">Modules/parsermodule.c</a>
для перевірки КОДУ на відповідність граматиці Python були >2000 рукописних рядків, які виглядали приблизно так:
//...

/* simple_stmt | compound_stmt
*
*/
static int
validate_stmt(node *tree)
{
int res = (validate_ntype(tree, stmt)
&& validate_numnodes(tree, 1, "stmt"));

if (res) {
tree = CHILD(tree, 0);

if (TYPE(tree) == simple_stmt)
res = validate_simple_stmt(tree);
else
res = validate_compound_stmt(tree);
}
return (res);
}

static int
validate_small_stmt(node *tree)
{
int nch = NCH(tree);
int res = validate_numnodes(tree, 1, "small_stmt");

if (res) {
int ntype = TYPE(CHILD(tree, 0));

if ( (ntype == expr_stmt)
|| (ntype == del_stmt)
|| (ntype == pass_stmt)
|| (ntype == flow_stmt)
|| (ntype == import_stmt)
|| (ntype == global_stmt)
|| (ntype == nonlocal_stmt)
|| (ntype == assert_stmt))
res = validate_node(CHILD(tree, 0));
else {
res = 0;
err_string("illegal small_stmt child type");
}
}
else if (nch == 1) {
res = 0;
PyErr_Format(parser_error,
"Unrecognized child node of small_stmt: %d.",
TYPE(CHILD(tree, 0)));
}
return (res);
}

/* compound_stmt:
* if_stmt | while_stmt | for_stmt | try_stmt | with_stmt | funcdef | classdef | decorated
*/
static int
validate_compound_stmt(node *tree)
{
int res = (validate_ntype(tree, compound_stmt)
&& validate_numnodes(tree, 1, "compound_stmt"));
int ntype;

if (!res)
return (0);

tree = CHILD(tree, 0);
ntype = TYPE(tree);
if ( (ntype == if_stmt)
|| (ntype == while_stmt)
|| (ntype == for_stmt)
|| (ntype == try_stmt)
|| (ntype == with_stmt)
|| (ntype == funcdef)
|| (ntype == async_stmt)
|| (ntype == classdef)
|| (ntype == decorated))
res = validate_node(tree);
else {
res = 0;
PyErr_Format(parser_error,
"Illegal compound statement type: %d.", TYPE(tree));
}
return (res);
}

//...

Легко здогадатися, що такий одноманітний код можна було б і автоматично генерувати по формальній граматиці. Трохи складніше здогадатися, що такий код вже генерується автоматично — саме так працюють автомати, використовувані першим парсером! Вище я потім в подробицях пояснював його пристрій, щоб пояснити, яким чином я в березні цього року запропонував замінити всі ці простирадла рукописного коду, які потрібно правити кожен раз, коли змінюється граматика, — на прогін всіх тих же самих автоматично згенерованих КА, якими користується сам парсер. Це розмов про те, потрібно чи програмістам знати алгоритми.

У червні мій патч був прийнятий, так що в Python 3.6+ вищенаведених простирадлом
Modules/parsermodule.c
вже немає, а натомість є кілька десятків рядків мого коду.




Працювати з таким громіздким і надлишковим КСД, як було показано вище, досить незручно; і тому другий парсер (
<a href="https://hg.python.org/cpython/file/default/Python/ast.c">Python/ast.c</a>
), написаний цілком вручну, обходить КОД і створює з нього абстрактне синтаксичне дерево. Граматика АСД описана у файлі
<a href="https://hg.python.org/cpython/file/default/Parser/Python.asdl">Parser/Python.asdl</a>
; для нашої програми АСД буде таким, як показано праворуч.

Замість роботи з КСД за допомогою модуля
parser
, документація радить використовувати модуль
<a href="https://docs.python.org/3.7/library/ast.html">ast</a>
і працювати з абстрактним деревом:
$ python
Python 3.7.0a0 (default:98c078fca8e0, Oct 31 2016, 08:33:23) 
[GCC 4.7.3] on linux
Type "help", "copyright", "credits" або "license" for more information.
>>> import ast
>>> ast.dump(ast.parse('if 42: print("Hello world")'))
"Module(body=[If(test=Num(n=42), body=[Expr(value=Call(func=Name(id='print', ctx=Load()), args=[Str(s='Hello world')], keywords=[]))], orelse=[])])"
>>> 

Як тільки АСД створено — КОД більше низачем не потрібно, і вся зайнята їм пам'ять звільняється; тому для «довгограючою» програми на Python немає великого значення, скільки пам'яті займало КОД. З іншого боку, для великих, але «скорострільних» скриптів (наприклад, пошук значення у величезному
dict
-литерале) — розмір КСД як раз і буде визначати споживання пам'яті скриптом. Все це на додачу до того, що саме розмір КОД визначає, чи вистачить пам'яті для того, щоб завантажити і запустити програму.

Необхідність проходу по довгих «бамбуковим гілкам» робить код
Python/ast.c
просто огидним:
static expr_ty
ast_for_expr(struct compiling *c, const node *n)
{

//...

loop:
switch (TYPE(n)) {
test case:
case test_nocond:
if (TYPE(CHILD(n, 0)) == lambdef ||
TYPE(CHILD(n, 0)) == lambdef_nocond)
return ast_for_lambdef(c, CHILD(n, 0));
else if (NCH(n) > 1)
return ast_for_ifexpr(c, n);
/* Fallthrough */
case or_test:
case and_test:
if (NCH(n) == 1) {
n = CHILD(n, 0);
goto loop;
}
// обробка булевих операцій

case not_test:
if (NCH(n) == 1) {
n = CHILD(n, 0);
goto loop;
}
// обробка not_test

case comparison:
if (NCH(n) == 1) {
n = CHILD(n, 0);
goto loop;
}
// обробка comparison

case star_expr:
return ast_for_starred(c, n);
/* The next five all cases handle BinOps. The main body of code
is the same in each case, but the switch turned inside out to
reuse the code for each type of operator.
*/
case expr:
case xor_expr:
case and_expr:
case shift_expr:
case arith_expr:
case term:
if (NCH(n) == 1) {
n = CHILD(n, 0);
goto loop;
}
return ast_for_binop(c, n);

// case yield_expr: і його обробка

case factor:
if (NCH(n) == 1) {
n = CHILD(n, 0);
goto loop;
}
return ast_for_factor(c, n);
case power:
return ast_for_power(c, n);
default:
PyErr_Format(PyExc_SystemError, "unhandled expr: %d", TYPE(n));
return NULL;
}
/* should never get here unless if error is set */
return NULL;
}

Багаторазово повторювані протягом другого парсера
if (NCH(n) == 1) n = CHILD(n, 0);
— іноді, як у цій функції, всередині циклу — означають «якщо у поточного вузла КОД всього одна дитина, то замість поточного вузла треба розглядати його дитини».

Але хіба щось заважає відразу під час створення КСД видаляти «однодетные» вузли, підставляючи замість них їх дітей? Адже це і заощадить купу пам'яті, і спростить другий парсер, дозволяючи позбавитися від багаторазового повторення
goto loop;
по всьому кодом, від виду якого Дейкстра завращался б дзигою у своїй труні!

У березні, разом з вищезазначеним патчем для
Modules/parsermodule.c
, я запропонував ще один патч, який:
  1. Додає в перший парсер автоматичне «стиснення» неветвящихся піддерев — в момент згортки (створення сайту КСД і повернення з поточного КА в попередній) «однодетный» вузол відповідного типу замінюється на свою дитину:
    diff -r ffc915a55a72 Parser/parser.c
    --- a/Parser/parser.c Mon Sep 05 00:01:47 2016 -0400
    +++ b/Parser/parser.c Mon Sep 05 08:30:19 2016 +0100
    @@ -52,16 +52,16 @@
    #ifdef Py_DEBUG
    
    static void
    s_pop(stack *s)
    {
    if (s_empty(s))
    Py_FatalError("s_pop: parser stack underflow -- FATAL");
    - s->s_top++;
    + PyNode_Compress(s->s_top++->s_parent);
    }
    
    #else /* !Py_DEBUG */
    
    -#define s_pop(s) (s)->s_top++
    +#define s_pop(s) PyNode_Compress((s)->s_top++->s_parent)
    
    #endif
    
    diff -r ffc915a55a72 Python/ast.c
    --- a/Python/ast.c Mon Sep 05 00:01:47 2016 -0400
    +++ b/Python/ast.c Mon Sep 05 08:30:19 2016 +0100
    @@ -5070,3 +5056,24 @@
    FstringParser_Dealloc(&state);
    return NULL;
    }
    +
    +void PyNode_Compress(node* n) {
    + if (NCH(n) == 1) {
    + node* ch;
    + switch (TYPE(n)) {
    + case suite: case comp_op: case subscript: case atom_expr:
    + case power: case factor: case expr: case xor_expr:
    + case and_expr: case shift_expr: case arith_expr: case term:
    + case comparison: case testlist_star_expr: case testlist:
    + case test: case test_nocond: case or_test: case and_test:
    + case not_test: case stmt: case dotted_as_name:
    + if (STR(n) != NULL)
    + PyObject_FREE(STR(n));
    + ch = CHILD(n, 0);
    + *n = *ch;
    + // All grandchildren are now сполучені штати прийняли; don't need to them free,
    + // so no need for PyNode_Free
    + PyObject_FREE(ch);
    + }
    + }
    +}
    
  2. Відповідним чином виправляє другий парсер, виключаючи з нього обхід «бамбукових гілок»: наприклад, згадана функція
    ast_for_expr
    замінюється на
    static expr_ty
    ast_for_expr(struct compiling *c, const node *n)
    {
    
    //...
    
    switch (TYPE(n)) {
    case lambdef:
    case lambdef_nocond:
    return ast_for_lambdef(c, n);
    test case:
    case test_nocond:
    assert(NCH(n) > 1);
    return ast_for_ifexpr(c, n);
    case or_test:
    case and_test:
    assert(NCH(n) > 1);
    // обробка булевих операцій
    
    case not_test:
    assert(NCH(n) > 1);
    // обробка not_test
    
    case comparison:
    assert(NCH(n) > 1);
    // обробка comparison
    
    case star_expr:
    return ast_for_starred(c, n);
    /* The next five all cases handle BinOps. The main body of code
    is the same in each case, but the switch turned inside out to
    reuse the code for each type of operator.
    */
    case expr:
    case xor_expr:
    case and_expr:
    case shift_expr:
    case arith_expr:
    case term:
    assert(NCH(n) > 1);
    return ast_for_binop(c, n);
    
    // case yield_expr: і його обробка
    
    case factor:
    assert(NCH(n) > 1);
    return ast_for_factor(c, n);
    case power:
    return ast_for_power(c, n);
    case atom:
    return ast_for_atom(c, n);
    case atom_expr:
    return ast_for_atom_expr(c, n);
    default:
    PyErr_Format(PyExc_SystemError, "unhandled expr: %d", TYPE(n));
    return NULL;
    }
    /* should never get here unless if error is set */
    return NULL;
    }
    
    З іншого боку, у багатьох вузлів в результаті «стиснення гілок» діти тепер можуть бути нових типів, і тому в багатьох місцях коду доводиться додавати нові умови.

  3. Оскільки «стислий КСД» вже не відповідає граматиці Python, то для перевірки його коректності
    Modules/parsermodule.c
    замість «сирої»
    _PyParser_Grammar
    тепер потрібно використовувати автомати, відповідні «транзитивному замикання» граматики: наприклад, для пари продукцій
    or_test ::= and_test
    test ::= or_test 'if' or_test 'else' test
    —додаються такі «транзитивні» продукції:
    test ::= or_test 'if' and_test 'else' test
    test ::= and_test 'if' or_test 'else' test
    test ::= and_test 'if' and_test 'else' test
    Під час ініціалізації модуля
    parser
    , функція
    Init_ValidationGrammar
    обходить автосгенерированные КА
    _PyParser_Grammar
    , на основі них створює «транзитивно замкнуті» КА, і зберігає їх у структурі
    ValidationGrammar
    . Для перевірки коректності КОД використовується саме
    ValidationGrammar
    .


Стислий КОД для нашого прикладу коду містить всього 21 сайт:
$ python 
Python 3.7.0a0 (default:98c078fca8e0+, Oct 31 2016, 09:00:27) 
[GCC 4.7.3] on linux
Type "help", "copyright", "credits" або "license" for more information.
>>> import parser
>>> parser.suite('if 42: print("Hello world")').tolist()
[257, [295, [297, [1, 'if'], [324, [2, '42']], [11, ':'], [270, [271, [272, [323, [324, [1, 'print']], [326, [7, '('], [334, [335, [324, [3, '"Hello world"']]]], [8, ')']]]]], [4, "]]]], [4, "], [0, "]]
>>> 

З моїм патчем стандартний набір бенчмарків показує скорочення споживання пам'яті процесом
python
до 30%
, при неизменившемся часу роботи. На вироджених прикладах скорочення споживання пам'яті доходить до триразового!

Але на жаль, за півроку з тих пір, як я запропонував свій патч, ніхто з мейнтейнерів так і не наважився його отревьюить — настільки він великий і страшний. У вересні же мені відповів сам Гвідо ван Россум: «Раз за весь цей час ніхто до патчу інтересу не проявив, — значить, нікого іншого споживання пам'яті парсером не турбує. Отже, немає сенсу витрачати час мейнтейнерів на його рев'ю.»

Сподіваюся, ця стаття пояснює, чому мій великий і страшний патч насправді потрібний і корисний; і сподіваюся, після цього пояснення у Python-спільноти дійдуть руки його отревьюить.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.