4 ms·

Having written a parser generator myself (https://github.com/YorickPeterse/ruby-ll https://github.com/YorickPeterse/ruby-ll), plenty of handwritten parsers, and

Having written a parser generator myself (https://github.com/YorickPeterse/ruby-ll https://github.com/YorickPeterse/ruby-ll), plenty of handwritten parsers, and having mess with parsing combinators I concluded I really don't like parsing combinators. Perhaps this was due to the APIs of the libraries I worked with (e.g. Nom in Rust), but it just lead to incredibly verbose and hard to work with code. Since writing recursive descent parsers is not that hard (at least if your grammar is LL(1), see https://github.com/YorickPeterse/inko/blob/a76a8c23f901c5b2a40c410aa2df85261e650769/compiler/lib/inkoc/parser.rb https://github.com/YorickPeterse/inko/blob/a76a8c23f901c5b2a... for an example) I would personally go with this approach whenever possible. Parser generators definitely have their use cases (and allow you to write a parser much faster), but error reporting is often tricky to get right.

bd82 9y ago
I also slightly dislike parser combinators. Mainly because usually you cannot easily debug them by placing a breakpoint. In the best case scenario the specific parser combinator has good tracing support to enable debugging. However, imho this is still inferior to simple breakpoints and debugging "directly" in one's favorite IDE.
- aidenn0 9y ago
  The only parser combinator library I used (smug, for common lisp) had little trouble with breakpoints; (any parse with significant backtracking was annoying but breakpoints worked fine) is it common that one cannot use breakpoints for debugging in other parser-combinator libraries?
  - bd82 9y ago
    I'm not familiar with Smug, but I would guess that the combinator is implemented using LISP macros which are than expanded into "real" source code (lisp lists) which is evaluated directly and can halt on break points. In programing languages which do not have true macros The combinator API normally creates a data structure representing the grammar which is than interpreted Which usually makes debugging harder and the parsing slower.
- kmicklas 9y ago
  I would argue that if you're tying to debug a parser with a tracing debugger you're doing something wrong.
abecedarius 9y ago
A design I like combines a combinator library with an optional facade that gives you a convenient grammar syntax a la a parser generator -- for example, Lua's LPEG works this way. LPEG is a little awkward imo in how it integrates semantic actions, and I tried to do better in my own library (which unfortunately isn't really ready to share and it's been on the back burner).
saltcured 9y ago
I think parser generators are generally easier to use with dynamic languages. Most of the code-generation tooling can be hidden by interpreters or JIT compilers, and dynamic typing and generics can make the action code much more concise. I learned and used bison+flex back in the 90s. More recently, I've enjoyed the PLY package for Python. It's essentially the same algorithms and abstractions, but it turns the usual bison grammar inside-out by embedding grammar fragments in your Python action code instead of embedding action code in a grammar file. Your grammar is a Python module. You write Python function definitions which feel almost like you are writing the interesting subset of a recursive-descent parser, i.e. the important reduction steps, while hand-waving about all the input-testing and buffering you would have to do in a bespoke recursive descent parser. The code comment on each function attaches the grammatical rule which fires that action. The PLY parser-generator function you call at the end of your grammar module uses Python introspection to find all the production rules and stitch the parser together. My only coding style complaint is how PLY abuses the function __doc__ strings to embed the grammar rules. I think using a decorator interface would have been a more "pythonic" interface to attach the grammatical rules to each action function...
- dnr 9y ago
  I used PLY to write a parser for a moderately complex internal language a while ago at work and it was a great experience. I ended up with very readable code. (And with only a little hackery I was able to write a tool to perform source code transformations while preserving comments and formatting around the changes.) I'd definitely use it again. The only potential downside is speed: it's Python, so there's only so fast it can go compared to other languages.

bd82 9y ago

I also slightly dislike parser combinators. Mainly because usually you cannot easily debug them by placing a breakpoint. In the best case scenario the specific parser combinator has good tracing support to enable debugging. However, imho this is still inferior to simple breakpoints and debugging "directly" in one's favorite IDE.

aidenn0 9y ago
The only parser combinator library I used (smug, for common lisp) had little trouble with breakpoints; (any parse with significant backtracking was annoying but breakpoints worked fine) is it common that one cannot use breakpoints for debugging in other parser-combinator libraries?
- bd82 9y ago
  I'm not familiar with Smug, but I would guess that the combinator is implemented using LISP macros which are than expanded into "real" source code (lisp lists) which is evaluated directly and can halt on break points. In programing languages which do not have true macros The combinator API normally creates a data structure representing the grammar which is than interpreted Which usually makes debugging harder and the parsing slower.
kmicklas 9y ago
I would argue that if you're tying to debug a parser with a tracing debugger you're doing something wrong.

abecedarius 9y ago

A design I like combines a combinator library with an optional facade that gives you a convenient grammar syntax a la a parser generator -- for example, Lua's LPEG works this way. LPEG is a little awkward imo in how it integrates semantic actions, and I tried to do better in my own library (which unfortunately isn't really ready to share and it's been on the back burner).

saltcured 9y ago

I think parser generators are generally easier to use with dynamic languages. Most of the code-generation tooling can be hidden by interpreters or JIT compilers, and dynamic typing and generics can make the action code much more concise. I learned and used bison+flex back in the 90s. More recently, I've enjoyed the PLY package for Python. It's essentially the same algorithms and abstractions, but it turns the usual bison grammar inside-out by embedding grammar fragments in your Python action code instead of embedding action code in a grammar file. Your grammar is a Python module. You write Python function definitions which feel almost like you are writing the interesting subset of a recursive-descent parser, i.e. the important reduction steps, while hand-waving about all the input-testing and buffering you would have to do in a bespoke recursive descent parser. The code comment on each function attaches the grammatical rule which fires that action. The PLY parser-generator function you call at the end of your grammar module uses Python introspection to find all the production rules and stitch the parser together. My only coding style complaint is how PLY abuses the function __doc__ strings to embed the grammar rules. I think using a decorator interface would have been a more "pythonic" interface to attach the grammatical rules to each action function...

dnr 9y ago
I used PLY to write a parser for a moderately complex internal language a while ago at work and it was a great experience. I ended up with very readable code. (And with only a little hackery I was able to write a tool to perform source code transformations while preserving comments and formatting around the changes.) I'd definitely use it again. The only potential downside is speed: it's Python, so there's only so fast it can go compared to other languages.