Comments 3
Мне очень нравится эта тема. На рабочем проекте есть задача создать встроенный в приложение интерпретатор языка для скриптинга. Но существующие языки (lua, python) не удовлетворяют требованиям (важна статическая типизация и определенный синтаксис для совместимости + дальнейшая трансляция в ANSI C). Я уже изучал ранее тему по книге дракона (создание компиляторов flex/bison), а потом ещё sicp и нашел тутор по kaleidoscope от llvm.
Хотел высказаться по поводу поддержки операторов. Мне как раз больше зашло решение не фиксировать приоритеты инфиксных операторов в самой грамматике (и вообще отказать от любых встроенных операторов), идея такая:
1 + 1; # Error: unknown function 'infix +(int, int)'
infix +(lhs: int, rhs: int): int {.builtin, left, priority=20.}; # ассоциативность и приоритет через аннотации
1 + 1; # => 2То есть, любой оператор просто функция. Инфиксная нотация - синтаксический сахар. Любое выражение парсится в PriorityAgnisticExpression как список '<expr> (<op> <expr>)*' а дерево с приоритетами строится в препроцессоре по таблице этих самых приоритетов алгоритмом сортировочной станции Дейкстры. Регистрировать операторы так же просто как обычные функции. Даже встроенных типов нет, их также нужно регистрировать явно. Такой себе конструктор получается "собери свой Си с сахаром и перегрузками" .
Antlr использую для прототипирования грамматики онлайн в AntlrLab, а реализую все в boost::spirit::x3. Я заметил, что мне неудобна концепция лексеров, как отдельного этапа парсинга, там есть свои неудобства, когда трактовка лексемы должна зависеть от контекста и вообще лексеры бывают черезчур жадными. С комбинаторами парсеров я добился большей гибкости.
Спасибо за развёрнутый комментарий — интересный кейс с регистрацией операторов через аннотации.
Тут вы правы — для языков, где приоритет операторов задаётся в коде программиста, а не в грамматике, левая рекурсия не подходит в принципе: грамматика просто не знает приоритеты на этапе компиляции. Для такой задачи «плоский парсер + sorting yard в постобработке» — обоснованный приём, не ANTLR-антипаттерн.
Я в статье говорил про более узкий случай: DSL с фиксированным набором операторов и приоритетов, прибитых на этапе разработки языка. Там левая рекурсия работает, потому что грамматика знает всё заранее.
Да, я понимаю. Это не критика вашего решения. Такие темы поднимаются не очень часто. Разработка языков - довольно нишевое занятие, и обсудить эту тему особо не с кем.
Когда меня попросили сделать технический доклад о реализации интерпретатора для команды, меня в мёртвой тишине выслушали, выпучили глаза и разошлись. Похоже, никто из них не хотел заниматься развитием этой темы (я про сопровождение или разработку чего‑то подобного).
Только один человек мог вести активную дискуссию - но он по долгу службы занимался подобными вещами и был «заражён», как и я.
От регулярок к ANTLR4: три архитектурных решения на парсере бизнес-формул