Results 11 to 20 of about 616 (167)
Validating LR(1) Parsers [PDF]
, 2012 An LR(1) parser is a finite-state automaton, equipped with a stack, which uses a combination of its current state and one lookahead symbol in order to determine which action to perform next. We present a validator which, when applied to a context-free grammar G and an automaton A, checks that A and G agree.
Jourdan, Jacques-Henri +2 more
openaire +1 more source
Journal of Computer and System Sciences, 1972 Certain techniques for modifying LR(k) parsing tables to decrease their size have been developed by Korenjak [2] and DeRemer [3, 4]. We show that the techniques of the latter can be characterized by two transformations on sets of tables. We then show that the “simple” LR(1) method of DeRemer [4] can be considered a special case of Korenjak's method [2].
Alfred V. Aho, Jeffrey D. Ullman
openaire +1 more source
LR parsers for natural languages [PDF]
Proceedings of the 22nd annual meeting on Association for Computational Linguistics -, 1984 MLR, an extended LR parser, is introduced, and its application to natural language parsing is discussed. An LR parser is a shift-reduce parser which is deterministically guided by a parsing table. A parsing table can be obtained automatically from a context-free phrase structure grammar.
openaire +1 more source
Towards Efficient, Typed LR Parsers
Electronic Notes in Theoretical Computer Science, 2006 AbstractThe LR parser generators that are bundled with many functional programming language implementations produce code that is untyped, needlessly inefficient, or both. We show that, using generalized algebraic data types, it is possible to produce parsers that are well-typed (so they cannot unexpectedly crash or fail) and nevertheless efficient ...
Pottier, François, Régis-Gianas, Yann
openaire +2 more sources
An alternative method of training probabilistic LR parsers [PDF]
Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics - ACL '04, 2004 We discuss existing approaches to train LR parsers, which have been used for statistical resolution of structural ambiguity. These approaches are nonoptimal, in the sense that a collection of probability distributions cannot be obtained. In particular, some probability distributions expressible in terms of a context-free grammar cannot be expressed in ...
M. J. NEDERHOF, SATTA, GIORGIO
openaire +2 more sources
Lexer and Parser Generators in Scheme [PDF]
, 2004 The implementation of a basic LEX-style lexer generator or YACC-style parser generator requires only textbook knowledge. The im-plementation of practical and useful generators that cooperate well with a specific language, however, requires more ...
Olin Shivers +7 more
core
A generalized LR(1) parser for extended context-free grammars [PDF]
, 2020 Tomita's Generalized LR(1) parser (GLR) algorithm for CF grammars runs in a linear time onLR(1) grammars and degrades to a polynomial bound otherwise.
Angelo Morzenti +3 more
core
On the size of parsers and LR(k)-grammars
Theoretical Computer Science, 2000 AbstractIn this paper, we consider two tradeoff results regarding the economy of description in parsing. One result is on the tradeoff between the size of a parser and its ability to detect an error early. The other result is on the tradeoff between the size of an LR(k)-grammar and the length k of the lookahead.
Hing Leung, Detlef Wotschke
openaire +1 more source
Extending lookahead for LR parsers
Journal of Computer and System Sciences, 1981 AbstractA practical method is presented for extending the lookahead of LR parsers, by the addition of “reduce-arcs.” Applied to an LR(0) parser, this gives a machine which is close in size to the corresponding LALR(1) machine, but is capable of making use of unbounded lookahead.
openaire +1 more source
, 2010 There has been a recent effort in the literature to reconsider grammar-dependent software development from an engineering point of view. As part of that effort, we examine a deficiency in the state of the art of practical LR parser table generation ...
Malloy, Brian A., Denny, Joel E.
core +1 more source