Практика использования парсер-комбинаторов peco и оператора match для создания простых DSL на языке Python

Задачи разработки компиляторов и интерпретаторов конфигурационных языков или даже полноценных Тьюринг-полных языков программирования время от времени встают перед разработчиками программного обеспечения. На практике, как правило, речь идёт о разработке предметно-ориентированных языков (англ. Domain Specific Language, DSL), проектируемых специально для решения узкого класса прикладных задач.

DSL-компиляторы применяются, в том числе, для:

• конфигурирования спецпроцессоров на основе FPGA (PyLog),

• описания правил SSA-оптимизаций в компиляторах,

• ускорения вычислений на CPU или GPU (numpy, numba и прочие JIT-компиляторы),

• компактного описания наборов конфигурационных файлов (Jsonnet, Dhall),

• описания фрагментов систем на едином языке, понятном не только техническим специалистам (Ubiquitous Language) и др.

Определимся, что далее по тексту мы будем называть компилятором инструмент для перевода программ с одного языка на другой язык (K.D. Cooper & L. Torczon, Engineering a Compiler, 2011).

Классическая архитектура компилятора включает фронтенд компилятора (англ. Compiler Frontend) и бэкенд компилятора (англ. Compiler Backend). Фронтенд компилятора преобразует программу на языке высокого уровня в промежуточное представление — дерево абстрактного синтаксиса (англ. Abstract Syntax Tree, AST), выполняя также семантический анализ AST, а бэкенд синтезирует целевой код из AST, при необходимости применяя оптимизирующие преобразования.

Замечание. В современных промышленных компиляторах, таких как LLVM и GCC, также выделяют стадию Middle-End, на которой к программе применяются оптимизирующие преобразования, не зависящие ни от входного, ни от выходного языка. Для упрощения мы относим эту стадию к бэкенду рассматриваемого в статье миниатюрного компилятора, хотя такие его части, как система переписывания AST и графовое промежуточное представление, о которых пойдёт речь далее, можно было бы выделить в отдельную стадию Middle-End.

На высоком уровне простой компилятор можно описать как:

Code -> AST -> Code'

В настоящей статье рассматривается один из способов реализации DSL-компиляторов на примере разработки системы символьного дифференцирования, как в SymPy, с использованием парсер-комбинаторов peco и структурного сопоставления с образцом по PEP 636. Материал рассчитан на прикладных разработчиков, уже знакомых с Python, но, надеюсь, может быть полезен и продолжающим компиляторщикам.

Средство для символьного дифференцирования выражений

Рассмотрим следующую задачу. Пусть дан текст на формальном языке для описания простых арифметических выражений с поддержкой переменных и вызовов функций, причём грамматика этого языка в расширенной форме Бэкуса-Наура (англ. Extended Backus-Naur Form, EBNF) по стандарту ISO/IEC 14977:1996 имеет вид:

' var = [a-z∂]+ ' num = [0-9]+ op   = "+" | "*" | "^" | "-" | "/"; expr = "(" , expr , op , expr , ")"      | var , "(" , expr , { "," , expr } , ")"      | var      | num;

В целях упрощения, для определения правил var и num использованы регулярные выражения. Однако, в «настоящем» EBNF пришлось бы явно перечислить все подходящие символы: letter = "a" | "b" | ...

По грамматике выше, имена переменных и функций (см. правило var) в рассматриваемом языке состоят из одной или нескольких букв в нижнем регистре, при этом поддерживаются операторы (см. правило op) сложения, умножения, возведения в степень и другие.

Грамматика expr уже интереснее — выражение может быть применением бинарного оператора к двум другим выражениям, вызовом функции, переменной или числом. EBNF, соответствующую стандарту ISO/IEC 14977:1996, легко визуализировать при помощи PlantUML и получить железнодорожную диаграмму (англ. railroad diagram), описывающую синтаксис выражения:

Примеры синтаксически корректных текстов на описанном языке включают следующие:

(x(y(5))-x) (exp((x+1))/(y^2)) x(z(y(x,(z+1)))) ∂(((2*(x^y))+(log(x))),x) ∂((x^(2+1)),x) ...

Однако, синтаксическая корректность выражения ещё не гарантирует, что выражение вычисляет что-то полезное и осмысленное. Исключим из списка выше выражения, не выполняющие полезных арифметических операций, и получим следующий набор:

(exp((x+1))/(y^2)) ∂(((2*(x^y))+(log(x))),x) ∂((x^(2+1)),x) ...

Выражение ∂(expr,x) выше обозначает производную выражения expr по x.

