Boundedly \(\text{LR}(k)\)-conflictable grammars
We present a new class of context-free grammars whose sentences are parsable in linear time and space. The class called boundedly LR\((k)\)- conflictable (BLRC\((k))\) grammars includes all LR\((k)\) grammars, some non-LR unambiguous grammars and some boundedly ambiguous grammars. A context-free grammar is said to be BLRC\((k)\) if the number of conflict occurrences during LR\((k)\) parsing for every sentence of the grammar is inherently bounded. A BLRC\((k)\) grammar can be considered as a natural extension of an LR\((k)\) grammar whose sentences can be parsed by an LR\((k)\) manner with multiple stacks. We show that it is a decidable problem whether a context-free grammar is BLRC\((k)\) for a given \(k\), whereas it is undecidable for arbitrary \(k\). The result is derived from an LR\((k)\) machine description grammar which describes the behavior of a given LR\((k)\) parser in terms of the grammar symbols. The relationship between the class of BLRC\((k)\) grammars (and languages) and those of other associated grammars (and languages), is also discussed.
scientific article; zbMATH DE number 567339