Генератор функциональных парсеров на JavaScript (с трансдьюсерами)

в 13:46, , рубрики: javascript, генерация парсеров, трансдьюсеры, функциональное программирование

Всем привет!

Увидел, что статья о трансдьюсерах на JavaScript стала вполне популярной и хотел отметить, что уже давно доступен генераторов парсеров на транзисторах^W трансдьюсерах. По крайней мере, очень на это похоже. У меня есть статья с подробным описанием на английском «Generating Functional Parsers» и, собственно, исходники.

Тут какие-то новые правила, постов-ссылок уже нет, просят всё обильно описывать — так что я подчинюсь и парой слов (разбавленных необходимой водой), расскажу, о чём это, а то могу ведь и не прав оказаться. Тем более русской версии статьи пока нет, да и скорее всего не будет. Одна надежда, что эта пройдёт.

Проект по ссылке выше — не идея сделать новый генератор парсеров, а скорее эксперимент, насколько идеальной читабельности парсера можно достичь, не сильно потеряв в скорости парсинга. На самом деле скорость была потеряна внушительно, признаюсь сразу, но по причине банальной — помимо трансдьюсеров, эта версия генерируемых парсеров основана на поимке и подавлении эксепшнов (при ошибке матчинга выбрасывается эксепшн, который по желанию перехватывают оборачивающие операторы). Во время экспериментирования о дырявости try/catch в популярных движках JS было искренее позабыто. Возможно, у вас будут советы по обходу этой проблемы.

Вот сравнение кода, сгенерированного pegjs в различных версиях (именно он был взят за основу и для создания альтернативы было практически полностью переписано ядро генерации по AST) и pegjs-fn, «дружелюбной версии». Это сравнение призвано убедить вас в удачном результате эксперимента, несмотря ни на что:

Сравнение кода сгенерированных парсеров

Результирующий код обильно спекулирует идеей отложенных функций (о которых я много писал на Хабре до осознанного самовыпиливания), a.k.a. частичным применением, из-за чего операторы парсинга (такие как and<code>, <code>or<code>, <code>sequence, choice) можно кобинировать в любых последовательностях.

Это позволяет из правила PEG:

start = . ('aa' / 'oo' / 'ee') .

Получить JavaScript-парсер с кодом:

rules.start = seqnc(ch(), choice(match('aa'), match('oo'), match('ee')), ch())

Конечно же, все операторы выполняются лениво, что и позволяет мне назвать их трансдьюсерами.

В статье по ссылке рассмотрен код каждого из операторов, с примерами.

Автор: shamansir

Источник

* - обязательные к заполнению поля