Skip Navigation



Journal of Logic and Computation Advance Access published online on May 30, 2007
Journal of Logic and Computation, doi:10.1093/logcom/exm009
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
18/2/205    most recent
exm009v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by van Eijck, J.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2007. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original papers

Sequentially Indexed Grammars

Jan van Eijck

CWI, Amsterdam, Uil-OTS, Utrecht, The Netherlands. E-mail: jan.van.eijck{at}cwi.nl

Received 9 February 2006.


  Abstract

This article defines the grammar class of sequentially indexed grammars (SIGs) that results of a change in the index stack handling mechanism of indexed grammars (Aho, 1968, Journal of the ACM, 15, 647–671; 1969, Journal of the ACM, 16, 383–406). SIGs are different from linear indexed grammars (Gazdar, 1988, Natural Language, Parsing and Linguistic, Theories, pp. 69–94) (the rule format is simpler) and they generate a strictly larger language class. We give a polynomial algorithm for parsing with SIGs that is a rather straightforward extension of the Earley algorithm for parsing with context-free grammars. SIGs are attractive because of the simple rule format, the natural correspondence between indices and traces, and the perspicuity of the parsing scheme.

Keywords: Deductive parsing; context-free grammars; indexed languages; nested stack automata; Earley parsing algorithm; polynomial parsing


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.