Division of Informatics
Forrest Hill & 80 South Bridge
Research Paper #861 | |
|---|---|
| Title: | Completeness Conditions for Mixed Strategy Bidirectional Parsing |
| Authors: | Ritchie,GD |
| Date: | Jun 1997 |
| Presented: | Submitted for publication in Computational Linguistics |
| Keywords: | |
| Abstract: | It has been suggested that, in certain circumstances, it might be useful for a grammar-writer to annotate which rules are to be used bottom-up and which are to be used top-down within a parser, using a bi-directional variant of the "active chart" parsing technique. the formal properties of such systems have not been fully explored. One limitation of this mixed strategy technique is that certain annotations of rules 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 bi-directional parsing for context free grammars, in which one or more symbols within a rule may be annotated as "triggers", so that the rule is either top-down (triggered from its left-hand side), or bottom-up (triggered from element(s) of its right-hand side). We define a decidable property of annotated grammars, such that any grammar with this property is provably complete. There are, however, some complete annotations of grammars which fall outside this decidable class. We show that membership of this wider class is undecidable. These reulsts suggest that the mixed strategy approach is or rather limited usefulness, regardless of whether it is empirically efficient or not. |
| Download: | POSTSCRIPT 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}