Olof (2022-12-12 20:57:44) Permalink
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.