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

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

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

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

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

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

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

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

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

Примечание

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

Как указано в ГОСТ 19781-90, компиляция — это трансляция программы с языка высокого уровня в форму, близкую к программе на машинном языке. Трансляция — это преобразование программы, представленной на одном языке программирования, в программу на другом языке и в определенном смысле равносильную первой. На высоком уровне транслятор можно описать как:

Code -> AST -> Code'

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

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

Рассмотрим следующую задачу. Пусть дан текст на формальном языке для описания простых арифметических выражений с поддержкой переменных и вызовов функций, причём грамматика этого языка в расширенной форме Бэкуса-Наура ^[16] (англ. 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 ^[17] и получить железнодорожную диаграмму (англ. 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 ^[18] или python lex/yacc ^[19] Д. Бизли.

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

Code -> AST

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

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

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

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

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 выше у нас получилось распознать. Функция ^[24]parse запускает процесс разбора заданной строки заданным правилом, а комбинатор ^[25]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 работает как звезда Клини ^[26] * — применяет парсер 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 ^[2]) выражение case op, *args соответствует всем последовательностям, содержащим хотя бы один элемент — таким как ('+', 'x', 'y') или ('exp', 2). При этом в переменную op помещается первый элемент последовательности, а в переменную args — список из всех остальных элементов.

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

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 ^[29]:

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

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

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

OPS = {
    '+': '{%s}+{%s}',
    '*': '{%s}{%s}',
    '^': '{%s}^{%s}',
    '-': '{%s}-{%s}',
    '/': '\frac{%s}{%s}',
    '∂': '\frac{\partial{\left(%s\right)}}{\partial{%s}}',
    'log': '\log(%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 ^[31]:

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

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

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

def topdown(rule, expr):
    match rule(expr):
        case op, *args:
            return (op, *(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))), '.')

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

Простое решение нашей проблемы — найти неподвижную точку ^[35] (англ. 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 ^[36] или PlantUML ^[37].

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

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

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

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

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

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

Отдельное спасибо Петру Советову @true-grue ^[44] за ценные комментарии, позволившие (существенно!) упростить примеры кода в статье, а также за рецензирование материала в целом. Спасибо пользователям Habr ^[45] за участие в обсуждении статьи, разъяснение материала по PEG в комментариях ^[46] и за рекомендации, позволившие повысить качество рукописи.