(возможно) Первый в мире генератор читабельных, хоть и чрезвычайно медленных, парсеров на JS

Опубликован: 07 ноя 2013
Метки: functional-programming 7 , javascript 15 , parsers 1

Если ты меня вообще помнишь, читатель — то, наверняка, помнишь и то, что мои посты в подавляющем количестве случаев разочарующе длинны и довольно-таки часто им предшествует лирическая предыстория. Заверяю тебя, этот пост отнюдь не исключение — я настолько же надёжный графоман, как и ранее, а то ещё и более закалённый.

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

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

Всё как в старые добрые времена. Добро пожаловать, друг.

Обширная предыстория

Не знаю, что конкретно ударило мне в голову года эдак два назад, но мне сильно не понравились существующие на тот момент парсеры Markdown, написанные на JS. Ты удивлён, не так ли?

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

Поскольку я любитель активно генерализировать задачи, я нашёл отличный генератор JS-парсеров PEG.js, потом нашёл GUI-ориентированную библиотеку по подсветке markdown-синтаксиса на C++ (которая используется в бесплатном, стильном и прекрасном Mac-OS-приложении для редактирования Markdown, не в пример мне кратко именующем себя Mou), из которого я выдрал LEG-грамматику Markdown (которая, в свою очередь была модифицирована из грамматики Джона МакФерлейна) и начал адаптировать всю эту портянку под PEG.js, параллельно её улучшая.

Чем всё это кончилось? Лишь тем, что я запомнил имя Ali Rantakari, автора библиотеки подсветки синтаксиса, минимум на два года с хвостиком. Не потому что он в чём-либо виноват, а просто вот так вот вышло.

Если взять глубже, всё вышеописанное зашло в свой локальный тупик в тот безрадостный момент, когда я увидел что сгенерированный парсер занимал просто неуважительные для меня 6МБ (по памяти эта цифра может быть воспроизведена неточно, но масштаб трагедии, я думаю, должен быть нагляден; да и вообще, почему-то в голове у меня крутится цифра 24) неминифицированного JavaScript-кода. Минифицированного — не сильно меньше. Да-да, читатель, ты не ошибся, парсер какого-то (TODO: пометить красным) вшивенького маркдауна, и 6МБ — это ни в какие ворота.

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

И, так как мне такого не рассказывали, я очень возмутился — очень много было неоптимальных, с точки JS-программиста, кусков кода в этом парсере, а ещё даже более раздражали Java-подобные имена функций в коде. Вот прям нет сил терпеть. Я даже пример того кода приводить не буду, прошу поверить мне на слово (на самом деле вот отреставрированный вариант, сгенерированный PegJS версии двухгодичной давности, но почему-то в шесть раз меньше по размеру, возможно из-за того что версия недостаточно ранняя ;) ). А вот сравнение современного варианта оригинального PegJS и описываемой здесь модификации.

И я ещё раз перегенерализировал задачу — убедил себя, что не могу позволить себе не привести этот парсер в приличный функциональный вид. Чтобы, например, такое вот правило:

1
2
3

shakespeare = ("To" / "2") space "b" "e"? space
              ("or" / "|") space ("not" / "!") space
              ("to" / "2") space "b" "e"?

Генерировало такой вот парсер:

rules.shakespeare = function() {
  return (
    seqnc(
      choice(match("To"), match("2")),
      ref(rules.space),
      match("b"), maybe(match("e")),
      ref(rules.space),
      choice(match("or"), match("|")),
      ref(rules.space),
      choice(match("not"), match("!")),
      ref(rules.space),
      choice(match("to"), match("2")),
      ref(rules.space),
      match("b"), maybe(match("e"))
    )
  ());
}

Или что-то вот такое абстрактное:

foo = "x"+ a:("-" c:some_rule { return c; })? { return a; }

Генерировало такой:

rules.foo = function() {
  return (
    action(
      seqnc(
        some(
          match("x")
        ),
        label("a",
          maybe(
            action(
              seqnc(
                match("-"),
                label("c",
                  ref(rules.some_rule)
                )
              ),
              function() { return c; }
            )
          )
        )
      ),
      { return a; }
    )
  ());
}

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

Такова была цель, и, надеюсь, ты согласишься, как идея она была достаточно красива.

… И вполне исполнима. Спустя аж джва с лишним года, её реализация у меня таки вышла! Не скажу, что я прямо так уж сильно торопился, я периодически вообще забрасывал это дело и преключался на другие, немногим более перспективные, а то и вообще уходил в запой. Тем не менее, два года, вечерами, я по крупинке ковырял код и тесты просто ради того, чтобы чем-то себя занять. Продумывал оптимизации и «операторы» в неподходящих жизненных ситуациях, в непредназначающихся обстановках, в неположенное время — точно так, как делает любой уважающий себя нерд.

