Каждый программист в глубине души желает написать свой калькуляторязык программирования, но, вспоминая, как противно было в институте писать полотна в полторы тысячи строк и отлаживать их, прячет глубины своей души подальше от клавиатуры.

Недавно вышел Boost 1.41, а с ним и Spirit 2, синтаксический анализатор, почти равный по возможностям оригинальным регулярным выражениям Perl. Я просто обязан о нём написать.

Сегодня мы попытаемся запрограммировать простой интерпретируемый язык.

Состав библиотеки

• Classic. Старая версия Spirit для слоупоков. Продокументирована очень хорошо, но от некоторых хаков и синтаксиса мозги заворачиваются трубочкой.
• Qi. Генератор парсеров. Собственно, это и есть новый Spirit, и далее в статье он будет так называться.
• Karma. Генератор генераторов. Позволяет выводить структуры данных с помощью того же самого синтаксиса, которым они разбираются из текста. Из девелоперского maillist можно сделать вывод, что Karma даже быстрее, чем boost::format.
• Lex. Генератор лексических анализаторов.

Краткое описание

• Spirit не требует дополнительных шагов компиляции
• Spirit устанавливать очень просто и этот процесс хорошо задокументирован, причём у большинства программистов на C++ библиотека Boost уже есть.
• Spirit не принуждает пользоваться лексическим анализатором. Не знаю как вам, а мне лень выписывать списки лексем и обновлять их вместе в кодом парсера.
• Код на Spirit медленно компилируется. Действительно медленно. Ни gcc, ни cl (Visual Studio 2008) не справились с компиляцией полной грамматики С++, состоящей из 180 правил, выпав с “out of heap”. Для первого Spirit в FAQ есть рекомендации по ускорению компиляции, а именно предложение разделить грамматику на части. В новой версии пока не пробовал, это не очевидно.
• Spirit не поддерживает левую рекурсию, поэтому некоторые правила придется переписывать вручную. Это просто.

Отдельным абзацом упомяну, что устанавливать Antlr 3, компилировать к нему рантайм для С++ и редактировать исходные коды, чтобы он перестал лепить extern "C" вокруг хидеров в генерируемых файлах, — это самое бестолковое времяпрепровождение для программиста, которое можно придумать. Не используйте эту библиотеку с С++.

Начнём...

… с форм Бекуса-Наура. Мы хотим сделать стандартные арифметические операторы (+, -, *, /), унарные операторы знака (+, -) и оператор присваивания (=) в стиле Си, т.е. возвращающий значение, а также переменные и числа с плавающей точкой. Получаем:

Строка :: = Идентификатор '=' Строка | Выражение
Выражение ::= Слагаемое (('+' | '-') Слагаемое)*
Слагаемое ::= Множитель (('*' | '/') Множитель)*
Множитель ::= Число | Атом | '+' Атом | '-' Атом
Атом ::= '(' Строка ')' | Идентификатор
Идентификатор ::= (Латиница | '_') (Латиница | Цифра | '_')*

Теперь переведём это в синтаксис Spirit.

row = (id >> '=' >> row) | expr;
expr = term >> *( '+' >> term | '-' >> term );
term = fact >> *( '*' >> fact | '/' >> fact );
fact = number | subf | '+' >> subf | '-' >> subf;
subf = '(' >> row >> ')' | id;
id = lexeme[ (alpha | '_') >> *(alnum | '_') ];
number = double_;

Зачем нужен lexeme? Дело в том, что мы хотим, чтобы Spirit за нам сам пропускал лишние пробелы во входных данных. Однако, если он будет пропускать пробелы внутри идентификатора, строка ab cd может считаться идентификатором abcd, что неверно. Поэтому мы запрещаем пропускать пробелы, применяя к правилу идентификатора lexeme. Встроенные парсеры double_, alpha, alnum тоже ничего сложного из себя не представляют.

Однако Spirit должен начинать с какого-то правила. Мы могли бы выбрать row. Но здесь есть одна особенность. Spirit ищет не только полные совпадения, но и частичные. Например, выражение a = b^c может совпасть с правилом row до символа ^, который не будет распознан. Поэтому мы создадим правило следующего вида:

start = row > eoi;

Оператор > означает “обязательно должно следовать”, а eoi — конец данных. start теперь должно полностью совпадать со всеми данными, иначе будет генерироваться exception.

Давайте теперь добавим немного семантики. Spirit генерирует к каждому выражению некоторый атрибут, связанное значение. Например double_ после совпадения будет иметь в себе значение типа double. Эти значения можно менять.

a = (double_ >> '+' >> double_)[_val = _1 + _2];

Квадратные скобки окружают семантические действия. По сути это функции, но благодаря библиотеке Phoenix можно их объявлять в самой строке. Любой человек, хотя бы поверхностно знакомый с функциональным программированием уже признал в них лямбда-функции. Да, это они. Для тех, кто не признал, поясню. _val = _1 + _2 эквивалентно определению функции

double no_name(double _1, double _2) {
    double _val;
    _val = _1 + _2;
    return _val;
}

И эта функция передается в качестве параметра. Смысл выражения для a прост: получить два числа, разделенные знаком +, сложить их атрибуты и вернуть сумму в качестве атрибута выражения.

Если мы не собираемся проводить никаких действий, писать для правила _val = _1 глупо. Для этого есть оператор %=.

a %= b; // то же, что и a = b[_val = _1]

Теперь разберемся с переменными. Воспользуемся встроенным с Spirit средством под названием symbol. Определим таблицу переменных

// char - тип, из которого созданы ключи, double - тип значения
symbols<char, double> names;

В правиле subf мы можем написать теперь names вместо id. names будет совпадать теперь только с идентификаторами, которые были определены. Чтобы определять новые переменные, поступим следующим образом.

row = (id >> '=' >> row)[_val = set_tbl(_1, _2, ref(names))]
    | expr[_val = _1];

Так как names вычислится сразу, как только С++ на него наткнется, мы передаем ссылку, полученную с помощью ref, определенного в Phoenix. Функцию set_tbl нам предстоит написать. К сожалению, С++ воспринимает вызов функции непосредственно, поэтому нам придется схитрить и сделать ленивую функцию.

// Метафункция для Phoenix
struct set_tbl_impl {
    // Устанавливаем type тип возвращаемого значения
    // В нашем случае он всегда такой же, как и у Value
    template <typename Key, typename Value, typename Table>
    struct result {
        typedef Value type;
    };
    // Добавляем в таблицу запись (или обновляем её)
    // Возвращаем значение, чтобы разрешить a = b = 1
    // (и не морочить голову с optional<double>)
    template <typename Key, typename Value, typename Table>
    Value operator()(Key s, Value d, Table table) const {
        table.add(s, d);
        return d;
    }
};
phx::function<set_tbl_impl> set_tbl;

Добавляем обработчик ошибок и ввод из консоли и получаем готовую программу.

Как видите, всё не так уж и сложно. Зачем это нужно? Выбирайте сами. Разбирать INI-файлы c настройками PHP, писать языки, заточенные под вашу конкретную задачу.

Для людей, которые особо тяготеют к регулярным выражениям Perl, я специально делаю перло-спиритовый словарь. Выложу его вскоре в апдейт или отдельным постом. Атомарная группировка, применение модификаторов к части выражения, нечувствительность к регистру, рекурсия, развертка, минимальные квантификаторы и обратные ссылки — всё имеет аналог в Spirit.

P.S. Почти первый пост.