On LR(k)-parsers of polynomial size (extended abstract)

DOI10.1007/978-3-642-14162-1_14zbMATH Open1288.68143arXiv1511.05770OpenAlexW1532817621MaRDI QIDQ3587436FDOQ3587436

Authors: Norbert Blum 

Publication date: 7 September 2010

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Abstract: Usually, a parser for an $LR(k)$-grammar $G$ is a deterministic pushdown transducer which produces backwards the unique rightmost derivation for a given input string $xinL(G)$. The best known upper bound for the size of such a parser is $O(2^{|G||Sigma{|}^k+klog|Sigma|+log|G|})$ where $|G|$ and $|Sigma|$ are the sizes of the grammar $G$ and the terminal alphabet $Sigma$, respectively. If we add to a parser the possibility to manipulate a directed graph of size $O(|G|n)$ where $n$ is the length of the input then we obtain an extended parser. The graph is used for an efficient parallel simulation of all potential leftmost derivations of the current right sentential form such that the unique rightmost derivation of the input can be computed. Given an arbitrary $LR(k)$-grammar $G$, we show how to construct an extended parser of $$ size where $|N|$ is the number of nonterminal symbols and $$ is the number of relevant lookaheads with respect to the grammar $G$. As the usual parser, this extended parser uses only tables as data structure. Using some ingenious data structures and increasing the parsing time by a small constant factor, the size of the extended parser can be reduced to $$. The parsing time is $O(ld(input)+k|G|n)$ where $ld(input)$ is the length of the derivation of the input. Moreover, we have constructed a one pass parser.

Full work available at URL: https://arxiv.org/abs/1511.05770

Recommendations

• Upper bounds on the size of LR(k) parsers
• scientific article; zbMATH DE number 1452980
• scientific article; zbMATH DE number 1076489
• On parsing LL-languages
• Optimization of LR(\(k\)) reduced parsers

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cited In (16)

• Title not available (Why is that?)
• An improved LALR\((k)\) parser generation for regular right part grammars
• On parsing LL-languages
• Title not available (Why is that?)
• Efficient \(LR(1)\) processor construction
• A polynomial-time parsing algorithm for \(K\)-depth languages
• Semantic routines and \(LR(k)\) parsers
• Complexity of extended vs. classic LR parsers
• On the incremental growth and shrinkage of LR goto-graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds on the size of deterministic parsers
• Upper bounds on the size of LR(k) parsers
• Title not available (Why is that?)
• On the size of parsers and \(\text{LR}(k)\)-grammars
• Title not available (Why is that?)

This page was built for publication: On \(\mathrm{LR}(k)\)-parsers of polynomial size (extended abstract)

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