On the reduction of LR(k) parsers

DOI10.1016/0020-0190(93)90134-UMaRDI QIDQ688231zbMATH OpenOpenAlexFDO

Authors Woo-Jun Park, Myung-Joon Lee, Kwang-Moo Choe

Publication date 24 August 1995

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90134-u

zbMATH Keywords

optimal reductionparsing theorywell-defined reduction

Mathematics Subject Classification ID

Theory of compilers and interpreters (68N20)

Review text

We propose a new formalism for merging \(LR(k)\) states without any conflict, after constructing the full \(LR(k)\) parsing table. First, we define a new relation compatible \(C\) and \(C\)-covering for a core block, both of which are different from the notion in dynamic reduction methods. Then, we propose well-defined reduction (WDR) which is a set of \(C\)- covering for each core block which reflect the rationale for \(LR(k)\) state reduction, as a new formalism. We present algorithms to compute a WDR and an \(LR(k)\)-based parser for the reduction. Furthermore, we introduce a useful core-restricted method, a locally optimal reduction as an approximation to an optimal reduction. The contribution of this paper to \(LR(k)\) parsing theory is summarized as follows: (1) to discover that set of \(LR(k)\) states of a core block after the merging is not a partition, but a covering of the block. (2) to propose WDR which provides a new formal view for the computation of an optimal reduction.

Recommendations

• Optimization of LR(\(k\)) reduced parsers
• scientific article; zbMATH DE number 4100631
• scientific article; zbMATH DE number 434493
• LR-parsing derived
• scientific article; zbMATH DE number 194074

Cites work

• A lattice-theoretical fixpoint theorem and its applications
• A new analysis of LALR formalisms
• A parsing automata approach to LR theory
• A practical general method for constructing LR(k) parsers
• scientific article; zbMATH DE number 3485226 (Why is no real title available?)
• scientific article; zbMATH DE number 3490427 (Why is no real title available?)
• On the reduction of \(LR(k)\) parsers
• On the translation of languages from left to right
• Simple LR(k) grammars
• SLR(k) covering for LR(k) grammars

Cited in

(13)

• Upper bounds on the size of LR(k) parsers
• Parameter-reduction of higher level grammars
• Optimization of LR(\(k\)) reduced parsers
• On the size of parsers and \(\text{LR}(k)\)-grammars
• On the prediction of reduction goals: A deterministic approach
• Some observations on LR-like parsing with delayed reduction
• scientific article; zbMATH DE number 434493 (Why is no real title available?)
• Redundancy of the Lempel-Ziv incremental parsing rule
• scientific article; zbMATH DE number 1076489 (Why is no real title available?)
• scientific article; zbMATH DE number 827977 (Why is no real title available?)
• scientific article; zbMATH DE number 1452981 (Why is no real title available?)
• Practical optimization of LR(1) parsers
• On the reduction of \(LR(k)\) parsers

This page was built for publication: On the reduction of \(LR(k)\) parsers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688231)