Some observations on LR-like parsing with delayed reduction

E. Bertsch; M.-J. Nederhof

doi:10.1016/j.ipl.2007.07.003

Some observations on LR-like parsing with delayed reduction

E. Bertsch, M.-J. Nederhof

School of Computer Science

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

Abstract

We discuss a bottom-up parsing technique based on delayed reductions, and investigate its capabilities and limitations. Some non LR(k) grammars, for any k, are handled deterministically by this method. Surprisingly, and counter-intuitively from the viewpoint of LR(k), increase of delay may lead to decrease of determinism. We also present a variant that uses both delay and lookahead. (C) 2007 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	195-199
Number of pages	5
Journal	Information Processing Letters
Volume	104
DOIs	https://doi.org/10.1016/j.ipl.2007.07.003
Publication status	Published - 16 Dec 2007

Keywords

formal languages
grammars
parsing
LR(k)

Access to Document

10.1016/j.ipl.2007.07.003

Cite this

@article{6183b66c9bc742b5b7135a9cd25f9529,

title = "Some observations on LR-like parsing with delayed reduction",

abstract = "We discuss a bottom-up parsing technique based on delayed reductions, and investigate its capabilities and limitations. Some non LR(k) grammars, for any k, are handled deterministically by this method. Surprisingly, and counter-intuitively from the viewpoint of LR(k), increase of delay may lead to decrease of determinism. We also present a variant that uses both delay and lookahead. (C) 2007 Elsevier B.V. All rights reserved.",

keywords = "formal languages, grammars, parsing, LR(k)",

author = "E. Bertsch and M.-J. Nederhof",

year = "2007",

month = dec,

day = "16",

doi = "10.1016/j.ipl.2007.07.003",

language = "English",

volume = "104",

pages = "195--199",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

}

TY - JOUR

T1 - Some observations on LR-like parsing with delayed reduction

AU - Bertsch, E.

AU - Nederhof, M.-J.

PY - 2007/12/16

Y1 - 2007/12/16

N2 - We discuss a bottom-up parsing technique based on delayed reductions, and investigate its capabilities and limitations. Some non LR(k) grammars, for any k, are handled deterministically by this method. Surprisingly, and counter-intuitively from the viewpoint of LR(k), increase of delay may lead to decrease of determinism. We also present a variant that uses both delay and lookahead. (C) 2007 Elsevier B.V. All rights reserved.

AB - We discuss a bottom-up parsing technique based on delayed reductions, and investigate its capabilities and limitations. Some non LR(k) grammars, for any k, are handled deterministically by this method. Surprisingly, and counter-intuitively from the viewpoint of LR(k), increase of delay may lead to decrease of determinism. We also present a variant that uses both delay and lookahead. (C) 2007 Elsevier B.V. All rights reserved.

KW - formal languages

KW - grammars

KW - parsing

KW - LR(k)

UR - http://www.scopus.com/inward/record.url?scp=34548397101&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2007.07.003

DO - 10.1016/j.ipl.2007.07.003

M3 - Article

SN - 0020-0190

VL - 104

SP - 195

EP - 199

JO - Information Processing Letters

JF - Information Processing Letters

ER -

Some observations on LR-like parsing with delayed reduction

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this