Division of Informatics
Forrest Hill & 80 South Bridge
Research Paper #763 | |
|---|---|
| Title: | Completeness Conditions for Mixed Strategy Context Free Parsing |
| Authors: | Ritchie,GD |
| Date: | Jul 1995 |
| Presented: | Submitted for publication in the "Journal of the A.M" |
| Keywords: | |
| 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 do not lead to analyses being missed during parsing. 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. |
| Download: | NO ONLINE COPY |
![[Search These Pages]](http://www.dai.ed.ac.uk/icons/dai_search.gif){kind=icon}
![[DAI Home Page]](http://www.dai.ed.ac.uk/icons/dai_home.gif){kind=icon}
![[Comment]](http://www.dai.ed.ac.uk/icons/dai_comment.gif){kind=icon}