Здравствуйте, уважаемые читатели.
Обычно, когда речь заходит о создании какого-либо расширения для существующего языка программирования, в воображении неминуемо начинают рождаться разнообразные сложные решения, включающие поиск описания формальной грамматики исходного языка, ее модификации, а затем и применения какого-либо инструмента, позволяющего по данной грамматике либо построить новый компилятор, либо модифицировать существующий компилятор. Причем такие инструменты существуют (bison/flex, yacc/lex, вероятно и многие другие) и успешно используются, несмотря на их явную сложность и громоздкость.
Понятно, что если предполагается внесение в язык относительно небольших модификаций, хотелось бы:
иметь более простую и быструю в разработке препроцессорную схему дополнения языка буквально на уровне написания 50-100 строк кода, обрабатывающего только вносимые расширения (их можно искать с помощью регулярных выражений, не работая в явной форме с базовой формальной грамматикой языка) и генерирующего для них код на исходном языке, который потом и будет обрабатываться стандартным компилятором;
интегрировать описание упомянутой в предыдущем пункте препроцессорной схемы непосредственно в саму программу. То есть, если мы хотим для нашей текущей программы расширение базового языка, мы встраиваем описание распознавания этого расширения и генерации соответствующего фрагмента на базовом языке непосредственно в программу (можно оформить расширение с помощью каких-либо новых конструкций, но можно и воспользоваться комментариями, записанными в специальном формате). Задача сводится только к тому, чтобы написать специальный препроцессор, который будет такие описания распознавать.
В этой статье кратко описывается одно такое препроцессорное решение, реализованное для C++ (точнее, оно входит в набор средств языка Planning C, который сам по себе является расширением C++).
Общая схема
Оформим написание расширения языка с помощью: а) конструкций-сканеров, которые с помощью регулярных выражений находят новые элементы и либо заменяют их на вызовы специальных «компилирующих» макросов , либо вносят новые записи в базу данных (или в базу фактов) препроцессора; б) «компилирующих» макросов, которые принимают набор параметров и генерируют фрагмент нового кода, при этом, чтобы согласовать поведение таких макросов друг с другом, они могут работать с общей базой данных/фактов, читая и внося в нее изменения.
Сканеры и макросы непосредственно вписываются в программу, для которой необходимо расширения языка, эта программа обрабатывается препроцессором, который применяет к данной программе описанные сканеры и макросы, вставляя в нее новые фрагменты, после чего описания макросов и сканеров удаляются и полученная конечная программа на стандартном исходном языке компилируется самым обычным компилятором.
Реализация схемы для C++ и Planning C
Думаю, нет необходимости подробно излагать данную схему, поэтому ограничусь описанием общих принципов и небольшим примером.
Реализация сканеров
Сканер состоит из одного-двух-трех основных регулярных выражений: а) необязательного предыдущего контекста, б) основной части, в) необязательного последующего контекста. Сканер находит блоки, состоящие из последовательных фрагментов, распознанных этими выражениями, и заменяет средние фрагменты (соответствующие основной части) либо вызовом компилирующего макроса с параметрами, либо пустой строкой (но при этом в базу данных/фактов вносится какая-либо специальная запись, которую потом смогут прочитать различные компилирующие макросы).
Замечу только, что я использовал не стандартные регулярные выражения, а модифицированные, дополненные возможностью небольшой логической обработки разбираемых выражений с помощью специальных предикатов. Это оказалось очень полезным для упрощения распознающих частей, например, для сбалансированных по различным видам скобок выражений языка.
Реализация компилирующих макросов
Это макросы с параметрами, которые включают специальный код, который, на базе переданных в макрос параметров, генерирует выходной фрагмент, помещаемый в обрабатываемую программу, заменяя вызов макроса. Фрагмент генерируется путем простой выдачи текста в выходной поток (как это сделано, например, в PHP). Вопрос о том, на каком языке пишутся такие макросы, не очень принципиален. Я воспользовался GNU Prolog, поскольку это хорошо вписывалось в разрабатываемый мной препроцессор, но вполне можно, например, использовать тот же PHP (обычно он генерирует HTML-фрагменты, но ничто не мешает ему генерировать фрагменты кода на любом языке).
Важно заметить, что препроцессинг такой программы, в которую вставлены такие макросы, не обязательно однократный. Может потребоваться, чтобы макрос А знал о том, что делает другой макрос Б – тогда, если по тексту вызов А предшествует Б, приходится делать препроцессинг как минимум двукратным, чтобы на первой стадии Б сгенерировал данные, а на второй А их прочитал. Это решается легко – в программу можно вставить прямое указание на то, сколько раз (максимально) выполнить препроцессинг, а макросам можно разрешить досрочно завершить итерации препроцессинга с помощью вызова специального предиката.
Пример
Предположим, что мы захотели ввести в язык C++ новую конструкцию, которая по окончании цикла позволяет обработать случай, когда он был прерван по break. Она имеет вид:
while(условие) {
тело_цикла
}
else обработка_прерывания_по_breakПример программы, вводящей и использующей такую конструкцию:
#include <iostream>
#scan(WhileElse)
// Сканер, генерирующий вызов компилирующего макроса while_else(параметры). Содержит предыдущий контекст и основную часть.
#def_pattern WhileElse => while_else (gid(), /root/COND/@Value, /root/BODY/@Value) {
(((^)|(\;)+|\}|\{|\)|\\n|(\\n|\\t|\b)else\b|(\\n|\\t|\b)do\b|\:)((\s|\\t)*\\n)*)(\s|\\t)*
@begin
(\s|\\t)*
(while(\\n|\s|\\t)*\(
(\\n|\s|\\t)*((.{1,300}?)->{COND}\))?=>{Predicates.BAL($,')')}
)
(\s|\\t)*
\{
(\\n|\s|\\t)*((.{1,8192}?)->{BODY}\})?=>{Predicates.BAL($,'}')}
(\\n|\s|\\t)*
else
@end
(\\n|\s|\\t)+
};
// Компилирующий макрос
#def_module() while_else(GID, COND, BODY) {
@goal:-brackets_off.
@goal:-
write('bool __break'), write(GID), write(' = false;'), nl,
write('while('), write(COND), write(') {'), nl,
write(' __break'), write(GID), write(' = true;'), nl,
write(BODY), nl,
write(' __break'), write(GID), write(' = false;'), nl,
write('}'), nl,
write('if (__break'), write(GID), write(') '), nl.
};
// Программа
int main() {
int A[10];
int k = 0;
while (k < 10) {
cin >> A[k];
if (A[k] == 0) break;
k++;
}
else
cout << "Был введен ноль!" << endl;
return 0;
}Кстати, после обработки препроцессором программа выглядит так:
#include <iostream>
int main() {
int A[10];
int k = 0;
bool __break1 = false;
while(k < 10) {
__break1 = true;
cin >> A[k];
if (A[k] == 0) break;
k++;
__break1 = false;
}
if (__break1)
cout << "Был введен ноль!" << endl;
return 0;
}Неожиданное применение – реализация автоматического распараллеливания исходных программ
В самом деле, если написать сканеры для всех стандартных синтаксических элементов языка (для каждого из них генерируется факт), а потом написать два «компилирующих» макроса, первый из которых анализирует распознанную программу (факты) и вставляет новые факты-директивы распараллеливания, а второй – генерирует по полученному набору фактов результирующий программный код, то так можно написать сколь угодно сложный параллелизатор, учитывая, что компилирующие макросы в моем варианте реализуют «интеллектуальный» подход на базе GNU Prolog.
Таким путем были написаны два параллелизатора – первый из них распараллеливает исходную программу на языке C, вставляя в нее директивы Cilk++, а второй использует специальные расщепляющие трансформации, о которых я писал на Хабре раньше.
Заключение
Как я уже писал выше, описанные схемы реализованы в специальном препроцессоре (для C++/Planning C) и успешно работают. С их помощью реализованы некоторые параллельные расширения языка (как пример – стандартные вычислительные топологии), а также два автоматических распараллеливателя для программ на C.
Комментарии (39)
ultrinfaern
11.08.2021 20:01+5Идея ничего, а вот реализация...
У вас не получиться парсить синтаксис любого языка регэкспами.
pekunov Автор
11.08.2021 20:12Это несколько спорный вопрос, тем более, что в данном случае регэкспы могут расширяться написанием и подключением внешних предикатов (оформляются в виде DLL). Я думаю, что таким гибридом все-таки можно разобрать конструкции любого языка с четкой формальной грамматикой, другое дело -- не всегда понятно, насколько компактной будет такая реализация.
ultrinfaern
11.08.2021 20:21+3Есть очень хороший ответ ( там про то, можно ли парсить html регэкспами, ну вас более запущенный случай)
:)
pekunov Автор
11.08.2021 20:42Я не зря писал про предикативные расширения регэкспов. С их помощью (например, написав предикат выделения сбалансированных по тегам подстрок) можно распознать и HTML (не берусь утверждать что все его конструкции, но можно). Причем здесь не будет противоречия с упомянутой Вами статьей, поскольку в ней упор идет на то, что HTML не описывается регулярной грамматикой. Вводя предикаты, можно распознавать уже не только регулярные грамматики, просто части, не являющиеся регулярными, возьмут на себя предикаты. Собственно, в приведенном мной примере один такой предикат Predicates.BAL уже есть -- он тестирует подстроку -- является ли она сбалансированным по различного видам скобок выражением.
ultrinfaern
11.08.2021 21:16+2Пример: напишите расширение которое будет ставить пробелы между множителями.
У нас в тексте есть два куска:
первый:
а*b
тут определяется ссылочная переменная b типа а - ваша регулярка должна этот кусок пропустить
второй:
a*b
ну тут точно умножение а на b - ваша регулярка должна поставить пробелы между множителями.
ЗЫ: Это был риторический пример.
pekunov Автор
11.08.2021 21:30Прекрасная задача :) Одним регэкспом здесь, конечно, не обойтись, нужно несколько, причем они будут работать с единой базой данных/фактов. Применительно к тому, о чем я писал в статье: здесь надо ввести как минимум K+1 сканеров -- первые K находят и разбирают все возможные определения типов, занося имена типов в базу фактов (в которую также уже занесены все стандартные типы). А последний сканер разбирает выражение a*b, проверяя по базе, является ли a именем типа и принимая решение о расстановке пробелов для компилирующего макроса.
ultrinfaern
11.08.2021 23:15+1Вам фиксированная база фактов не поможет. Нужен контекст разбора выражения, так как локально в блоке все может переопределяться. При выходе из блока старые определения восстанавливаются. Блоки вкладываются один в другой, идут друг за другом, и т.д и т.п. Нет ничего глобального вообще. И это все нужно отслеживать. Для конкретной строки нужно знать ее динамическое окружение. Регэкспы тут не помогут. Тут нужен полный парсер. Вот когда компилятор компилирует, он как раз и ведет динамическую базу. Она постоянно меняется в зависимости от считанной лексемы - определения добавляются и грохаются - то есть отслеживается контекст.
pekunov Автор
11.08.2021 23:26Вы знаете, эти проблемы победимы -- я сталкивался с ними, когда при данном подходе писал распараллеливатели для C-программ. Именно этим (отслеживанием контекста) там и приходилось заниматься помимо всего прочего (поскольку надо отслеживать все пути исполнения и четко различать локальные и глобальные декларации), -- удалось справиться, если в двух словах. Правда пришлось написать по регэкспу для каждой типовой синтаксической конструкции (if, for, while, ...) и весьма сложный компилирующий макрос.
ultrinfaern
11.08.2021 23:50+1Вы просто написали регэкспы на стандартный случай и только для своей программы. Вы же понимете, что это не серьезно. Это все должно работать при самом нестандартном варианте. Я так понимаю, что вы сами глядя на написанные вами регэкспы всегда можете написать неработающий. контрпример. Так вот, такого контрпримера быть не должно.
pekunov Автор
12.08.2021 00:01Распараллеливатель писался именно в расчете на общий случай (а не на одну конкретную программу) и неработающие контрпримеры старательно искоренялись, когда обнаруживались.
Если же Вы имеете в виду общую постановку вопроса -- что не стоит писать компиляторы/параллелизаторы на регэкспах, я в общем случае могу даже и согласиться. Я ставил перед собой более простую задачу -- доказать, что можно писать расширители языков и распараллеливатели на сканерах (модифицированных регэкспах) + компилирующих макросах с общей базой фактов. Это доказано построением, как это и принято в конструктивной математике.
Wyrd
12.08.2021 00:48Тот же С++ имеет контекстно-зависимую грамматику, это сильно мешает парсить его регулярками. В частности, С++ парсер должен уметь ВЫПОЛНЯТЬ достаточное объемное (и полное по Тьюрингу!) подмножество С++ кода (т.к. constexpr может влиять на контекст ниже написанного кода, а С++ грамматика контекстно-зависима - один и тот же код («текст») может означать совершенно разные вещи в зависимости от, скажем, наличия объявления переменной/поля/класса выше по тексту, которое в свою очередь может вычисляться шаблонной магией и constexpr-ам, например, при инстанцировании шаблона, условный метод getX() может объявляться или не объявляться в зависимости от наличия условного поля X у конкретного типа).
Regex-ы (по крайней мере стандартные) не являются полными по Тьюрингу, поэтому вышеописанные операции они (в общем случае) выполнить не могут даже в теории. Поэтому они и называются РЕГУЛЯРНЫЕ выражения. Для С++ таки нужен полноценный парсер.
Есть и хорошие новости - полноценные парсеры писать самому не надо, они уже написаны для всех популярных языков и большинство поддерживает плагины (т.к. можно добавить свой синтаксис), в С#, к примеру, это кастомный синтаксис для всяких DSL прямо в проект можно встроить штатными средствами. Для С++ есть clang, для JS - Babel, итд
pekunov Автор
12.08.2021 01:11полноценные парсеры писать самому не надо, они уже написаны для всех популярных языков и большинство поддерживает плагины (т.к. можно добавить свой синтаксис)
Не думаю, что (в случае небольших нововведений в язык) такие решения проще, чем предложенное в данной статье. Бритва Оккама, так сказать, не умножаем сущности сверх необходимости.
Что же касается регэкспов, то как я уже упоминал, при полноценном разборе текста на ЯВУ (кстати, такая задача в простых случаях абсолютно не нужна, в чем можно убедиться из примера в моей статье) они выполняют исключительно лексический и часть синтаксического разбора. Весь оставщийся синтаксический разбор выполняет код компилирующего макроса (это, фактически, GNU Prolog, полный по Тьюрингу). Для С (не C++) работает прекрасно.
0xd34df00d
12.08.2021 03:22+1Тот же С++ имеет контекстно-зависимую грамматику
В частности, С++ парсер должен уметь ВЫПОЛНЯТЬ достаточное объемное (и полное по Тьюрингу!)Совершенно очевидно, что это взаимно противоречащие утверждения, так как КЗ-грамматики разрешимы.
Wyrd
12.08.2021 05:52Ну знаете, так у нас тогда ни одного Тьюринг полного языка нету - память-то ограничена максимум 2^64 байт. В С++ ограничения пожёстче, конечно, но
0xd34df00d
12.08.2021 18:55+1Только это ограничения принципиально разного рода. Языки от вычёркивания ограничения на 2^64 не сломаются.
Wyrd
13.08.2021 03:59Ну так и компилятор С++ не сломается принципиально. Все так или иначе упирается в объём доступной памяти и максимальную глубину рекурсии. Шаблоны в плюсах - это чистый функциональный язык оперирующий типами и константами. Он является полным по Тьюрингу в предположении что у вас достаточно памяти чтоб скомпилировать шаблоны адской вложенности. Ну а любые constexpr можно свести к шаблонной магии
Если вас до сих пор не убедило, вот пруфы:
0xd34df00d
13.08.2021 09:34+1Я не понимаю, зачем вам меня убеждать в том, что метапрограммирование в плюсах полно по Тьюрингу, если я соответствующий пример привёл в соседнем комментарии, да и чуть выше написал на эту тему.
Собственно, именно это и означает, что парсинг плюсов неразрешим и, как следствие, не может быть выполнен даже КЗ-грамматиками (которые, как известно, разрешимы).
0xd34df00d
12.08.2021 03:18+3Если вы хотите обрабатывать
a*bдля любого термаa, а не просто токена, то предложите, пожалуйста, конечное множество регулярок, которые будут корректно обрабатыватьconsteval bool IsPrime(int n) { for (int i = 2; i < n; ++i) if (!(n % i)) return false; return true; } template<bool B> struct S { using T = int; }; template<> struct S<true> { constexpr static int T = 42; }; int main() { const int N1 = 5; const int N2 = 10; int b = 0; { /*int v =*/ S<IsPrime(N1)>::T*b; } { S<IsPrime(N2)>::T*b /*= nullptr*/; } }для любых
N1,N2.pekunov Автор
12.08.2021 14:47Чтобы решить такую проблему хотя бы частично, не остается ничего кроме, как написать для регэкспа, проверяющего, тип это или нет, предикат, позволяющий выполнять фрагменты кода C++, чтобы он всегда мог вычислить S<IsPrime(N)>::T. Кстати, в частном случае это, думаю, можно сделать сравнительно дешевым (хотя и медленным) способом -- вызывать в предикате стандартный компилятор C++ для интересующего кода с подобающей оберткой и возвращать результат. И конечно, есть и более дорогой (хотя и более правильный) метод -- воспользоваться каким-либо из существующих интерпретаторов C++, вызывая его из регэксп-предиката.
Тяжелые решения. Однако успокаивает, что Ваш пример все-таки искусственный. Не надо бы писать такой код, он чреват тяжелыми синтаксическими ошибками со стороны программиста :)
0xd34df00d
12.08.2021 18:54+1Однако успокаивает, что Ваш пример все-таки искусственный. Не надо бы писать такой код, он чреват тяжелыми синтаксическими ошибками со стороны программиста :)
Он искусственный только потому, что он очень сильно редуцированный.
Раньше я довольно много занимался всяким компилтайм-метапрограммированием, и там такое — норма, и вполне себе идёт в прод.
psycha0s
11.08.2021 20:35+2Регулярными выражениями можно парсить исключительно регулярные грамматики (тип 3 по иерархии Хомского). Контекстно-свободные и контекстно-зависимые грамматики так разобрать, увы, уже не получится.
PrinceKorwin
11.08.2021 21:07+1Вы попробуйте Perl распарсить регулярками. Очень много интересного узнаете :)
Perl вообще даже обычной стейт-машиной не парсится. Оригинальный парсер в этом плане очень запутанный.
Сообщество пыталось около 7 лет написать нормальный парсер, но в итоге сдалась и сделала сабсет синтаксиса (намёк на Parrot).
Serge78rus
11.08.2021 23:02А Вы помните сообщения об ошибках компиляции, выдаваемые древними компиляторами (типа всяких Борландов) при ошибке в шаблоне? Пытаясь сопоставить эти сообщения с исходным текстом, иногда хотелось плюнуть и навсегда уйти из профессии. Не будет ли у Вас той же самой проблемы?
pekunov Автор
11.08.2021 23:20Да, такая проблема есть. Вряд ли в данном подходе ее можно решить полностью, но частичное решение может быть таким: в компилирующем макросе при генерации кода можно вставлять конструкции вида "write('#line '), write(__LINE__+относительный_номер_строки), nl", которые укажут компилятору (через стандартную директиву #line) на строку исходного кода, на которую он сошлется при возникновении ошибки в текущем сгенерированном фрагменте.
PrinceKorwin
11.08.2021 23:21+3В этом плане мне нравятся сообщения по ошибкам от Rust компилятора.
Он старается по мере сил кроме сообщения + конкретного места где она произошла (не просто строка, а прям показывает что именно в строке не понравилось) еще объяснять почему произошла ошибка (например показывает в какой именно строке выше произошла передача владением значением), но также пытается привести пример того, как именно можно исправить ошибку (например добавить & чтобы передать значение по ссылке как того требует функция).
cranium256
12.08.2021 01:36+1Допустим, вам каким-то чудом удалось правильно распарсить исходник на С++ с помощью регулярок, развернуть макросы и откомпилировать. А отлаживать получившуюся программу вы как собираетесь? Компилятор отладочную информацию создаст для текста после вашего чудо-препроцессора.
И есть подозрение, что вы плохо кончите. Всегда пишите код так, будто сопровождать его будет склонный к насилию психопат, который знает, где вы живете. — Martin Goldingpekunov Автор
12.08.2021 12:57Допустим, вам каким-то чудом удалось правильно распарсить исходник на С++ с помощью регулярок, развернуть макросы и откомпилировать. А отлаживать получившуюся программу вы как собираетесь? Компилятор отладочную информацию создаст для текста после вашего чудо-препроцессора.
Да, есть и такая проблема. Ее решением я не занимался, но если вдруг этот проект получит реальное практическое применение, подумаю. Вообще же, "проблем, не разрешимых ни при каких мыслимых условиях -- не существует" (А.Азимов).
pekunov Автор
12.08.2021 19:51А отлаживать получившуюся программу вы как собираетесь?
Кстати, по-моему, схожие проблемы не решены и в стандартном C++.
Например, как отлаживать программу с многострочным макросом? Для кода в макросе -- почти никак. По крайней мере в моей версии MSVC.
#include <iostream> #define A(a,b,c) cout<<a<<endl; \ cout<<b<<endl; \ cout<<c<<endl; int main() { A(1,2,3); }cranium256
12.08.2021 19:56Да, это так. Именно поэтому я и поднял вопрос. Макросы в С/С++, за исключением самых примитивных — боль. Автор предлагает к ней добавить термоядерную боль. Мазохизм?
oleshii
15.08.2021 16:47+1#include <iostream> using std::cout; using std::endl; #define A(a,b,c){\ cout<<a<<endl; \ cout<<b<<endl; \ cout<<c<<endl;\ }\ int main() { A(1,2,3); } // run results root@root-vmu:~/SRCS$ ./test 1 2 3 gcc --version gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0 Copyright (C) 2017 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. cat /etc/os-release NAME="Ubuntu" VERSION="18.04.1 LTS (Bionic Beaver)" ID=ubuntu ID_LIKE=debian PRETTY_NAME="Ubuntu 18.04.1 LTS" VERSION_ID="18.04" HOME_URL="https://www.ubuntu.com/" SUPPORT_URL="https://help.ubuntu.com/" BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/" PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy" VERSION_CODENAME=bionic UBUNTU_CODENAME=bionicpekunov Автор
15.08.2021 16:58Да, так конечно правильнее (я упустил using), спасибо. Кстати, подозреваю, что под Linux отладить многострочный макрос не проще, чем в Windows.
oleshii
15.08.2021 17:11Да не проблема. Кроме того, в многострочниках нужно указывать scope, или {...} Макро - мощное средство. Многие их не любят и заменяют на что-то иное. Но при умелом пользовании это классная вещь. Со временем просто приходит привычка писать их правильно. Если уж поотлаживать его, то можно для начала заменить его inline функцией, или же смотреть его assembler развёртку.
Gryphon88
14.08.2021 18:54+1За что не люблю шаблоны с макросами — они привносят новую семантику, в итоге смутное чувство, что пишешь в одном файле на нескольких языках сразу. Как по мне всю эту кодогенерацию стоит официально назвать отдельным языком и запускать как pre-build шагом в IDE.
evgenyk
А вот написал бы кто-нибудь не расширитель, а сужатель языка! Особенно C++. Ему бы памятник поставили бы благодарные разработчики.
Daddy_Cool
Шепотом… создать новый язык?
Сужатель языка — это гениально! Но увы… сейчас кто угодно бросается в безбрежный окиян С++ и плывет куда угодно, с кем угодно, за чем угодно. С++ это свобода на грани анархии.
iliazeus
https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines
https://docs.microsoft.com/en-us/cpp/code-quality/using-the-cpp-core-guidelines-checkers