Это хорошие новости. Но, как всегда, нашлись и плохие. И, конечно же грустные. Приведу статистику (как только gist выдержал эти килограммы?):

css.pegjs — исходная грамматика
- размер: 13.4кБ
- строк: 552 ± 15 на комментарии
css.old_pegjs.parser.js — парсер, сгенерированный оригинальной версией PEG.js двухгодичной давности, коммит 4f86fca3d7
- размер: 367кБ
- строк: 11,378 ± 15 на комментарии,
- парсинг файла размером 11.8кБ x 10 раз: 11.60мс
css.cur_pegjs.parser.js — парсер, сгенерированный текущей оригинальной версией PEG.js,
- размер: 334кБ,
- строк: 11,225 ± 15 на комментарии,
- парсинг файла размером 11.8кБ x 10 раз: 19.40мс
css.pegjs_fn.parser.js — парсер, сгенерированный моей текущей версией PEG.js-FN,
- размер: 107кБ,
- строк: 4,452 ± 200 на комментарии (у меня много комментариев и там много чего свернуть можно),
- парсинг файла размером 11.8кБ x 10 раз: 561.60мс

То есть при не-особо-сильной экономии на размере, скорость увеличилась не просто кардинально, а катастрофически (в 30 раз относительно текущей версии). Можно свалить на частный случай парсера, JSON-парсер парсит всего в 5-20 раз дольше оригинала, но к сожалению скорость парсинга увеличивается экспоненциально относительно размера парсящегося файла (как ты думаешь, читатель, может это подсказка?).

Но я пока ещё ничего не оптимизировал. Вообще. Даже не брался.

Отдельная беда в том, что автор PEG.js, David Majda, пока я ковырялся со своей версией, перевёл всё своё хозяйство на псевдо-байткод (статистика выше, тем не менее, представлена именно с байткодовой версией). Нет, безусловно я следил за тем, что там происходит, и исправно обновлял тесты на новые. Но я хотел добиться своего результата, так как вообще не с чем было даже сравнить, чтобы оценить уровень бесполезности моей идея. Кстати, 469 тестов, это вам не хухры-мухры. Очень приятно смотреть, как они все проходят. Особенно после моментов, когда до этого бывало такое, что в десятый раз исправляешь три теста и начинают валиться пятьдесят. Впрочем, тебя таким не удивить.

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

Оптимизацию я наметил на будущее, может быть что-то и выйдет. Но сейчас никак нельзя останавливаться.

Ибо в процессе, как я считаю, я изобрёл Функциональные Операторы Парсинга (если только их ещё не придумали в Хаскеле — иначе я сильно опоздал и остаётся лелеять надежду на туманный шанс запатентовать прелестный термин).

О них и пойдёт речь.

Ах да, все исходники — в моём проекте PEG.js-FN на гитхабе.

Структура парсера

В парсерах, сгенерированных PEGjs-FN (в отличие, кстати, от оригинала [по крайней мере, на данный момент]), пользовательский код чётко отделяется от кода самого парсера собственной областью видимости.

«Что за пользовательский код?», — спросишь ты.

В PEG.js есть замечательная возможность заключить любую часть правила грамматики в скобки и выполнить некий JS-код, если эта часть совпала с исходной строкой. При этом в JS-коде, в виде переменных, доступны все предшествующие именованные совпадения, находящиеся на том же уровне контекста или выше. Эти «совпадения» также могут скрывать под собой другой JS-код, по такому же принципу возвращающий и выполняющий всё, что программисту угодно.

Возьмём пример выше:

1	foo = "x"+ a:("-" c:some_rule { return c; })? { return a; }

Если ты знаком с PEG-грамматикой, то ты всё понял. Если нет — то нет, но не отчаивайся, я попробую объяснить.

Здесь совпадение с именем a должно бы было возвращать символ “-”, конкатенированный с результатом парсинга по правилу some_rule — но действие этого совпадения переопределено и оно возвращает только результат парсинга по правилу some_rule. Тем же образом, совпадение по правилу foo в данном случае возвращает не набор символов «x», конкатенированных с результатом парсинга по последовательности a — а лишь результат парсинга по последовательности a. А могло и запустить искуственный интеллект, который вернул бы новейший сонет Шекспира.

Кроме того, PEG.js предоставляет и другую замечательную возможность: предварить весь парсер неким глобальным (для парсера) JS-кодом, который, следовательно, будет доступен всем таким блокам кода. В PEG.js такой код именуется инициализатором.

