A parsing algorithm for non-deterministic context-sensitive languages

Henk Harkema

A parsing algorithm for non-deterministic context-sensitive languages

Henk Harkema

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

58 Downloads (Pure)

Abstract

In this paper a shift-reduce algorithm for the recognition of sentences of non-deterministic languages defined by context-sensitive grammars is introduced. The algorithm is a composite of Tomita's efficient parsing method for nondeterministic languages and a procedure for processing deterministic context-sensitive languages, proposed by Walters. The algorithm that is presented in this paper employs two (graphstructured) stacks, one of which is used for representing the context of the several active processes (an extension of the traditional input buffer). The other stack is the normal parsing stack. The two stacks are linked by means of a set of pointers. When manipulating context-sensitive languages in an LR-manner, there is no need for a seperate goto table anymore. In case of a reduce action, all the symbols of the left-hand side of the rule under consideration are pushed back into the input buffer. The state which appears on top of the stack when having popped off the symbols of the right-hand side, and the first symbol in the input buffer determine the next action.

Original language	English
Title of host publication	Tomita's Algorithm - Extensions and Applications
Subtitle of host publication	Proceedings of the first Twente Workshop on Language Technology
Editors	Rob Heemels, Anton Nijholt, Klaas Sikkel
Place of Publication	Enschede
Publisher	University of Twente
Pages	21-31
Publication status	Published - 1 Sept 1992
Event	1st Twente Workshop on Language Technology, TWLT 1: Tomita's Algorithm: Extensions and Applications - Enschede, Netherlands Duration: 22 Mar 1991 → 22 Mar 1991 Conference number: 1

Publication series

Name	Memoranda Informatica
Publisher	University of Twente
Number	91-68
ISSN (Print)	0924-3755

Workshop

Workshop	1st Twente Workshop on Language Technology, TWLT 1
Abbreviated title	TWLT
Country/Territory	Netherlands
City	Enschede
Period	22/03/91 → 22/03/91

Access to Document

Harkema1992parsingFinal published version, 3.89 MB

Cite this

@inproceedings{80a058e42ac14e418e4070bcb1d36840,

title = "A parsing algorithm for non-deterministic context-sensitive languages",

abstract = "In this paper a shift-reduce algorithm for the recognition of sentences of non-deterministic languages defined by context-sensitive grammars is introduced. The algorithm is a composite of Tomita's efficient parsing method for nondeterministic languages and a procedure for processing deterministic context-sensitive languages, proposed by Walters. The algorithm that is presented in this paper employs two (graphstructured) stacks, one of which is used for representing the context of the several active processes (an extension of the traditional input buffer). The other stack is the normal parsing stack. The two stacks are linked by means of a set of pointers. When manipulating context-sensitive languages in an LR-manner, there is no need for a seperate goto table anymore. In case of a reduce action, all the symbols of the left-hand side of the rule under consideration are pushed back into the input buffer. The state which appears on top of the stack when having popped off the symbols of the right-hand side, and the first symbol in the input buffer determine the next action. ",

author = "Henk Harkema",

year = "1992",

month = sep,

day = "1",

language = "English",

series = "Memoranda Informatica",

publisher = "University of Twente",

number = "91-68",

pages = "21--31",

editor = "Rob Heemels and Anton Nijholt and Klaas Sikkel",

booktitle = "Tomita's Algorithm - Extensions and Applications",

address = "Netherlands",

note = "1st Twente Workshop on Language Technology, TWLT 1 : Tomita's Algorithm: Extensions and Applications, TWLT ; Conference date: 22-03-1991 Through 22-03-1991",

}

Harkema, H 1992, A parsing algorithm for non-deterministic context-sensitive languages. in R Heemels, A Nijholt & K Sikkel (eds), Tomita's Algorithm - Extensions and Applications: Proceedings of the first Twente Workshop on Language Technology. Memoranda Informatica, no. 91-68, University of Twente, Enschede, pp. 21-31, 1st Twente Workshop on Language Technology, TWLT 1, Enschede, Netherlands, 22/03/91.

A parsing algorithm for non-deterministic context-sensitive languages. / Harkema, Henk.
Tomita's Algorithm - Extensions and Applications: Proceedings of the first Twente Workshop on Language Technology. ed. / Rob Heemels; Anton Nijholt; Klaas Sikkel. Enschede: University of Twente, 1992. p. 21-31 (Memoranda Informatica; No. 91-68).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

T1 - A parsing algorithm for non-deterministic context-sensitive languages

AU - Harkema, Henk

N1 - Conference code: 1

PY - 1992/9/1

Y1 - 1992/9/1

N2 - In this paper a shift-reduce algorithm for the recognition of sentences of non-deterministic languages defined by context-sensitive grammars is introduced. The algorithm is a composite of Tomita's efficient parsing method for nondeterministic languages and a procedure for processing deterministic context-sensitive languages, proposed by Walters. The algorithm that is presented in this paper employs two (graphstructured) stacks, one of which is used for representing the context of the several active processes (an extension of the traditional input buffer). The other stack is the normal parsing stack. The two stacks are linked by means of a set of pointers. When manipulating context-sensitive languages in an LR-manner, there is no need for a seperate goto table anymore. In case of a reduce action, all the symbols of the left-hand side of the rule under consideration are pushed back into the input buffer. The state which appears on top of the stack when having popped off the symbols of the right-hand side, and the first symbol in the input buffer determine the next action.

AB - In this paper a shift-reduce algorithm for the recognition of sentences of non-deterministic languages defined by context-sensitive grammars is introduced. The algorithm is a composite of Tomita's efficient parsing method for nondeterministic languages and a procedure for processing deterministic context-sensitive languages, proposed by Walters. The algorithm that is presented in this paper employs two (graphstructured) stacks, one of which is used for representing the context of the several active processes (an extension of the traditional input buffer). The other stack is the normal parsing stack. The two stacks are linked by means of a set of pointers. When manipulating context-sensitive languages in an LR-manner, there is no need for a seperate goto table anymore. In case of a reduce action, all the symbols of the left-hand side of the rule under consideration are pushed back into the input buffer. The state which appears on top of the stack when having popped off the symbols of the right-hand side, and the first symbol in the input buffer determine the next action.

M3 - Conference contribution

T3 - Memoranda Informatica

SP - 21

EP - 31

BT - Tomita's Algorithm - Extensions and Applications

A2 - Heemels, Rob

A2 - Nijholt, Anton

A2 - Sikkel, Klaas

PB - University of Twente

CY - Enschede

T2 - 1st Twente Workshop on Language Technology, TWLT 1

Y2 - 22 March 1991 through 22 March 1991

ER -

A parsing algorithm for non-deterministic context-sensitive languages

Abstract

Publication series

Workshop

Access to Document

Fingerprint

Cite this