An efficient context-free parsing algorithm

DOI10.1145/362007.362035zbMATH Open0185.43401OpenAlexW4376522561WikidataQ56047564 ScholiaQ56047564MaRDI QIDQ5578055FDOQ5578055

Authors: Jay Earley 

Publication date: 1970

Published in: Communications of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

computer science and automata

Cited In (only showing first 100 items - show all)

• A Yacc extension for LRR grammar parsing
• A sheaf-theoretic approach to pattern matching and related problems
• Parsing as abstract interpretation of grammar semantics
• Approximate matching between a context-free grammar and a finite-state automaton
• Characteristic parsing: A framework for producing compact deterministic parsers. II
• BRNGLR: a cubic Tomita-style GLR parsing algorithm
• Efficient LR(1) parsers
• Exact matching of RNA secondary structure patterns
• Unambiguous Boolean grammars
• Toward discourse representation via pregroup grammars
• Ambiguity and precedence in syntax description
• On the semantic equivalence of language syntax formalisms
• Approximately matching context-free languages
• Direct parsing of ID/LP grammars
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• Simple, functional, sound and complete parsing for all context-free grammars
• If the current clique algorithms are optimal, so is Valiant's parser
• A new one pass algorithm for estimating stochastic context-free grammars
• Interleaving natural language parsing and generation through uniform processing
• Computing abstract decorations of parse forests using dynamic programming and algebraic power series
• Information flow in tabular interpretations for generalized push-down automata
• Parsing schemata and correctness of parsing algorithms
• PHRASE parsers from multi-axiom grammars
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• An extended Earley's algorithm for Petri net controlled grammars without \(\lambda\) rules and cyclic rules
• Recognition mechanisms for schema-based knowledge representations
• Local constraints in programming languages. I: Syntax
• Error-repair parsing schemata
• The weighted grammar constraint
• An efficient recognizer for the Boolean closure of context-free languages
• A syntactic approach based on distortion-tolerant Adjacency Grammars and a spatial-directed parser to interpret sketched diagrams
• Applications of scheduling theory to formal language theory
• Definite clause grammars for language analysis - A survey of the formalism and a comparison with augmented transition networks
• Optimum binary search trees
• Parsing extended LR(k) grammars
• LR-parsing of extended context free grammars
• Top-down syntax nalysis
• SR(s,k) parsers: A class of shift-reduce bounded-context parsers
• Relationships between pushdown automata with counters and complexity classes
• The Earley algorithm as a problem representation
• An efficient all-parses systolic algorithm for general context-free parsing
• Characteristic parsing: A framework for producing compact deterministic parsers. I
• Manipulating derivation forests by scheduling techniques
• Random Generation for Finitely Ambiguous Context-free Languages
• Systolic parsing of context-free languages
• Early action in an Earley parser
• On the incremental growth and shrinkage of LR goto-graphs
• Earley's parsing algorithm and \(k\)-Petri net controlled grammars
• Recursive query processing: The power of logic
• Lexical ambiguity in tree adjoining grammars
• A recursive ascent Earley parser
• Theory and practice of unparsed patterns for metacompilation
• Efficiency of pregroups and the French noun phrase
• Recursive ascent parsing: From Earley to Marcus
• How to produce all sentences from a two-level grammar
• Complexity in left-associative grammar
• A yo-yo parsing algorithm for a large class of van Wijngaarden grammars
• Processing natural language with schema constraint networks
• On the complexity of the recognition of parallel 2D-image languages
• Technical analysis for portofolio trading by syntactic pattern recognition
• A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead
• Precedences in specifications and implementations of programming languages
• An experimental ambiguity detection tool
• Enumerating grammar-based extractions
• Improved normal form for grammars with one-sided contexts
• Classes of formal grammars
• Finding the smallest binarization of a CFG is NP-hard
• Sequential classification of strings generated by SCFG's
• Theory of formal grammars
• Title not available (Why is that?)
• An on-the-fly grammar modification mechanism for composing and defining extensible languages
• Efficient reconfigurable embedded parsers
• Synchronous context-free grammars and optimal linear parsing strategies
• MRG parser for visual languages
• Linear processing with pregroups
• Super-pattern matching
• Syntactic recognizer for expandable languages
• Agenda control for heterogeneous reasoners
• A principled approach to grammars for controlled natural languages and predictive editors
• ASF+SDF parsing tools applied to ELAN
• Enhancing practical TAG parsing efficiency by capturing redundancy
• Recursive inversion models for permutations
• Recognition is not parsing - SPPF-style parsing from cubic recognisers
• Title not available (Why is that?)
• Analyzing ambiguity of context-free grammars
• parallel parsing from recurrence equations
• Chart parsing of scattered context grammars
• Tabulator-Turingmaschine und Komplexität. (Tabulator Turing machine and complexity)
• Fifty Years of Prolog and Beyond
• String editing under pattern constraints
• Towards a Taxonomy for ECFG and RRPG Parsing
• Attribute and unification grammar: A review and analysis of formalisms
• Lessons on off-policy methods from a notification component of a chatbot
• Integrating code generation and peephole optimization
• Schrödinger's token
• Rational transductions and complexity of counting problems
• Rational transductions and complexity of counting problems
• Model Theoretic Syntax and Parsing
• Automatic correction of syntax-errors in programming languages
• Efficient parsing algorithms for general context-free parsers

This page was built for publication: An efficient context-free parsing algorithm

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