Парсер/токенизатор 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.

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

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

Книги для программистов: 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

Корневой узел CST, возвращаемый PyParser_ParseFileObject(), критичен для следующей стадии — преобразования CST в абстрактное синтаксическое дерево (AST).

Тип узла определяется в файле Include node.h:

Книги для программистов: 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