7 ms·

Show HN: Using Parsing Expression Grammars to rewrite source code

63 points by sebcat 10y ago

VertexRed 10y ago
I viewed this on my phone and it was annoying and difficult to read due to the typing effect in the header which caused the content below to move up and down.
- chrismcb 10y ago
  It is a readme on guthub. What typing effect are you talking about?
  - VertexRed 10y ago
    Wrong tab. Comment was meant for https://news.ycombinator.com/item?id=12498976 https://news.ycombinator.com/item?id=12498976
leafo 10y ago
Parsing expression grammars are my favorite way to parse text. I also use Lua and LPeg. Here's a tutorial I wrote on them: http://leafo.net/guides/parsing-expression-grammars.html http://leafo.net/guides/parsing-expression-grammars.html Additionally, I've written an entire programming language with them: http://moonscript.org/ http://moonscript.org/ Here's the grammar: https://github.com/leafo/moonscript/blob/master/moonscript/parse.moon#L106 https://github.com/leafo/moonscript/blob/master/moonscript/p... My favorite part is that you express the grammar in code, not some simplified language designed to write parsers. So you get all the nice things a programming language normally gives you. (eg. you can use functions instead of having support for macros) I've also started experimenting with compiling LPeg style grammars to C, for even more speed. This uses the peg library: https://github.com/leafo/moonparse https://github.com/leafo/moonparse You can see how the grammar looks here: https://github.com/leafo/moonparse/blob/master/parse.peg.moon#L115 https://github.com/leafo/moonparse/blob/master/parse.peg.moo...
- sebcat 10y ago
  Nice work! I agree with you regarding LPeg values as first class objects in Lua. It's a really nice fit, and a much nicer way to solve parsing problems than using flex/bison IMO. Having it in Lua allows for pretty fast code-writing -> test cycles too, if you're cooking up a one-off grammar on the fly for something. I had a university course where we wrote recursive descent parsers in Java, using the standard library. One of the grammars were the classic calculator grammar. We're talking abstract class for parse tree nodes, one class for every node type (Node, NumberNode, AddNode, DivNode) &c. If someone back then would have walked in with the example present in your tutorial and told me that you can write a parser for what we were doing in less than 20 lines that, after you understand the core concepts of PEG, is a lot more legible and comprehensible than all that Java code was... I wish I knew then what I know now :)
