Boundedly \(\text{LR}(k)\)-conflictable grammars (Q1323386): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf01218406 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2079714538 / rank | |||
Normal rank |
Latest revision as of 12:15, 30 July 2024
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