Именно такие выражения нас будут интересовать в следующих разделах.

Фронтенд компилятора

Классическая реализация фронтенда компилятора включает два этапа — лексический разбор и синтаксический разбор. На этапе лексического разбора строка с текстом программы преобразуется в список лексических единиц — токенов, а на этапе синтаксического разбора из списка токенов строится AST. Подобным образом работают такие инструменты, как flex и bison или python lex/yacc Д. Бизли.

Однако, мы применим другой подход, известный в литературе как РВ-грамматика — грамматику, разбирающую выражение (англ. Parsing Expression Grammar, PEG). PEG, в отличие от контекстно-свободных грамматик, не могут быть неоднозначными — проверка альтернатив оператором | в PEG производится всегда последовательно. Кроме того, PEG позволяет разобрать текст сразу в AST, без выделенного этапа лексического разбора строки:

Code -> AST

Начало работы

Для разбора нашего формального языка мы воспользуемся комбинаторами разбора, реализованными в библиотеке parsing expression combinators (peco). По сравнению с существующими аналогами [1, 2], библиотека peco проста и минималистична: она не имеет внешних зависимостей и представляет собой единственный Python-файл, содержащий менее 100 непустых строк кода (sic!), 0 классов и всего 16 комбинаторов — функций высшего порядка, принимающих на вход функции и возвращающих другие функции. Эти комбинаторы генерируют парсеры, которые принимают на вход и возвращают состояние разбора:

Peco = namedtuple('Peco', 'text pos ok stack glob')

Например, так выглядит комбинатор разбора альтернатив.

Для начала работы необходимо подключить peco к нашему проекту. В случае, если мы работаем в git-репозитории, один из простейших способов сделать это — добавить peco в наш репозиторий как подмодуль git, выполнив из корня нашего репозитория команду:

git submodule add https://github.com/true-grue/peco.git peco

Теперь можно приступать к разработке фронтенда компилятора!

Начнём с разбора имён переменных и функций:

from peco.peco import *  var = eat(r'[a-z∂]+')  print(parse('∂', var).ok)   # True print(parse('exp', var).ok) # True print(parse('42', var).ok)  # False

Отлично! Имена переменных по самому первому правилу в EBNF выше у нас получилось распознать. Функция parse запускает процесс разбора заданной строки заданным правилом, а комбинатор eat принимает на вход регулярное выражение и во время разбора текста пробует применить регулярное выражение к строке, начиная с текущей позиции pos. В случае успеха eat перемещает курсор pos вперёд на число распознанных регулярным выражением символов.

Аналогичным образом разберём числа:

num = eat(r'[0-9]+')  print(parse('1', num).ok)  # True print(parse('42', num).ok) # True print(parse('x', num).ok)  # False

Также разберём операторы, поддерживающиеся в нашем формальном языке:

op = eat(r'\+|\*|\^|-|/')  print(parse('+', op).ok) # True print(parse('%', op).ok) # False

Для разбора имён, чисел и операторов нам оказалось достаточно регулярных выражений — и это ожидаемый результат, ведь простые последовательности букв или цифр — это регулярный язык, регулярный язык распознаётся конечным автоматом, а регулярное выражение позволяет задать такой конечный автомат.

Реализуем теперь правило разбора для выражения expr:

expr = lambda s: expr(s) expr = alt(     seq(eat(r'\('), expr, op, expr, eat(r'\)')),     seq(var, eat(r'\('), expr, many(seq(eat(r','), expr)), eat(r'\)')),     var,     num, )  print(parse('(exp((x+1))/(y^2))', expr).ok)      # True     print(parse('∂(((2*(x^y))+log(x)),x)', expr).ok) # True print(parse('∂((x^(2+1)),x)', expr).ok)          # True print(parse('∂(x^(2+1)),x)', expr).ok)           # False

Здесь регулярных выражений оказалось недостаточно, добавились новые комбинаторы!

• Комбинатор alt пробует применить к входному тексту парсеры по порядку и возвращает первый успешный результат.

• Комбинатор seq применяет к тексту все переданные ему парсеры последовательно, передвигая курсор вправо после каждого удачного распознавания, при этом должны сработать все переданные парсеры.

• Комбинатор many работает как звезда Клини * — применяет парсер 0 или ∞ раз.

Замечание. Выражение expr = lambda s: expr(s) позволяет сделать правило expr рекурсивным: сначала в области видимости создаётся функция с именем expr, вызывающая в своём теле функцию с именем expr. Однако после выполнения инструкции expr = alt(...) имя expr в текущей области видимости переопределяется, и ранее определённая функция expr теперь в своём теле вызывает новую функцию. Убедитесь в этом при помощи вызова locals() или globals().

