A parsing algorithm for non-deterministic context-sensitive languages

In this paper a shift-reduce algorithm for the recognition of sentences of non-deterministic lan­guages defined by context-sensitive grammars is introduced. The algorithm is a composite of Tomita's efficient parsing method for non­deterministic languages and a procedure for pro­cessing deterministic context-sensitive languages, proposed by Walters. The algorithm that is presented in this paper employs two (graph­structured) 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 in­put 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.