I think it can be a good idea to also mention Floyd's operator precendence grammars. They still parse most languages you can think of, have closure properties similar to regular expressions, are very convenient for implementing math grammars, and have a notion of local parsability (each node of the parse tree corresponds to subsets of the string with different branches being overlapping) that make them really good for incremental parsing (i.e. updating the parse tree in log time as you type since you can do tree search for the node that changed and propagate changes up), which is really useful for editor plugins. Local parsability is also very good for error recovery since the kinds of parse errors you can get are guarenteed to be local.
The article fails to see that both LL and LR are back-tracking less parsers. In the times these parser were developed, creating a back-tracking parser was just out of the question, because memory restrictions did not allow files to be stored in RAM. Memorization is a powerfull technique to reduce the negative impact of back-tracking. Again it was not considered a valid solution to creating parsers (in the old days) because of its memory overhead. Nowadays, there is no reason to not use a back-tracking parser and for many use cases, they are just efficient enough. See for example https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStudio.html which parses the whole input again on each edit of the input.
Tony Smith (2025-02-14T10:55:55.694572949+00:00) Permalink
Great article - thank you. I'm looking at implementing a DSL in Rust and will definitely look at gmrtools. One thought I'll offer is that I found a simple explanation of a shift/reduce conflict was "my grammar is ambiguous because my parser doesn't know whether to shift the next token, or reduce what it has so far". This will be obvious to those who write a lot of parsers, but as someone who does it rarely, this was a key insight and maybe it'll help others.