On the covering of parsable grammars

Anton Nijholt

doi:10.1016/S0022-0000(77)80027-5

On the covering of parsable grammars

Anton Nijholt

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

6 Citations (Scopus)

52 Downloads (Pure)

Abstract

The notion of a parsable grammar is introduced. A definition of cover is provided which is a generalization of a well-known definition of cover. With this new definition of cover we prove that every parsable grammar is covered by an LR(1) grammar or, if the language is prefic-free, by a strict-deterministic grammar. A consequence of this result is that every LR(k) grammar is covered by an LR(1) or a strict deterministic grammar.

Original language	English
Pages (from-to)	99-110
Number of pages	12
Journal	Journal of computer and system sciences
Volume	15
Issue number	1
DOIs	https://doi.org/10.1016/S0022-0000(77)80027-5
Publication status	Published - Aug 1977

Keywords

HMI-SLT: Speech and Language Technology

Access to Document

10.1016/S0022-0000(77)80027-5Licence: Other

jcss1977
open
Final published version, 1.65 MBLicence: Other

Cite this

@article{a1ad8edaa5a9463ebc7d54671207e93a,

title = "On the covering of parsable grammars",

abstract = "The notion of a parsable grammar is introduced. A definition of cover is provided which is a generalization of a well-known definition of cover. With this new definition of cover we prove that every parsable grammar is covered by an LR(1) grammar or, if the language is prefic-free, by a strict-deterministic grammar. A consequence of this result is that every LR(k) grammar is covered by an LR(1) or a strict deterministic grammar.",

keywords = "HMI-SLT: Speech and Language Technology",

author = "Anton Nijholt",

year = "1977",

month = aug,

doi = "10.1016/S0022-0000(77)80027-5",

language = "English",

volume = "15",

pages = "99--110",

journal = "Journal of computer and system sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - On the covering of parsable grammars

AU - Nijholt, Anton

PY - 1977/8

Y1 - 1977/8

N2 - The notion of a parsable grammar is introduced. A definition of cover is provided which is a generalization of a well-known definition of cover. With this new definition of cover we prove that every parsable grammar is covered by an LR(1) grammar or, if the language is prefic-free, by a strict-deterministic grammar. A consequence of this result is that every LR(k) grammar is covered by an LR(1) or a strict deterministic grammar.

AB - The notion of a parsable grammar is introduced. A definition of cover is provided which is a generalization of a well-known definition of cover. With this new definition of cover we prove that every parsable grammar is covered by an LR(1) grammar or, if the language is prefic-free, by a strict-deterministic grammar. A consequence of this result is that every LR(k) grammar is covered by an LR(1) or a strict deterministic grammar.

KW - HMI-SLT: Speech and Language Technology

U2 - 10.1016/S0022-0000(77)80027-5

DO - 10.1016/S0022-0000(77)80027-5

M3 - Article

VL - 15

SP - 99

EP - 110

JO - Journal of computer and system sciences

JF - Journal of computer and system sciences

SN - 0022-0000

IS - 1

ER -

On the covering of parsable grammars

Abstract

Keywords

Access to Document

Fingerprint

Cite this