Paper: A Structure-sharing Parser for Lexicalized Grammars

ACL ID P98-1061
Title A Structure-sharing Parser for Lexicalized Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1998

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.