1996 SALS-SIG Seminars
SALS-SIG Research Seminar
Mixed Top-down/Bottom-Up Parsing
Department of Artificial Intelligence, University of Edinburgh, Scotland
When: Friday, 12th July 1996
Where: Room E6A357, Macquarie University
It has been suggested that, in certain circumstances, it might be useful for a grammar-writer to indicate which rules are to be used bottom-up and which are to be used top-down within a parser. One limitation of this technique is that certain allocations of rules to these classes can lead to incompleteness; that is, there may be valid analyses of the input string which cannot be found by the parser. We formalise a fairly natural notion of ``mixed strategy'' parsing for context free grammars, in which a rule may be top-down, bottom-up, or both, and then define a condition of ``analysability'' which is a decidable property of such grammars. Any grammar with this property is provably complete. It is also possible to construct grammars which are not ``analysable'' but nevertheless can be parsed successfully. The property defining this wider class of grammars is undecidable. We conclude with some discussion of the relevance of this work to parsers for processing natural language.
|Last modified: July 1997|