PEG.js - parser generator for JavaScript

http://pegjs.majda.cz/

by dmajda • 16 years ago

74 43 16 years ago

pegjs.majda.cz

raganwald• 16 years ago

Are there PEGs available for languages like Javascript? Given recent discussion of Perl being undecidable, I assume there isn't one for Perl. Has anyone tackled such a thing for Ruby?

Update: Thanks for the links! That being said, I didn't mean parsers written in Javascript or Ruby, I mean PEGs or CFGs that parse Javascript and/or Ruby programs :-)

ErrantX2• 16 years ago

http://treetop.rubyforge.org/

Im writing a programming language in Ruby at the moment - and after playing with that for a few days I've gone back to "hand coded lexer plus Racc for grammar". It's probably personal preference but I find that a little more tunable.

dmajda5• 16 years ago

What exactly you didn't like?

moserware• 16 years ago

You might look at OMeta/JS: http://tinlizzie.org/ometa-js/#JavaScript_Compiler

OMeta is based upon PEGs and is worth a look because it has some great meta-meta ideas from the 60's that were ignored.

(Also, there are several ports of OMeta to other languages)

scythe• 16 years ago

They're native in Perl 6, and people above have linked to libraries for Lua and Clojure. I think there's a library for Python as well somewhere or other.

Also peg/leg for C is intended (iirc) as a direct competitor to flex/bison et al.

dmajda5• 16 years ago

ECMAScript 5 PEG parser: http://boshi.inimino.org/3box/PEG/build/ES5.html

(Hmm, I must definitely try to port it to PEG.js :-)

As for Ruby, I am not sure if it is even possible to create a PEG grammar. Its lexer and parser are heavily interconnected and there is a lot of state involved. If the grammar will be created, I don't think it would be pretty.

patrickg• 16 years ago

I love LPEG for Lua. It usually takes me some time to write a decent grammar, but once it works it is rather straightforward to read it. (http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html)

Now seeing this for javascript makes me think if I should actually do more work with js.

richard_lyman• 16 years ago

Amen on the easy to read part. I'm the author of clj-peg ( http://www.lithinos.com/clj-peg/ ), and the main reason I wanted to write it was to have grammars that were human readable.

allyt• 16 years ago

I'm really interested in human-readable grammars. Thanks for your work.

euroclydon3• 16 years ago

I'm confused about the grammar example.

How does: multiplicative : primary "* " multiplicative { return $1 * $3; }

return the product of two integers?

mbrubeck2• 16 years ago

HN formatting messed up your asterisks. The whole rule is:

    multiplicative    : primary "*" multiplicative { return $1 * $3; }
                      / primary

"primary" refers to another rule in the grammar, which is defined as integer or a parenthesized expression. This snippet defines "multiplicative", which is either a primary, or a primary followed by an asterisk followed by another multiplicative. (This recursively expands to allow any number of primaries, separated by asterisks.)

The value of the multiplicative expression is the value of the first term times the value of the third term. (The second term is just the literal string "*".)

barrkel7• 16 years ago

On the face of it, however, the grammar is problematic. There's a reason it uses "additive", "multiplicative" and "primary" rather than a more traditional expression, term and factor: by using commutative operators like + and multiply, and leaving out - and / it disguises the fact that the grammar is actually evaluating the expression from right to left, rather than the expected order of left to right.

euroclydon3• 16 years ago

Thanks, what I don't get from reading the grammar is how, as you say, multiplicative is either a primary or primary followed by a multiplicative. Clearly I understand that it needs to be defined this way, but is that either part just inherit to PEG or this implementation or what, b/c I don't get it form the syntax?

euroclydon3• 16 years ago

btw, how did you escape that asterisk in quotes?

scott_s2• 16 years ago

I had to do some digging for myself to verify that, yes, PEGs are a recent concept distinct from the kind of grammars I'm already familiar with. See Bryan Ford's paper, Parsing Expression Grammars: A Recognition-Based Syntactic Foundation from PoPL 2004: http://portal.acm.org/citation.cfm?id=964001.964011

barrkel7• 16 years ago

Memoization to get linear performance out of backtracking, which is exponential without it, is certainly a nice sleight of hand, but I wouldn't be under any illusions that the constant factor is competitive with say an LALR recognizer. Also, with a scheme that maps so closely to recursive descent, it's easy to miss what amount to grammar ambiguities, where nested productions preferentially eat tokens that may be in the follow set (i.e. the if/else problem).

cynicalkane9• 16 years ago

PEGs don't have grammar ambiguities. Every PEG is deterministic.

Grammar ambiguities are resolved by ordered choice. If there are two ways to parse something, the first way will be tried first. If it succeeds, the ordered choice short-circuits and the second way is ignored. So you can resolve, say, the classic dangling else problem by ordering your choices correctly.

silentbicycle2• 16 years ago

There's a really good VM-based PEG parsing system called LPEG (http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html). Paper: http://www.inf.puc-rio.br/~roberto/docs/peg.pdf

It's for Lua, but there isn't anything in the VM design that requires Lua per se - porting it to another language's C API wouldn't be difficult. In my experience, LPEG has been quite easy to use for the sort of tasks one would normally apply regular expressions to (and then some, as it handles recursive structures far better), it's quite fast, and it's easy to tune incrementally. In my (not yet ready for release) Lua/LPEG webserver, I'm handling 1000+ requests per second in about 2MB ram total* , so LPEG's design has tamed the usual space issues caused by PEG memoization.

* Only a tiny amount of that time is due to request parsing, it's mostly because I'm still working the kinks out of the event loop.

One strike against it is that there isn't a whole lot of casual documentation, though the documentation that does exist (the research paper and a library reference) is quite thorough. Also, it takes advantage of Lua's operator overloading to make the grammars concise, which takes getting used to. Still, having it so thoroughly integrated into the language is extremely convenient, and it's quite a bit more expressive than regular expressions.

Also, here's a link to the PEG paper on the author's site, rather than behind the ACM's paywall: http://www.bford.info/pub/lang/peg.pdf . Gotta love the ACM.

grayrest• 16 years ago

There are a couple other parser generators for JS:

* http://zaa.ch/2k - Jison

* http://inimino.org/~inimino/blog/peg_first_release - another Packrat (has an es5 parser as an example)

Plus a few more that work but produce generated code that's too slow to be useful.

mnemonik• 16 years ago

Worth noting that, last I heard, CoffeeScript is using Zaach's Jison: http://zaa.ch/2o

cousin_it• 16 years ago

A parser generator? Why oh why? It sounds so 80s. JavaScript is strong enough to express parser combinators, e.g. see Chris Double's implementation (also based on the PEG formalism):

http://www.bluishcoder.co.nz/2007/10/javascript-parser-combi...

I did the same thing in ActionScript. It's easy and fun.

dmajda5• 16 years ago

I believe that the classical generated parser has generally better performance potential - there is less function calling, less string passing (but this may be avoided easily in combinators too) and more opportunity for optimalization if you have the whole grammar AST in hand.

doublec• 16 years ago

It was pointed out to me that my git repository hosting this code was down. I've now moved it to github if anyone was looking for it:

http://github.com/doublec/jsparse

PEG.js - parser generator for JavaScript

Related Stories