Метарегулярные выражения на D
Пробежался по хабам и не нашел ничего написанного одновременно в хабы «D» и «Ненормальное программирование». Может сложиться совершенно ложное представление что на D пишут исключительно нормальные люди, или еще хуже того — что знание D автоматически делает из любого программиста нормального человека. Спешу опровергнуть.
Хотя сам я строго говоря программистом на D не являюсь — у меня нет ни одного промышленного проекта, зато я периодически с удовольствием роюсь в чужом коде выковыривая вкусные изюминки. А еще я пишу для себя небольшие утилиты, чаще всего для обработки текстовых данных, то что обычно делается на скриптовых языках, благо D предлагает очень неслабый набор инструментов для работы со строками.
Ну, а там где текстовые процессоры, там и регулярные выражения, как же без них. И здесь D снова оказывается на высоте, по легкости и удобству использования его библиотека регулярных выражений приближается к Perl. Но в Perl регулярки являются частью синтаксиса, можно сказать что сам язык выстроен в значительной мере вокруг них, а в D это вполне себе независимый модуль — std.regex из стандартной библиотеки написанный Дмитрием Ольшанским. Еще один замечательный момент — парсер выражения может быть построен во время компиляции (естественно если само выражение задано литералом), и разумеется я не мог удержаться чтобы не посмотреть как оно внутри устроено.
И вот тут то, разбираясь в деталях у меня слетела шляпа возникла мысль, а нельзя ли вызывать одно регулярное выражение изнутри другого? Не вставить литерал (как тривиально можно сделать в Perl например), а непосредственно вызвать скомпилированный код одного выражения изнутри другого. Достаточно на мой взгляд дурацкая идея чтобы с ней стоило поиграть.
Итак, чего мы хотим? Примерно вот такого (пока это псевдокод):
INT=regexp("\d+");
LIST=regexp("INT(,INT)*");Поскольку пост рассчитан на широкую аудиторию ненормальных программистов, не только тех которые знакомы с D, я пожалуй сначала опишу те языковые конструкции которые мы будем использовать.
Я и сам предпочитаю иметь шпаргалку перед глазами, прямо как первоклассник выучивший четверостишие к уроку.
Вообще, D предлагает широчайший выбор базовых приемов программирования и метапрограммирования, но мы здесь постараемся ограничиться минимально необходимым набором, зато постараемся подробно разобраться с каждым. Тем кто заинтересуется, я очень рекомендую прочитать замечательную статью Templates Revisited написанную автором языка, она посвящена шаблонам в целом, но в качестве примера как раз демонстрирует compile-time парсер регулярных выражений который я и взял за основу. Да, разумеется я написал свою маленький парсер для экспериментов, далеко не полный и не совсем корректный, зато идеально подходящий в качестве подопытного кролика.
Итак:
вычисления времени компиляции.
С этим все просто, грубо говоря любое выражение которое можно вычислить во время компиляции будет вычислено. Вторая фундаментальная конструкция — static if (…), проверяется во время компиляции (или не компилируется вообще), неимоверно упрощает метапрограммирование.
шаблоны
В D шаблоны как функций так и классов декларируются с помощью дополнительного набора параметров:
int f(T)(T x int y);
struct(T,U) А { T x; U y; } и вызываются как
f!(int)(1, 2);
A!(int,string) a; Шаблонным параметром может быть тоже грубо говоря что угодно, включая плавающие и строковые литералы и любые символы. Однако ключевое слово template тоже сохранено и создает параметризованные namespace’s которые мы будем широко использовать:
template X(T) {
const T x=0;
} mixin
Эта конструкция вставляет литерал прямо в код: mixin("static int x=0;"); тоже пригодится.
операции со строками
Их миллион, но нам реально понадобится только slicing: "ABCDEFGH"[2..4] == "CDE"; Обратите внимание что приведенный пример тоже вычисляется во время компиляции.
alias
Это означает просто синоним, но с широчайшим спектром применения, особенно в параметрах шаблонов (тот самый упомянутый any symbol)
знаменитый eponymous trick
я сознательно не буду использовать, поскольку поначалу от него у новичков слегка сносит крышу. В конце концов это не более чем синтаксический сахар и без него всегда можно обойтись.
Вот собственно и весь наш инструментарий, переходим к парсеру.
Вид сверху:
1. template regex(string re)
2. {
3. static if(re.length) {
4. // parse escaped sequences
5. static if(re[0] == '\\') {
6. alias atom=compile_escape!re;
7.
8. // parse character class
9. } else static if(re[0] == '[') {
10. alias atom=compile_class!re;
11.
12. // parse atom
13. } else static if(re[0] == '(') {
14. alias atom=compile_atom!re;
15.
16. // parse dot
17. } else static if(re[0] == '.') {
18. alias atom=compile_anychar!re;
19.
20. // parse regular literals
21 } else {
22. alias atom=compile_char!re;
23. }
24.
25. // parse predicate (if any) *+?
26. alias pred=compile_pred!(atom, re[atom.skip..$]);
27. alias result=both_of!(pred, regex!(re[pred.skip..$]));
28.
29. // public result
30. static const size_t skip=result.skip;
31. alias match=result.match;
32.
33. } else {
34. static const size_t skip=0;
35. // end of regular expression
36. alias match=test_empty!(re);
37. }
38. }Во первых, что это? Не функция, не класс, шаблон в чистом виде, просто кусок кода параметризованный литералом. Тем не менее, alias на него исправно берется.
Второе что следует заметить, из всего этого обилия кода компилируется только одна маленькая ветка (обратите внимание на каскад static if)
Возвращаемые значения? Их два (стр 30–31 и 34–36): static const size_t skip; — показывает сколько символов из регулярного выражения мы использовали.alias match; — это нечто, (то есть alias) которое можно вызывать как функцию с параметром string.
Ну и предлагается использовать это примерно вот так:
alias myRe=regex!"A?[a-z]+\d*";
auto result=myRe.match(some_string);Забегая вперед, скажу что возвращаемое значение — структура из двух элементов:
struct Match
{
bool _success;
ulong length;
bool opCast(T : bool)() const { return _success; }
}первый показывает удовлетворяет ли строка регулярному выражению, а второй — длину пройденной подстроки. Хотя сейчас, во время компиляции, нам это глубоко по барабану.
Пройдемся теперь по веточкам, удобнее начинать снизу:
Если регулярное выражение пустое (re.length == 0) (стр 33), мы возвращаем ссылку на функцию возвращающую всегда true, то есть Match (true, 0). Это успешный конец парсинга.
Если регулярное выражение не пустое (стр 3), мы сначала выбираем субпарсер из набора compileXXX в зависимости от первого символа: служебные \.[(_ или любой другой символ. Субпарсер имеет тот же интерфейс что и парсер верхнего уровня — определяет внутри себя константы skip и match и в последней (простейшей, стр 22) ветке возвращает skip=1 и ссылку на функцию проверяющую первые символы двух строк на равенство, вот так:
template compile_char(string re)
{
static const size_t skip=1;
alias match=test_char!re;
}
// match single character
Match test_char(string re)(string s)
{
static if(re.length) {
if(s.length && s[0] == re[0])
return Match(1,1);
}
return Match(0,0);
}Вторая конструкция здесь — обычная шаблонная функция которая будет вызвана во время исполнения.
Остальные субпарсеры ненамного сложнее и устроены аналогично, но что происходит после, когда парсер выбран? Дальше может идти предикат, один из ?*+, или не идти, поэтому выбранный субпарсер передается в еще один парсер: compile_pred (стр 26):
// modify previous (term) regex with one of *+? predicates, or none
template compile_pred(alias term, string re)
{
static if(re.length) {
static if(re[0] == '*') {
static const size_t skip=term.skip+1;
alias match=zero_or_more!term;
} else static if(re[0] == '+') {
static const size_t skip=term.skip+1;
alias match=one_or_more!term;
} else static if(re[0] == '?') {
static const size_t skip=term.skip+1;
alias match=zero_or_one!term;
} else {
// no predicate, return term
static const size_t skip=term.skip;
alias match=term.match;
}
} else {
// no predicate, end of regex, also return term
static const size_t skip=term.skip;
alias match=term.match;
}
}
// conditionally match the expression, always match but matched length may be different
Match zero_or_one(alias term)(string s)
{
Match r=term.match(s);
return r? r : Match(1,0);
}Здесь, по уже обкатанному сценарию, в зависимости от предиката skip увеличивается на единицу, а функция match устанавливается на одну из шаблонных функций _zero_or_more (*), zero_or_one (?) или one_ormore (+), одну из них я привел для примера. Или, если предикат отсутствует, оба эти значения берутся неизменными из атомарного парсера.
Как всегда с шаблонами, в конце должна быть рекурсия
Возвращаясь к главному парсеру, мы получили законченное выражение для субпарсера с предикатом и теперь наконец передаем его в последний субпарсер, который вызывает оба парсера по очереди и вычисляет суммарную длину (стр 27):
alias result=both_of!(pred, regex!(re[pred.skip..$]));
static const size_t skip=result.skip;
alias match=result.match;
...
// match both expressions
template both_of(alias re1, alias re2)
{
static const size_t skip=re1.skip+re2.skip;
alias match=test_join!(re1,re2);
}
// match both of expressions, return matched length
Match test_join(alias re1, alias re2)(string s) {
auto m1=re1.match(s);
if(m1) {
auto m2=re2.match(s[m1.length..$]);
return Match(m1 && m2, m1.length+m2.length);
}
return m1;
}заметьте что вторым параметром для субпарсера both_of главный парсер передает самого себя, но с урезанным регулярным выражением — regex!(re[pred.skip…$]), первые символы уже использованные субпарсерами отрезаются. Таким образом, регулярное выражение будет рекурсивно пройдено до конца, будет построена цепочка из шаблонных функций типа test_char, test_space, test_range, one_or_more и т.д., и мы вернемся к тому с чего начинали — пустому выражения для которого всегда вызывается функция test_empty возвращающая Match (true, 0).
Парсинг закончен.
Прежде чем перейти к сути поста, я хочу привести еще один вспомогательный шаблон (он уже использовался в разборе выражений »[]» и »()»). Как легко понять, он рекурсивно вычисляет длину строки до заданного символа. Скоро он нам пригодится:
// misc., return length of literal up the to terminator
template extract_until(string s, char terminator)
{
static assert(s.length, "missing terminator");
static if(s[0] == terminator) {
static const length=0;
} else {
static const length=1+extract_until!(s[1..$], terminator).length;
}
}Наконец мы дошли до сути
Итак, мы построили модельный парсер который понимает конструкции \s \d \w \x. [a-z] (AB) * + ? , теперь совсем легко оказывается добавить к нему еще одну веточку. Если кто заметил, вместе с другими пропущенными выражениями я поленился построить обработку предиката {n, m}. Поскольку грех не использовать такие красивые скобки, я их узурпирую для выражения {SUBEXPR}. Смотрите, сначала добавляем ветку в главный парсер:
// parse meta expression
} else static if(re[0] == '{') {
alias atom=compile_meta!re;теперь добавляем для него субпарсер, удивительно простой:
template compile_meta(string re)
{
static const skip=2+extract_until!(re[1..$], '}').length;
mixin("alias match="~re[1..skip-1]~".match;");
}первая строчка вычисляет длину подвыражения до замыкающей скобки, а вторая использует mixin чтобы вставить в код ссылку вида: alias match=SUBEXPR.match;. И это все! Оно начинает работать.
Теперь мы можем наконец написать:
alias NUM=regex!"\\d+";
alias INT=regex!"[+-]?{NUM}";
alias LIST=regex!"{INT}(,{INT})*";
assert(NUM.match("1234") == Match(true, "1234".length));
assert(INT.match("-12") == Match(true, "-12".length));
assert(LIST.match("1,+2,-3,4") == Match(true, "1,+2,-3,4".length));Прямо бизон какой-то получился.
И тут мне подумалось …
Если бы я был персонажем голливудского фильма, этаким сумасшедшим гением, я бы по законам жанра обязательно должен был что-то упустить, какую-то мелочь, которая в конце и разрушила бы мои злобные планы.
И только подумал, как вот оно -циклическая зависимость модулей. Дело в том что это все прекрасно работает внутри одного файла, а если бы я попытался выделить этот код в отдельную библиотеку или модуль то ничего бы не получилось. В примере выше символы NUM и INT определенные в user-code должны быть экспортированы вниз, на уровень модуля metare, что очевидно невозможно. Но ничего, когда-нибудь, в каком-нибудь языке, кем-нибудь будет предложен способ обхода и тогда я наконец завоюю этот мир.
Всем спасибо, надеюсь было забавно.
Как обычно, если кому-либо понадобится — ссылка на код
