Deterministic Parsing using PCFGs

Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 338–347, Gothenburg, Sweden, April 26-30 2014. c⃝2014 Association for Computational Linguistics Deterministic Parsing using PCFGs Mark-Jan Nederhof and Martin McCaffery School of Computer Science University of St Andrews, UK Abstract We propose the design of deterministic constituent parsers that choose parser ac- tions according to the probabilities of parses of a given probabilistic context-free grammar. Several variants are presented. One of these deterministically constructs a parse structure while postponing commit- ment to labels. We investigate theoretical time complexities and report experiments. 1 Introduction Transition-based dependency parsing (Yamada and Matsumoto, 2003; Nivre, 2008) has attracted considerable attention, not only due to its high ac- curacy but also due to its small running time. The latter is often realized through determinism, i.e. for each configuration a unique next action is cho- sen. The action may be a shift of the next word onto the stack, or it may be the addition of a de- pendency link between words. Because of the determinism, the running time is often linear or close to linear; most of the time and space resources are spent on deciding the next parser action. Generalizations that allow nonde- terminism, while maintaining polynomial running time, were proposed by (Huang and Sagae, 2010; Kuhlmann et al., 2011). This work has influenced, and has been in- fluenced by, similar developments in constituent parsing. The challenge here is to deterministi- cally choose a shift or reduce action. As in the case of dependency parsing, solutions to this prob- lem are often expressed in terms of classifiers of some kind. Common approaches involve maxi- mum entropy (Ratnaparkhi, 1997; Tsuruoka and Tsujii, 2005), decision trees (Wong and Wu, 1999; Kalt, 2004), and support vector machines (Sagae and Lavie, 2005). The programming-languages community rec- ognized early on that large classes of gram- mars allow deterministic, i.e. linear-time, pars- ing, provided parsing decisions are postponed as long as possible. This has led to (deterministic) LR(k) parsing (Knuth, 1965; Sippu and Soisalon- Soininen, 1990), which is a form of shift-reduce parsing. Here the parser needs to commit to a grammar rule only after all input covered by the right-hand side of that rule has been processed, while it may consult the next k symbols (the lookahead). LR is the optimal, i.e. most determin- istic, parsing strategy that has this property. De- terministic LR parsing has also been considered relevant to psycholinguistics (Shieber, 1983). Nondeterministic variants of LR(k) parsing, for use in natural language processing, have been proposed as well, some using tabulation to en- sure polynomial running time in the length of the input string (Tomita, 1988; Billot and Lang, 1989). However, nondeterministic LR(k) pars- ing is potentially as expensive as, and possibly more expensive than, traditional tabular parsing algorithms such as CKY parsing (Younger, 1967; Aho and Ullman, 1972), as shown by for exam- ple (Shann, 1991); greater values of k make mat- ters worse (Lankhorst, 1991). For this reason, LR …

Content truncated to 500 words