ScholarLens Back to search
2007•Journal of Logic and ComputationRequires access

Sequentially Indexed Grammars

Jan van Eijck

Open publisher page 1 citations

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.

About this research paper

What this paper is about

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.

Why it matters

OpenAlex reports 1 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available 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.

Key concepts: L-attributed grammar, Indexed grammar, Computer science, Parsing, Tree-adjoining grammar, Parsing expression grammar, Rule-based machine translation, Programming language

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
Sequentially Indexed Grammars — Research Paper | ScholarLens