96    Лексический анализ и парсинг с использованием синтаксических деревьев

В выводе встречаются символические имена в нижнем регистре (например, 'arith_expr') и лексемы в верхнем регистре (например, 'NUMBER').

АБСТРАКТНЫЕ СИНТАКСИЧЕСКИЕ ДЕРЕВЬЯ

На следующем этапе интерпретатор CPython преобразует дерево CST, сгенерированное парсером, в нечто более логичное и подходящее для выполнения.

Конкретные синтаксические деревья являются буквальным представлением текста из кодового файла. Базовая грамматическая структура Python была интерпретирована, но CST не может использоваться для представления функций, областей видимости, циклов или других базовых средств языка Python.

Прежде чем код будет скомпилирован, CST необходимо преобразовать в структуру более высокого уровня, представляющую фактические конструкции Python. Эта структура является представлением CST и называется абстрактным синтаксическим деревом (AST).

Например, бинарная операция в AST называется BinOp и определяется как разновидность выражения. Она имеет три компонента:

1.left: левая часть операции.

2.op: оператор (например, +, - или *).

3.right: правая часть выражения.

Представление дерева AST для выражения a + 1 может выглядеть так:

Expr

Книги для программистов: https://t.me/booksforits

Абстрактные синтаксические деревья    97

Деревья AST строятся парсером CPython, но их также можно генерировать из кода Python с использованием модуля ast в стандартной библиотеке.

Прежде чем погружаться в реализацию AST, будет полезно понять, как выглядит AST для несложного фрагмента Python-кода.

Исходные файлы

Ниже перечислены исходные файлы, относящиеся к абстрактным синтаксическим деревьям.

ФАЙЛ НАЗНАЧЕНИЕ

Include Python-ast.h Объявление типов узлов AST, генерируемых

Parser asdl_c.py

Parser Python.asdl Список типов узлов и свойств AST на предметно-ориенти- рованном языке ASDL 5

Использование Instaviz для просмотра абстрактных синтаксических деревьев

Instaviz — пакет Python, написанный специально для этой книги. Он выводит AST и cкомпилированный код в веб-интерфейсе.

Чтобы установить Instaviz, загрузите пакет instaviz с помощью pip:

$ pip install instaviz

Затем откройте REPL, выполнив команду python в командной строке без аргументов.

Функция instaviz.show() принимает единственный аргумент — объект кода. Такие объекты будут рассматриваться в следующей главе. В данном примере определяется функция и используется ее имя как значение аргумента:

$ python

>>>import instaviz

>>>def example(): a = 1

Книги для программистов: https://t.me/booksforits

98    Лексический анализ и парсинг с использованием синтаксических деревьев

b = a + 1 return b

>>>instaviz.show(example)

Вкомандной строке появляется уведомление о том, что веб-сервер был запущен на порте 8080. Если порт используется для других целей, его можно

изменить вызовом instaviz.show(example, port=9090) или с другим номером порта.

В браузере выводятся подробные сведения о функции:

Граф внизу слева изображает функцию, объявленную в REPL и представленную в виде абстрактного синтаксического дерева. Каждый узел в дереве представляется типом AST. Эти типы находятся в модуле ast и наследуются от _ast.AST.

Книги для программистов: https://t.me/booksforits

Абстрактные синтаксические деревья    99

Некоторые узлы обладают свойствами, связывающими их с дочерними узлами, в отличие от деревьев CST, которые содержат обобщенное свойство дочернего узла.

Например, если кликнуть по узлу Assign в центре, он связывается со строкой b = a + 1:

Узел Assign содержит два свойства:

1. targets — список присваиваемых имен. Это список, потому что синтаксис распаковки позволяет присвоить значения сразу нескольким переменным одним выражением.

2.value — присваиваемое значение, которым в данном случае является команда BinOp — a + 1.

Если кликнуть по команде BinOp, выводятся соответствующие свойства:

zz left: узел слева от оператора.

zz op: оператор, в данном случае — узел Add (+) для сложения. zz right: узел справа от оператора.

Книги для программистов: https://t.me/booksforits

100    Лексический анализ и парсинг с использованием синтаксических деревьев

Компиляция AST

