Расширение языка программирования (C++/Planning C). Волшебные сканеры и компилирующие макросы

Kate

Administrator
Команда форума
Здравствуйте, уважаемые читатели.

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

 
Сверху