3 ms·

Writing a BNF Grammar

51 points by mbellotti 6y ago

analognoise 6y ago
What about context sensitive languages like VHDL?
- loup-vaillant 6y ago
  Don't design them. Contextual grammars are a pain to deal with, both for the implementer and the user. Alternatively, you can split the parsing into stage. Take XML for instance. The fact that it's opening and closing tags must be marked by the same identifier makes it context sensitive. You can however get around that by simply registering opening and closing tags in the parsing stage, and verify they match only later. Really, though: if you have the liberty to design the syntax yourself, context sensitivity is generally best avoided. Heck, you probably want to limit yourself to a subset of context free grammars, like LR (which is guaranteed non-ambiguous). You can restrict even further, and stick to LL(1) —which goes a long way if you parse binary operators in a later stage, with shunting yard or precedence climbing. Easier parsing means easier tooling, more predictable syntax, easier error handling… Sure, if you don't have a choice (compatibility or business imperative), you can introduce some context sensitivity. Ideally though, you want to use the least powerful grammar you can get away with.
  - gumby 6y ago
    Great comment
- jsmith45 6y ago
  The most common trick to parsing grammars with a few context sensitive bits is to create some grammar that accepts too much. It allows things that are not valid in those context sensitive places, but gets the grammar correct in all the other places. It generally will be an overly permissive form of one of the possible parses. Then a second pass over the tree can collect context, and when it reaches these spots it determines if the current parse is correct, and validates it against a more restrictive version if so. If some other parse was needed, it transforms the tree into said other parse. An alternative is to skip a parser generator entirely and so something like a recursive descent parser, which can easily collect any needed context as it goes, and use that in deciding how to parse anything context sensitive.
tester34 6y ago
"There are only two types of people who write the code for parsers from scratch: absolutely beginners and absolute experts."
- gumby 6y ago
  Good advice, but every good rule requires context: sometimes a really simple grammar (e.g. a lisp tokenizer) is faster to implement with a tiny handmade recursive descent parser that could fit on a single page of code. Faster to write and easier to understand than calling out to a pen external lexer. Not THAT being said I will contradict myself: when you are writing a tiny language like that it’s easy to accidentally add dependencies like context-sensitive behavior. Which means if things grow to the point where you need a parser generator it may become much harder.
- rualca 6y ago
  That quote without context or the rationale just feels needlessly snarky, as it leaves out arguments in favour of using parser generators.
lordgrenville 6y ago
Off topic: I've noticed HN has started suffixing the sitestr in submissions from GitHub, Twitter, etc. with the username (first subdirectory after the TLD). Probably worth doing it for dev.to as well (not that it shows up here very often).
hardmath123 6y ago
Here’s a plug for the “nearley playground,” which is a great way to interactively build/debug BNF grammars. https://omrelli.ug/nearley-playground/ https://omrelli.ug/nearley-playground/
ethanwillis 6y ago
There was a book I checked out of the library in college that I haven't been able to find ever again. All I remember is that it was a series by various author, "IBM System series" and there was one specifically on compilers that goes through building symbol tables, BNF grammar, different parsing methods, etc. Has anyone else here read/seen this book and can you remember the exact titles?
qubex 6y ago
Tangentially related: I must enjoyed Polygen (https://polygen.org https://polygen.org) that generates text using a BNF template and I have always wanted to construct a template that generated viable templates (BNF of BNF?) but haven’t ever gotten around to it.

51 points by mbellotti 6y ago

analognoise 6y ago

What about context sensitive languages like VHDL?

loup-vaillant 6y ago
Don't design them. Contextual grammars are a pain to deal with, both for the implementer and the user. Alternatively, you can split the parsing into stage. Take XML for instance. The fact that it's opening and closing tags must be marked by the same identifier makes it context sensitive. You can however get around that by simply registering opening and closing tags in the parsing stage, and verify they match only later. Really, though: if you have the liberty to design the syntax yourself, context sensitivity is generally best avoided. Heck, you probably want to limit yourself to a subset of context free grammars, like LR (which is guaranteed non-ambiguous). You can restrict even further, and stick to LL(1) —which goes a long way if you parse binary operators in a later stage, with shunting yard or precedence climbing. Easier parsing means easier tooling, more predictable syntax, easier error handling… Sure, if you don't have a choice (compatibility or business imperative), you can introduce some context sensitivity. Ideally though, you want to use the least powerful grammar you can get away with.
- gumby 6y ago
  Great comment
jsmith45 6y ago
The most common trick to parsing grammars with a few context sensitive bits is to create some grammar that accepts too much. It allows things that are not valid in those context sensitive places, but gets the grammar correct in all the other places. It generally will be an overly permissive form of one of the possible parses. Then a second pass over the tree can collect context, and when it reaches these spots it determines if the current parse is correct, and validates it against a more restrictive version if so. If some other parse was needed, it transforms the tree into said other parse. An alternative is to skip a parser generator entirely and so something like a recursive descent parser, which can easily collect any needed context as it goes, and use that in deciding how to parse anything context sensitive.

tester34 6y ago

"There are only two types of people who write the code for parsers from scratch: absolutely beginners and absolute experts."

gumby 6y ago
Good advice, but every good rule requires context: sometimes a really simple grammar (e.g. a lisp tokenizer) is faster to implement with a tiny handmade recursive descent parser that could fit on a single page of code. Faster to write and easier to understand than calling out to a pen external lexer. Not THAT being said I will contradict myself: when you are writing a tiny language like that it’s easy to accidentally add dependencies like context-sensitive behavior. Which means if things grow to the point where you need a parser generator it may become much harder.
rualca 6y ago
That quote without context or the rationale just feels needlessly snarky, as it leaves out arguments in favour of using parser generators.

lordgrenville 6y ago

Off topic: I've noticed HN has started suffixing the sitestr in submissions from GitHub, Twitter, etc. with the username (first subdirectory after the TLD). Probably worth doing it for dev.to as well (not that it shows up here very often).

hardmath123 6y ago

Here’s a plug for the “nearley playground,” which is a great way to interactively build/debug BNF grammars. https://omrelli.ug/nearley-playground/ https://omrelli.ug/nearley-playground/

ethanwillis 6y ago

There was a book I checked out of the library in college that I haven't been able to find ever again. All I remember is that it was a series by various author, "IBM System series" and there was one specifically on compilers that goes through building symbol tables, BNF grammar, different parsing methods, etc. Has anyone else here read/seen this book and can you remember the exact titles?

qubex 6y ago

Tangentially related: I must enjoyed Polygen (https://polygen.org https://polygen.org) that generates text using a BNF template and I have always wanted to construct a template that generated viable templates (BNF of BNF?) but haven’t ever gotten around to it.