4 ms·

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.

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.