Optimization of LR(k) parsers
From MaRDI portal
Publication:2561843
DOI10.1016/S0022-0000(72)80031-XzbMath0264.68032OpenAlexW2032687123MaRDI QIDQ2561843
Publication date: 1972
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(72)80031-x
Related Items
BUP: A bottom-up parser embedded in Prolog, The word problem for groups with regular relations. Improvement of the Knuth-Bendix algorithm, NTS languages are deterministic and congruential, A new one pass algorithm for estimating stochastic context-free grammars, On the size of unambiguous context-free grammars, A nondeterministic program logic, Proof versus formalization, A Yacc extension for LRR grammar parsing, A parallel parsing algorithm for arbitrary context-free grammars, Context-free relations and their characteristics, The interchange or pump (di)lemmas for context-free languages, Representation and uniformization of algebraic transductions, A model of the loop formation process on knitting machines using finite automata theory, On a recursive ascent parser, Gaifman's theorem on categorial grammars revisited, A unified framework for disambiguating finite transductions, On some decision questions concerning pushdown machines, Recognition mechanisms for schema-based knowledge representations, The language intersection problem for non-recursive context-free grammars, Parallel \(LL\) parsing, A method for transforming grammars into LL(k) form, Multipass precedence analysis, Local constraints in programming languages. I: Syntax, Achievable high scores of \(\varepsilon\)-moves and running times in DPDA computations, On the space optimizing effect of eliminating single productions from LR parsers, On parsing two-level grammars, LR(0) grammars generated by LR(0) parsers, Lexical ambiguity in tree adjoining grammars, Some decision problems about controlled rewriting systems, A parsing automata approach to LR theory, Position-restricted grammar forms and grammars, A new proof technique to establish equivalence of the original and the generated lambda-free CFG with linear increase in size, Structure preserving elimination of null productions from context-free grammars, A characterization of Thompson digraphs., A pushdown automaton or a context-free grammar - which is more economical?, Translations on a subclass of LR(k) grammars, Parsing and generation with static discontinuity grammars, An efficient incremental LR parser for grammars with epsilon productions, Automatic average-case analysis of algorithms, Abstract grammars based on transductions, Conflict detection and resolution in a lexical analyzer generator, A syntactic approach to time-varying pattern analysis, Optimization of LR(\(k\)) reduced parsers, On efficient implementation of LR-attributed grammars, An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata, An efficient semantic evaluator for warped LC(1) attributed grammars, Commutation-augmented pregroup grammars and push-down automata with cancellation, Efficient reconfigurable embedded parsers, An NC algorithm for recognizing tree adjoining languages, A functional LR parser, Reversible pushdown automata, Enumeration and generating functions of Rota-Baxter words., An improved bound for detecting looping configurations in deterministic PDA's, Equational tree transformations, Edge-disjoint spanning trees and depth-first search, The membership question for ETOL-languages is polynomially complete, Complete operator precedence, LR-parsing of extended context free grammars, Relative complexity of checking and evaluating, The covering problem for linear context-free grammars, A parallel parsing system for natural language analysis, The polynomial-time hierarchy, Concerning bounded-right-context grammars, An alternative approach to the improvement of LR(k) parsers, A practical general method for constructing LR(k) parsers, A direct algorithm for checking equivalence of LL(k) grammars, A strong pumping lemma for context-free languages, Characteristic parsing: A framework for producing compact deterministic parsers. I, Characteristic parsing: A framework for producing compact deterministic parsers. II, The ELL(1) parser generator and the error recovery mechanism, Classes of formal grammars, LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata, Some decidability results about regular and pushdown translations, Fast recognition of context-sensitive structures, Efficient coding of formalized messages, Systolic parsing of context-free languages, An efficient all-parses systolic algorithm for general context-free parsing, On the enlargement of the class of regular languages by the shuffle closure, Semantic-syntax-directed translation and its application to image processing, On LC(0) grammars and languages, Deterministic acceptors for indexed languages, On regular tree languages and deterministic pushdown automata, Early action in an Earley parser, A metatheorem for undecidable properties of formal languages and its application to LRR and LLR grammars and languages, A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars, On incremental evaluation of ordered attributed grammars, The comparison of the expressive power of first-order dynamic logics, Lower bounds on the size of deterministic parsers, Practical LL(1)-based parsing of van Wijngaarden grammars, Tree pushdown automata, Complexity of normal form grammars, A language-driven generalized numerical database translator, On fault tolerance of syntax, A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead, Decoders with initial state invariance for multivalued encodings, Code migration and program maintainability -- A categorical perspective, On conservative extensions of syntax in system development, The complexity of computing maximal word functions, A class of coders based on gsm, Boundedly \(\text{LR}(k)\)-conflictable grammars, Syntactic/semantic techniques in pattern recognition: A survey, One-Sided Random Context Grammars with Leftmost Derivations, State-complexity of finite-state devices, state compressibility and incompressibility, LL(1) grammars and Sub-LL(1) grammars, CALS technologies and tolerant translators, DM-automata and classes of context-free languages, Syntactic recognizer for expandable languages, Incremental construction of minimal tree automata, An experimental ambiguity detection tool, Decidability of the problem of semantic equivalence of words in the class of syntax-directed translations, Algorithms for minimization of finite acyclic automata and pattern matching in terms, Deterministic realization of nondeterministic computations with a low measure of nondeterminism, Epsilon weak precedence grammars and languages, Unnamed Item, Inferability of context-free programmed grammars, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, Rational transductions and complexity of counting problems, Ogden's lemma for nonterminal bounded languages, Analyzing Ambiguity of Context-Free Grammars, Error detection in precedence parsers, Computational complexity of formal translations, Unnamed Item, Unnamed Item, Concerning existential definition of the class \(NP\): Theoretical analysis of an alternative approach, An error-correcting syntactic decoder for computer networks, Unnamed Item, Unnamed Item, New problems complete for nondeterministic log space, Some theoretical aspects of parallel parsing, Unnamed Item, The Strong, Weak, and Very Weak Finite Context and Kernel Properties, Linear Parsing Expression Grammars, A note on weak operator precedence grammars, Grammar functors and covers: From non-left-recursive to greibach normal form grammars, Deep pushdown automata, Direct parsing of ID/LP grammars, Analyzing ambiguity of context-free grammars, Normal form algorithms for extended context-free grammars, On parsing LL-languages, On parsing and condensing substrings of LR languages in linear time, Unnamed Item, On comparingLL(k) andLR(k) grammars, Unnamed Item, Transductions Computed by PC-Systems of Monotone Deterministic Restarting Automata, Finite Automata as Time-Inv Linear Systems Observability, Reachability and More, Fuzzy pushdown automata, Parsers for indexed grammars, A new definition for simple precedence grammars, String and graph grammar characterizations of bounded regular languages, Deterministic Stack Transducers, Comparisons between some pumping conditions for context-free languages, Theory of language processors and parallel computations, Theory of language processors and parallel computations, Inference of a class of CFPG by means of semantic rules, Sublogarithmic ambiguity, Measuring nondeterminism in pushdown automata, Fuzzy context-free languages. I: Generalized fuzzy context-free grammars, Greibach normal form transformation revisited., Computing a context-free grammar-generating series, On reducing the number of states in a PDA, Synchronous context-free grammars and optimal linear parsing strategies, Random Generation for Finitely Ambiguous Context-free Languages