Совокупность описанных возможностей и есть пользовательский код — по сути, любой JS-код, содержащийся в грамматике.

Итак, структура:

(function() {

 // общие для пользовательского кода и парсера переменные
 var input, ppos, pos;

 // весь пользовательский код, изолированный от кода парсера
 var __user_code = function() {

   // функции, предоставляемые пользователю парсером
   function offset(), function text(), ...

   // инлайн-код пользовательского инициализатора
   function PARSE_ME_BABY...
   function SHIT_THAT_KILLED_ELVIS...

   return {
     // сгруппированные по имени правила блоки пользовательского кода
     foo: [ function(ctx) { return (function(c) { return c; })(ctx.c); },
            function(ctx) { return (function(a) { return a; })(ctx.a); }  ]
     ...
   }

 };

 // код парсера, изолированный от пользовательского кода
 return (function() {

   // переменные, доступные только правилам, операторам и парсеру
   var code, rules = {};

   // код правил, входящих в данный парсер
   rules.foo = function() { var code = code.foo;
                            return action(seqnc(...))(code[1]); }
   rules.start = rules.foo;

   // все использующиеся в парсере операторы
   // (неиспользующиеся не включаются)
   function action() { ... }
   function seqnc() { ... }
   function match() { ... }
   ...

   // парсеро-независимые утилиты и хелперы
   ...

   return {
     ...
     parse: function(_input) {
        input = _input;
        code = __user_code();
        return rules.start();
     }
   }

 })();

})();

Довольно просто, не правда ли? :)

Пояснения

Области видимости операторов в парсере реализованы через цепочки прототипов JS, то есть на каждую вложенную область видимости создаётся JS-объект, свойства которого хранят текущую область видимости, а прототип указывает на родительскую область видимости. Возможно, этот факт тоже пагубно влияет на скорость.

Все результаты выполнения правил кэшируются по ключу «имя правила + позиция во входной строке», как и в оригинале.

При неудачном парсинге выбрасывается исключение MatchFailed, которое, если не было перехвачено, снабжается дополнительной информацией, вроде двумерных координат неудачи (строка: столбец), и выдаётся пользователю.

Операторы

Краткий вводный ликбез дан, можем перейти непосредственно к разбору операторов.

Секрет операторов парсинга — а по-другому их и не назовёшь – в том, что все они — суть отложенные функции. Когда они вызываются в первый раз, в них передаётся лишь часть контекста вызова и она надёжно хранится вплоть до момента второго вызова, когда бы он ни произошёл. Эту технику также называют частичным применением, и будь ты хаскелист или скалист, она тебе знакома на все сто.

В JavaScript для реализации частичного применения можно построить либо небольшую лесенку из анонимных функций, либо использовать Function.bind. Я, как и писал в статье про Асинхронного Самурая, остановился на первом варианте. Не стоит ныне напускать ненужной важности на этот приём, по-моему тот пост и так понапустил достаточно.

Что это даёт нам?

Частичное применение решает все проблемы создания функциональных и читабельных парсеров одним махом. По крайней мере, если у вас на руках AST-дерево грамматики (а PEG.js мастерски создаёт AST-деревья).

Предположим, у вас есть активный на текущий момент оператор, который выполняет последовательность других операторов, одного за другим, но если какой-то из них не совпал со строкой ввода, не бьёт панику, прерывая работу парсера и ругаясь несовпадениями, а тихо откатывается назад.

То есть если один из цепочки операторов бросает исключение, надо первое же из них перехватить и подавить. А ведь этот оператор может состоять из уходящих далеко вглубь цепочек других операторов. Или сам быть где-то в глубине этой цепочки. Далекой-далекой глубине. Но при этом всегда конечной.

Применив частичное применение (TODO: убрать тавтологию) к каждому из дочерних операторов мы, при первом вызове, «замораживаем» слепки информации об их вызове по цепочке, принуждая их сохранить данные о своих внутренних операторах. Затем для каждого из внутренних операторов второго уровня мы рекурсивно повторяем это действие — и так далее и далее вглубь. Это первая часть контекста. При этом наш активный оператор таким же образом «замораживает» всю цепочку целиком при первом вызове себя любимого.

Например, код sequence(match("foo"), or(match('bar'), ch())), запомнит лишь (внутри оператора sequence), что в этой точке надо будет попробовать сравнить входную строку со строкой "foo", затем попробовать сравнить оставшуюся часть c "bar", а если не выйдет — откатиться и убедиться что строка не кончилась и следующим за "foo" идёт некий символ (так действует оператор ch()). Но он не выполнит этих действий фактически, а «притормозит» их до следующего вызова sequence.

