The Lemon Parser Generator
sqlite.org
sqlite.org
Given a Labelled BNF grammar the tool produces:
- an abstract syntax implementation in the target language,
- a case skeleton for the abstract syntax in the target language,
- a pretty-printer in the target language,
- an Alex, JLex, or Flex lexer generator file ,
- a Happy, CUP, or Bison parser generator file, and
- a LaTeX file containing a readable specification of the language.
Might be fun to expand on this to generate tree-sitter, highlight.js, or a vscode extension.
Lemon produces this report for my grammar:
Parser statistics:
terminal symbols................... 19
non-terminal symbols............... 42
total symbols...................... 61
rules.............................. 75
states............................. 56
conflicts.......................... 0
action table entries............... 377
lookahead table entries............ 379
total table size (bytes)........... 1433
$ wc src/parser.c
2200 10090 78282 src/parser.c
re2c for tokenizing, and lemon for parsing =
There are many variations of how grammars are written, usually variants of Backus–Naur form, and often I find a grammar spec is published using a different variant than what is expected by the parser tool I want to use (e.g., a grammar-based fuzzer).
For example, Python's grammar (https://docs.python.org/3/reference/grammar.html) has custom syntax with a whole PEP (https://peps.python.org/pep-0617/) describing the grammar of the grammar.
It would be nice to have a tool that can at least help with the mechanical transformation between these grammar syntaxes.
That being said, based on my playing around with lemon, the grammar is only a small part of the work with getting the actions right taking up the bulk of the time. You have to insert a bunch of attribute indicators (for lack of a better term) that get passed into the actions anyway so you can’t just take a perfectly formed grammar and use it without a bunch of work.
Plus some parser generators like left-recursive, some like right-recursive, some have ‘sugar’ to indicate repetition and/or optionality, some don’t so you have to specify it manually using empty rules, lots of different ways to do the same thing.
Its all parser generator all the way down.
Why does it seem as if almost every parser generator defines its own quirky grammar syntax? What's wrong or so difficult with just accepting W3C EBNF? Who thinks it's a good idea to force grammars to be re-written in the first place?
Does nobody complain about vendor lock-in due to the quirky grammar syntax they were forced to use?
Where are the automatic conversion utilities for these parser generators? Something that takes, say W3C EBNF and spits out the quirky parser generator grammar language? Shouldn't that be simple?
I really don't get it.
Why should we do what the W3C want?
Anyway - not all grammars are expressible using EBNF. For example prioritised choice.
The only thing I would change is the way it is distributed: the links at the end point to a sort of amalgamation of the actual sources that make up the parser generator (in the same style that is used for the SQLite source amalgamation), but I think it would be more beneficial to have access to the separate files that actually make up this amalgamation (and you could hide as static variables / functions some of the implementation details this way).
Anyway, excellent tool!
There is one sentence on Lemon's homepage which points that direction, which is very easy to miss.
All of the hwaci tools are maintained in Fossil repos and distributed as amalgamations, so that's consistent at least.
That reads much better than legalese.
It’s a little ways behind the canonical implementation, because I haven’t touched it for a while, but lemon changes very slowly if at all
The Lemon Parser Generator - https://news.ycombinator.com/item?id=10295087 - Sept 2015 (10 comments)
The Lemon Parser Generator - https://news.ycombinator.com/item?id=4473854 - Sept 2012 (2 comments)
Of course this works best in a language that supports operator overloading and compile-time operations.
In the old days, in C++, this would have been done with template metaprogramming, which cost various annoyances. Now no such workarounds are needed.
This morning I added a commit to a fossil repo, and that commit was on a .y lemon file.
That's not a typical thing I do in a day.