Pull to refresh

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

Reading time 2 min
Views 8.7K
Всем привет!

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

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

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

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

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

Также важно заметить, что peg.js-fn удачно проходит все тесты peg.js.

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

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

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

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

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

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

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

P.S. Все упоминания трансдьюсеров в этом посте употреблены исключительно для привлечения внимания и в качестве некоторой самоиронии. На самом деле никаких веских оснований связывать предложенный подход с ними я не имею, кроме того, что из существующих на данный момент терминов, для описанного подхода этот, возможно, подходит лучше всего.
Tags:
Hubs:
+10
Comments 7
Comments Comments 7

Articles