- •Об авторе
- •О группе редакторов
- •Предисловие
- •Введение
- •Как использовать эту книгу
- •Загрузка исходного кода CPython
- •Что в исходном коде?
- •Настройка среды разработки
- •IDE или редактор?
- •Настройка Visual Studio
- •Настройка Visual Studio Code
- •Настройка Vim
- •Выводы
- •Компиляция CPython
- •Компиляция CPython на macOS
- •Компиляция CPython на Linux
- •Установка специализированной версии
- •Знакомство с Make
- •Make-цели CPython
- •Компиляция CPython на Windows
- •Профильная оптимизация
- •Выводы
- •Грамматика и язык Python
- •Спецификация языка Python
- •Генератор парсеров
- •Повторное генерирование грамматики
- •Выводы
- •Конфигурация и ввод
- •Конфигурация состояния
- •Структура данных конфигурации среды выполнения
- •Конфигурация сборки
- •Сборка модуля из входных данных
- •Выводы
- •Генерирование конкретного синтаксического дерева
- •Парсер/токенизатор CPython
- •Абстрактные синтаксические деревья
- •Важные термины
- •Пример: добавление оператора «почти равно»
- •Выводы
- •Компилятор
- •Исходные файлы
- •Важные термины
- •Создание экземпляра компилятора
- •Флаги будущей функциональности и флаги компилятора
- •Таблицы символических имен
- •Основная компиляция
- •Ассемблер
- •Создание объекта кода
- •Использование Instaviz для вывода объекта кода
- •Пример: реализация оператора «почти равно»
- •Выводы
- •Цикл вычисления
- •Исходные файлы
- •Важные термины
- •Построение состояния потока
- •Построение объектов кадров
- •Выполнение кадра
- •Стек значений
- •Пример: добавление элемента в список
- •Выводы
- •Управление памятью
- •Выделение памяти в C
- •Проектирование системы управления памятью Python
- •Аллокаторы памяти CPython
- •Область выделения объектной памяти и PyMem
- •Область выделения сырой памяти
- •Нестандартные области выделения памяти
- •Санитайзеры выделенной памяти
- •Арена памяти PyArena
- •Подсчет ссылок
- •Сборка мусора
- •Выводы
- •Параллелизм и конкурентность
- •Модели параллелизма и конкурентности
- •Структура процесса
- •Многопроцессорный параллелизм
- •Многопоточность
- •Асинхронное программирование
- •Генераторы
- •Сопрограммы
- •Асинхронные генераторы
- •Субинтерпретаторы
- •Выводы
- •Объекты и типы
- •Примеры этой главы
- •Встроенные типы
- •Типы объектов
- •Тип type
- •Типы bool и long
- •Тип строки Юникода
- •Словари
- •Выводы
- •Стандартная библиотека
- •Модули Python
- •Модули Python и C
- •Набор тестов
- •Запуск набора тестов в Windows
- •Запуск набора тестов в Linux или macOS
- •Флаги тестирования
- •Запуск конкретных тестов
- •Модули тестирования
- •Вспомогательные средства тестирования
- •Выводы
- •Отладка
- •Обработчик сбоев
- •Компиляция поддержки отладки
- •LLDB для macOS
- •Отладчик Visual Studio
- •Отладчик CLion
- •Выводы
- •Бенчмаркинг, профилирование и трассировка
- •Использование timeit для микробенчмарка
- •Использование набора тестов производительности Python
- •Профилирование кода Python с использованием cProfile
- •Выводы
- •Что дальше?
- •Создание расширений C для CPython
- •Улучшение приложений Python
- •Участие в проекте CPython
- •Дальнейшее обучение
- •Препроцессор C
- •Базовый синтаксис C
- •Выводы
- •Благодарности
Парсер/токенизатор CPython 91
'__name__', '__package__', '__spec__', '_main', '_name', '_value', 'and_expr', 'and_test', 'annassign', 'arglist', 'argument', 'arith_expr', 'assert_stmt', 'async_funcdef', 'async_stmt', 'atom', 'atom_expr',
...
>>>import token
>>>dir(token)
['AMPER', 'AMPEREQUAL', 'AT', 'ATEQUAL', 'CIRCUMFLEX', 'CIRCUMFLEXEQUAL', 'COLON', 'COMMA', 'COMMENT', 'DEDENT', 'DOT',
'DOUBLESLASH', 'DOUBLESLASHEQUAL', 'DOUBLESTAR', 'DOUBLESTAREQUAL',
...
ПАРСЕР/ТОКЕНИЗАТОР CPYTHON
В языках программирования применяются разные реализации лексического анализатора. Некоторые языки используют лексический анализатор/генератор как дополнение к парсеру. В CPython существует модуль парсера/ токенизатора, написанный на C.
Исходные файлы
Ниже перечислены исходные файлы, относящиеся к парсеру/выделителю лексем.
ФАЙЛ |
НАЗНАЧЕНИЕ |
Python pythonrun.c |
Запускает парсер и компилятор для входных данных |
Parser parsetok.c |
Реализация парсера и токенизатора |
Parser tokenizer.c |
Реализация токенизатора |
Parser tokenizer.h |
Заголовочный файл для реализации токенизатора, |
|
описывающий модели данных (например, состояние |
|
лексем) |
Include token.h |
Объявление типов лексем, генерируемых |
|
Tools scripts generate_token.py |
Include node.h |
Интерфейс разбора узлов дерева и макросы для токе- |
|
низатора |
Книги для программистов: https://t.me/booksforits
92 Лексический анализ и парсинг с использованием синтаксических деревьев
Ввод данных в парсер из файла
Точка входа парсера/токенизатора, PyParser_ASTFromFileObject(), получает дескриптор файла, флаги компилятора и экземпляр PyArena и преобразует объект файла в модуль.
Процедура состоит из двух шагов:
1.Преобразование в CST с использованием PyParser_ParseFileObject().
2.Преобразование в AST или модуль функцией AST — P y A S T _
FromNodeObject().
Функция PyParser_ParseFileObject() выполняет две важные задачи:
1. Создание экземпляра состояния токенизатора tok_state при помощи
PyTokenizer_FromFile().
2. Преобразование лексем в CST (список узлов) функцией parsetok().
Логика парсера/токенизатора
Парсер/токенизатор получает текстовый ввод и запускает токенизатор и парсер в цикле, пока курсор не достигнет конца текста (или не произойдет ошибка синтаксиса).
Перед этим парсер/токенизатор создает tok_state — временную структуру данных для хранения всех состояний, используемых токенизатором. Состояние содержит такую информацию, как текущая позиция курсора и строка.
Парсер/токенизатор вызывает tok_get() для получения следующей лексемы. Затем он передает полученный идентификатор лексемы парсеру, который использует ДКА парсера/генератора для создания узла конкретного синтаксического дерева.
tok_get() — одна из самых сложных функций во всей кодовой базе CPython. Она содержит свыше 640 строк, и в ней отражены десятилетия унаследованных граничных случаев, новые языковые возможности и синтаксис.
Процесс вызова токенизатора и парсера в цикле может быть наглядно представлен следующим образом:
Книги для программистов: https://t.me/booksforits
Парсер/токенизатор CPython 93
/
•
ID
•
CST
CST
Корневой узел CST, возвращаемый PyParser_ParseFileObject(), критичен для следующей стадии — преобразования CST в абстрактное синтаксическое дерево (AST).
Тип узла определяется в файле Include node.h:
typedef struct _node { |
|
short |
n_type; |
char |
*n_str; |
int |
n_lineno; |
int |
n_col_offset; |
int |
n_nchildren; |
struct |
_node *n_child; |
int |
n_end_lineno; |
int |
n_end_col_offset; |
} node; |
|
Книги для программистов: https://t.me/booksforits
94 Лексический анализ и парсинг с использованием синтаксических деревьев
Так как CST является деревом синтаксиса, идентификаторов лексем и символических имен, компилятору трудно принимать быстрые решения, основанные на коде Python.
Прежде чем переходить к AST, отметим, что существует возможность просмотра вывода стадии разбора. В CPython имеется модуль стандартной библиотеки parser, который предоставляет функции C с Python API.
Вывод будет числовым, в нем используются номера лексем и символических имен, сгенерированных на стадии make regen-grammar и хранящихся
вInclude token.h:
>>>from pprint import pprint
>>>import parser
>>>st = parser.expr('a + 1')
>>>pprint(parser.st2list(st))
[258,
[332,
[306,
[310,
[311,
[312,
[313,
[316,
[317,
[318,
[319,
[320,
[321, [322, [323, [324, [325, [1, 'a']]]]]], [14, '+'],
[321, [322, [323, [324, [325, [2, '1']]]]]]]]]]]]]]]]],
[4, ''], [0, '']]
Чтобы вам было проще понять вывод, можно взять все числа из модулей symbol и token, поместить их в словарь и рекурсивно заменить значения в выводе parser.st2list() именами лексем:
cpython-book-samples 21 lex.py
import symbol import token import parser
def lex(expression):
symbols = {v: k for k, v in symbol.__dict__.items() if isinstance(v, int)}
Книги для программистов: https://t.me/booksforits
Парсер/токенизатор CPython 95
tokens = {v: k for k, v in token.__dict__.items() if isinstance(v, int)}
lexicon = {**symbols, **tokens} st = parser.expr(expression) st_list = parser.st2list(st)
def replace(l: list): r = []
for i in l:
if isinstance(i, list): r.append(replace(i))
else:
if i in lexicon: r.append(lexicon[i])
else:
r.append(i)
return r
return replace(st_list)
Выполните lex() с простым выражением (например, a + 1), чтобы увидеть, как оно представляется в виде дерева парсера:
>>>from pprint import pprint
>>>pprint(lex('a + 1'))
['eval_input', ['testlist', ['test',
['or_test', ['and_test',
['not_test', ['comparison',
['expr', ['xor_expr',
['and_expr', ['shift_expr', ['arith_expr',
['term',
['factor', ['power', ['atom_expr', ['atom', ['NAME', 'a']]]]]],
['PLUS', '+'], ['term',
['factor',
['power', ['atom_expr', ['atom', ['NUMBER', '1']]]]]]]]]]]]]]]]],
['NEWLINE', ''], ['ENDMARKER', '']]
Книги для программистов: https://t.me/booksforits