И один единственный толчок — второй вызов активного оператора, запускает мощный импульс развёртки — словно доминошки, расставленные в форме дерева, они начинают задевать друг друга, приоткрывая своим падением совпавшие строки и результаты JS-кода, пока в конце концов импульс не дойдёт до кончика самой длинной ветки. (FIXME: слишком качественная аллегория).

Или не дойдёт, если какая-то из неудач парсинга не была подавлена логикой парсера и просочилась наружу.

Собрав результаты вместе, мы получаем результат парсинга этого оператора. И группы операторов, в которую он входит. Таким же образом мы выполняем и правила, придавая импульс цепочке операторов внутри них. Потому что правила — те же операторы парсинга, и единственное их отличие — в том, что они не предопределены — вернее, описаны самим пользователем. Но принцип их «откладывания» идентичен принципу «откладывания» операторов. И начинаем парсить весь текст мы с того же единственного импульса — запускаем искру стартового правила — и вжих!

Если вам всё ещё не очень понятно, попробуйте сравнить грамматику и код сгенерированного парсера в этом примере (там есть выдержка из парсера и сгенерированный парсер целиком).

Оптимизации, кстати, если и затронут код операторов вообще, то затронут минимально — в плане смены форматов вызова внутренних функций парсера, что никоим образом не поменяет их логики.

Наконец, пройдёмся по каждому из операторов подробнее. Код большинства из них не превышает десяти строк, но я постараюсь максимально уныло описать действие каждого — подобно тому, как это делают в справочниках. На самом деле самое важное в нижеследующей части — именно код операторов, ибо он подобен паттернам — а я продолжу надеяться, что он понятен без пояснений: даже несмотря на то, что в целях экономии места и незамутнённости твоего взора я опустил код некоторых внутренних функций парсера вроде safe, failed и inctx (их код, при необходимости, можно подсмотреть по ссылке из предыдущего абзаца (повторю её, чтобы ты лишний раз не бегал глазами)).

1. `ch`

Описание: Проверить, имеется ли в текущей позиции какой бы то ни было символ и вернуть его. Конец строки ввода в текущей позиции расценивается как ошибка парсинга.

Синтаксис в грамматике: .

Код:

function ch() {
  if (pos >= ilen) failed(ANY, EOI);
  return input[pos++];
}

Если текущая позиция парсинга по значению больше или равна длине строки, сообщить о том, что парсинг не удался, и при том, что ожидался любой символ (маркер ANY), был обнаружен конец ввода (маркер EOI — End of Input): функция failed конструирует исключение MatchFailed и выбрасывает его наружу.

Если позиция находится в пределах длины строки — возвращает текущий символ, затем инкрементируя позицию парсинга.

Пример:

1
2
3

var input = 'foo';
// PEG: start = . . .
seqnc(ch(), ch(), ch())(); // == [ 'f', 'o', 'o' ]

2. `match`

Описание: Сравнить входную строку с переданной, стартовав с текущей позиции;

Синтаксис в грамматике: "строка", 'строка'

Код:

function match(str) {
  var slen = str.length;
  if ((pos + slen) > ilen) { failed(str, EOI); }
  if (input.substr(pos, slen) === str) {
    pos += slen; return str;
  }
  failed(str, cc());
}

Если сумма значений текущей позиции и длины переданной строки больше длины входной строки, сообщить о неудаче парсинга, пояснив, что ожидалась переданная строка, а был обнаружен конец ввода (маркер EOI — End of Input).

Если участок ввода, начинающийся от текущей позиции парсинга и равный по длине переданной строке идентичен по содержимому переданной строке, увеличить позицию парсинга на длину переданной строки и вернуть её.

Если участок не идентичен переданной строке, сообщить о несовпадении, пояснив, что ожидалась переданная строка, а был обнаружен другой символ: функция cc() (не путать с оператором ch) возвращает текущий символ или маркер EOI, если текущая позиция превышает длину строки ввода.

Пример:

1
2
3

var input = 'foo';
// PEG: start = . 'oo'
seqnc(ch(), match("oo"))(); // == [ 'f', 'oo' ]

3. `re`

Описание: Сравнить входную строку с переданным регулярным выражением, начиная с текущей позиции парсинга. На самом деле в PEG.js намеренно запрещены все регулярные выражения кроме наборов символов в виде [...] и [^...] (чтобы пользователь не имел возможности заменить правила PEG «конкурирующими» спецификациями). По этой причине и внутрь данного оператора враг не пройдёт, а будет вырезан на этапе составления AST-дерева. С другой стороны, в этот же оператор перенаправляются проверки match с ignore-case флагом.

Синтаксис в грамматике: [<символы>], [^<символы>], [<символ1>-<символn>], [^<символ1>-<символn>], "строка"i, '<строка>'i

