A parsing algorithm for non-deterministic context-sensitive languages

Henk Harkema

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    28 Downloads (Pure)


    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.
    Original languageEnglish
    Title of host publicationTomita's Algorithm - Extensions and Applications
    Subtitle of host publicationProceedings of the first Twente Workshop on Language Technology
    EditorsRob Heemels, Anton Nijholt, Klaas Sikkel
    Place of PublicationEnschede
    PublisherUniversity of Twente
    Publication statusPublished - 1 Sept 1992
    Event1st Twente Workshop on Language Technology, TWLT 1: Tomita's Algorithm: Extensions and Applications - Enschede, Netherlands
    Duration: 22 Mar 199122 Mar 1991
    Conference number: 1

    Publication series

    NameMemoranda Informatica
    PublisherUniversity of Twente
    ISSN (Print)0924-3755


    Workshop1st Twente Workshop on Language Technology, TWLT 1
    Abbreviated titleTWLT


    Dive into the research topics of 'A parsing algorithm for non-deterministic context-sensitive languages'. Together they form a unique fingerprint.

    Cite this