Simple chain grammars

Anton Nijholt; Arto Salomaa; Magnus Steinby

doi:10.1007/3-540-08342-1_27

Simple chain grammars

Anton Nijholt, Arto Salomaa (Editor), Magnus Steinby (Editor)

Research output: Contribution to conference › Paper › peer-review

4 Citations (Scopus)

93 Downloads (Pure)

Abstract

A subclass of the LR(0)-grammars, the class of simple chain grammars is introduced. Although there exist simple chain grammars which are not LL(k) for any k, this new class of grammars is very close related to the class of LL(1) and simple LL(1) grammars. In fact it can be proved (not in this paper) that each simple chain grammar has an equivalent simple LL(1) grammar. A very simple (bottom-up) parsing method is provided. This method follows directly from the definition of a simple chain grammar and can easily be given in terms of the well-known LR(0) parsing method.

Original language	Undefined
Pages	352-364
Number of pages	13
DOIs	https://doi.org/10.1007/3-540-08342-1_27
Publication status	Published - Jul 1977
Event	Fourth Conference on Automata, Languages and Programming - Turku, Finland Duration: 18 Jul 1977 → 22 Jul 1977

Conference

Conference	Fourth Conference on Automata, Languages and Programming
Period	18/07/77 → 22/07/77
Other	18-22 July 1977

Keywords

IR-66788
EWI-8807

Access to Document

10.1007/3-540-08342-1_27

icalp1977Final published version, 707 KB

Cite this

@conference{2868cc7bbf2e40c7b4aa93ec068d9b81,

title = "Simple chain grammars",

abstract = "A subclass of the LR(0)-grammars, the class of simple chain grammars is introduced. Although there exist simple chain grammars which are not LL(k) for any k, this new class of grammars is very close related to the class of LL(1) and simple LL(1) grammars. In fact it can be proved (not in this paper) that each simple chain grammar has an equivalent simple LL(1) grammar. A very simple (bottom-up) parsing method is provided. This method follows directly from the definition of a simple chain grammar and can easily be given in terms of the well-known LR(0) parsing method.",

keywords = "IR-66788, EWI-8807",

author = "Anton Nijholt and Arto Salomaa and Magnus Steinby",

year = "1977",

month = jul,

doi = "10.1007/3-540-08342-1_27",

language = "Undefined",

pages = "352--364",

note = "Fourth Conference on Automata, Languages and Programming ; Conference date: 18-07-1977 Through 22-07-1977",

}

TY - CONF

T1 - Simple chain grammars

AU - Nijholt, Anton

A2 - Salomaa, Arto

A2 - Steinby, Magnus

PY - 1977/7

Y1 - 1977/7

N2 - A subclass of the LR(0)-grammars, the class of simple chain grammars is introduced. Although there exist simple chain grammars which are not LL(k) for any k, this new class of grammars is very close related to the class of LL(1) and simple LL(1) grammars. In fact it can be proved (not in this paper) that each simple chain grammar has an equivalent simple LL(1) grammar. A very simple (bottom-up) parsing method is provided. This method follows directly from the definition of a simple chain grammar and can easily be given in terms of the well-known LR(0) parsing method.

AB - A subclass of the LR(0)-grammars, the class of simple chain grammars is introduced. Although there exist simple chain grammars which are not LL(k) for any k, this new class of grammars is very close related to the class of LL(1) and simple LL(1) grammars. In fact it can be proved (not in this paper) that each simple chain grammar has an equivalent simple LL(1) grammar. A very simple (bottom-up) parsing method is provided. This method follows directly from the definition of a simple chain grammar and can easily be given in terms of the well-known LR(0) parsing method.

KW - IR-66788

KW - EWI-8807

U2 - 10.1007/3-540-08342-1_27

DO - 10.1007/3-540-08342-1_27

M3 - Paper

SP - 352

EP - 364

T2 - Fourth Conference on Automata, Languages and Programming

Y2 - 18 July 1977 through 22 July 1977

ER -