Код:

function re(rx, desc) {
  var res, desc = desc || rx.source;
  if (res = rx.exec(input.substr(pos))) {
    if (res.index !== 0) failed(desc, cc());
    pos += res[0].length; return res[0];
  } else failed(desc, cc());
}

Принимает объект регулярного выражения rx и его символьное описание desc. Выполняет сравнение входной строки с rx, начиная с текущей позции парсинга.

Если сравнение не удалось, с помощью функции failed() выбрасывает исключение MatchFailed с пояснением, что ожидалось описанное в desc, а был найден символ на текущей позиции, который возвращает функция cc() (не путать с ch).

Если сравнение удалось — увеличивает позицию парсинга на длину совпавшей строки и возвращает последнюю.

Пример:

1
2
3

var input = 'foo';
// PEG: start = [^f-o]+
some(re(/[^p-v]/))(); // == [ 'f', 'o', 'o' ]

4. `text`

Описание: Вместо комплексного результата выражения вернуть совпадающий текст. Имеет смысл, например, при переопределении оператора seqnc, который «упаковывает» результаты последовательности операторов в массив.

Синтаксис в грамматике: $<выражение>

Код:

function text(f) {
  var p_pos = pos;
  f(); return input.substr(p_pos, pos-p_pos);
}

Сохранить локально предыдущую позицию парсинга, выполнить переданный оператор f не сохраняя возвращённого им результата и вернуть отрезок входной строки между предыдущей позицией парсинга и новой (выполнение операторов влияет на позицию). Если было выброшено и не перехвачено исключение, парсинг прекращается.

Пример:

1
2
3

var input = 'foo';
// PEG: start = $(. . .)
text(seqnc(ch(), ch(), ch()))(); // == [ 'foo' ], а не [ 'f', 'o', 'o' ]

5. `maybe`

Описание: Проверить, присутствует ли данное выражение во входной строке максимум один раз, и если да — переместить позицию на конец совпадения, а если нет — не совершать ничего.

Синтаксис в грамматике: <выражение>?

Код:

function maybe(f) {
  var missed = 0,
      res = safe(f, function() { missed = 1; });
  if (missed) return '';
  return res;
}

Выполнить переданный оператор f в безопасном контексте с помощью функции safe, которая передаёт исключение, если оно возникло при выполнении оператора, в переданную вторым параметром анонимную функцию, которая, в свою очередь, устанавливает флаг missed в единицу. Если флаг missed установлен, вернуть пустую строку, иначе вернуть результат выполнения оператора.

Когда совпадение имело место, позиция парсинга корректно перемещается оператором f или операторами, которые он вызывает.

Пример:

1
2
3

var input = 'foo';
// PEG: start = 'f'? (. .)?
seqnc(maybe(match('f')), maybe(seqnc(ch(), ch())))(); // == [ 'f', [ 'o', 'o' ] ]

6. `some`

Описание: Проверить, присутствует ли данное выражение во входной строке минимум один раз и переместить позицию на конец совпадения или нескольких совпадений.

Синтаксис в грамматике: <выражение>+

Код:

1
2
3

function some(f) {
  return [f()].concat(any(f)());
}

Выполнить переданный оператор f в небезопасном контексте, то есть если будет выброшено исключение, то действие оператора some будет остановлено, и затем объединить его результат с результатом выполнения оператора any (проверить на ноль или более совпадений и вернуть их), рассмотренного ниже, с теми же параметрами.

Когда совпадения имели место, позиция парсинга корректно перемещается оператором f или операторами, которые он вызывает.

Пример:

1
2
3

var input = 'foo';
// PEG: start = 'f'? .+
seqnc(maybe(match('f')), some(ch()))(); // == [ 'f', [ 'o', 'o' ] ]

7. `any`

Описание: Проверить максимальное количество последовательных совпадений с данным выражением. Если совпадения были — переместить позицию парсинга на конец последнего совпадения, если совпадений не было — просто ничего не совершать.

Синтаксис в грамматике: <выражение>*

Код:

function any(f) {
  var s = [],
      missed = 0,
      on_miss = function() { missed = 1; }
  while (!missed) {
    s.push(safe(f, on_miss));
  }
  if (missed) s.splice(-1);
  return s;
}

Выполнять переданный оператор f в безопасном контексте с помощью функции safe пока флаг missed не будет установлен в единицу (совпадения кончились). Функция safe передаёт исключение, если оно возникло при выполнении оператора в функцию on_miss, которая, в свою очередь, устанавливает флаг missed. Все удачные результаты накапливаются в массив s.

Если флаг missed был установлен, убрать последний (сорвавшийся) результат из массива s и вернуть его; иначе вернуть массив с результами s без изменений.

