Как писать парсеры на JavaScript
…, а именно как писать LL парсеры для не очень сложных структур при помощи конструирования сложного парсера из более простых. Изредка возникает необходимость распарсить что то несложное, скажем некую XML-подобную структуру или какой нибудь data URL, и тогда обычно возникает либо простыня хитрого трудно читаемого кода либо зависимость от какой то ещё более сложной и хитрой библиотеки для парсинга. Здесь я собираюсь совместить несколько известных идей (какие то из них попадались на Хабре) и показать как можно просто и лаконично написать довольно сложные парсеры уложившись при этом в совсем немного строчек кода. Для примера я буду писать парсер XML-подобной структуры. И да, я не буду вставлять сюда картинку для привлечения внимания. В статье вообще картинок нет, поэтому читать будет трудно.Основная идеяОна в том, что каждый кусочек входного текста парсится отдельной функцией (назовём её «паттерном») и комбинируя эти функции можно получать более сложные функции которые смогут парсить более сложные тексты. Итак, паттерн — это такой объект у которого есть метод exec который и осуществляет парсинг. Этой функции указывают что и откуда парсить и она возвращает распарсенное и то место где парсинг закончился:
var digit = { exec: function (str, pos) { var chr = str.charAt (pos); if (chr >= »0» && chr <= "9") return { res: +chr, end: pos + 1}; } }; Теперь digit это паттерн парсящий цифры и его можно использовать так:
assert.deepEqual (digit.exec (»5», 0), { res: 5, end: 1 }); assert.deepEqual (digit.exec («Q», 0), void 0); Почему именно такой интерфейс? Потому что в JS есть встроенный класс RegExp с очень похожим интерфейсом. Для удобства введём класс Pattern (смотрите на него как на аналог RegExp) экземпляры которого и будут представлять собой эти паттерны:
function Pattern (exec) { this.exec = exec; } Затем введём несколько простых паттернов которые пригодятся практически в людом более-менее сложном парсере.
Простые паттерны Самый простой паттерн это txt — он парсит фиксированную наперёд заданную строку текста:
function txt (text) { return new Pattern (function (str, pos) { if (str.substr (pos, text.length) == text) return { res: text, end: pos + text.length }; }); } Применяется он так:
assert.deepEqual (txt («abc»).exec («abc», 0), { res: «abc», end: 3 }); assert.deepEqual (txt («abc»).exec («def», 0), void 0); Если бы в JS были конструкторы-по-умолчанию (как в C++), то запись txt («abc») можно было бы сократить до «abc» в контексте конструирования более сложного паттерна.
Затем введём его аналог для регулярных выражений и назовём его rgx:
function rgx (regexp) { return new Pattern (function (str, pos) { var m = regexp.exec (str.slice (pos)); if (m && m.index === 0) return { res: m[0], end: pos + m[0].length }; }); } Применяют его так:
assert.deepEqual (rgx (/\d+/).exec (»123», 0), { res:»123», end: 3 }); assert.deepEqual (rgx (/\d+/).exec («abc», 0), void 0); Опять же, если бы в JS были конструторы-по-умолчанию, то запись rgx (/abc/) можно было сократить до /abc/.
Паттерны-комбинаторы Теперь нужно ввести несколько паттернов которые комбинируют уже имеющиеся паттерны. Самый простой из таких «комбинаторов» это opt — он делает любой паттерн не обязательным, т.е. если исходный паттерн p не может распарсить текст, то opt (p) на этом же тексте скажет, что всё распарсилось, только результат парсинга пуст:
function opt (pattern) { return new Pattern (function (str, pos) { return pattern.exec (str, pos) || { res: void 0, end: pos }; }); } Пример использования:
assert.deepEqual (opt (txt («abc»)).exec («abc»), { res: «abc», end: 3 }); assert.deepEqual (opt (txt («abc»)).exec (»123»), { res: void 0, end: 0 }); Если бы в JS была возможна перегрузка операторов и конструкторы-по-умолчанию, то запись opt (p) можно было бы сократить до p || void 0 (это хорошо видно из того как реализован opt).
Следующий по сложности паттерн-комбинатор это exc — он парсит только то, что может распарсить первый паттерн и не может распарсить второй:
function exc (pattern, except) { return new Pattern (function (str, pos) { return! except.exec (str, pos) && pattern.exec (str, pos); }); } Если W (p) это множество текстов которые парсит паттерн p, то W (exc (p, q)) = W (p) \ W (q). Это удобно например когда нужно распарсить все большие буквы кроме буквы H:
var p = exc (rgx (/[A-Z]/), txt («H»));
assert.deepEqual (p.exec («R», 0), { res: «R», end: 1 }); assert.deepEqual (p.exec («H», 0), void 0); Если бы в JS была перегрузка операторов, то exc (p1, p2) можно было бы сократить до p1 — p2 или до ! p2 && p1 (для этого, правда, потребуется ввести паттерн-комбинатор all/and который будет работать как оператор &&).
Затем идёт паттерн-комбинатор any — он берёт несколько паттернов и конструирует новый, который парсит то, что парсит первый из данных паттернов. Можно сказать, что W (any (p1, p2, p3, …)) = W (p1) v W (p2) v W (p3) v…
function any (…patterns) { return new Pattern (function (str, pos) { for (var r, i = 0; i < patterns.length; i++) if (r = patterns[i].exec(str, pos)) return r; }); } Я воспользовался конструкцией ...patterns (harmony:rest_parameters), чтобы избежать корявого кода вроде [].slice.call(arguments, 0). Пример использования any:
var p = any (txt («abc»), txt («def»));
assert.deepEqual (p.exec («abc», 0), { res: «abc», end: 3 }); assert.deepEqual (p.exec («def», 0), { res: «def», end: 3 }); assert.deepEqual (p.exec («ABC», 0), void 0); Если бы в JS была перегрузка операторов, то any (p1, p2) можно было бы сократить до p1 || p2.
Следующий паттерн-комбинатор это seq — он последовательно парсит текст данной ему последовательностью паттернов и выдаёт массив результатов:
function seq (…patterns) { return new Pattern (function (str, pos) { var i, r, end = pos, res = [];
for (i = 0; i < patterns.length; i++) { r = patterns[i].exec(str, end); if (!r) return; res.push(r.res); end = r.end; }
return { res: res, end: end }; }); } Применяется он так:
var p = seq (txt («abc»), txt («def»));
assert.deepEqual (p.exec («abcdef»), { res: [«abc», «def»], end: 6 }); assert.deepEqual (p.exec («abcde7»), void 0); Если бы в JS была перегрузка операторов, то seq (p1, p2) можно было бы сократить до p1, p2 (перегружен оператор «запятая»).
Ну и наконец паттерн-комбинатор rep — он много раз применяет известный паттерн к тексту и выдаёт массив результатов. Как правило это применяется для парсинга неких однотипных конструкций разделённых скажем запятыми, поэтому rep принимает два аргумента: основной паттерн результаты которого нам интересны и разделяющий паттерн результаты которого отбрасываются:
function rep (pattern, separator) { var separated = ! separator? pattern: seq (separator, pattern).then (r => r[1]);
return new Pattern (function (str, pos) { var res = [], end = pos, r = pattern.exec (str, end);
while (r && r.end > end) { res.push (r.res); end = r.end; r = separated.exec (str, end); }
return { res: res, end: end }; }); } Можно добавить ещё пару параметров min и max которые будут контролировать сколько повторений допустимо. Здесь я воспользовался стрелочной функцией r => r[1] (harmony: arrow_functions), чтобы не писать function (z) { return z[1] }. Обратите внимание на то как rep сводится к seq при помощи Pattern#then (идея взята у Promise#then):
function Pattern (exec) { …
this.then = function (transform) { return new Pattern (function (str, pos) { var r = exec (str, pos); return r && { res: transform (r.res), end: r.end }; }); }; } Этот метод позволяет выводить из одного паттерна другой при помощи применения произвольного преобразования к результатам первого. Кстати, знатоки хаскеля, можно ли сказать что этот Pattern#then делает из паттерна монаду?
Ну, а rep применяется таким образом:
var p = rep (rgx (/\d+/), txt (»,»));
assert.deepEqual (p.exec (»1,23,456», 0), { res: [»1»,»23»,»456»], end: 8 }); assert.deepEqual (p.exec (»123ABC», 0), { res: [»123»], end: 3 }); assert.deepEqual (p.exec («ABC», 0), void 0); Какой либо внятной аналогии с перегрузкой операторов для rep мне в голову не приходит.
В итоге получается около 70 строчек на все эти rep/seq/any. На этом список паттернов-комбинаторов заканчивается и можно переходить собственно к конструированию паттерна распознающего XML-подобный текст.
Парсер XML-подобных текстов Ограничимся вот такими XML-подобными текстами:
var name = rgx (/[a-z]+/i).then (s => s.toLowerCase ()); var char = rgx (/[^»&]/i); var quoted = seq (txt ('»'), rep (char), txt ('»')).then (r => r[1].join ('')); var attr = seq (name, txt ('='), quoted).then (r => ({ name: r[0], value: r[2] })); Здесь attr парсит именованный атрибут со значением в виде строки, quoted — парсит строку в кавычках, char — парсит одну букву в строке (зачем это писать в виде отдельного паттерна? затем, что потом «научить» этот char парсить т.н. xml entities), ну, а name парсит имя атрибута (обратите внимание что парсит он как большие так и малые буквы, но возвращает распарсенное имя где все буквы малые). Применение attr выглядит так:
assert.deepEqual ( attr.exec ('title=«Chapter 1»', 0), { res: { name: «title», value: «Chapter 1» }, end: 17 }); Далее сконструируем паттерн умеющий парсить заголовок вида :
var wsp = rgx (/\s+/);
var attrs = rep (attr, wsp).then (r => { var m = {}; r.forEach (a => (m[a.name] = a.value)); return m; });
var header = seq (txt ('')).then (r => r[2]); Здесь wsp парсит один или несколько пробелов, attrs парсит один или несколько именованных атрибутов и возвращает распарсенное в виде словаря (rep возвратил бы массив пар имя-значение, но словарь удобнее, поэтому массив преобразуется в словарь внутри then), а header парсит собственно заголовок и возвращает только атрибуты заголовка в виде того самого словаря:
assert.deepEqual (
header.exec ('', 0),
{ res: { version:»1.0», encoding: «utf-8» }, end: … });
Теперь перейдём к распарсиванию конструкций вида
var text = rep (char).then (r => r.join ('')); var subnode = new Pattern ((str, pos) => node.exec (str, pos));
var node = seq ( txt ('<'), name, wsp, attrs, txt('>'), rep (any (text, subnode), opt (wsp)), txt ('')) .then (r => ({ name: r[1], attrs: r[3], nodes: r[5] })); Здесь text парсит текст внутри узла (node) и использует паттерн char который может быть научен распознавать xml entities, subnode парсит внутренний узел (фактически subnode = node) и node парсит узел с атрибутами и внутренними узлами. Зачем такое хитрое определение subnode? Если в определении node сослаться на node напрямую (как то так: node = seq (…, node, …)) то окажется, что на момент определения node эта переменная ещё пуста. Трюк с subnode позволяет убрать эту циклическую зависимость.
Осталось определить паттерн распознающий весь файл с заголовком:
var xml = seq (header, node).then (r => ({ root: r[1], attrs: r[0] })); Применение соответственно такое:
assert.deepEqual ( xml.exec (src), { attrs: { version: '1.0', encoding: 'utf-8' }, root: { name: 'book', attrs: { title: 'Book 1' }, nodes: [ { name: 'chapter', attrs: { title: 'Chapter 1' }, nodes: […] }, … ] } }); Здесь я вызываю Pattern#exec с одним аргументом и смысл этого в том, что я хочу распарсить строку с самого начала и убедиться, что она распарсилась до конца, ну, а поскольку она распарсилась до конца, то вернуть достаточно только распарсенное без указателя на то место где парсер остановился (я и так знаю, что это конец строки):
function Pattern (name, exec) { …
this.exec = function (str, pos) { var r = exec (str, pos || 0); return pos >= 0? r: ! r? null: r.end!= str.length? null: r.res; }; } Собственно весь парсер в 20 строчек (не забываем про те 70 которые реализуют rep, seq, any и пр.):
var name = rgx (/[a-z]+/i).then (s => s.toLowerCase ()); var char = rgx (/[^»&]/i); var quoted = seq (txt ('»'), rep (char), txt ('»')).then (r => r[1].join ('')); var attr = seq (name, txt ('='), quoted).then (r => ({ name: r[0], value: r[2] }));
var wsp = rgx (/\s+/);
var attrs = rep (attr, wsp).then (r => { var m = {}; r.forEach (a => (m[a.name] = a.value)); return m; });
var header = seq (txt ('')).then (r => r[2]);
var text = rep (char).then (r => r.join ('')); var subnode = new Pattern ((str, pos) => node.exec (str, pos));
var node = seq ( txt ('<'), name, wsp, attrs, txt('>'), rep (any (text, subnode), opt (wsp)), txt ('')) .then (r => ({ name: r[1], attrs: r[3], nodes: r[5] }));
var xml = seq (header, node).then (r => ({ root: r[1], attrs: r[0] })); Стоит отметить, что каждый var здесь строго соответствует одному правилу ABNF и потому если надо что то распарсить по описанию в RFC (а там любят ABNF), то перенос тех правил — дело механическое. Более того, поскольку сами правила ABNF (а также EBNF и PEG) строго формальны, то можно написать парсер этих правил и затем, вместо вызовов rep, seq и пр. писать что то такое:
var dataurl = new ABNF ('«data:» mime »;» attrs,»,» data', { mime: /[a-z]+\/[a-z]+/i, attrs: …, data: /.*/ }).then (r => ({ mime: r[1], attrs: r[3], data: r[5] })); И применять как обычно:
assert.deepEqual ( dataurl.exec ('data: text/plain; charset=«utf-8», how+are+you%3f'), { mime: «text/plain», attrs: { charset: «utf-8» }, data: «how are you?» }); Ещё немного буков Почему Pattern#exec возвращает null/undefined если распарсить ничего не удалось? Почему бы не бросать исключение? Если использовать исключения таким образом, то парсер станет медленнее раз в двадцать. Исключения хороши для исключительных случаев.
Описанный способ позволяет писать LL парсеры которые подходят не для всех целей. Например если надо распарсить XML вида
Также LL парсеры плохо подходят для разбора разнообразных синтаксических/математических выражений где есть операторы с разным приоритетом и т.п. LL парсер конечно можно написать, но он будет несколько запутан и будет работать медленно. LR парсер будет запутан сам по себе, но будет быстр. Поэтому такие выражения удобно парсить т.н. алгоритмом Пратта который неплохо объяснил Крокфорд (если эта ссылка у вас фиолетовая, то в парсерах вы наверно разбираетесь лучше меня и вам наверно было очень скучно читать всё это).
Надеюсь кому нибудь это пригодится. В своё время я писал парсеры разной степени корявости и описанный выше способ был для меня открытием.
