I need a way of generating parsers for all deterministic context-free grammars.
I know that every deterministic context-free grammar can be parsed by some LR(k) parser. The problem is that I need to generate parsers for grammars of unknown k. So, to handle every deterministic context-free grammar, k would need to be infinite.
I also know that GLR parsers can parse all context-free grammars, deterministic or not. But I need to reject non-deterministic grammars. I'm not sure if GLR can detect that property from an input grammar.
Is there a type of parser generator that can handle all deterministic context-free grammars, while rejecting non-deterministic grammars, without needing a k input? (The only input is the grammar itself)
The problem of “given a CFG, decide whether it’s LR(k) for any k” is, surprisingly, undecidable! This means that it’s not possible for any parser generator to always be able to take an arbitrary grammar and determine which choice of k to use, or even if such a choice of k exists.
In practice, most grammars that we care about are fairly close to LR(1), for some definition of “fairly close,” which is why most parser generators focus on that simpler case.