Пример:

1
2
3

var input = 'foo';
// PEG: start = 'f'+ 'o'*
seqnc(some(match('f')), any(match('o')))(); // == [ [ 'f' ], [ 'o', 'o' ] ]

8. `and`

Описание: Проверить совпадение и если оно имело место, вернуть пустую строку и не передвигать позицию парсинга. Если совпадения не произошло, выбросить ошибку парсинга.

Синтаксис в грамматике: &<выражение>

Код:

function and(f) {
  var p_pos = pos, missed = 0;
  nr = 1; safe(f, function() {
    missed = 1;
  }); nr = 0;
  pos = p_pos;
  if (missed) failed(EOI, cc());
  return '';
}

Сохранить позицию локально и выполнить переданный оператор f в безопасном контексте с помощью функции safe. Функция safe передаёт исключение, если оно возникло при выполнении оператора, в анонимную функцию, которая, в свою очередь, устанавливает флаг missed.

Перед выполнением оператора f все возникшие исключения подавляются флагом nr (not report), парсер проверяет этот флаг при несовпадениях и если он установлен, не накапливает информацию о произошедшем (иначе даже подавленные исключения сохраняют информацию о несовпадениях и переносят её в финальную ошибку парсинга). После выполнения оператора значение флага возвращается в ложь.

Затем значение позиции парсинга откатывается до предыдущего (это важно сделать до сообщения об ошибке или возвращения значения) и если имело место исключение, порождается ошибка парсинга с пояснением, что ожидался конец ввода (маркер EOI, End of Input), а был обнаружен текущий символ; если исключений не было, оператор возвращает пустую строку.

Пример:

1
2
3

var input = 'foo';
// PEG: start = &'f' 'foo'
seqnc(and(match('f')), match('foo'))(); // == [ '', 'foo' ]

9. `not`

Описание: Проверить совпадение и если оно не имело места, вернуть пустую строку и не передвигать позицию парсинга. Если совпадене произошло, выбросить ошибку парсинга.

Синтаксис в грамматике: !<выражение>

Код:

function not(f) {
  var p_pos = pos, missed = 0;
  nr = 1; safe(f, function() {
    missed = 1;
  }); nr = 0;
  pos = p_pos;
  if (missed) return '';
  failed(EOI, cc());
}

Затем значение позиции парсинга откатывается до предыдущего (это важно сделать до сообщения об ошибке или возвращения значения) и если имело место исключение, оператор возвращает пустую строку; если исключений не было, порождается ошибка парсинга с пояснением, что ожидался конец ввода (маркер EOI, End of Input), а был обнаружен текущий символ.

Пример:

1
2
3

var input = 'foo';
// PEG: start = !'g' 'foo'
seqnc(not(match('f')), match('foo'))(); // == [ '', 'foo' ]

10. `seqnc`

Описание: Вычислить несколько операторов в порядке очереди, вернуть результаты их выполнения обёрнутыми в массив.

Синтаксис в грамматике: <выражение1> <выражение2> ...

Код:

function seqnc(/*f...*/) {
  var ppos = pos;
  var fs = arguments,
      s = [],
      on_miss = function(e) {
                  pos = ppos; throw e; };
  for (var fi = 0; fl = fs.length;
        fi < fl; fi++) {
      s.push(safe(fs[fi], on_miss));
  }
  return s;
}

Принимает список операторов в качестве параметров (их может быть неограниченное количество, благодаря использованию arguments) — сохраняет его в переменной fs. Сохраняет локально текущую позицию парсинга в переменной ppos. s — массив, в который будут собраны результаты выполнения переданных операторов.

Итерируясь по списку операторов, выполняет каждый в безопасном окружении с помощью функции safe, которая передаёт первое же перехваченное исключение в функцию on_miss, которая, в свою очередь, предварительно отматывает позицию парсинга назад, а потом выбрасывает то же самое исключение (выполнение операторов влияет на позицию).

Если исключений поймано не было, возвращает массив результатов.

Пример:

var input = 'foo';
// PEG: start = . 'oo'
seqnc(ch(), match('oo'))();
// == [ 'f', 'oo' ]

11. `choice`

Описание: Проверить, совпадает ли входная строка с текущей позиции с одним из перечисленных выражений. Если да — вернуть совпадение, если нет — сообщить о неудаче парсинга.

Синтаксис в грамматике: <выражение1> / <выражение2> / ...

Код:

function choice(/*f...*/) {
  var fs = arguments,
      missed = 0,
      my_e = null,
      on_miss = function(e) { my_e = e; missed = 1; };
  for (var fi = 0, fl = fs.length;
       fi < fl; fi++) {
    var res = safe(fs[fi], on_miss);
    if (!missed) return res;
    missed = 0;
  }
  throw my_e;
}

