Results 11 to 20 of about 284 (123)
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
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
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
Disambiguation Filters for Scannerless Generalized LR Parsers [PDF]
, 2002 In this paper we present the fusion of generalized LR parsing and scannerless parsing. This combination supports syntax de.nitions in which all aspects (lexical and context-free) of the syntax of a language are de.ned explicitly in one formalism. Furthermore, there are no restrictions on the class of grammars, thus allowing a natural syntax tree ...
Mark van den Brand +3 more
openaire +6 more sources
Reachability and error diagnosis in LR(1) parsers [PDF]
Proceedings of the 25th International Conference on Compiler Construction, 2016 Given an LR(1) automaton, what are the states in which an error can be detected? For each such " error state " , what is a minimal input sentence that causes an error in this state? We propose an algorithm that answers these questions. This allows building a collection of pairs of an erroneous input sentence and a (handwritten) diagnostic message ...
openaire +2 more sources
On LR(k)-parsers of polynomial size
CoRR, 2015 Usually, a parser for an $LR(k)$-grammar $G$ is a deterministic pushdown transducer which produces backwards the unique rightmost derivation for a given input string $x \in L(G)$. The best known upper bound for the size of such a parser is $O(2^{|G||Σ|^k+k\log |Σ| + \log |G|})$ where $|G|$ and $|Σ|$ are the sizes of the grammar $G$ and the terminal ...
openaire +2 more sources
Optimizing directly executable LR parsers [PDF]
, 1991 Traditionally, LR parsers are implemented as table interpreters. A parser generator creates tables whose entries are interpreted by the parser driver. Recent research shows that much faster LR parsers can be obtained by converting the table entries into directly executed code.
openaire +1 more source