- david-given 10y ago
  Last time I used Lpeg for a big project I ran into difficulties with error detection and recovery --- writing the parser for correct input was beautifully easy, but writing a parser that would gracefully handle incorrect input was very hard. (I'm reminded of the apocryphal Prolog compiler which, if you gave it a program with a syntax error, would just reply 'No.'.) When I asked about the best way to handle errors it was suggested to me that I should add alternatives to my rules that would catch errors and return an error token from there; but of course, that short circuits any alternatives further up the grammar tree, so it wasn't very satisfactory. A quick look at your grammar doesn't show anything like this --- how are you dealing with errors?
  - meric 10y ago
    Hey, while you are trying out parser combinators, what do you think of this one? http://github.com/meric/leftry http://github.com/meric/leftry It's very new and I would like some comments on how to make it easier to use. You can check out http://github.com/meric/l2l http://github.com/meric/l2l, which is a hybrid lisp and lua programming language that relies on the parser combinator library. (See the lua.lua in that project, where the Lua grammar is implemented using Leftry)
akavel 10y ago
I really wish the expressions were better documented/explained in the source. They're dense, similarly to regexps, and regexps also benefit immensely from explanation when used as a demo/teaching tool.
- sebcat 10y ago
  Good point. I added a new branch where I broke the "literal" rule into multiple rules and added some comments where I try to explain what's going on in English. I also added an achor to it in the master README.md. I find it a bit hard to accurately describe the operations with words though, if there's any ambiguities in the wording, let me know! https://github.com/sebcat/move-literals/blob/commented_expressions/move-literals.lua#L17 https://github.com/sebcat/move-literals/blob/commented_expre...
  - akavel 10y ago
    Awesome, thanks! It's the first time I've seen example PEGs explained so nicely. I've let myself add a few small comments with some additional suggestions. Some additional comments I didn't know how to add on github: - in load_data(), you should most probably use `local` on l.99 and 103; - in load_data() l.99, you could consider using the idiom: local f = assert(io.open(file, "rb")) though arguably it's clearer as it is now. Other than that, it would be even cooler if you could also add some examples in the repo of how to deal with parsing errors, as you showed in another comment!
    - sebcat 10y ago
      Thank you for the feedback. The commented_expressions branch looks a lot better than master now, I'll probably merge it. I added the code from the comment to README.md.
ulrikrasmussen 10y ago
Minor technical nitpick for the README: You're not moving up the Chomsky hierarchy but rather moving sideways ;). PEGs are non-Chomskyan parsing formalisms, in the sense that the family of languages describable by PEGs are not to be found in the Chomsky hierarchy. For example, they are not regular, as they can match patterns such as a^n b^n. On the other hand, they are also not context-free, as they can also match non-context-free patterns such as a^n b^n c^n. Finally, since PEG can be parsed in linear time, there must also be some CFG which cannot be recognized by any PEG - this follows due to a result by Lee [1]. [1] L. Lee. Fast Context Free Grammar Parsing Requires Fast Boolean Matrix Multiplication. http://arxiv.org/pdf/cs/0112018.pdf http://arxiv.org/pdf/cs/0112018.pdf
- versteegen 10y ago
  Interesting. I see that the Wikipedia PEG article still states that the existence of CFG- but not PEG-parsable languages is an open problem.
  - ulrikrasmussen 10y ago
    It is! It is surprisingly difficult to come up with a grammar and a proof that it cannot be recognized by a PEG. Part of the reason is probably that PEGs and CFGs are quite different: A CFG is a set of generative rules which specify a set of strings, whereas a PEG is actually more like a recursive program. There's an open question on Stack Exchange for anyone who feel like taking a stab at the problem: http://cstheory.stackexchange.com/questions/34792/does-peg-contain-cfg http://cstheory.stackexchange.com/questions/34792/does-peg-c...
    - versteegen 10y ago
      OK. I thought you meant that a non-constructive proof existed that there is such a CFG. That's how I interpreted "Finally, since PEG can be parsed in linear time, there must also be some CFG which cannot be recognized by any PEG". But I see that on cstheory you wrote instead (being more precise?) "most probably ... PEG does not contain CFG".
nightcracker 10y ago
A while back I made a PEG parser in Python in ~400 LOC, that can parse itself. It's actually quite straightforward: https://gist.github.com/orlp/e880287287985ccd9288def8f6741b47 https://gist.github.com/orlp/e880287287985ccd9288def8f6741b4.... I've also added a 'skipper' feature, that makes handling whitespace a breeze.

63 points by sebcat 10y ago

I viewed this on my phone and it was annoying and difficult to read due to the typing effect in the header which caused the content below to move up and down.

chrismcb 10y ago
It is a readme on guthub. What typing effect are you talking about?
- VertexRed 10y ago
  Wrong tab. Comment was meant for https://news.ycombinator.com/item?id=12498976 https://news.ycombinator.com/item?id=12498976

leafo 10y ago

Parsing expression grammars are my favorite way to parse text. I also use Lua and LPeg. Here's a tutorial I wrote on them: http://leafo.net/guides/parsing-expression-grammars.html http://leafo.net/guides/parsing-expression-grammars.html Additionally, I've written an entire programming language with them: http://moonscript.org/ http://moonscript.org/ Here's the grammar: https://github.com/leafo/moonscript/blob/master/moonscript/parse.moon#L106 https://github.com/leafo/moonscript/blob/master/moonscript/p... My favorite part is that you express the grammar in code, not some simplified language designed to write parsers. So you get all the nice things a programming language normally gives you. (eg. you can use functions instead of having support for macros) I've also started experimenting with compiling LPeg style grammars to C, for even more speed. This uses the peg library: https://github.com/leafo/moonparse https://github.com/leafo/moonparse You can see how the grammar looks here: https://github.com/leafo/moonparse/blob/master/parse.peg.moon#L115 https://github.com/leafo/moonparse/blob/master/parse.peg.moo...

sebcat 10y ago
Nice work! I agree with you regarding LPeg values as first class objects in Lua. It's a really nice fit, and a much nicer way to solve parsing problems than using flex/bison IMO. Having it in Lua allows for pretty fast code-writing -> test cycles too, if you're cooking up a one-off grammar on the fly for something. I had a university course where we wrote recursive descent parsers in Java, using the standard library. One of the grammars were the classic calculator grammar. We're talking abstract class for parse tree nodes, one class for every node type (Node, NumberNode, AddNode, DivNode) &c. If someone back then would have walked in with the example present in your tutorial and told me that you can write a parser for what we were doing in less than 20 lines that, after you understand the core concepts of PEG, is a lot more legible and comprehensible than all that Java code was... I wish I knew then what I know now :)
david-given 10y ago
Last time I used Lpeg for a big project I ran into difficulties with error detection and recovery --- writing the parser for correct input was beautifully easy, but writing a parser that would gracefully handle incorrect input was very hard. (I'm reminded of the apocryphal Prolog compiler which, if you gave it a program with a syntax error, would just reply 'No.'.) When I asked about the best way to handle errors it was suggested to me that I should add alternatives to my rules that would catch errors and return an error token from there; but of course, that short circuits any alternatives further up the grammar tree, so it wasn't very satisfactory. A quick look at your grammar doesn't show anything like this --- how are you dealing with errors?
- meric 10y ago
  Hey, while you are trying out parser combinators, what do you think of this one? http://github.com/meric/leftry http://github.com/meric/leftry It's very new and I would like some comments on how to make it easier to use. You can check out http://github.com/meric/l2l http://github.com/meric/l2l, which is a hybrid lisp and lua programming language that relies on the parser combinator library. (See the lua.lua in that project, where the Lua grammar is implemented using Leftry)

akavel 10y ago

I really wish the expressions were better documented/explained in the source. They're dense, similarly to regexps, and regexps also benefit immensely from explanation when used as a demo/teaching tool.

sebcat 10y ago
Good point. I added a new branch where I broke the "literal" rule into multiple rules and added some comments where I try to explain what's going on in English. I also added an achor to it in the master README.md. I find it a bit hard to accurately describe the operations with words though, if there's any ambiguities in the wording, let me know! https://github.com/sebcat/move-literals/blob/commented_expressions/move-literals.lua#L17 https://github.com/sebcat/move-literals/blob/commented_expre...
- akavel 10y ago
  Awesome, thanks! It's the first time I've seen example PEGs explained so nicely. I've let myself add a few small comments with some additional suggestions. Some additional comments I didn't know how to add on github: - in load_data(), you should most probably use `local` on l.99 and 103; - in load_data() l.99, you could consider using the idiom: local f = assert(io.open(file, "rb")) though arguably it's clearer as it is now. Other than that, it would be even cooler if you could also add some examples in the repo of how to deal with parsing errors, as you showed in another comment!
  - sebcat 10y ago
    Thank you for the feedback. The commented_expressions branch looks a lot better than master now, I'll probably merge it. I added the code from the comment to README.md.

ulrikrasmussen 10y ago

Minor technical nitpick for the README: You're not moving up the Chomsky hierarchy but rather moving sideways ;). PEGs are non-Chomskyan parsing formalisms, in the sense that the family of languages describable by PEGs are not to be found in the Chomsky hierarchy. For example, they are not regular, as they can match patterns such as a^n b^n. On the other hand, they are also not context-free, as they can also match non-context-free patterns such as a^n b^n c^n. Finally, since PEG can be parsed in linear time, there must also be some CFG which cannot be recognized by any PEG - this follows due to a result by Lee [1]. [1] L. Lee. Fast Context Free Grammar Parsing Requires Fast Boolean Matrix Multiplication. http://arxiv.org/pdf/cs/0112018.pdf http://arxiv.org/pdf/cs/0112018.pdf

versteegen 10y ago
Interesting. I see that the Wikipedia PEG article still states that the existence of CFG- but not PEG-parsable languages is an open problem.
- ulrikrasmussen 10y ago
  It is! It is surprisingly difficult to come up with a grammar and a proof that it cannot be recognized by a PEG. Part of the reason is probably that PEGs and CFGs are quite different: A CFG is a set of generative rules which specify a set of strings, whereas a PEG is actually more like a recursive program. There's an open question on Stack Exchange for anyone who feel like taking a stab at the problem: http://cstheory.stackexchange.com/questions/34792/does-peg-contain-cfg http://cstheory.stackexchange.com/questions/34792/does-peg-c...
  - versteegen 10y ago
    OK. I thought you meant that a non-constructive proof existed that there is such a CFG. That's how I interpreted "Finally, since PEG can be parsed in linear time, there must also be some CFG which cannot be recognized by any PEG". But I see that on cstheory you wrote instead (being more precise?) "most probably ... PEG does not contain CFG".

nightcracker 10y ago

A while back I made a PEG parser in Python in ~400 LOC, that can parse itself. It's actually quite straightforward: https://gist.github.com/orlp/e880287287985ccd9288def8f6741b47 https://gist.github.com/orlp/e880287287985ccd9288def8f6741b4.... I've also added a 'skipper' feature, that makes handling whitespace a breeze.