Grammar Compaction and Computation Sharing in Automaton-based Parsing
John A. Carroll, Nicolas Nicolov, Olga Shaumyan, Martine Smets, David James Weir · 1998
Wide-coverage grammars in Lexicalised TreeAdjoining Grammar (ltag) and related formalisms are structurally complex, containing many hundreds of elementary trees. In the context of the development of a full-scale ltag-like grammar and parsing system, we have investigated the claim that because many of these trees have a great deal of structure in common, a parser that manipulates trees individually performs a considerable amount of redundant computation. This claim has been used to motivate a parsing technique that encodes trees as finite state automata and captures overlapping computation through automata minimization. Our preliminary results show that this technique leads to considerable computation sharing. 1 Introduction The paper presents work that forms part of the ongoing LexSys project 1 . Our overall aim is to bring together and test in practice a variety of current nlp techniques, including the organisation of grammars into inheritance hierarchies for compact representati...