PatMat: сопоставление с образцом из Снобола-4

[vak]

PatMat - библиотека Си++ для сопоставления текстовых строк с образцом, перенесённая из древнего языка Снобол-4. Я когда-то безрезультатно пытался разыскать, а тут неожиданно набрёл. Добавил сборку через CMake и пофиксил одну фичу: отложенную подстановку переменных при замене. Ничо так работает, вполне можно пользоваться.

Описание на английском: Tutorial.org

История

Тут интересна история вопроса. Так судьба сложилась, что первой книжкой по программированию оказался Снобол-4, русский перевод 1980 года. Мне тогда было 14 лет, я учился в восьмом классе киевской физмат-школы, и штудировал премудрости Снобола тайком от учителей во время скучных уроков. География, история, литература всякая - ну вы понимаете. 😊

В дальнейшей жизни Снобол ни разу не пригодился, впрочем. Его реализации на советских машинах не встречались. Но элегантность и мощь сопоставления с образцом хорошо запомнилась. Исторически победил другой подход: юниксные регулярные выражения. Хотя они далеко не такие элегантные и мощные.

Снобол активно развивался и использовался в 60-е, однако был довольно тормознутым. В 1971-м Robert Dewar сделал из него компилятор, назвал Spitbol. Скорость выросла в десятки раз. Кстати, версия Spitbol нынче существует для Linux-x86_64, Linux-i386, ARM (Raspberry Pi) и некоторых других архитектур. Компилятор Spitbol написан на самом Spitbol, и генерит ассемблерный код для нужной архитектуры. Входной язык в точности совпадает со Snobol-4.

В 1997-м народ выдернул реализацию сравнения с шаблоном из Spitbol и переписал на Аду. Получился пакет GNAT.Spitbol.Patterns. В комментариях там можно видеть подробное описание программного интерфейса.

Постепенно Ада сошла со сцены, и в 2007-м Philip Budne переписал этот пакет с Ады на Си++. С 2013-го проект развивает Henry Weller, под именем PatMat. С этим пакетом я и стал играться.

Были попытки создать на основе Си++-ной реализации пакеты для Питона (snopy) и Lua (lspipat). Почему-то заглохло дело. Есть вариант на JavaStript: spipatjs.

Пример №1

Задача найти в строке два одинаковых символа подряд, и напечатать. Вот код из изначальной книжки 1968-го года. Заметьте, что для печати мы связываем шаблон с псевдо-переменной OUTPUT, присваивание которой означает печать в выходной поток.



А вот аналогичный код на Си++.

#include "Pattern.H"

using namespace PatMat;
using namespace std;

int main()
{
    string x;
    const Pattern pair = (Len(1) % x & +x) * output;

    pair("cook"); cout << endl;
    pair("common"); cout << endl;
    pair("aaron"); cout << endl;
    pair("chickadee"); cout << endl;
}

Компилируем, запускаем:

$ ./example1
oo
mm
aa
ee

Пример №4

Мощь снобольных шаблонов ярче всего видна в случае рекурсивных шаблонов. Здесь распознаём арифметические выражения, состоящие из переменных x y z, операций + - * / и скобок ( ). Я проверял этот код на версии Снобола с ftp.regressive.org - работает правильно. Но если скомпилировать Спитболом - крэшится. Что-то где-то поломано.



Если переписать в лоб на Си++ - PatMat зависает, циклится на рекурсии TERM, не поднимаясь на уровень EXP. Пришлось избавиться от лишних рекурсий, задействовав примитив Arbno.

#include "Pattern.H"

using namespace PatMat;
using namespace std;

void match(const Pattern &exp, const string &input)
{
    // Must match the whole string.
    const Pattern pattern = Pos(0U) & exp & Rpos(0U);

    if (pattern(input)) {
        cout << input << " is an expression" << endl;
    } else {
        cout << input << " is not an expression" << endl;
    }
}

int main()
{
    Pattern variable, addop, mulop, factor, term, exp;

    variable = Any("xyz");
    addop    = Any("+-");
    mulop    = Any("*/");
    factor   = variable | '(' & +exp & ')';
    term     = factor & Arbno(mulop & factor);
    exp      = addop & term & Arbno(addop & term) | term & Arbno(addop & term);

    match(exp, "x+y*(z+x)");
    match(exp, "x+y+z");
    match(exp, "xy");
    match(exp, "-x*y");
    match(exp, "+x*-y");
}

Компилируем, запускаем:

$ ./example4
x+y*(z+x) is an expression
x+y+z is an expression
xy is not an expression
-x*y is an expression
+x*-y is not an expression

Comments

[spamsink]

Круто!

[juan_gandhi]

А у вас в плюсах парсеров-комбинаторов нету?