An Alternative Method of Training Probabilistic LR Parsers

An alternative method of training probabilistic LR parsers Mark-Jan Nederhof Faculty of Arts University of Groningen P.O. Box 716 NL-9700 AS Groningen The Netherlands markjan@let.rug.nl Giorgio Satta Dept. of Information Engineering University of Padua via Gradenigo, 6/A I-35131 Padova Italy satta@dei.unipd.it Abstract We discuss existing approaches to train LR parsers, which have been used for statistical resolution of structural ambiguity. These approaches are non- optimal, 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 terms of the LR parser constructed from that grammar, under the restrictions of the existing approaches to training of LR parsers. We present an alternative way of training that is provably optimal, and that al- lows all probability distributions expressible in the context-free grammar to be carried over to the LR parser. We also demonstrate empirically that this kind of training can be effectively applied on a large treebank. 1 Introduction The LR parsing strategy was originally devised for programming languages (Sippu and Soisalon- Soininen, 1990), but has been used in a wide range of other areas as well, such as for natural language processing (Lavie and Tomita, 1993; Briscoe and Carroll, 1993; Ruland, 2000). The main difference between the application to programming languages and the application to natural languages is that in the latter case the parsers should be nondetermin- istic, in order to deal with ambiguous context-free grammars (CFGs). Nondeterminism can be han- dled in a number of ways, but the most efficient is tabulation, which allows processing in polyno- mial time. Tabular LR parsing is known from the work by (Tomita, 1986), but can also be achieved by the generic tabulation technique due to (Lang, 1974; Billot and Lang, 1989), which assumes an in- put pushdown transducer (PDT). In this context, the LR parsing strategy can be seen as a particular map- ping from context-free grammars to PDTs. The acronym ‘LR’ stands for ‘Left-to-right pro- cessing of the input, producing a Right-most deriva- tion (in reverse)’. When we construct a PDT A from a CFG G by the LR parsing strategy and apply it on an input sentence, then the set of output strings of A represents the set of all right-most derivations that G allows for that sentence. Such an output string enu- merates the rules (or labels that identify the rules uniquely) that occur in the corresponding right-most derivation, in reversed order. If LR parsers do not use lookahead to decide be- tween alternative transitions, they are called LR(0) parsers. More generally, if LR parsers look ahead k symbols, they are called LR(k) parsers; some sim- plified LR parsing models that use lookahead are called SLR(k) and LALR(k) parsing (Sippu and Soisalon-Soininen, 1990). In order to simplify the discussion, we abstain from using lookahead in this article, and ‘LR parsing’ can further be read as ‘LR(0) parsing’. We would like to point out how- ever that our observations carry over to LR …

Content truncated to 500 words