Fast LR parsing Using Rich (Tree Adjoining) Grammars

Fast LR Parsing Using Rich (Tree Adjoining) Grammars Carlos A. Prolo Department of Computer and Information Science University of Pennsylvania prolo@linc.cis.upenn.edu Abstract We describe an LR parser of parts-of- speech (and punctuation labels) for Tree Adjoining Grammars (TAGs), that solves table conflicts in a greedy way, with lim- ited amount of backtracking. We evaluate the parser using the Penn Treebank show- ing that the method yield very fast parsers with at least reasonable accuracy, confirm- ing the intuition that LR parsing benefits from the use of rich grammars. 1 Introduction The LR approach for parsing has long been con- sidered for natural language parsing (Lang, 1974; Tomita, 1985; Wright and Wrigley, 1991; Shieber, 1983; Pereira, 1985; Merlo, 1996), but it was not until a more recent past, with the advent of corpus- based techniques made possible by the availability of large treebanks, that parsing results and evalu- ation started being reported (Briscoe and Carroll, 1993; Inui et al., 1997; Carroll and Briscoe, 1996; Ruland, 2000). The appeal of LR parsing (Knuth, 1965) derives from its high capacity of postponement of struc- tural decisions, therefore allowing for much of the spurious local ambiguity to be automatically dis- carded. But it is still the case that conflicts arise in the LR table for natural language grammars, and in large quantity. The key question is how one can use the contextual information contained in the parsing stack to cope with the remaining (local) ambiguity manifested as conflicts in the LR tables. The afore- mentioned work has concentrated on LR parsing for CFGs which has a clear deficiency in making avail- able sufficient context in the LR states. (Shieber and Johnson, 1993) hints at the relevance of rich grammars on this respect. They use Tree Adjoining Grammars (TAGs) (Joshi and Schabes, 1997; Joshi et al., 1975) to defend the possibility of granular in- cremental computations in LR parsing. Incidentally or not, they make use of disambiguation contexts that are only possible in a state of a conceptual LR parser for a rich grammar formalism such as TAG, but not for a CFG. Concrete LR-like algorithms for TAGs have only recently been proposed (Prolo, 2000; Nederhof, 1998), though their evaluation was restricted to the quality of the parsing table (see also (Schabes and Vijay-Shanker, 1990; Kinyon, 1997) for earlier at- tempts). In this paper, we revisit the LR parsing technique, applied to a rich grammar formalism: TAG. Follow- ing (Briscoe and Carroll, 1993), conflict resolution is based on contextual information extracted from the so called Instantaneous Description or Configu- ration: a stack, representing the control memory of the LR parser, and a lookahead sequence, here lim- ited to one symbol.1 However, while Briscoe and Carroll invested on massive parallel computation of the possible parsing paths, with pruning and posterior ranking, we ex- 1Unlike (Wright and Wrigley, 1991)’s approach who tries to transpose PCFG probabilities to LR tables, facing difficulties which, to the best of our knowledge, have not been yet solved to content (cf. also …

Content truncated to 500 words