Мы реализовали грамматику, успешно распознающую все выражения из вводной части! Но, всё-таки, ожидается, что результатом работы фронтенда компилятора окажется AST, построенное из текста программы.

Внимательный читатель наверняка обратит внимание, что помимо полей text, pos и ok, с которыми мы уже работали, у состояния peco есть поле stack. Для обновления содержимого этого поля в peco реализованы комбинаторы push, to и group:

• Комбинатор push(f) добавляет на стек распознанную парсером f строку.

• Комбинатор to(f) снимает с вершины стека n элементов, где n — число аргументов функции f, позволяет обработать извлечённый набор элементов и поместить результат обработки обратно на стек.

• Комбинатор group(f) объединяет все элементы, размещённые парсером f на стеке, в единственный кортеж.

Перепишем нашу грамматику, используя стек для хранения и преобразования результатов распознавания:

from peco.peco import * from pprint import pprint  # Добавим на стек распознанную строку (push). var = push(eat(r'[a-z∂]+'))  # Добавим на стек распознанную строку, состоящую из цифр (push). # Снимем строку с вершины стека, преобразуем в int, добавим обратно (to).  num = seq(push(eat(r'[0-9]+')), to(lambda x: int(x)))  # Добавим на стек распознанную строку из одного символа (push). op = push(eat(r'\+|\*|\^|-|/'))  expr = lambda s: expr(s)  # Вынесем аргументы функции в отдельное правило args для читаемости. # Сгруппируем аргументы, добавленные на стек парсерами expr, в кортеж (group). args = group(seq(expr, many(seq(eat(r','), expr)))) expr = alt(     # Снимем 3 элемента со стека и добавим 1 кортеж     # в префиксной форме обратно на стек (to).     seq(eat(r'\('), expr, op, expr, eat(r'\)'),         to(lambda lhs, op, rhs: (op, lhs, rhs))),     # Снимем 2 элемента со стека и добавим 1 кортеж     # в префиксной форме обратно на стек (to).     seq(var, eat(r'\('), args, eat(r'\)'),         to(lambda fun, args: (fun, *args))),     var,     num, )  pprint(parse('x', expr).stack[0]) # 'x' pprint(parse('1', expr).stack[0]) # 1 pprint(parse('∂((x^2),x)', expr).stack[0]) # ('∂', ('^', 'x', 2), 'x') pprint(parse('∂(((2*(x^y))+log(x)),x)', expr).stack[0]) # ('∂', ('+', ('*', 2, ('^', 'x', 'y')), ('log', 'x')), 'x')

Отлично, мы получили AST, описанное при помощи вложенных друг в друга кортежей!

Первый элемент кортежа — это оператор или имя функции, такую форму в дальнейшем будет удобно интерпретировать. Кстати, реализованную грамматику несложно доработать для поддержки пробелов и переносов строк. Читаемость грамматики можно улучшить, воспользовавшись комбинатором list_of и назначив имена mk* для функций-«строителей» AST:

from peco.peco import *  # Поддержка пробелов и переносов строк. space = eat(r'\s*') token = lambda f: seq(space, f) tok = lambda c: token(push(eat(c))) skip = lambda c: token(eat(c))  # Функции-«строители» AST. mknum = to(lambda x: int(x)) mkbop = to(lambda lhs, op, rhs: (op, lhs, rhs)) mkfun = to(lambda fun, args: (fun, *args))  var = tok(r'[a-z∂]+') num = seq(tok(r'[0-9]+'), mknum) bop = tok(r'\+|\*|\^|-|/')  expr = lambda s: expr(s) args = group(list_of(expr, skip(','))) expr = alt(     seq(skip(r'\('), expr, bop, expr, skip(r'\)'), mkbop),     seq(var, skip(r'\('), args, skip(r'\)'), mkfun),     var,     num, )  src = ''' ∂(( (2 * ( var ^ power )) +     log(var) ),   var) '''  ast, = parse(src, seq(expr, space)).stack print(ast) # ('∂', ('+', ('*', 2, ('^', 'var', 'power')), ('log', 'var')), 'var')

Грамматика заняла всего 20 строк кода!

Бэкенд компилятора

Бэкенд компилятора синтезирует целевой код из AST:

AST -> Code'

Мы реализуем несколько модулей бэкенда компилятора для синтеза кода на разных языках.

Синтез кода на DSL dot для Graphviz

Начнём с визуализации вложенных друг в друга кортежей — структуры данных, которую в предыдущем разделе мы назвали AST. Нужно ведь показать, что у нас действительно получилось синтаксическое дерево!

