6 ms·

PEG.js - parser generator for JavaScript

74 points by dmajda 17y ago

raganwald 17y 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 :-)
- ErrantX 17y ago
  http://treetop.rubyforge.org/ 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.
  - dmajda 17y ago
    What exactly you didn't like?
    - ErrantX 17y ago
      Just personal preference: I prefer the grammar structure for parsers like Racc
- moserware 17y ago
  You might look at OMeta/JS: http://tinlizzie.org/ometa-js/#JavaScript_Compiler 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 17y 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.
- dmajda 17y ago
  ECMAScript 5 PEG parser: http://boshi.inimino.org/3box/PEG/build/ES5.html 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 17y 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 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 17y ago
  Amen on the easy to read part. I'm the author of clj-peg ( http://www.lithinos.com/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 17y ago
    I'm really interested in human-readable grammars. Thanks for your work.
euroclydon 17y ago
I'm confused about the grammar example. How does: multiplicative : primary "* " multiplicative { return $1 * $3; } return the product of two integers?
- mbrubeck 17y 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 "*".)
  - euroclydon 17y 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?
    - mbrubeck 17y ago
      The "/" at the start of the second line is a choice operator. For example, this is how you would define a term a that can match either b or c: a: b / c (The asterisks in my post were escaped because they were in a code block, or because there were not two of them in the same line.)
  - euroclydon 17y ago
    btw, how did you escape that asterisk in quotes?
  - barrkel 17y ago
scott_s 17y 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 http://portal.acm.org/citation.cfm?id=964001.964011
- barrkel 17y 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).
  - cynicalkane 17y 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.
    - silentbicycle 17y ago
      Right, and PEGs only have one level of backtracking, so you don't have potentially massive slowdown due to backtracking several levels and re-trying everything along the way. While the backtracking behavior is different, choice order affects PEG rules similarly to Prolog.
    - barrkel 17y ago
      I know all of that. My point is that the if/else problem really is an ambiguity (i.e. it is a language bug, not just a problem you have to get around in parsing), and problems similar to it crop up when your tool doesn't alert you to first/follow conflicts, in LL(1) parlance. That PEGs encode the implementation strategy inside the declarative grammar is a flaw, in my opinion, not a benefit.
grayrest 17y ago
There are a couple other parser generators for JS: * http://zaa.ch/2k http://zaa.ch/2k - Jison * http://inimino.org/~inimino/blog/peg_first_release 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 17y ago
  Worth noting that, last I heard, CoffeeScript is using Zaach's Jison: http://zaa.ch/2o http://zaa.ch/2o
cousin_it 17y 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-combinators.html http://www.bluishcoder.co.nz/2007/10/javascript-parser-combi... I did the same thing in ActionScript. It's easy and fun.
- dmajda 17y 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 17y 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 http://github.com/doublec/jsparse

74 points by dmajda 17y 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 :-)

ErrantX 17y ago
http://treetop.rubyforge.org/ 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.
- dmajda 17y ago
  What exactly you didn't like?
  - ErrantX 17y ago
    Just personal preference: I prefer the grammar structure for parsers like Racc
moserware 17y ago
You might look at OMeta/JS: http://tinlizzie.org/ometa-js/#JavaScript_Compiler 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 17y 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.
dmajda 17y ago
ECMAScript 5 PEG parser: http://boshi.inimino.org/3box/PEG/build/ES5.html 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 17y 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 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 17y ago
Amen on the easy to read part. I'm the author of clj-peg ( http://www.lithinos.com/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 17y ago
  I'm really interested in human-readable grammars. Thanks for your work.

euroclydon 17y ago

I'm confused about the grammar example. How does: multiplicative : primary "* " multiplicative { return $1 * $3; } return the product of two integers?

mbrubeck 17y 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 "*".)
- euroclydon 17y 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?
  - mbrubeck 17y ago
    The "/" at the start of the second line is a choice operator. For example, this is how you would define a term a that can match either b or c: a: b / c (The asterisks in my post were escaped because they were in a code block, or because there were not two of them in the same line.)
- euroclydon 17y ago
  btw, how did you escape that asterisk in quotes?
- barrkel 17y ago

scott_s 17y 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 http://portal.acm.org/citation.cfm?id=964001.964011

barrkel 17y 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).
- cynicalkane 17y 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.
  - silentbicycle 17y ago
    Right, and PEGs only have one level of backtracking, so you don't have potentially massive slowdown due to backtracking several levels and re-trying everything along the way. While the backtracking behavior is different, choice order affects PEG rules similarly to Prolog.
  - barrkel 17y ago
    I know all of that. My point is that the if/else problem really is an ambiguity (i.e. it is a language bug, not just a problem you have to get around in parsing), and problems similar to it crop up when your tool doesn't alert you to first/follow conflicts, in LL(1) parlance. That PEGs encode the implementation strategy inside the declarative grammar is a flaw, in my opinion, not a benefit.

grayrest 17y ago

There are a couple other parser generators for JS: * http://zaa.ch/2k http://zaa.ch/2k - Jison * http://inimino.org/~inimino/blog/peg_first_release 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 17y ago
Worth noting that, last I heard, CoffeeScript is using Zaach's Jison: http://zaa.ch/2o http://zaa.ch/2o

cousin_it 17y 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-combinators.html http://www.bluishcoder.co.nz/2007/10/javascript-parser-combi... I did the same thing in ActionScript. It's easy and fun.

dmajda 17y 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 17y 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 http://github.com/doublec/jsparse