5 ms·

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-expr

by 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)
  - versteegen 10y ago
    Neat. I did find the readme confusing. I had to jump up and down the page to make sense of it. 'any' is mentioned but not documented. The first few examples made absolutely zero sense until I've read quite a bit further, despite being familiar with parsers and grammars -- it's not a very gentle introduction. OK but your actual question was about usability. I don't understand why 'factor' takes a generation function as an argument instead of something much less verbose, like an array/table. That looks like it would be my biggest complaint. Is it implementation detail, or to allow self reference, or to allow arbitrary code inside one? If the latter, can providing a function instead of simpler syntax be made optional? There ought to be alternatives to allowing self-reference too. It's cute that a parser can be used as an iterator. How useful is it in practice to match concatenated valid sentences like that? I never saw a use for it in my own tasks.
    - meric 10y ago
      Thanks for taking a look at it, I could really use your feedback to improve the documentation - definitely an area I need to improve. The anonymous function is so that it waits till all the non terminals are defined. The iterator feature is cute, which was reason enough for me to do it. :) Much appreciated.
- YeGoblynQueenne 10y ago
  >> (I'm reminded of the apocryphal Prolog compiler which, if you gave it a program with a syntax error, would just reply 'No.'.) I don't believe you remember this correctly. The Prolog interpreter will raise an error for syntax errors. If you misspel something but don't cause a syntax error then you may get an unexpected "no" (or "false") but a syntax error causes compilation to fail, in Prolog as in any language. In any case, a "no" ("false") is the proof procedure failing to prove your query true (or, more accurately, finding a way to prove it false). It's not an error and it's not a failure of the interpreter.

by leafo 10y ago

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)
- versteegen 10y ago
  Neat. I did find the readme confusing. I had to jump up and down the page to make sense of it. 'any' is mentioned but not documented. The first few examples made absolutely zero sense until I've read quite a bit further, despite being familiar with parsers and grammars -- it's not a very gentle introduction. OK but your actual question was about usability. I don't understand why 'factor' takes a generation function as an argument instead of something much less verbose, like an array/table. That looks like it would be my biggest complaint. Is it implementation detail, or to allow self reference, or to allow arbitrary code inside one? If the latter, can providing a function instead of simpler syntax be made optional? There ought to be alternatives to allowing self-reference too. It's cute that a parser can be used as an iterator. How useful is it in practice to match concatenated valid sentences like that? I never saw a use for it in my own tasks.
  - meric 10y ago
    Thanks for taking a look at it, I could really use your feedback to improve the documentation - definitely an area I need to improve. The anonymous function is so that it waits till all the non terminals are defined. The iterator feature is cute, which was reason enough for me to do it. :) Much appreciated.
YeGoblynQueenne 10y ago
>> (I'm reminded of the apocryphal Prolog compiler which, if you gave it a program with a syntax error, would just reply 'No.'.) I don't believe you remember this correctly. The Prolog interpreter will raise an error for syntax errors. If you misspel something but don't cause a syntax error then you may get an unexpected "no" (or "false") but a syntax error causes compilation to fail, in Prolog as in any language. In any case, a "no" ("false") is the proof procedure failing to prove your query true (or, more accurately, finding a way to prove it false). It's not an error and it's not a failure of the interpreter.