Boundedly \(\text{LR}(k)\)-conflictable grammars (Q1323386)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Boundedly \(\text{LR}(k)\)-conflictable grammars |
scientific article |
Statements
Boundedly \(\text{LR}(k)\)-conflictable grammars (English)
0 references
10 May 1994
0 references
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.
0 references
linear time parsing
0 references
context-free grammars
0 references
ambiguous grammars
0 references
LR\((k)\) parsing
0 references
LR\((k)\) grammar
0 references