A Structure-sharing Parser for Lexicalized Grammars

A structure-sharing parser for lexicalized grammars Roger Evans Information Technology Research Institute University of Brighton Brighton, BN2 4G J, UK Roger. Evans @it ri. brighton, ac. uk David Weir Cognitive and Computing Sciences University of Sussex Brighton, BN1 9QH, UK David.Weir@cogs.susx.ac.uk Abstract In wide-coverage lexicalized grammars many of the elementary structures have substructures in common. This means that in conventional pars- ing algorithms some of the computation associ- ated with different structures is duplicated. In this paper we describe a precompilation tech- nique for such grammars which allows some of this computation to be shared. In our approach the elementary structures of the grammar are transformed into finite state automata which can be merged and minimised using standard al- gorithms, and then parsed using an automaton- based parser. We present algorithms for con- structing automata from elementary structures, merging and minimising them, and string recog- nition and parse recovery with the resulting grammar. 1 Introduction It is well-known that fully lexicalised grammar formalisms such as LTAG (Joshi and Schabes, 1991) are difficult to parse with efficiently. Each word in the parser's input string introduces an elementary tree into the parse table for each of its possible readings, and there is often a substantial overlap in structure between these trees. A conventional parsing algorithm (Vijay- Shanker and Joshi, 1985) views the trees as in- dependent, and so is likely to duplicate the pro- cessing of this common structure. Parsing could be made more efficient (empirically if not for- mally), if the shared structure could be identi- fied and processed only once. Recent work by Evans and Weir (1997) and Chen and Vijay-Shanker (1997) addresses this problem from two different perspectives. Evans and Weir (1997) outline a technique for com- piling LTAG grammars into automata which are then merged to introduce some sharing of struc- ture. Chen and Vijay-Shanker (1997) use un- derspecified tree descriptions to represent sets of trees during parsing. The present paper takes the former approach, but extends our previous work by: • showing how merged automata can be min- imised, so that they share as much struc- ture as possible; • showing that by precompiling additional information, parsing can be broken down into recognition followed by parse recovery; • providing a formal treatment of the algo- rithms for transforming and minimising the grammar, recognition and parse recovery. In the following sections we outline the basic approach, and describe informally our improve- ments to the previous account. We then give a formal account of the optimisation process and a possible parsing algorithm that makes use of it 1 . 2 Automaton-based parsing Conventional LTAG parsers (Vijay-Shanker and Joshi, 1985; Schabes and Joshi, 1988; Vijay- Shanker and Weir, 1993) maintain a parse ta- ble, a set of items corresponding to complete and partial constituents. Parsing proceeds by first seeding the table with items anchored on the input string, and then repeatedly scanning the table for parser actions. Parser actions introduce new items into the table licensed by one or more …

Content truncated to 500 words