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 |