Comments 39
А вот написал бы кто-нибудь не расширитель, а сужатель языка! Особенно C++. Ему бы памятник поставили бы благодарные разработчики.
Идея ничего, а вот реализация...
У вас не получиться парсить синтаксис любого языка регэкспами.
Это несколько спорный вопрос, тем более, что в данном случае регэкспы могут расширяться написанием и подключением внешних предикатов (оформляются в виде DLL). Я думаю, что таким гибридом все-таки можно разобрать конструкции любого языка с четкой формальной грамматикой, другое дело -- не всегда понятно, насколько компактной будет такая реализация.
Есть очень хороший ответ ( там про то, можно ли парсить html регэкспами, ну вас более запущенный случай)
:)
Я не зря писал про предикативные расширения регэкспов. С их помощью (например, написав предикат выделения сбалансированных по тегам подстрок) можно распознать и HTML (не берусь утверждать что все его конструкции, но можно). Причем здесь не будет противоречия с упомянутой Вами статьей, поскольку в ней упор идет на то, что HTML не описывается регулярной грамматикой. Вводя предикаты, можно распознавать уже не только регулярные грамматики, просто части, не являющиеся регулярными, возьмут на себя предикаты. Собственно, в приведенном мной примере один такой предикат Predicates.BAL уже есть -- он тестирует подстроку -- является ли она сбалансированным по различного видам скобок выражением.
Пример: напишите расширение которое будет ставить пробелы между множителями.
У нас в тексте есть два куска:
первый:
а*b
тут определяется ссылочная переменная b типа а - ваша регулярка должна этот кусок пропустить
второй:
a*b
ну тут точно умножение а на b - ваша регулярка должна поставить пробелы между множителями.
ЗЫ: Это был риторический пример.
Прекрасная задача :) Одним регэкспом здесь, конечно, не обойтись, нужно несколько, причем они будут работать с единой базой данных/фактов. Применительно к тому, о чем я писал в статье: здесь надо ввести как минимум K+1 сканеров -- первые K находят и разбирают все возможные определения типов, занося имена типов в базу фактов (в которую также уже занесены все стандартные типы). А последний сканер разбирает выражение a*b, проверяя по базе, является ли a именем типа и принимая решение о расстановке пробелов для компилирующего макроса.
Вам фиксированная база фактов не поможет. Нужен контекст разбора выражения, так как локально в блоке все может переопределяться. При выходе из блока старые определения восстанавливаются. Блоки вкладываются один в другой, идут друг за другом, и т.д и т.п. Нет ничего глобального вообще. И это все нужно отслеживать. Для конкретной строки нужно знать ее динамическое окружение. Регэкспы тут не помогут. Тут нужен полный парсер. Вот когда компилятор компилирует, он как раз и ведет динамическую базу. Она постоянно меняется в зависимости от считанной лексемы - определения добавляются и грохаются - то есть отслеживается контекст.
Вы знаете, эти проблемы победимы -- я сталкивался с ними, когда при данном подходе писал распараллеливатели для C-программ. Именно этим (отслеживанием контекста) там и приходилось заниматься помимо всего прочего (поскольку надо отслеживать все пути исполнения и четко различать локальные и глобальные декларации), -- удалось справиться, если в двух словах. Правда пришлось написать по регэкспу для каждой типовой синтаксической конструкции (if, for, while, ...) и весьма сложный компилирующий макрос.
Вы просто написали регэкспы на стандартный случай и только для своей программы. Вы же понимете, что это не серьезно. Это все должно работать при самом нестандартном варианте. Я так понимаю, что вы сами глядя на написанные вами регэкспы всегда можете написать неработающий. контрпример. Так вот, такого контрпримера быть не должно.
Распараллеливатель писался именно в расчете на общий случай (а не на одну конкретную программу) и неработающие контрпримеры старательно искоренялись, когда обнаруживались.
Если же Вы имеете в виду общую постановку вопроса -- что не стоит писать компиляторы/параллелизаторы на регэкспах, я в общем случае могу даже и согласиться. Я ставил перед собой более простую задачу -- доказать, что можно писать расширители языков и распараллеливатели на сканерах (модифицированных регэкспах) + компилирующих макросах с общей базой фактов. Это доказано построением, как это и принято в конструктивной математике.
Тот же С++ имеет контекстно-зависимую грамматику, это сильно мешает парсить его регулярками. В частности, С++ парсер должен уметь ВЫПОЛНЯТЬ достаточное объемное (и полное по Тьюрингу!) подмножество С++ кода (т.к. constexpr может влиять на контекст ниже написанного кода, а С++ грамматика контекстно-зависима - один и тот же код («текст») может означать совершенно разные вещи в зависимости от, скажем, наличия объявления переменной/поля/класса выше по тексту, которое в свою очередь может вычисляться шаблонной магией и constexpr-ам, например, при инстанцировании шаблона, условный метод getX() может объявляться или не объявляться в зависимости от наличия условного поля X у конкретного типа).
Regex-ы (по крайней мере стандартные) не являются полными по Тьюрингу, поэтому вышеописанные операции они (в общем случае) выполнить не могут даже в теории. Поэтому они и называются РЕГУЛЯРНЫЕ выражения. Для С++ таки нужен полноценный парсер.
Есть и хорошие новости - полноценные парсеры писать самому не надо, они уже написаны для всех популярных языков и большинство поддерживает плагины (т.к. можно добавить свой синтаксис), в С#, к примеру, это кастомный синтаксис для всяких DSL прямо в проект можно встроить штатными средствами. Для С++ есть clang, для JS - Babel, итд
полноценные парсеры писать самому не надо, они уже написаны для всех популярных языков и большинство поддерживает плагины (т.к. можно добавить свой синтаксис)
Не думаю, что (в случае небольших нововведений в язык) такие решения проще, чем предложенное в данной статье. Бритва Оккама, так сказать, не умножаем сущности сверх необходимости.
Что же касается регэкспов, то как я уже упоминал, при полноценном разборе текста на ЯВУ (кстати, такая задача в простых случаях абсолютно не нужна, в чем можно убедиться из примера в моей статье) они выполняют исключительно лексический и часть синтаксического разбора. Весь оставщийся синтаксический разбор выполняет код компилирующего макроса (это, фактически, GNU Prolog, полный по Тьюрингу). Для С (не C++) работает прекрасно.
Ну знаете, так у нас тогда ни одного Тьюринг полного языка нету - память-то ограничена максимум 2^64 байт. В С++ ограничения пожёстче, конечно, но
Ну так и компилятор С++ не сломается принципиально. Все так или иначе упирается в объём доступной памяти и максимальную глубину рекурсии. Шаблоны в плюсах - это чистый функциональный язык оперирующий типами и константами. Он является полным по Тьюрингу в предположении что у вас достаточно памяти чтоб скомпилировать шаблоны адской вложенности. Ну а любые constexpr можно свести к шаблонной магии
Если вас до сих пор не убедило, вот пруфы:
Чтобы решить такую проблему хотя бы частично, не остается ничего кроме, как написать для регэкспа, проверяющего, тип это или нет, предикат, позволяющий выполнять фрагменты кода C++, чтобы он всегда мог вычислить S<IsPrime(N)>::T. Кстати, в частном случае это, думаю, можно сделать сравнительно дешевым (хотя и медленным) способом -- вызывать в предикате стандартный компилятор C++ для интересующего кода с подобающей оберткой и возвращать результат. И конечно, есть и более дорогой (хотя и более правильный) метод -- воспользоваться каким-либо из существующих интерпретаторов C++, вызывая его из регэксп-предиката.
Тяжелые решения. Однако успокаивает, что Ваш пример все-таки искусственный. Не надо бы писать такой код, он чреват тяжелыми синтаксическими ошибками со стороны программиста :)
Регулярными выражениями можно парсить исключительно регулярные грамматики (тип 3 по иерархии Хомского). Контекстно-свободные и контекстно-зависимые грамматики так разобрать, увы, уже не получится.
Вы попробуйте Perl распарсить регулярками. Очень много интересного узнаете :)
Perl вообще даже обычной стейт-машиной не парсится. Оригинальный парсер в этом плане очень запутанный.
Сообщество пыталось около 7 лет написать нормальный парсер, но в итоге сдалась и сделала сабсет синтаксиса (намёк на Parrot).
Да, такая проблема есть. Вряд ли в данном подходе ее можно решить полностью, но частичное решение может быть таким: в компилирующем макросе при генерации кода можно вставлять конструкции вида "write('#line '), write(__LINE__+относительный_номер_строки), nl", которые укажут компилятору (через стандартную директиву #line) на строку исходного кода, на которую он сошлется при возникновении ошибки в текущем сгенерированном фрагменте.
В этом плане мне нравятся сообщения по ошибкам от Rust компилятора.
Он старается по мере сил кроме сообщения + конкретного места где она произошла (не просто строка, а прям показывает что именно в строке не понравилось) еще объяснять почему произошла ошибка (например показывает в какой именно строке выше произошла передача владением значением), но также пытается привести пример того, как именно можно исправить ошибку (например добавить & чтобы передать значение по ссылке как того требует функция).
И есть подозрение, что вы плохо кончите. Всегда пишите код так, будто сопровождать его будет склонный к насилию психопат, который знает, где вы живете. — Martin Golding
Допустим, вам каким-то чудом удалось правильно распарсить исходник на С++ с помощью регулярок, развернуть макросы и откомпилировать. А отлаживать получившуюся программу вы как собираетесь? Компилятор отладочную информацию создаст для текста после вашего чудо-препроцессора.
Да, есть и такая проблема. Ее решением я не занимался, но если вдруг этот проект получит реальное практическое применение, подумаю. Вообще же, "проблем, не разрешимых ни при каких мыслимых условиях -- не существует" (А.Азимов).
А отлаживать получившуюся программу вы как собираетесь?
Кстати, по-моему, схожие проблемы не решены и в стандартном C++.
Например, как отлаживать программу с многострочным макросом? Для кода в макросе -- почти никак. По крайней мере в моей версии MSVC.
#include <iostream>
#define A(a,b,c) cout<<a<<endl; \
cout<<b<<endl; \
cout<<c<<endl;
int main() {
A(1,2,3);
}
Расширение языка программирования (C++/Planning C). Волшебные сканеры и компилирующие макросы