JavaScript functional parser generator (with transducers)


I saw that the article on JavaScript transducers became quite popular and wanted to note that a parser generator for ^ W transducers has been available for a long time. At least that's very similar. I have an article with a detailed description in English " Generating Functional Parsers " and, in fact, the source code .

There are some new rules, there are no links anymore, they are asking me to describe everything abundantly - so I will obey a couple of words (diluted with the necessary water), I’ll tell you what it is about, otherwise I may not be right. Moreover, there is no Russian version of the article, and most likely will not. One hope that this will pass.

The project using the link above is not an idea to create a new parser generator, but rather an experiment on how perfect parser readability can be achieved without losing much parsing speed. In fact, the speed was impressive, I admit right away, but due to the banal one - in addition to transducers, this version of the generated parsers is based on the capture and suppression of execution (if a match fails, an execution is thrown, which is optionally intercepted by the wrapping operators). During experimentation about try / catch leakages in popular JS engines, it was sincerely forgotten. You may have tips to work around this problem.

Here is a comparison of the code generated by peg.jsin various versions (it was he who was taken as the basis and to create an alternative the kernel of the generation according to AST was almost completely rewritten) and peg.js-fn , the “friendly version”. This comparison is designed to convince you of a successful experiment, no matter what:

Comparing the code of generated parsers

It is also important to note that peg.js-fn passes all peg.js tests successfully .

The resulting code is abundantly speculating the idea of deferred function (which I wrote a lot Habré to deliberate samovypilivaniya), aka partial application, which is why operators parsing (such as and, or, sequence, choice) can kobinirovat in any sequence.

This allows from the PEG rule:

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

Get JavaScript parser with code:

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

Of course, all the operators are executed lazily, which allows me to call them transducers.

The article uses the link to consider the code of each of the operators, with examples.

PS All references to transducers in this post are used solely to attract attention and as a kind of self-irony. In fact, I have no good reason to associate the proposed approach with them, except that of the currently existing terms, this approach is probably best suited for the described approach .

Also popular now: