Linear-time suffix parsing for deterministic languages

M J Nederhof; E Bertsch

doi:10.1145/233551.233555

Linear-time suffix parsing for deterministic languages

M J Nederhof^*, E Bertsch

^*Corresponding author for this work

Faculty of Arts

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

8 Citations (Scopus)

Abstract

We present a linear-time algorithm to decide for any fixed deterministic context-free language L and input string w whether w is a suffix of some string in L. In contrast to a previously published technique, the decision procedure may be extended to produce syntactic structures (parses) without an increase in time complexity. We also show how this algorithm may be applied to process incorrect input in linear time.

Original language	English
Pages (from-to)	524-554
Number of pages	31
Journal	Journal of the Association for Computing Machinery
Volume	43
Issue number	3
DOIs	https://doi.org/10.1145/233551.233555
Publication status	Published - May-1996

Keywords

SYNTAX ERROR RECOVERY
ALGORITHM

Access to Document

10.1145/233551.233555

Handle.net

Persistent link

Embargoed Document

Linear-time suffix parsing for deterministic languages
Final publisher's version, 2.3 MB

Cite this

@article{e2fe94d687c94f05a4d9846dc1e9da5f,

title = "Linear-time suffix parsing for deterministic languages",

abstract = "We present a linear-time algorithm to decide for any fixed deterministic context-free language L and input string w whether w is a suffix of some string in L. In contrast to a previously published technique, the decision procedure may be extended to produce syntactic structures (parses) without an increase in time complexity. We also show how this algorithm may be applied to process incorrect input in linear time.",

keywords = "SYNTAX ERROR RECOVERY, ALGORITHM",

author = "Nederhof, {M J} and E Bertsch",

year = "1996",

month = may,

doi = "10.1145/233551.233555",

language = "English",

volume = "43",

pages = "524--554",

journal = "Journal of the Association for Computing Machinery",

number = "3",

}

TY - JOUR

T1 - Linear-time suffix parsing for deterministic languages

AU - Nederhof, M J

AU - Bertsch, E

PY - 1996/5

Y1 - 1996/5

N2 - We present a linear-time algorithm to decide for any fixed deterministic context-free language L and input string w whether w is a suffix of some string in L. In contrast to a previously published technique, the decision procedure may be extended to produce syntactic structures (parses) without an increase in time complexity. We also show how this algorithm may be applied to process incorrect input in linear time.

AB - We present a linear-time algorithm to decide for any fixed deterministic context-free language L and input string w whether w is a suffix of some string in L. In contrast to a previously published technique, the decision procedure may be extended to produce syntactic structures (parses) without an increase in time complexity. We also show how this algorithm may be applied to process incorrect input in linear time.

KW - SYNTAX ERROR RECOVERY

KW - ALGORITHM

U2 - 10.1145/233551.233555

DO - 10.1145/233551.233555

M3 - Article

VL - 43

SP - 524

EP - 554

JO - Journal of the Association for Computing Machinery

JF - Journal of the Association for Computing Machinery

IS - 3

ER -

Linear-time suffix parsing for deterministic languages

Abstract

Keywords

Access to Document

Handle.net

Embargoed Document

Fingerprint

Cite this