Boundedly \(\text{LR}(k)\)-conflictable grammars (Q1323386)

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.