An Improved Context-Free Recognizer

DOI10.1145/357103.357112zbMath0461.68084OpenAlexW2047092246MaRDI QIDQ3911426

Susan L. Graham, Michael A. Harrison, Walter L. Ruzzo

Publication date: 1980

Published in: ACM Transactions on Programming Languages and Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/357103.357112

zbMATH Keywords

dynamic programmingdata structurescontext-free grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20) Theory of operating systems (68N25)

Related Items

Algebraic dynamic programming for multiple context-free grammars ⋮ Decision problems for word-hyperbolic semigroups ⋮ Finding the smallest binarization of a CFG is NP-hard ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ A recognition and parsing algorithm for arbitrary conjunctive grammars. ⋮ New architectures for constructed complex systems ⋮ Schrödinger's token ⋮ Efficient reconfigurable embedded parsers ⋮ Sparse RNA folding: time and space efficient algorithms ⋮ Direct parsing of ID/LP grammars ⋮ A divide-and-conquer approach to general context-free parsing ⋮ An efficient recognizer for the Boolean closure of context-free languages ⋮ Parallel on-line parsing in constant time per word ⋮ A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead ⋮ Improved normal form for grammars with one-sided contexts