University of Sussex
Browse

File(s) not publicly available

Parsing some constrained grammar formalisms

journal contribution
posted on 2023-06-07, 13:28 authored by K. Vijay-Shanker, David WeirDavid Weir
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).

History

Publication status

  • Published

Journal

Computational Linguistics

ISSN

0891-2017

Issue

4

Volume

19

Page range

591-636

Department affiliated with

  • Informatics Publications

Full text available

  • No

Peer reviewed?

  • No

Legacy Posted Date

2006-11-21

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC