3 ms·

Roberto Ierusalimschy's lpeg is around 2.4k loc of ansi C without any dependency beside libC and lua.h (needed to interface with Lua, since it's a Lua library).

by pygy_ 16y ago

Roberto Ierusalimschy's lpeg is around 2.4k loc of ansi C without any dependency beside libC and lua.h (needed to interface with Lua, since it's a Lua library). It implements an efficient pattern matching system based on Parsing Expression Grammars (akin to CFGs, but without ambiguities). It consists of a Pattern/Grammar to bytecode compiler and a custom VM to interpret the result of the compiling phase. Nice and clean. http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html http://en.wikipedia.org/wiki/Parsing_expression_grammar http://en.wikipedia.org/wiki/Parsing_expression_grammar

silentbicycle 16y ago
The Lua code itself (while not <2 kloc) is also clean, well designed C, and definitely worth study. It gets quite a bit of functionality out of 12.6 kloc, and if you work with C, Lua is an ally (it's like Tcl, but good). :) Also, in my experience, LPEG is a great fit for middle-ground parsing - more complex than Perlish regexps (which it handles well), and including those a bit more complex still, but it's awkward for really complex parsing (since it inherently combines lexing and parsing). But I dissed Perl and Tcl, so -1. Screw useful information. ;)
- beagle3 16y ago
  > but it's awkward for really complex parsing (since it inherently combines lexing and parsing). I'm kind of surprised by that statement - grammars for programming languages expressed in PEG always seem much cleaner to me than the lex/parse separation. Can you give an example of a grammar that you find is complicated by PEG?
  - silentbicycle 16y ago
    I initially wrote the parser for a (proprietary) query language compiler using LPEG, and keeping track of lexical issues (whitespace, etc.) along with the grammatical structure complicated things. When I broke it apart and wrote a quick FSM-based lexer and a recursive descent parser, it became much simpler. Perhaps I could have factored the PEG grammar better, but with every PEG grammar I've had grow beyond a certain point, I've wished I could separate the lexing and parsing stages. I much prefer working with LPEG to regular expressions for small to midsized stuff, though.

by pygy_ 16y ago

silentbicycle 16y ago

The Lua code itself (while not <2 kloc) is also clean, well designed C, and definitely worth study. It gets quite a bit of functionality out of 12.6 kloc, and if you work with C, Lua is an ally (it's like Tcl, but good). :) Also, in my experience, LPEG is a great fit for middle-ground parsing - more complex than Perlish regexps (which it handles well), and including those a bit more complex still, but it's awkward for really complex parsing (since it inherently combines lexing and parsing). But I dissed Perl and Tcl, so -1. Screw useful information. ;)

beagle3 16y ago
> but it's awkward for really complex parsing (since it inherently combines lexing and parsing). I'm kind of surprised by that statement - grammars for programming languages expressed in PEG always seem much cleaner to me than the lex/parse separation. Can you give an example of a grammar that you find is complicated by PEG?
- silentbicycle 16y ago
  I initially wrote the parser for a (proprietary) query language compiler using LPEG, and keeping track of lexical issues (whitespace, etc.) along with the grammatical structure complicated things. When I broke it apart and wrote a quick FSM-based lexer and a recursive descent parser, it became much simpler. Perhaps I could have factored the PEG grammar better, but with every PEG grammar I've had grow beyond a certain point, I've wished I could separate the lexing and parsing stages. I much prefer working with LPEG to regular expressions for small to midsized stuff, though.