Parsing some constrained grammar formalisms

Vijay-Shanker, K. and Weir, David (1993) Parsing some constrained grammar formalisms. Computational Linguistics, 19 (4). pp. 591-636. ISSN 0891-2017

Full text not available from this repository.

Abstract

In this paper we present a scheme to extend a recognition algorithm for Context-Free Gram- mars (CFG) that can be used to derive polynomial-time recognition algorithms for a set of formalisms that generate a superset of languages generated by CFG. We describe the scheme by developing a Cocke-Kasami-Younger (CKY)-like pure bottom-up recognition algorithm for Linear Indexed Grammars and show how it can be adapted to give algorithms for Tree Adjoining Grammars and Combinatory Categorial Grammars. This is the only polynomial-time recognition algorithm for Combinatory Categorial Grammars that we are aware of. The main contribution of this paper is the general scheme we propose for parsing a variety of formalisms whose derivation process is controlled by an explicit or implicit stack. The ideas presented here can be suitably modified for other parsing styles or used in the generalized framework set out by Lang (1990).

Item Type: Article
Schools and Departments: School of Engineering and Informatics > Informatics
Subjects: Q Science > QA Mathematics > QA0075 Electronic computers. Computer science
Depositing User: David Weir
Date Deposited: 21 Nov 2006
Last Modified: 27 Aug 2019 11:22
URI: http://sro.sussex.ac.uk/id/eprint/501
Google Scholar:115 Citations
📧 Request an update