Simple chain grammars and languages

Anton Nijholt

doi:10.1016/0304-3975(79)90032-X

Simple chain grammars and languages

Anton Nijholt

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

224 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>0, this new class of grammars is very closely related to the LL(1) and simple LL(1) grammars. In fact it can be shown that every simple chain grammar has an equivalent simple LL(1) grammar. Cover properties for simple chain grammars are investigated and a deterministic pushdown transducer which acts as a right parser for simple chain grammars is presented.

Original language	Undefined
Article number	10.1016/0304-3975(79)90032-X
Pages (from-to)	287-309
Number of pages	23
Journal	Theoretical computer science
Volume	9
Issue number	3
DOIs	https://doi.org/10.1016/0304-3975(79)90032-X
Publication status	Published - Oct 1979

Keywords

EWI-9199
IR-66914
HMI-SLT: Speech and Language Technology

Access to Document

10.1016/0304-3975(79)90032-X

tcs1979Final published version, 2.24 MB

Cite this

@article{30863da48532470eb97a670931e7caf1,

title = "Simple chain grammars and languages",

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>0, this new class of grammars is very closely related to the LL(1) and simple LL(1) grammars. In fact it can be shown that every simple chain grammar has an equivalent simple LL(1) grammar. Cover properties for simple chain grammars are investigated and a deterministic pushdown transducer which acts as a right parser for simple chain grammars is presented.",

keywords = "EWI-9199, IR-66914, HMI-SLT: Speech and Language Technology",

author = "Anton Nijholt",

year = "1979",

month = oct,

doi = "10.1016/0304-3975(79)90032-X",

language = "Undefined",

volume = "9",

pages = "287--309",

journal = "Theoretical computer science",

issn = "0304-3975",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Simple chain grammars and languages

AU - Nijholt, Anton

PY - 1979/10

Y1 - 1979/10

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>0, this new class of grammars is very closely related to the LL(1) and simple LL(1) grammars. In fact it can be shown that every simple chain grammar has an equivalent simple LL(1) grammar. Cover properties for simple chain grammars are investigated and a deterministic pushdown transducer which acts as a right parser for simple chain grammars is presented.

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>0, this new class of grammars is very closely related to the LL(1) and simple LL(1) grammars. In fact it can be shown that every simple chain grammar has an equivalent simple LL(1) grammar. Cover properties for simple chain grammars are investigated and a deterministic pushdown transducer which acts as a right parser for simple chain grammars is presented.

KW - EWI-9199

KW - IR-66914

KW - HMI-SLT: Speech and Language Technology

U2 - 10.1016/0304-3975(79)90032-X

DO - 10.1016/0304-3975(79)90032-X

M3 - Article

SN - 0304-3975

VL - 9

SP - 287

EP - 309

JO - Theoretical computer science

JF - Theoretical computer science

IS - 3

M1 - 10.1016/0304-3975(79)90032-X

ER -