6 ms·

Language.js - A fast PEG parser written in JavaScript

101 points by ryannielsen 15y ago

aashay 15y ago
No README?
notJim 15y ago
Could really use a readme. Languagejs.com goes to a GoDaddy landing page. I guess this is what PEG is: http://en.wikipedia.org/wiki/Parsing_expression_grammar http://en.wikipedia.org/wiki/Parsing_expression_grammar
tolmasky 15y ago
This just got pushed literally today as I gave a presentation on it at CappCon, wasn't expecting it to get posted here, README and so forth are coming. EDIT: OK, there is a README up, but again, this is not officially "launched" or anything, I was planning on putting the docs and website together this week, so check back later.
- brok3nmachine 15y ago
  Nice. Look forward to hearing more. Currently part of a team that is using node.js with peg.js (http://pegjs.majda.cz/documentation http://pegjs.majda.cz/documentation) for a service that defines a grammar for a query language, which is translated into one or more internal service API calls for an enterprise backend. Needs to handle hundreds of req/s, so any performance improvements over peg.js will definitely make your solution more appealing as well.
- ryannielsen 15y ago
  Sorry for the pre-announce, then! I was intrigued by the tweets of others at CappCon, and this is the first I've ever heard of a PEG... it felt like something others on HN would like to know about. I'm very interested in language.js and Obj-J 2.0, and look forward to hearing more about both.
sjs 15y ago
Just a note: Francisco didn't release this. He just pushed it to Github and others have posted it here. I don't think he mentioned it on twitter even, it's a glimpse of something he's hacking on.
samstokes 15y ago
The "naughty OR" operator, and placing syntax error nodes in the syntax tree, are awesome ideas. I hope someone steals them and adds them to Parsec :)
geuis 15y ago
Can someone summarize what PEG is? I read through the Wikipedia page but can't make heads or tails of it. What is this used for?
- kevinburke 15y ago
  PEG parsers get rid of the dangling else problem with recursive descent parsers where it's unclear in the following statement whether if e then s1 else if e then s2 else s3 the else s3 should be with the first if or the second if - usually you have to code special rules into your parser. It also allows for a worst-case linear time parse, and there are some language rules you can express with a PEG parser that you can't with a recursive descent parser.
  - andrewflnr 15y ago
    Wouldn't you just have an end symbol for if statements, "end" or "}" or something? That's what I did in my little recursive parser. Maybe what I should ask is, how does a PEG parser resolve it?
    - chipsy 15y ago
      In a PEG you operate under the expectation that all rules will be tried exhaustively, so if one fails you just move on to the next, and if they all fail you drop back a level of recursion. Thus you can have rules like: "if <if-expr>" where if-expr can contain "<statements> else" or "<statements> if" or "then <statements>", where statements is a set of predefined keywords, another set of PEG rules, or a regular expression matcher. And then you can just expect that they'll all be tried at some point. The main issue with this, of course, is the one you raised, with endings and creating rules for delimiting new blocks. Although it's possible to define a good set of rules, it's still hard to distinguish between a continuation of a statement and the start of a new one, and in most cases you won't get a useful syntax error message using a naive PEG system like the one in PEG.js, because it'll just drop all the way to the top level and then fail at the first character without telling you how far/deep it got before the syntax broke. So in practice having end symbols is still useful to make the grammar operate sanely. PEG can also be used to execute a relatively flat pass that mostly produces tokens and simple expressions, while other methods are applied to the resulting tree to get the complete structure. This is an approach which I find a little less mind-bending than trying to cram everything into PEG rules, since you can use varying methods of parsing as the situation dictates.
aeontech 15y ago
Great idea, but... ungoogleable name choice. Definitely look forward to hearing more about this though.
- wccrawford 15y ago
  It's actually the second result for 'languagejs' already, so it's not too bad.
- kree10 15y ago
  Nondescript names are de rigueur for JavaScript-related projects. See also: prototype, node, underscore, backbone, processing, reflection, glow...
abraham 15y ago
From Google Chrome after following the link on GitHub: "The website at languagejs.com has been reported as a “phishing” site. Phishing sites trick users into disclosing personal or financial information, often by pretending to represent trusted institutions, such as banks."
- tlrobinson 15y ago
  Odd, it's just a parked GoDaddy page.
