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

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

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

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

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

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

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

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

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

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 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))), '.')

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

Простое решение нашей проблемы — найти неподвижную точку (англ. 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 за ценные комментарии, позволившие (существенно!) упростить примеры кода в статье, а также за рецензирование материала в целом. Спасибо пользователям Habr за активное участие в обсуждении статьи, разъяснение материала по PEG в комментариях и за рекомендации, позволившие повысить качество рукописи.