LL conflict resolution using the embedded left LR parser

Bostjan Slivnik1

  1. University of Ljubljana, Faculty of Computer and Information Science
    Trzaska cesta 25, 1000 Ljubljana, Slovenia
    bostjan.slivnik@fri.uni-lj.si

Abstract

A method for resolving LL(k) conflicts using small LR(k) parsers (called embedded left LR(k) parsers) is described. An embedded left LR(k) parser is capable of (a) producing the prefix of the left parse of the input string and (b) stopping not on the end-of-file marker but on any string from the set of lookahead strings fixed at the parser generation time. The conditions regarding the termination of the embedded left LR(k) parser if used within LL(k) (and similar) parsers are defined and examined in-depth. It is proved that an LL(k) parser augmented with a set of embedded left LR(k) parsers can parse any deterministic context-free grammar in the same asymptotic time as LR(k) parser. As the embedded left LR(k) parser produces the prefix of the left parse, the LL(k) parser augmented with embedded left LR(k) parsers still produces the left parse and the compiler writer does not need to bother with different parsing strategies during the compiler implementation.

Key words

embedded parsing, left LR parsing, LL conflicts

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS111216023S

Publication information

Volume 9, Issue 3 (September 2012)
Special Issue on Advances in Computer Languages, Modeling and Agents
Year of Publication: 2012
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Slivnik, B.: LL conflict resolution using the embedded left LR parser. Computer Science and Information Systems, Vol. 9, No. 3, 1105-1124. (2012), https://doi.org/10.2298/CSIS111216023S