ltamake 15y ago
Pretty cool stuff. Shame I don't have much of a use for it. :(

101 points by ryannielsen 15y ago

No README?

Could really use a readme. Languagejs.com goes to a GoDaddy landing page. I guess this is what PEG is: http://en.wikipedia.org/wiki/Parsing_expression_grammar http://en.wikipedia.org/wiki/Parsing_expression_grammar

tolmasky 15y ago

This just got pushed literally today as I gave a presentation on it at CappCon, wasn't expecting it to get posted here, README and so forth are coming. EDIT: OK, there is a README up, but again, this is not officially "launched" or anything, I was planning on putting the docs and website together this week, so check back later.

brok3nmachine 15y ago
Nice. Look forward to hearing more. Currently part of a team that is using node.js with peg.js (http://pegjs.majda.cz/documentation http://pegjs.majda.cz/documentation) for a service that defines a grammar for a query language, which is translated into one or more internal service API calls for an enterprise backend. Needs to handle hundreds of req/s, so any performance improvements over peg.js will definitely make your solution more appealing as well.
ryannielsen 15y ago
Sorry for the pre-announce, then! I was intrigued by the tweets of others at CappCon, and this is the first I've ever heard of a PEG... it felt like something others on HN would like to know about. I'm very interested in language.js and Obj-J 2.0, and look forward to hearing more about both.

sjs 15y ago

Just a note: Francisco didn't release this. He just pushed it to Github and others have posted it here. I don't think he mentioned it on twitter even, it's a glimpse of something he's hacking on.

samstokes 15y ago

The "naughty OR" operator, and placing syntax error nodes in the syntax tree, are awesome ideas. I hope someone steals them and adds them to Parsec :)

geuis 15y ago

Can someone summarize what PEG is? I read through the Wikipedia page but can't make heads or tails of it. What is this used for?

kevinburke 15y ago
PEG parsers get rid of the dangling else problem with recursive descent parsers where it's unclear in the following statement whether if e then s1 else if e then s2 else s3 the else s3 should be with the first if or the second if - usually you have to code special rules into your parser. It also allows for a worst-case linear time parse, and there are some language rules you can express with a PEG parser that you can't with a recursive descent parser.
- andrewflnr 15y ago
  Wouldn't you just have an end symbol for if statements, "end" or "}" or something? That's what I did in my little recursive parser. Maybe what I should ask is, how does a PEG parser resolve it?
  - chipsy 15y ago
    In a PEG you operate under the expectation that all rules will be tried exhaustively, so if one fails you just move on to the next, and if they all fail you drop back a level of recursion. Thus you can have rules like: "if <if-expr>" where if-expr can contain "<statements> else" or "<statements> if" or "then <statements>", where statements is a set of predefined keywords, another set of PEG rules, or a regular expression matcher. And then you can just expect that they'll all be tried at some point. The main issue with this, of course, is the one you raised, with endings and creating rules for delimiting new blocks. Although it's possible to define a good set of rules, it's still hard to distinguish between a continuation of a statement and the start of a new one, and in most cases you won't get a useful syntax error message using a naive PEG system like the one in PEG.js, because it'll just drop all the way to the top level and then fail at the first character without telling you how far/deep it got before the syntax broke. So in practice having end symbols is still useful to make the grammar operate sanely. PEG can also be used to execute a relatively flat pass that mostly produces tokens and simple expressions, while other methods are applied to the resulting tree to get the complete structure. This is an approach which I find a little less mind-bending than trying to cram everything into PEG rules, since you can use varying methods of parsing as the situation dictates.

aeontech 15y ago

Great idea, but... ungoogleable name choice. Definitely look forward to hearing more about this though.

wccrawford 15y ago
It's actually the second result for 'languagejs' already, so it's not too bad.
kree10 15y ago
Nondescript names are de rigueur for JavaScript-related projects. See also: prototype, node, underscore, backbone, processing, reflection, glow...

abraham 15y ago

From Google Chrome after following the link on GitHub: "The website at languagejs.com has been reported as a “phishing” site. Phishing sites trick users into disclosing personal or financial information, often by pretending to represent trusted institutions, such as banks."

tlrobinson 15y ago
Odd, it's just a parked GoDaddy page.

ltamake 15y ago

Pretty cool stuff. Shame I don't have much of a use for it. :(