ES parsing tools (Re: Short Functions)

Claus Reinke claus.reinke at talk21.com
Wed Jun 1 06:56:01 PDT 2011


Hi Tom,

> I just wanted to provide a bit more context on our Ometa experiment: 
> our goal was to build an executable parser whose definition was as 
> close as possible to the BNF in the ES5 spec, which worked out fairly 
> well. The main purpose of the tool was to be able to quickly experiment 
> with syntax extensions, but it has never been our goal to have this tool 
> be a "production-quality" JS parser.

Yes, that is understood. Still, one doesn't want to be hampered by
unnecessary performance issues. I found your project only recently, 
so I made my own decision before I knew that there is an ES5 grammar 
for Ometa/JS. Ever since then, I've wondered how big an advantage 
Ometa's grammar optimizations give you over what I'm working on. 
Hence my surprise when Brendan described it as "slo-o-o-o-wwwww".

> For rapid prototyping, Ometa is a marvelous tool. I liked it a lot.
> Performance-wise, I have not pitched it against other JS parser 
> generators (I actually don't know of many others).

Thanks for confirming the general suitability. As for alternatives,
so far, I've found pegjs and jsparse (see my response to Kam).

> In terms of grammar validation, Ometa is fairly weak. We did at 
> one point get Alex Warth to implement an exclusive choice operator 
> "||", in addition to the standard PEG prioritized choice ("|" operator 
> in Ometa), as a tool to help us get more confidence in the grammar. 
> However, the implementation of that operator is naive and slow 
> (as testified here: <http://tinlizzie.org/ometa-js/#xor_perf>).

Ah, so that is a check-there-is-at-most-one-match operator,
which backtracks through every alternative even after a successful
match. If that was enabled by default, it would explain the impression
of Ometa being slo-o-o-o-wwwww, rather than slow but useable.

Still, from playing with esparser/index.html, I get the impression
that the implementation is drastically slower than I expected 
(compared to pegjs, and my extended version of jsparse). And 
that does seem to have a call to "ES5Parser.disableXORs()" in it. 

For reference, peg-0.6.1.js can self-parse in less than 30 seconds 
(using FF4 on a notebook), while esparser can't handle that code 
here.

If that first impression should be representative, it would be an 
obstacle to your work. From browsing esparser/bundle.js, there
are some very odd implementation decisions in Ometa/JS that 
are not likely to be good for performance (check the implementation 
of "Keyword", which has a method call and String construction for 
every single character, each of which is extracted via .at(idx), after 
several levels of function calls; or the implementation of _or, 
which uses exception handling to handle choices, in an inner loop).

Assuming that most of Ometa/JS is itself generated, you might
be able to tune the generator or its library code to get more 
useable performance, without having to change your own code.

Btw, doing my usual ES5/PEG check, I like that "||" alerts you to
some grammar problems (only when they occur, a dynamic rather
than static check) but you might still want to correct them (the 
"id \n : 1" example will not parse as expected). 

Claus

 


More information about the es-discuss mailing list