Boundedly \(\text{LR}(k)\)-conflictable grammars
type: Item
instance of: scholarly article
title: Boundedly \(\text{LR}(k)\)-conflictable grammars
zbMATH Open document ID: 0790.68062
DOI: 10.1007/BF01218406
author: Myung-Joon Lee
author: Kwang-Moo Choe
published in: Acta Informatica
publication date: 1994-05-10T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68N20
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 567339
zbMATH Keywords: linear time parsing
zbMATH Keywords: context-free grammars
zbMATH Keywords: ambiguous grammars
zbMATH Keywords: LR\((k)\) parsing
zbMATH Keywords: LR\((k)\) grammar
MaRDI profile type: Publication
cites work: Optimization of LR(k) parsers
cites work: LR-regular grammars - an extension of LR(k) grammars
cites work: Simple LR(k) grammars
cites work: Q4198075
cites work: Complexity metatheorems for context-free grammar problems
cites work: On the translation of languages from left to right
cites work: SLR(k) covering for LR(k) grammars
cites work: On the Complete Covering Problem for LR ( k )Grammars
cites work: A new analysis of LALR formalisms
cites work: Noncanonical Extensions of Bottom-Up Parsing Techniques
cites work: Bounded context parsable grammars
full work available at URL: https://doi.org/10.1007/bf01218406
OpenAlex ID: W2079714538
description: scientific article; zbMATH DE number 567339