Direct parsing of ID/LP grammars

DSpace/Manakin Repository

Direct parsing of ID/LP grammars

Citable link to this page

 

 
Title: Direct parsing of ID/LP grammars
Author: Shieber, Stuart ORCID  0000-0002-7733-8195
Citation: Shieber, Stuart M. Direct parsing of ID/LP grammars. Linguistics and Philosophy, 7(2):135-154, 1984. The original publication is available at www.springerlink.com.
Full Text & Related Files:
Abstract: The Immediate Dominance/Linear Precedence (ID/LP) formalism is a recent
extension of Generalized Phrase Structure Grammar (GPSG) designed to
perform some of the tasks previously assigned to metarules--for example,
modeling the word-order characteristics of so-called free-word-order
languages. It allows a simple specification of classes of rules that
differ only in constituent order. ID/LP grammars (as well as metarule
grammars) have been proposed for use in parsing by expanding them into
equivalent context-free grammars. We develop a parsing algorithm, based
on the algorithm of Earley, for parsing ID/LP grammars directly,
circumventing the initial expansion phase. A proof of correctness is
supplied. We also discuss some aspects of the time complexity of the
algorithm and some formal properties associated with ID/LP grammars and
their relationship to context-free grammars.
Published Version: http://dx.doi.org/10.1007/BF00630810
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:2031670
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters