Direct parsing of ID/LP grammars
| Title: | Direct parsing of ID/LP grammars |
| Author: | Shieber, Stuart |
| 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: |
Shieber_DirectParsing.pdf (861.9Kb; PDF) 
|
| 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 |
This item appears in the following Collection(s)
-
FAS Scholarly Articles [5128]
Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
Contact administrator regarding this item (to report mistakes or request changes)
