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

DOI10.1007/978-3-642-14162-1_14MaRDI QIDQ3587436zbMATH OpenOpenAlexFDO

Authors Norbert Blum

Publication date 7 September 2010

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

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(17)

• Upper bounds on the size of LR(k) parsers
• Semantic routines and \(LR(k)\) parsers
• Boundedly \(\text{LR}(k)\)-conflictable grammars
• On the size of parsers and \(\text{LR}(k)\)-grammars
• A polynomial-time parsing algorithm for \(K\)-depth languages
• scientific article; zbMATH DE number 4033120 (Why is no real title available?)
• scientific article; zbMATH DE number 4051037 (Why is no real title available?)
• scientific article; zbMATH DE number 60388 (Why is no real title available?)
• scientific article; zbMATH DE number 194074 (Why is no real title available?)
• On the incremental growth and shrinkage of LR goto-graphs
• scientific article; zbMATH DE number 1452980 (Why is no real title available?)
• scientific article; zbMATH DE number 1452981 (Why is no real title available?)
• Efficient LR(1) processor construction
• Complexity of extended vs. classic LR parsers
• On parsing LL-languages
• An improved LALR\((k)\) parser generation for regular right part grammars
• Lower bounds on the size of deterministic parsers

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)