Сначала полезно преобразовать вложенные кортежи в графовое промежуточное представление (англ. Intermediate Representation, IR). Граф — это совокупность непустого множества вершин и множества связей между вершинами, но для упрощения работы мы сохраним вершины в словаре dict[int, str], где ключ — это номер вершины при обходе AST. Связи сохраним в словаре dict[int, list[int]]:

def walk(ast, names, graph):     i = len(names)     match ast:         case op, *args:             names[i] = op             graph[i] = [walk(arg, names, graph) for arg in args]         case atom:             names[i] = atom     return i  ast = ('∂', ('+', ('*', 2, ('^', 'x', 'y')), ('log', 'x')), 'x') names, graph = {}, {} walk(ast, names, graph) print(names) # {0: '∂', 1: '+', 2: '*', 3: 2, 4: '^', 5: 'x', 6: 'y', 7: 'log', 8: 'x', 9: 'x'} print(graph) # {4: [5, 6], 2: [3, 4], 7: [8], 1: [2, 7], 0: [1, 9]}

В операторе match структурного сопоставления с образцом (см. PEP 636) выражение case op, *args соответствует всем последовательностям, содержащим хотя бы один элемент — таким как ('+', 'x', 'y') или ('exp', 2). При этом в переменную op помещается первый элемент последовательности, а в переменную args — список из всех остальных элементов.

От графового IR легко перейти, например, к коду на DSL dot визуализатора graphviz:

def dot(names, graph):     print('digraph {')     print('node [shape=rect, fontname="Ubuntu Mono"]')     for i, name in names.items():         print(f'{i} [label="{name}"]')     for source in graph:         for target in graph[source]:             print(f'{source} -> {target}')     print('}')  dot(names, graph)

Визуализировать полученный код на языке dot легко в онлайн-версии graphviz:

Синтез команд LaTeX

Поскольку мы работаем с формулами и собираемся сделать систему символьного дифференцирования, было бы удобно смотреть на наши выражения не как на код или деревья, а как на настоящие формулы.

Формулы мы сможем получить, если научимся транслировать наше AST в набор команд системы компьютерной вёрстки LaTeX. Для этого создадим словарь OPS с шаблонами для поддерживаемых операторов и функций, а затем вновь воспользуемся структурным сопоставлением с образцом для рекурсивного обхода AST:

OPS = {     '+': '{%s}+{%s}',     '*': '{%s}{%s}',     '^': '{%s}^{%s}',     '-': '{%s}-{%s}',     '/': '\\frac{%s}{%s}',     '∂': '\\frac{\\partial{\\left(%s\\right)}}{\\partial{%s}}', }  def tex(tree):     match tree:         case op, *args:             return OPS[op] % tuple(map(tex, args))         case atom:             return atom  ast = ('∂', ('+', ('*', 2, ('^', 'x', 'y')), ('log', 'x')), 'x') print(tex(ast), '.') # \frac{\partial{\left({{2}{{x}^{y}}}+{\log{x}}\right)}}{\partial{x}}.

Визуализировать формулу LaTeX можно, например, в онлайн-редакторе LaTeX:

Система переписывания AST

В настоящих компиляторах к AST, построенному фронтендом компилятора, применяется целый ряд оптимизирующих преобразований: выполняется свёртка констант (англ. constant folding), преобразование AST к IR в форме статического одиночного присваивания (англ. static single assignment form, SSA), которое затем переписывается для удаления недостижимого кода, экономии выражений, раскрутки циклов, …

Нашу систему символьного дифференцирования мы также реализуем как переписывающую систему (англ. term rewriting system, TRS) на основе таблицы производных функций. Алгоритм здесь следующий: если мы в процессе обхода AST встречаем поддерево, соответствующее формуле из левой части таблицы, то мы это поддерево заменяем на поддерево, соответствующее формуле из правой части таблицы:

def topdown(rule, expr):     match rule(expr):         case (spec, *args):             return (spec, *(topdown(rule, arg) for arg in args))         case expr:             return expr  def derive(expr):     match expr:         case ('∂', ('+', u, v), var):             return ('+', ('∂', u, var), ('∂', v, var))         case ('∂', ('*', int(c), expr), var):             return ('*', c, ('∂', expr, var))         case ('∂', ('log', expr), var):             return ('/', ('∂', expr, var), expr)         case ('∂', ('^', expr, n), var):             return ('*', n, ('*', ('^', expr, ('-', n, 1)), ('∂', expr, var)))         case ('∂', str(var0), str(var)) if var0 == var:             return 1         case expr:             return expr  # Попробуем переписать AST без спуска от корня к листьям: ast = ('∂', ('+', ('*', 2, ('^', 'x', 'y')), ('log', 'x')), 'x') print(tex(ast), '=', tex(derive(ast)), '.')

