1996 SALS-SIG Seminars

SALS-SIG Research Seminar

Mixed Top-down/Bottom-Up Parsing

Graeme Ritchie
Department of Artificial Intelligence, University of Edinburgh, Scotland

When: Friday, 12th July 1996

Time: 11:45am

Where: Room E6A357, Macquarie University

Abstract:

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.

Enquiries: Maria Milosavljevic 9850 6345 mariam@mpce.mq.edu.au