Informatics Report Series


Report   

EDI-INF-RR-0021


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Completeness Conditions for Mixed Strategy Bidirectional Parsing
Authors: Graeme Ritchie
Date:Dec 1999
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 bidirectional 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 bidirectional 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 results suggest that the mixed strategy approach is of rather limited usefulness, regardless of whether it is empirically efficient or not.
Copyright:
Graeme Ritchie, University of Edinburgh 1999. All Rights Reserved
The Association for Computational Linguistics will have the following exclusive rights for a period of five years: 1) to license abstracts, quotation extracts, reprints, and/or translations of the work for publication; 2) to license reprints of the Article to third persons for educational photocopying; 3) to license others to create abstracts of the Article; 4) to license secondary publishers to reproduce the Article in print, microform, or any computer-readable form including electronic on-line databases. This also includes licensing the Article for document delivery. After five years following the date of the publication
Links To Paper
No links available
Bibtex format
@Misc{EDI-INF-RR-0021,
author = { Graeme Ritchie },
title = {Completeness Conditions for Mixed Strategy Bidirectional Parsing},
year = 1999,
month = {Dec},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh