Optimization of LR(k) parsers
From MaRDI portal
Publication:2561843
DOI10.1016/S0022-0000(72)80031-XzbMath0264.68032MaRDI QIDQ2561843
Publication date: 1972
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68Q45: Formal languages and automata
Related Items
A parallel parsing system for natural language analysis, On some decision questions concerning pushdown machines, Recognition mechanisms for schema-based knowledge representations, The language intersection problem for non-recursive context-free 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, An NC algorithm for recognizing tree adjoining languages, 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, 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, Complexity of normal form grammars, A language-driven generalized numerical database translator, 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, On conservative extensions of syntax in system development, Representation and uniformization of algebraic transductions, Parallel \(LL\) parsing, Lexical ambiguity in tree adjoining grammars, Some decision problems about controlled rewriting systems, Parsing and generation with static discontinuity grammars, Commutation-augmented pregroup grammars and push-down automata with cancellation, On incremental evaluation of ordered attributed grammars, Tree pushdown automata, BUP: A bottom-up parser embedded in Prolog, NTS languages are deterministic and congruential, On the size of unambiguous context-free grammars, A nondeterministic program logic, A Yacc extension for LRR grammar parsing, The interchange or pump (di)lemmas for context-free languages, On a recursive ascent parser, Gaifman's theorem on categorial grammars revisited, A unified framework for disambiguating finite transductions, A method for transforming grammars into LL(k) form, 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, 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 pushdown automaton or a context-free grammar - which is more economical?, Translations on a subclass of LR(k) 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, A functional LR parser, An improved bound for detecting looping configurations in deterministic PDA's, 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, 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, Some decidability results about regular and pushdown translations, Fast recognition of context-sensitive structures, Deterministic acceptors for indexed languages, On fault tolerance of syntax, The complexity of computing maximal word functions, A class of coders based on gsm, Boundedly \(\text{LR}(k)\)-conflictable grammars, The word problem for groups with regular relations. Improvement of the Knuth-Bendix algorithm, Proof versus formalization, A parallel parsing algorithm for arbitrary context-free grammars, Context-free relations and their characteristics, A model of the loop formation process on knitting machines using finite automata theory, Multipass precedence analysis, A characterization of Thompson digraphs., Code migration and program maintainability -- A categorical perspective, Efficient coding of formalized messages, On LC(0) grammars and languages, 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, Greibach normal form transformation revisited., Computing a context-free grammar-generating series, DM-automata and classes of context-free languages, Syntactic recognizer for expandable languages, Concerning existential definition of the class \(NP\): Theoretical analysis of an alternative approach, CALS technologies and tolerant translators, Deep pushdown automata, Sublogarithmic ambiguity, Comparisons between some pumping conditions for context-free languages, Rational transductions and complexity of counting problems, State-complexity of finite-state devices, state compressibility and incompressibility, Error detection in precedence parsers, A note on weak operator precedence grammars, Normal form algorithms for extended context-free grammars, On parsing LL-languages, On parsing and condensing substrings of LR languages in linear time, Fuzzy pushdown automata, Theory of language processors and parallel computations, Theory of language processors and parallel computations, Measuring nondeterminism in pushdown automata, Fuzzy context-free languages. I: Generalized fuzzy context-free grammars, Random Generation for Finitely Ambiguous Context-free Languages, Inferability of context-free programmed grammars, Some theoretical aspects of parallel parsing, Direct parsing of ID/LP grammars, Epsilon weak precedence grammars and languages, Analyzing Ambiguity of Context-Free Grammars, Unnamed Item, LL(1) grammars and Sub-LL(1) grammars, Unnamed Item, Ogden's lemma for nonterminal bounded languages, Unnamed Item, Unnamed Item, Grammar functors and covers: From non-left-recursive to greibach normal form grammars, On comparingLL(k) andLR(k) grammars, Inference of a class of CFPG by means of semantic rules, On reducing the number of states in a PDA, Syntactic/semantic techniques in pattern recognition: A survey, 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, Computational complexity of formal translations, An error-correcting syntactic decoder for computer networks, New problems complete for nondeterministic log space, Parsers for indexed grammars, A new definition for simple precedence grammars, String and graph grammar characterizations of bounded regular languages