Для преобразования формулы в LaTeX мы воспользовались реализованной функцией tex:

Теперь обойдём AST, переписывая всё, что можно, при помощи функции topdown:

ast = ('∂', ('+', ('*', 2, ('^', 'x', 'y')), ('log', 'x')), 'x') print(tex(ast), '=', tex(derive(ast)), '=', tex(topdown(derive, ast)), '.')

Ура, посчитали! Но в конце первого слагаемого находится единица, которую обычно не записывают в ответе. Как нам избавиться от такой избыточности? Правильно, реализовать ещё один набор правил переписывания, для упрощения выражений!

def simplify(expr):     match expr:         case ('*', 1, expr) | ('*', expr, 1):             return expr         case ('-', int(lhs), int(rhs)):             return lhs - rhs         case ('^', expr, 1):             return expr         case expr:             return expr  ast = ('∂', ('+', ('*', 2, ('^', 'x', 'y')), ('log', 'x')), 'x') print(tex(ast), '=', tex(topdown(simplify, topdown(derive, ast))), '.')

Отлично, убрали избыточность. А что, если после упрощения выражения при обходе AST сверху вниз появляется возможность упростить его ещё сильнее? Например, применение наших правил переписывания к следующему AST порождает выражение, всё ещё содержащее избыточное возведение в степень ('^', 'x', 1):

ast = ('∂', ('+', ('^', 'x', 2), ('^', 'x', 3)), 'x') print(tex(ast), '=', tex(topdown(simplify, topdown(derive, ast))), '.')

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

Простое решение нашей проблемы — найти неподвижную точку (англ. fixed point), то есть такое AST, для которого справедливо утверждение: ast == topdown(simplify, ast). Реализуем функцию rewrite, которая найдёт неподвижную точку, и будем упрощать наши выражения всегда с её помощью:

def rewrite(rule, expr):     while (new_expr := topdown(rule, expr)) != expr:         expr = new_expr     return new_expr  ast = ('∂', ('+', ('^', 'x', 2), ('^', 'x', 3)), 'x') print(tex(ast), '=', tex(rewrite(simplify, rewrite(derive, ast))), '.')

Готово! Получаем желаемый результат:

Обзор основных результатов

Кажется, нам удалось реализовать компилятор простого минималистичного DSL, который умеет дифференцировать и упрощать выражения, транслировать выражения в LaTeX-код для визуализации формул, а также в код на языке dot для визуализации деревьев при помощи graphviz. Архитектура нашего компилятора теперь имеет следующий вид:

Нашим компилятором теперь можно пользоваться следующим образом:

src = '∂( ((( (3 * (x ^ y)) + log((x ^ y))) + (4*x)) + (x^2)), x)' ast, = parse(src, seq(expr, space)).stack print(tex(ast), '=', tex(rewrite(simplify, rewrite(derive, ast))), '.')

Задача 1. Добавьте новые правила переписывания в derive и simplify для поддержки символьного дифференцирования других выражений на нашем формальном языке из вводной части статьи, а также для упрощения 2-го слагаемого из правой части формулы выше.

Задача 2. Попробуйте реализовать трансляцию нашего графового IR в форматы визуализаторов диаграмм и графов Mermaid или PlantUML.

Задача 3. Попробуйте при помощи peco разобрать язык с более сложной грамматикой, например, LaTeX. В качестве примера можно изучить тесты в репозитории peco, а также реализацию разбора синтаксиса учебного языка aozaki.

Дальнейшее изучение

Литература по компиляторам для новичков и продолжающих собрана в замечательном репозитории Что читать о разработке компиляторов? на GitHub. Кроме того, выделю материалы, которые заинтересуют и практикующих компиляторщиков, и им сочувствующих:

• Константин Владимиров, Оптимизирующие компиляторы: теория и алгоритмы, Курс лекций по компиляторам, 2024 [По материалам курса есть одноимённая книга].

• Пётр Советов, В Python есть готовый фронтенд для вашего компилятора, Запись выступления на конференции PiterPy, 2023 [Материалы опубликованы на GitHub].

• Павел Соломатин, JIT-компилятор Python в 300 строк, Habr, 2022.

Отдельное спасибо Петру Советову @true-grue за ценные комментарии, позволившие (существенно!) упростить примеры кода в статье, а также за рецензирование материала.