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

Здравствуйте, уважаемые читатели.

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