An Improved Context-Free Recognizer

DOI10.1145/357103.357112MaRDI QIDQ3911426zbMATH OpenOpenAlexFDO

Authors 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

context-free grammarsdata structuresdynamic programming

Mathematics Subject Classification ID

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

Cited in

(17)

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

This page was built for publication: An Improved Context-Free Recognizer

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