Компиляция AST в C — дело нетривиальное. Модуль Python ast.c содержит более 5000 строк кода.

Есть несколько точек входа, образующих часть общедоступного API для работы с AST. AST API получает узел дерева (CST), имя файла, флаги компилятора и область для хранения данных в памяти.

Результат имеет тип mod_ty, который представляет модуль Python, определенный в Include Python-ast.h.

mod_ty — контейнер для одного из четырех типов модулей в Python:

1.Module

2.Interactive

3.Expression

4.FunctionType

Все типы модулей перечислены в файле Parser Python.asdl. Все типы модулей, типы команд, типы выражений, операторы и включения (comprehensions) определяются в этом файле.

Книги для программистов: https://t.me/booksforits

Абстрактные синтаксические деревья    101

Названия типов в Parser Python.asdl соотносятся с классами, генерируемыми AST, и с именами для этих же классов, которые приводятся в модуле стандартной библиотеки ast:

--ASDL's 4 builtin types are:

--identifier, int, string, constant

module Python

Модуль ast импортирует Include Python-ast.h — файл, созданный автоматически из Parser Python.asdl при повторном генерировании грамматики. Параметры и имена в Include Python-ast.h напрямую соответствуют заданным в Parser Python.asdl.

Тип mod_ty генерируется в Include Python-ast.h из определения Module

в Parser Python.asdl:

enum _mod_kind {Module_kind=1, Interactive_kind=2, Expression_kind=3, FunctionType_kind=4};

struct _mod {

enum _mod_kind kind; union {

struct {

asdl_seq *body; asdl_seq *type_ignores;

} Module;

struct {

asdl_seq *body; } Interactive;

struct {

expr_ty body; } Expression;

struct {

asdl_seq *argtypes; expr_ty returns;

} FunctionType;

} v;

};

Книги для программистов: https://t.me/booksforits

102    Лексический анализ и парсинг с использованием синтаксических деревьев

Заголовочный файл и структуры C позволяют программе Python ast.c быстро генерировать структуры с указателями на соответствующие данные.

Точка входа AST, PyAST_FromNodeObject(), по сути представляет собой оператор switch для результата TYPE(n). TYPE() — макрос, используемый AST для определения типа узлов в конкретном синтаксическом дереве.

Результатом TYPE() является тип лексемы или символического имени.

Начиная с корневого узла, тип может относиться только к одному из определенных типов модулей — Module, Interactive, Expression или FunctionType:

zz Для file_input должен использоваться тип Module.

zz Для eval_input (например, для ввода из REPL) должен использоваться тип Expression.

Для каждого типа оператора в Python ast.c есть соответствующая функция C ast_for_xxx, которая просматривает узлы CST для заполнения свойств этой команды.

Одним из простых примеров служит выражение возведения в степень — например, 2 ** 4 (то есть 2 в степени 4). ast_for_power() возвращает BinOp с оператором Pow (Power), левой частью e (2) и правой частью f (4):

Python ast.c, строка 2717

static expr_ty

ast_for_power(struct compiling *c, const node *n)

{

/* power: atom trailer* ('**' factor)* */

expr_ty e; REQ(n, power);

e = ast_for_atom_expr(c, CHILD(n, 0)); if (!e)

return NULL; if (NCH(n) == 1)

return e;

if (TYPE(CHILD(n, NCH(n) - 1)) == factor) {

expr_ty f = ast_for_expr(c, CHILD(n, NCH(n) - 1)); if (!f)

return NULL;

e = BinOp(e, Pow, f, LINENO(n), n->n_col_offset, n->n_end_lineno, n->n_end_col_offset, c->c_arena);

}

return e;

}

Книги для программистов: https://t.me/booksforits

Абстрактные синтаксические деревья    103

Чтобы увидеть результат, отправьте короткую функцию модулю instaviz:

>>>def foo(): 2**4

>>>import instaviz

>>>instaviz.show(foo)

Соответствующие свойства отображаются в пользовательском интерфейсе:

Короче говоря, у каждого типа оператора и выражения имеется соответствующая функция ast_for_*() для его создания. Аргументы определяются

Книги для программистов: https://t.me/booksforits