3 ms·

I was quite impressed with GLR parsers, as they can deal really well with ambiguity and are relatively easy to implement. They have limited adoption though as t

I was quite impressed with GLR parsers, as they can deal really well with ambiguity and are relatively easy to implement. They have limited adoption though as they have high constant overhead and hand-written recursive-descent parsers can easily outcompete them for most languages. The Elkhound paper [1] explains GLR parsing in detail and is quite enjoyable to read. 1: https://people.eecs.berkeley.edu/~necula/Papers/elkhound_cc04.pdf https://people.eecs.berkeley.edu/~necula/Papers/elkhound_cc0...

082349872349872 4y ago
The point of TFA is why reach for GLA, why even pay a cost for ambiguity, if you have control over the grammar, and can specify an unambiguous one to begin with? IMNSHO we should be aware of "big hammer" solutions but not be afraid to pick concrete representations when they make things easy on the machine. (in particular, tests using the former are wonderful double checks for deployment candidates using the latter) [when would specifying an unambiguous grammar be premature optimisation? when changing the language later is cheap (unlikely!), or when the strings in that language are always going to be of size <= k. Nerd snipe: what —to order of magnitude— is k ca. 2023?]
- nine_k 4y ago
  Unambiguous grammars are easy not just to machines. Most importantly, they matter to humans. Reading something like Lua or Golang or SQL is usually much easier than C++, to say nothing of Perl.
- sshine 4y ago
  > we should be aware of "big hammer" solutions Parser combinators have become my preferred "medium hammer" strategy: Sometimes you get a more readable parser than if you use regex, even though your language is regular. Sometimes you get corner cases where you have to think and an LR parser generator wouldn't require thinking. On the other hand, you have one tool that almost always does the job well, is readable, and embeds nicely.

082349872349872 4y ago

The point of TFA is why reach for GLA, why even pay a cost for ambiguity, if you have control over the grammar, and can specify an unambiguous one to begin with? IMNSHO we should be aware of "big hammer" solutions but not be afraid to pick concrete representations when they make things easy on the machine. (in particular, tests using the former are wonderful double checks for deployment candidates using the latter) [when would specifying an unambiguous grammar be premature optimisation? when changing the language later is cheap (unlikely!), or when the strings in that language are always going to be of size <= k. Nerd snipe: what —to order of magnitude— is k ca. 2023?]

nine_k 4y ago
Unambiguous grammars are easy not just to machines. Most importantly, they matter to humans. Reading something like Lua or Golang or SQL is usually much easier than C++, to say nothing of Perl.
sshine 4y ago
> we should be aware of "big hammer" solutions Parser combinators have become my preferred "medium hammer" strategy: Sometimes you get a more readable parser than if you use regex, even though your language is regular. Sometimes you get corner cases where you have to think and an LR parser generator wouldn't require thinking. On the other hand, you have one tool that almost always does the job well, is readable, and embeds nicely.