Принимает список операторов в качестве параметров (их может быть неограниченное количество, благодаря использованию arguments) — сохраняет его в переменной fs. Подготавливает функцию on_miss, которая устанавливает флаг missed в единицу.

Итерируясь по списку операторов, выполняет каждый в безопасном окружении с помощью функции safe, которая передаёт первое же перехваченное исключение в функцию on_miss, которая, в свою очередь, устанавливает флаг missed в единицу и сохраняет последнее исключение. Если исключения для текущего оператора не было выброшено (missed равен нулю), значит совпадение найдено и можно вернуть результат выполнения этого оператора. Сбрасывает флаг missed в ноль для следующей итерации цикла.

Если ни один из операторов не выполнился удачно, выбрасывает последнее исключение (внутренними средствами парсера, не приведёнными здесь (функция failed), в метаданных исключения были накоплены все не совпавшие варианты).

Пример:

var input = 'foo';
// PEG: start = . ('aa' / 'oo' / 'ee') .
seqnc(choice(ch(), match('aa'), match('oo'), match('ee')))();
// == [ 'f', 'oo' ]

12. `action`

Описание: Выполнить переданное выражение, но вместо совпадения вернуть результат выполнения JavaScript-кода. Если проверка на совпадение была неудачной или код вернул null, сообщить об ошибке парсинга.

Синтаксис в грамматике: <выражение> { <javascript-код> }

Код:

function action(f, code) {
  function inctx(function() {
    ppos = pos; var res;
    f(); res = code(cctx);
    if (res === null) { pos = ppos;
      failed(SOMETHING, NOTHING); }
    return res;
  });
}

Принимает оператор f и пользовательский код code. Всё тело оператора выполняется внутри собственном контексте a.k.a. области видимости (дочерней к той, из которой он был вызван) — этому способствует функция inctx (от in context).

Текущая позиция парсинга сохраняется как предыдущая: из пользовательского кода можно вызвать служебные функции, которые возвращают позицию, с которой был начат парсинг текущего оператора action (offset), номер строки (line) и колонки (column) для этой позиции или совпавший отрезок строки (text).

Затем выполняется оператор f (если он выбрасывает своё исключение MatchFailed, парсинг полностью прекращается). Возвращённое им значение не сохраняется. После него выполняется пользовательский код, принимая текущий уровень контекста cctx (в этой переменной хранятся именованные значения, доступные на текущем уровне контекста, а переменные внешних контекстов доступны по цепочке его прототипов), и если он вернул null, позиция парсинга возвращается в предыдущее состояние (выполнение операторов влияет на позицию) и с помощью функции failed выбрасывается исключение MatchFailed с сообщением, что ожидалось хотя бы что-то (маркер SOMETHING), а не обнаружилось ничего (маркер NOTHING).

Если код вернул некий результат, тот мирно возвращается из оператора.

Пример:

