Relating Complexity to Practical Performance in Parsing With Wide-Coverage Unification Grammars

RELATING COMPLEXITY TO PRACTICAL PERFORMANCE IN PARSING WITH WIDE-COVERAGE UNIFICATION GRAMMARS John Carroll University of Cambridge, Computer Laboratory Pembroke Street, Cambridge CB2 3QG, UK jac@cl.cam.ac.uk Abstract The paper demonstrates that exponential com- plexities with respect to grammar size and input length have little impact on the performance of three unification-based parsing algorithms, using a wide-coverage grammar. The results imply that the study and optimisation of unification-based parsing must rely on empirical data until complex- ity theory can more accurately predict the practi- cal behaviour of such parserQ. 1. INTRODUCTION General-purpose natural language (NL) analysis systems have recently started to use declarative unification-based sentence grammar formalisms; systems of this type include SRI's CLARE sys- tem (Alshawi et al., 1992) and the A1vey NL Tools (ANLT; Briscoe et al., 1987a). Using a declarative formalism helps ease the task of developing and maintaining the grammar (Kaplan, 1987). In ad- dition to syntactic processing, the systems incor- porate lexical, morphological, and semantic pro- cessing, and have been applied successfully to the analysis of naturally-occurring texts (e.g. Alshawi et al., 1992; Briscoe & Carroll, 1993). Evaluations of the grammars in these par- ticular systems have shown them to have wide coverage (Alshawi et al., 1992; Taylor, Grover &= Briscoe, 1989) 2. However, although the practical throughput of parsers with such realistic gram- mars is important, for example when process- 1This research was supported by SERC/DTI project 4/1/1261 'Extensions to the Alvey Natu- ral Language Tools' and by EC ESPRIT BRA-7315 'ACQUILEX-II'. I am grateful to Ted Briscoe for com- ments on an earlier version of this paper, to David Weir for valuable discussions, and to Hiyan Alshawi for assistance with the CLARE system. 2For example, Taylor et al. demonstrate that the ANLT grammar is in principle able to analyse 96.8% of a corpus of 10,000 noun phrases taken from a variety of corpora. ing large amounts of text or in interactive ap- plications, there is little published research that compares the performance of different parsing algorithms using wide-coverage unification-based grammars. Previous comparisons have either fo- cussed on context-free (CF) or augmented CF parsing (Tomita, 1987; Billot & Lang, 1989), or have used relatively small, limited-coverage unification grammars and lexicons (Shann, 1989; Bouma & van Noord, 1993; Maxwell & Kaplan, 1993). It is not clear that these results scale up to reflect accurately the behaviour of parsers using realistic, complex unification-based gram- mars: in particular, with grammars admitting less ambiguity parse time will tend to increase more slowly with increasing input length, and also with smaller grammars rule application can be con- strained tightly with relatively simple predictive techniques. Also, since none of these studies relate observed performance to that of other comparable parsing systems, implementational oversights may not be apparent and so be a confounding factor in any general conclusions made. Other research directed towards improving the throughput of unification-based parsing sys- tems has been concerned with the unification oper- ation itself, which can consume up to 90% of parse time (e.g. Tomabechi, 1991) in …

Content truncated to 500 words