Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 53
Не совсем понял один момент. То, что вы называете «XML-подобным» текстом, есть самый что ни на есть обычный XML-документ. Какова была задача, что не было возможности воспользоваться встроенными средствами и пришлось реализовывать парсер самостоятельно?
«XML-подобный» потому что в нём нет конструкций вроде <a:b ...>, нет xml entities, не учитываются теги вида <abc .../> и т.п. А задача была показать применение описанного метода на примере XML как хорошо известного формата. А на практике полезнее писать парсер для, скажем, заголовка WWW-Authenticate, но если бы я привёл пример такого парсера, то мало бы кто понял, что там вообще парсится.
Если вам просто нужен парсер и нет желания упражняться в его написании, то лучше воспользоваться генератором. Тем более, что часто можно найти готовую грамматику. Ссылка на один из генераторов. Кстати, я им пользовался не совсем по прямому назначению. Обычно парсеры используют для чтения неких документов. У меня же было формализованное описание некого API, описав грамматику я получил сначала парсер для описания, а при помощи парсера получил генератор кода для работы с API.
Автоматические сгенерированные парсеры весьма объёмны. Так например упомянутый вами PEG показывает пример как из простейшей грамматики из 5-ти правил генерируется парсер на 400 строк. Если встроить такое в свой код (например в свою библиотеку) — не проблема, то наверно это и вправду рабочее решение. Генераторы парсеров имеют и другую проблему: однажды сгенерировав код парсера, поменять его сложно — нужно будет взять оригинальное описание грамматики, изменить её, применить оригинальный генератор и заменить сгенерированное. Оба этих ограничения наводят меня на мысль, что генераторы парсеров уместны на серверах Node.
Если в цикле развертывания есть этап компиляции (что довольно часто встречается для JS и не только для серверного), то генерация парсера из грамматики вообще не проблема. Считаем исходником грамматику и все.
А по скорости не пробовали сравнить? Объём кода всё-таки не главное.
Автоматические сгенерированные парсеры весьма объёмны.
ваша статья тоже не маленькая. :) серьезно, классно, что вы так подробно объясняете причины выбора тех или иных решений и иллюстрируете суть простыми примерами реализации. практически, академичная статья. единственное, что на практике это использовать вряд-ли получится. для «промышленного» применения, при генерации js-парсеров, нужно учитывать еще ряд крайне важных «потребительских» характеристик, без которых, как говорят в народе, такая «простота хуже воровства».
во-первых, парсер обязан генерировать адекватные сообщения об ошибках, с классификацией проблем и четкой локализацией мест и причин их возникновения. обычное дело, когда код, связанный с анализом ошибок во входных данных и выводом соответствующих сообщений, занимает в объеме больше, нежели собственно код парсинга, как такового. важность момента может быть не очевидной на начальных этапах, но опыт будет дорого стоить. например, можно вспомнить как из стека BEM, после нескольких человеко-лет вложений в разработку и внедрение, был выкинут пресловутый bemhtml, вместе с его умопомрачительным DSL.
во вторых, парсер должен быть алгоритмически простым (в смысле «O») и быстрым. пусть
char — парсит одну букву в строке. это универсально. но когда парсинг каждой буквы приводит к созданию объектов и вызову пачки методов, я сомневаюсь, что такая архитектура позволит достичь производительности сколь-нибудь выше плинтуса. именно поэтому «академические» реализации встречаются только в учебниках, а на практике грамматика компиляется в хитросплетенную, развесистую и только машине понятную «лапшу». это не прихоть. x4 в объеме кода приятнее, нежели x4 по потребляемой памяти или процессору.в третьих, нужна возможность парсить асинхронно. в js, вы очень быстро с этим столкнетесь, поскольку асинхронность очень распространена в js, а асинхронный код обладает «вирусным» эффектом (если на низком уровне появляется асинхронный код, то и весь высокоуровневый код должен быть асинхронным). ничего страшного, просто решение этой задачи усложняет решение двух предыдущих на порядок.
Вы пытаетесь применить моё решение для написания простых парсеров в рамках маленьких js библиотек размером в несколько тысяч строк для решения больших и сложных задач распарсивания очень сложных и больших текстов где важна производительность и сообщения об ошибках и потому неизбежно обнаруживаете указанные вами недостатки. Однако всё это верно лишь для больших и сложных парсеров.
Моя же цель была показать как можно распарсить что то простое малым количеством простого кода. Вот допустим вы пишете js библиотеку которая должна оставаться в рамках 5-6 тысяч строк и эта библиотека должна парсить что то небольшое из HTTP ответов, скажем те же WWW-Authenticate заголовки. Тут есть два варианта: написать парсер самому или использовать хороший генератор парсеров. Во втором случае вы получаете кучу сложностей в виде проблем с лицензионным соглашением (можно ли использовать тот генератор в рамках вашей библиотеки?), тысячми строк нечитаемого сгенерированного кода, невозможностью исправить этот код добавив что то новое в парсер (нужно ведь заново генерить весь парсер), и такие сомнительные плюсы как скорость (какая разница будет этот парсер работать за 1 мс или за 10 мс если HTTP запрос идёт 100 мс и возникает редко?) и хорошие сообщения об ошибках (их всё равно никто не будет читать в описанном случае). Самописный же парсер лишён этих недостатков (ибо занимает меньше 100 строчек), хотя и не обладает ненужной скоростью и ненужными сообщениями об ошибках.
Моя же цель была показать как можно распарсить что то простое малым количеством простого кода. Вот допустим вы пишете js библиотеку которая должна оставаться в рамках 5-6 тысяч строк и эта библиотека должна парсить что то небольшое из HTTP ответов, скажем те же WWW-Authenticate заголовки. Тут есть два варианта: написать парсер самому или использовать хороший генератор парсеров. Во втором случае вы получаете кучу сложностей в виде проблем с лицензионным соглашением (можно ли использовать тот генератор в рамках вашей библиотеки?), тысячми строк нечитаемого сгенерированного кода, невозможностью исправить этот код добавив что то новое в парсер (нужно ведь заново генерить весь парсер), и такие сомнительные плюсы как скорость (какая разница будет этот парсер работать за 1 мс или за 10 мс если HTTP запрос идёт 100 мс и возникает редко?) и хорошие сообщения об ошибках (их всё равно никто не будет читать в описанном случае). Самописный же парсер лишён этих недостатков (ибо занимает меньше 100 строчек), хотя и не обладает ненужной скоростью и ненужными сообщениями об ошибках.
> в третьих, нужна возможность парсить асинхронно
Очень интересно, как из синхронного решения вы планируете получить асинхронное. Очень крутая фраза :)
> можно вспомнить как из стека BEM, после нескольких человеко-лет вложений в разработку и внедрение, был выкинут пресловутый bemhtml
Оо, чего только не узнаешь. А bemhtml@2 наверное возник из ниоткуда? А bemtree?
Очень интересно, как из синхронного решения вы планируете получить асинхронное. Очень крутая фраза :)
> можно вспомнить как из стека BEM, после нескольких человеко-лет вложений в разработку и внедрение, был выкинут пресловутый bemhtml
Оо, чего только не узнаешь. А bemhtml@2 наверное возник из ниоткуда? А bemtree?
Есть еще JS/CC, но он мне не особенно понравился. Там генерируется множество таблиц переходов от чего код разбухает значительно. PEG понравился в разы больше и для разбора небольших простых правил самое оно.
Очень интересует тема грамматик, если на хабре впредь будут подобные посты, то я с интересом их буду читать.
У меня есть простой парсер, основанный на идее комбинаторов. На гитхабе, в виде npm-пакета: StreetStrider/str-reader. Если у кого-то есть интерес поревьюить/покритиковать, то это можно сделать (на гитхабе или здесь в лс).
У меня есть простой парсер, основанный на идее комбинаторов. На гитхабе, в виде npm-пакета: StreetStrider/str-reader. Если у кого-то есть интерес поревьюить/покритиковать, то это можно сделать (на гитхабе или здесь в лс).
Я думал о том, чтобы написать генератор ассемблеро-подобных (очень быстрых, но нечитаемых, возможно с использованием «use asm») парсеров который бы парсил описание грамматики на ABNF/EBNF/PEG и выдавал ассемблеро-подобный код на JS — этакий компилятор ABNF, но пока ничего толкового не придумал. Как придумаю — напишу. Возможно придётся утащить пару идей у peg.js :)
Использовал Jison. Шикарнейшая вещь.
Для не очень сложных грамматик (no-backtrack-PEG, соответственно это что-то вроде LL(1)), (и не в продакшене, если что) лично мне нравится вот эта штука: www.bayfronttechnologies.com/mc_workshop.html.
> Как писать парсеры на JavaScript
Не писать :)
То что у вас получилось, кстати, похоже на красивый синтаксический сахар для метода рекурсивного спуска.
Я похожий интерфейс в своё время пилил на Lua для packrat-парсера. Там получилось особенно хорошо, потому что в Lua можно не писать скобки при вызове функции с литералом в качестве параметра, из-за чего код получается примерно таким:
Полный код примера использования:
Не писать :)
То что у вас получилось, кстати, похоже на красивый синтаксический сахар для метода рекурсивного спуска.
Я похожий интерфейс в своё время пилил на Lua для packrat-парсера. Там получилось особенно хорошо, потому что в Lua можно не писать скобки при вызове функции с литералом в качестве параметра, из-за чего код получается примерно таким:
local digit = peg.R"09"
Полный код примера использования:
--- калькулятор
local function accum(u,op,v)
if op=="+" then return u+v
elseif op=="-" then return u-v
elseif op=="*" then return u*v
elseif op=="/" then return u/v
end
end
local space = peg.S" \n\t":star()
local digit = peg.R"09"
local sign = peg.S"+-"
local unsigned = digit:plus()
local number = (sign^{0,1}*unsigned*("."*unsigned)^{0,1}):C()/tonumber*space
local Open = "(" * space
local Close = ")" * space
local mulop = peg.S"/*":C() * space
local sumop = peg.S"-+":C() * space
-- необходимо сделать Fake(), т.к. тут рекурсия value -> sum -> mul -> value
-- реальная формула для value доопределяется тремя строками ниже
local value = peg.Fake()
local mul = (value * (mulop*value):Cg():star()):Cf(accum)
local sum = (mul * (sumop*mul):Cg():star()):Cf(accum)
value:define(number + Open*sum*Close)
local expression = sum * peg.eof
--print(expression"3 + 5*9 / (1+1) - 12 + 0.012")
print(expression(io.read()))
То что у вас получилось, кстати, похоже на красивый синтаксический сахар для метода рекурсивного спуска.
Так и есть. Эту статью можно было бы назвать «как написать парсер для XML/dataURL/… и уложиться в 100 строк,» что весьма актуально для либ запускаемых в браузере где размер имеет значение. Во всех остальных случаях лучше наверно будет держать описание грамматики в отдельном файле и во время билда автоматически генерить парсер известной и проверенной тулзой. Впрочем даже здесь есть исключения — GCC вон перешёл на самопальный парсер и уж их то уличить в незнании основ парсинга точно нельзя.
Не OMeta ли то, что вы описываете?
Уж слишком часто встречается фраза «Если бы в JS была перегрузка операторов» — fake-operator-overloading
Я JS только учусь и статья сложная для меня, поэтому прошу объяснить, кому несложно: чем вышенаписанная простыня лучше DOMParser, который справляется с XML и HTML?
Ответ на вопрос. Если стоит вопрос почему стоит писать парсеры? То любой инструмент вроде Bem, Jade, React.JS, Emmet не обходится без парсинга. Поэтому парсить надо уметь, чтобы при случае применить свое знание.
Впрочем, все стоит помнить простое правило: Пользуйтесь уже проверенными, готовыми, покрытых тестами парсерами.
Впрочем, все стоит помнить простое правило: Пользуйтесь уже проверенными, готовыми, покрытых тестами парсерами.
DOMParser лучше для XML. Самопальные парсеры хороши только когда надо распарсить что то очень необычное.
Хотя и тут есть подводный камень: DOMParser не поддерживается в IE 8.
Ну для необычного я использую RegExp. Мне кажется оно проще.
Ну да ладно, я просто до этого не дорос. Не буду больше лезть во взрослую песочницу )
Спасибо!
Ну да ладно, я просто до этого не дорос. Не буду больше лезть во взрослую песочницу )
Спасибо!
Для совсем простых текстов сойдёт и RegExp. Так, например, чтобы распарсить URI на составляющие его части (scheme, user, host, port, path, query, hash) достаточно регулярки. Но что то с повторяющимися структурами (например Data URL) уже не выйдет распарсить регуляркой. Попробуйте написать регулярку для data URL вида:
data:text/plain;charset=«utf-8»;sometag=123;anothertag=abc,qwerty
Хочется написать что то такое:
^data:(\w+/\w+)(;\w+=\w+)*,.*$
Однако вы обнаружите, что (;\w+=\w+)* запоминает лишь последний атрибут вида abc=def, а вовсе не массив атрибутов, как хотелось бы. И эта проблема нерешаема в RegExp. В таких случаях нужен парсер.
Ещё один типичный случай это когда надо распарсить XML-подобную стркутуру где есть вложенные самоподобные структуры. Скажем как распарсить вот такое выражение со скобками:
(1, 2, (4, 5, (6), 7, (8), 9), 0)
Регулярки здесь не помогут, а вот LL парсер с этим легко справится.
data:text/plain;charset=«utf-8»;sometag=123;anothertag=abc,qwerty
Хочется написать что то такое:
^data:(\w+/\w+)(;\w+=\w+)*,.*$
Однако вы обнаружите, что (;\w+=\w+)* запоминает лишь последний атрибут вида abc=def, а вовсе не массив атрибутов, как хотелось бы. И эта проблема нерешаема в RegExp. В таких случаях нужен парсер.
Ещё один типичный случай это когда надо распарсить XML-подобную стркутуру где есть вложенные самоподобные структуры. Скажем как распарсить вот такое выражение со скобками:
(1, 2, (4, 5, (6), 7, (8), 9), 0)
Регулярки здесь не помогут, а вот LL парсер с этим легко справится.
Ясно. Спасибо!
Регулярки здесь не помогутНу, это смотря какие регулярки! Не знаю что умеет RegExp на Javascript, а на Perl это делается например так:
use Data::Dumper;
"(1, 2, (4, 5, (6), 7, (8), 9), 0)" =~
/(?{@s=();$r=[]})(\((?{local @s=(@s,$r);local $r=[];push @{$s[-1]},$r})(?:(\d), (?{push $r,$^N})|(?1), )*(\d)(?{push $r,$^N;$r=pop @s})\))/ms;
print Dumper @{$r};
$VAR1 = [
'1',
'2',
[
'4',
'5',
[
'6'
],
'7',
[
'8'
],
'9'
],
'0'
];
При желании это регулярное выражение можно записать более читабельно:"(1, 2, (4, 5, (6), 7, (8), 9), 0)" =~ /
(?{ @s=(); $r=[]; })
(
\( (?{
local @s = (@s, $r);
local $r = [];
push $s[-1], $r;
})
(?:
(\d),\s (?{ push $r, $^N })
| (?1),\s
)*
(\d) (?{ push $r, $^N })
\) (?{ $r = pop @s })
)
/xms;
Это не регулярка, а смесь перла и регулярок. Впрочем топик не о перле, а о JS и там такое сделать не получится.
Да нет, должно получиться, только синтаксис немного другой, вообще в JS regexp перлоподобный.
Тут другой вопрос, что стоило бы подсчитать, как правильно кто-то упомянул выше, что эффективнее по скорости, т.к. некоторые regexp очень нагружают процессор при неправильном использовании.
Тут другой вопрос, что стоило бы подсчитать, как правильно кто-то упомянул выше, что эффективнее по скорости, т.к. некоторые regexp очень нагружают процессор при неправильном использовании.
Буду очень удивлён если обнаружится, что в JS можно делать что то подобное., а с этим JS я уже лет десять знаком. По сравнению с методом парсинга который я описал любая регулярка работает за пренебрежимо малое время.
Про то что некоторые регулярки нагружают процессор хорошо написано тут: swtch.com/~rsc/regexp/regexp1.html Но это проблема не регулярок, а их реализации, причём в перле, как отмечает автор указанной статьи, они (были) реализованы как раз медленно.
Про то что некоторые регулярки нагружают процессор хорошо написано тут: swtch.com/~rsc/regexp/regexp1.html Но это проблема не регулярок, а их реализации, причём в перле, как отмечает автор указанной статьи, они (были) реализованы как раз медленно.
И эта проблема нерешаема в RegExp. В таких случаях нужен парсер.
Одна регулярка не поможет. А две — вполне.
Если бы в JS были конструкторы-по-умолчанию (как в C++), то запись txt(«abc») можно было бы сократить до «abc» в контексте конструирования более сложного паттерна.
А что мешает опционально расширять прототип String/RegExp etc? Раз уж извращаться, то по полной ;)
Например:
String.prototype.parse = function (str, pos) {
if (str.substr(pos, this.length) == this)
return { res: this, end: pos + this.length };
};
RegExp.prototype.parse = function(str, pos) {
var m = this.exec(str.substr(pos));
if (m && m.index === pos)
return { res: m[0], end: pos + m[0].length };
};
assert.deepEqual("abc".parse("abc", 0), { res: "abc", end: 3 });
assert.deepEqual(/\d+/.parse("123", 0), { res: "123", end: 3 });
Такой способ не позволит комбинировать парсеры и получать более сложные парсеры. Например из «abc» и /\d+/ я могу получить rep(rgx(/\d+/), txt(«abc»)) — парсер который распознаёт чередование «abc» и цифр. Если же у меня есть методы parse которые вы написали, то они никак не помогут сконструировать аналог этого rep.
Почему же? Просто вместо exec везде используйте parse (или другой метод, так как exec занят у RegExp).
А, я понял. Вы хотите переименовать exec в parse и вмонтировать этот parse прямо в String и RegExp чтобы они стали очень похожи на Pattern. У этого подхода есть небольшая проблема. Что если я захочу иметь два режима работы parse/exec:
p.exec(str, pos) возвращает (res, end)
p.exec(str) возвращает (res) и полагает, что pos = 0, а также проверяет что end = str.length
Если exec/parse вмонтирован в String и RegExp, то придётся дописать этот второй режим к каждому.
p.exec(str, pos) возвращает (res, end)
p.exec(str) возвращает (res) и полагает, что pos = 0, а также проверяет что end = str.length
Если exec/parse вмонтирован в String и RegExp, то придётся дописать этот второй режим к каждому.
Да, верно, это я и предлагал :)
Описанная проблема тоже решаема, можно сделать фабрику parse, как то так:
Описанная проблема тоже решаема, можно сделать фабрику parse, как то так:
var createParse = function(fn){
return function(str, pos){
if (arguments.length == 1)
pos = 0;
var res = fn.call(this, str, pos);
if (res && arguments.length == 1)
res = res.res.length == res.end ? res.res : undefined;
return res;
};
};
String.prototype.parse = createParse(function (str, pos) {
if (str.substr(pos, this.length) == this)
return { res: this, end: pos + this.length };
});
Интересная статья, интересные комментарии. Спасибо!
Кстати, можно использовать существующие инструменты для создания парсеров, например JavaCC, и скомпилировать полученный Java код в JavaScript с помощью GWT. Последние версии JavaCC поддерживают компиляцию себя в JavaScript.
regexp.exec(str.slice(pos))
а в данном случае не произойдет копирование части строки?
в принципе строки менять нельзя, так что теоретически возможна работа slice без копирования…
а за чем вы делаете так
а не так
?
И еще надо не забывать регекспы начинать писать с ^
спасибо за статью, метод then очень понравился
var char = rgx(/[^"&]/i);
rep(char).then(r => r.join(''))
а не так
rgx(/^[^"&]*/i)
?
И еще надо не забывать регекспы начинать писать с ^
спасибо за статью, метод then очень понравился
В этом случае можно парсить в 2 прохода: на первом генерировать массив токенов, которыми будут текст и теги (открывающий, закрывающий, самозакрывающийся), а на втором строить дерево.<book attr1="..." attr2="..." очень много атрибутов ???
То в том месте где стоит ??? может оказаться как /> так и просто >. Теперь если LL парсер пытался всё это распарсить как <book ...> а на месте ??? оказался />, то парсер отбросит всё то что он так долго парсил и начнёт заново в предположении, что это <book .../>
При чем на втором проходе можно применять те же Pattern, opt, exc, any, seq, rep, изменятся только терминальные методы
Может кому-то пригодится. Сделал на основе идей из этой статьи библиотеку парсер-комбинаторов: nano parser. В ней есть возможность кеширования и парсинга масива строк (что актуально для использования с шаблонными литералами из ES 2015)
Успешно применил библиотеку для создания строкового jsx: es6x
Успешно применил библиотеку для создания строкового jsx: es6x
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как писать парсеры на JavaScript