DC Field | Value | Language |
---|---|---|
dc.contributor.author | LEE, MJ | ko |
dc.contributor.author | Choe, Kwang-Moo | ko |
dc.date.accessioned | 2013-02-25T19:01:11Z | - |
dc.date.available | 2013-02-25T19:01:11Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 1994-04 | - |
dc.identifier.citation | ACTA INFORMATICA, v.31, no.3, pp.261 - 283 | - |
dc.identifier.issn | 0001-5903 | - |
dc.identifier.uri | http://hdl.handle.net/10203/64513 | - |
dc.description.abstract | 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 occurences 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. | - |
dc.language | English | - |
dc.publisher | SPRINGER VERLAG | - |
dc.subject | LR(K) GRAMMARS | - |
dc.title | BOUNDEDLY LR(K)-CONFLICTABLE GRAMMARS | - |
dc.type | Article | - |
dc.identifier.wosid | A1994NJ04000003 | - |
dc.identifier.scopusid | 2-s2.0-34249769949 | - |
dc.type.rims | ART | - |
dc.citation.volume | 31 | - |
dc.citation.issue | 3 | - |
dc.citation.beginningpage | 261 | - |
dc.citation.endingpage | 283 | - |
dc.citation.publicationname | ACTA INFORMATICA | - |
dc.contributor.localauthor | Choe, Kwang-Moo | - |
dc.contributor.nonIdAuthor | LEE, MJ | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordPlus | LR(K) GRAMMARS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.