An efficient context-free parsing algorithm
From MaRDI portal
Publication:5578055
DOI10.1145/362007.362035zbMath0185.43401OpenAlexW4376522561WikidataQ56047564 ScholiaQ56047564MaRDI QIDQ5578055
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
Related Items (only showing first 100 items - show all)
Applications of scheduling theory to formal language theory ⋮ Earley’s Parsing Algorithm and k-Petri Net Controlled Grammars ⋮ A new one pass algorithm for estimating stochastic context-free grammars ⋮ Unnamed Item ⋮ A Yacc extension for LRR grammar parsing ⋮ Attribute and unification grammar: A review and analysis of formalisms ⋮ Finding the smallest binarization of a CFG is NP-hard ⋮ Recursive inversion models for permutations ⋮ Super-pattern matching ⋮ Syntactic recognizer for expandable languages ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Recognition is not parsing - SPPF-style parsing from cubic recognisers ⋮ An experimental ambiguity detection tool ⋮ Recognition mechanisms for schema-based knowledge representations ⋮ Characterizations and extensions of pushdown translations ⋮ Rational transductions and complexity of counting problems ⋮ Interleaving natural language parsing and generation through uniform processing ⋮ Parsing schemata and correctness of parsing algorithms ⋮ Computing abstract decorations of parse forests using dynamic programming and algebraic power series ⋮ Information flow in tabular interpretations for generalized push-down automata ⋮ PHRASE parsers from multi-axiom grammars ⋮ A syntactic approach based on distortion-tolerant Adjacency Grammars and a spatial-directed parser to interpret sketched diagrams ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Rational transductions and complexity of counting problems ⋮ Parsing extended LR(k) grammars ⋮ Local constraints in programming languages. I: Syntax ⋮ Definite clause grammars for language analysis - A survey of the formalism and a comparison with augmented transition networks ⋮ A recognition and parsing algorithm for arbitrary conjunctive grammars. ⋮ On the semantic equivalence of language syntax formalisms ⋮ Lexical ambiguity in tree adjoining grammars ⋮ parallel parsing from recurrence equations ⋮ Sequential classification of strings generated by SCFG's ⋮ SR(s,k) parsers: A class of shift-reduce bounded-context parsers ⋮ An extended Earley's algorithm for Petri net controlled grammars without \(\lambda\) rules and cyclic rules ⋮ On the incremental growth and shrinkage of LR goto-graphs ⋮ BRNGLR: a cubic Tomita-style GLR parsing algorithm ⋮ A recursive ascent Earley parser ⋮ Approximately matching context-free languages ⋮ Precedences in specifications and implementations of programming languages ⋮ Linear processing with pregroups ⋮ Unambiguous Boolean grammars ⋮ Using attributed flow graph parsing to recognize clichés in programs ⋮ Schrödinger's token ⋮ An on-the-fly grammar modification mechanism for composing and defining extensible languages ⋮ Efficient reconfigurable embedded parsers ⋮ A sheaf-theoretic approach to pattern matching and related problems ⋮ Recursive ascent parsing: From Earley to Marcus ⋮ 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 ⋮ Relationships between pushdown automata with counters and complexity classes ⋮ A principled approach to grammars for controlled natural languages and predictive editors ⋮ Model Theoretic Syntax and Parsing ⋮ Agenda control for heterogeneous reasoners ⋮ Automatic correction of syntax-errors in programming languages ⋮ The weighted grammar constraint ⋮ The Earley algorithm as a problem representation ⋮ Efficient parsing algorithms for general context-free parsers ⋮ Ambiguity and precedence in syntax description ⋮ Direct parsing of ID/LP grammars ⋮ Theory and practice of unparsed patterns for metacompilation ⋮ Analyzing ambiguity of context-free grammars ⋮ A syntactic approach to fingerprint pattern recognition ⋮ Error-repair parsing schemata ⋮ LR-parsing of extended context free grammars ⋮ Sequentielle Analyse kontextfreier Sprachen ⋮ Efficiency of pregroups and the French noun phrase ⋮ Exact matching of RNA secondary structure patterns ⋮ Characteristic parsing: A framework for producing compact deterministic parsers. I ⋮ Characteristic parsing: A framework for producing compact deterministic parsers. II ⋮ Classes of formal grammars ⋮ Towards a Taxonomy for ECFG and RRPG Parsing ⋮ Toward discourse representation via pregroup grammars ⋮ Unnamed Item ⋮ Recursive query processing: The power of logic ⋮ Systolic parsing of context-free languages ⋮ An efficient all-parses systolic algorithm for general context-free parsing ⋮ Manipulating derivation forests by scheduling techniques ⋮ Enhancing Practical TAG Parsing Efficiency by Capturing Redundancy ⋮ Integrating code generation and peephole optimization ⋮ Tabulator-Turingmaschine und Komplexität. (Tabulator Turing machine and complexity) ⋮ Simple, Functional, Sound and Complete Parsing for All Context-Free Grammars ⋮ Optimum binary search trees ⋮ Top-down syntax nalysis ⋮ Efficient LR(1) parsers ⋮ Lessons on off-policy methods from a notification component of a chatbot ⋮ Early action in an Earley parser ⋮ A divide-and-conquer approach to general context-free parsing ⋮ Theory of formal grammars ⋮ Parsing as abstract interpretation of grammar semantics ⋮ How to produce all sentences from a two-level grammar ⋮ 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 ⋮ Improved normal form for grammars with one-sided contexts ⋮ On the complexity of the recognition of parallel 2D-image languages ⋮ Technical analysis for portofolio trading by syntactic pattern recognition ⋮ Synchronous context-free grammars and optimal linear parsing strategies ⋮ Random Generation for Finitely Ambiguous Context-free Languages ⋮ Approximate matching between a context-free grammar and a finite-state automaton ⋮ Chart parsing of scattered context grammars
This page was built for publication: An efficient context-free parsing algorithm