var input = 'foo';
// PEG: start = 'fo' (. { return offset(); })
seqnc(match('fo'), action(ch(), function() { return offset(); })();
// == [ 'fo', 2 ]

13. `pre`

Описание: Выполнить переданный код и вернуть пустую строку, если код вернул истину (или что угодно, что JavaScript посчитает за истину). Иначе сообщить об ошибке парсинга.

Синтаксис в грамматике: & { <javascript-код> }

Код:

function pre(code) {
  ppos = pos;
  return code(cctx) ? '' : failed(cc(), EOI);
}

Предварительно приравнивает глобальную предпозицию парсинга к текущей.

Принимает пользовательский код code. В виду того, что для выполнения этого кода не нужен никакой дополнительный внутрений контекст кроме того, в котором он уже находится, если находится вообще — код выполняется без обиняков, принимая в качестве параметра текущий уровень контекста cctx (в этом объекте хранятся именованные значения, доступные на текущем уровне контекста, а переменные внешних контекстов доступны по цепочке его прототипов).

Возвращает пустую строку если код вернул истинное значение; или сообщает о неудаче парсинга с пояснением, что ожидался текущий символ, а был обнаружен конец ввода (маркер EOI, End of Input), если значение было ложным.

Пример:

var input = 'foo';
// PEG: start = &{ return true; } 'foo'
seqnc(pre(function() { return true; }), match('foo'))();
// == [ '', 'foo' ]

14. `xpre`

Описание: Выполнить переданный код и вернуть пустую строку, если код вернул ложь (или что угодно, что JavaScript посчитает за ложь). Иначе сообщить об ошибке парсинга.

Синтаксис в грамматике: ! { <javascript-код> }

Код:

function xpre(code) {
  ppos = pos;
  return code(cctx) ? failed(cc(), EOI) : '';
}

Предварительно приравнивает глобальную предпозицию парсинга к текущей.

Возвращает пустую строку если код вернул ложное значение; или сообщает о неудаче парсинга с пояснением, что ожидался текущий символ, а был обнаружен конец ввода (маркер EOI, End of Input), если значение было истинным.

Пример:

var input = 'foo';
// PEG: start = !{ return false; } 'foo'
seqnc(xpre(function() { return false; }), match('foo'))();
// == [ '', 'foo' ]

15. `label`

Описание: Сохранить результат вычисления переданного выражения в текущем контексте под указанным именем.

Синтаксис в грамматике: <имя>:<выражение>

Код:

1
2
3

function label(lbl, f) {
  return cctx[lbl] = f();
}

В объекте cctx хранятся именованные значения, доступные на текущем уровне контекста, а переменные внешних контекстов доступны по цепочке его прототипов.

Записывает результат вычисления переданного оператора f в объект cctx под указанным именем lbl.

Пример:

var input = 'foo';
// PEG: start = a:. 'oo' { return a + 'bb'; }
action(seqnc(label('a', ch()), match('oo')),
       function { return a + 'bb' })();      // == 'fbb'

16. Правило

Описание: Именованное правило парсинга, позволяет ссылаться на данное правило из других правил, содержит неограниченное число выражений-операторов.

Синтаксис в грамматике: <имя_правила> = <выражения>

Код:

1
2
3

rules.<имя_правила> = function() {
  return (<код_корневого_оператора>)();
}

Содержимое любого правила в AST-дереве автоматически оборачивается в корневой оператор (если оно содержит одно выражение, то это оператор этого выражения, если несколько — оператор seqnc). Поэтому вызов правила эквивалентен вычислению и возвращению значения этого оператора.

Пример:

// PEG: space = " "
rules.space = function() { return (match(' '))(); }
// PEG: foo = . . .
rules.foo = function() { return (seqnc(ch(), ch(), ch()))(); }
// PEG: foo "bar" = . 'o'+
rules.foo = function() { return (as('bar',
                                    seqnc(ch(), some(match('o')))
                                   ))(); }
// input = 'foo'
rules.foo(); // == [ 'f', [ 'o', 'o' ] ]

17. `ref`

Описание: Используется для вызова указанного правила в данной позиции парсинга.

Синтаксис в грамматике: <имя_правила>

Код:

1	function ref = inctx;

Эквивалентно вызову корневого оператора правила в его собственном контексте, поэтому приравнивается фукнции inctx, которая при вызове оператора создаёт внутренний уровень контекста и присваивает его переменной cctx.

Пример:

var input = 'foo';
// PEG: start = fo_rule 'o'
//      fo_rule = 'fo'
rules.start = seqnc(ref(rules.fo_rule), match('o'));
rules.fo_rule = match('fo');
rules.start(); // == [ 'fo', 'o' ];

18. `as`

Описание: Выполнить правило под другим именем. Влияет только на вывод ошибки парсинга.

Синтаксис в грамматике: <имя-правила> "<алиас>" = <выражения>

Код:

function as(name, f) {
  alias = name; var res = f();
  alias = ''; return res;
}

На время выполнения оператора f (структура AST-дерева гарантирует, что это будет корневой оператор правила) подменяет имя текущего правила (глобальная переменная alias) на переданное, затем возвращает результат. Если во время выполнения оператора произошла ошибка парсинга, в описании этой ошибки будет содержаться указанное имя правила.

Пример:

var input = 'foo';
// PEG: start "blah" = 'bar'
as('blah', match('bar'))();
// MatchFailed: Expected blah, but 'f' found

Эпилог

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

И да, можешь погенерировать функциональных парсеров онлайн, если хочешь. А если тебя расстраивает факт черепашьей скорости моих функциональныx парсеров, я вовсе не против если ты поиграешься с оригинальной нефункциональной версией.

На сим прощаюсь, твой шаман.сэр.

Обширная предыстория

Структура парсера

Пояснения

Операторы

1. ch

2. match

3. re

4. text

5. maybe

6. some

7. any

8. and

9. not

10. seqnc

11. choice

12. action

13. pre

14. xpre

15. label

16. Правило

17. ref

18. as

Эпилог

1. `ch`

2. `match`

3. `re`

4. `text`

5. `maybe`

6. `some`

7. `any`

8. `and`

9. `not`

10. `seqnc`

11. `choice`

12. `action`

13. `pre`

14. `xpre`

15. `label`

17. `ref`

18. `as`