Parsing of Context-Free Languages

Nicolaas Sikkel, Antinus Nijholt

    Research output: Book/ReportReportOther research output

    109 Downloads (Pure)

    Abstract

    Parsing is the process of assigning structure to sentences. The structure is obtained from the grammatical description of the language. Both in Computer Science and in Computational Linguistics, context-free grammars and associated parsing algorithms are among the most useful tools. Numerous parsing algorithms have been developed. Special subclasses of the context-free grammars have been introduced in order to allow and induce efficient parsing algorithms. Special superclasses of the context-free grammars have been introduced in order to allow use of variants of efficient parsing methods that had been developed for context-free grammars. At first sight many parsing algorithms seem to be different, but nevertheless related. Some unifying approaches have been attempted in the past, but none survived the changing field. This report introduces a unifying approach at a level between grammars and algorithms, introducing so-called parsing schemata. In the parsing schemata framework the essentials of different parsing algorithms can be compared and it can be shown how to derive an algorithm from another one. The insight that is obtained this way also allows the derivation of new algorithms and it allows less tedious observations about correctness than usual. The framework can also be applied to grammar formalisms beyond the context-free grammars.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherCentre for Telematics and Information Technology (CTIT)
    Publication statusPublished - 1996

    Publication series

    NameCTIT Technical Report Series
    No.96-32
    ISSN (Print)1381-3625

    Keywords

    • IR-79691

    Cite this