3 ms·

Tangentially related, here's a tool I've wanted (someone else) to build: There are many variations of how grammars are written, usually variants of Backus–Naur

Tangentially related, here's a tool I've wanted (someone else) to build: 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 https://docs.python.org/3/reference/grammar.html) has custom syntax with a whole PEP (https://peps.python.org/pep-0617/ 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.

UncleEntity 4y ago
You could use lemon to parse that custom BNF grammar to turn it into a grammar that lemon likes. 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.
junon 4y ago
FWIW tree-sitter has done a lot of the ground work for this sort of thing, if you need to support a lot of different languages.
IIAOPSW 4y ago
Why not just use the parser generator to generate a parser that will standardize the grammar and then use the parser generator again on the output of that parser to generate a parser for the desired grammar? Its all parser generator all the way down.
mingodad 4y ago
I did something like this here https://github.com/mingodad/lalr-parser-test https://github.com/mingodad/lalr-parser-test where I expanded byacc/bison/lemon to generate a naked grammar, ebnf grammar (understood by https://www.bottlecaps.de/rr/ui https://www.bottlecaps.de/rr/ui to generate railroad diagrams) and interchange the grammar between then (byacc/bison to lemon and the other way around too, taking in account the difference in how they interpret rules precedence).

UncleEntity 4y ago

You could use lemon to parse that custom BNF grammar to turn it into a grammar that lemon likes. 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.

junon 4y ago

FWIW tree-sitter has done a lot of the ground work for this sort of thing, if you need to support a lot of different languages.

IIAOPSW 4y ago

Why not just use the parser generator to generate a parser that will standardize the grammar and then use the parser generator again on the output of that parser to generate a parser for the desired grammar? Its all parser generator all the way down.

mingodad 4y ago

I did something like this here https://github.com/mingodad/lalr-parser-test https://github.com/mingodad/lalr-parser-test where I expanded byacc/bison/lemon to generate a naked grammar, ebnf grammar (understood by https://www.bottlecaps.de/rr/ui https://www.bottlecaps.de/rr/ui to generate railroad diagrams) and interchange the grammar between then (byacc/bison to lemon and the other way around too, taking in account the difference in how they interpret rules precedence).