Parsing Schemata and Correctness of Parsing Algorithms

Nicolaas Sikkel

    Research output: Contribution to journalArticleAcademicpeer-review

    6 Citations (Scopus)

    Abstract

    Parsing schemata give a high-level formal description of parsers. These can be used, among others, as an intermediate level of abstraction for deriving the formal correctness of a parser. A parser is correct if it duly implements a parsing schema that is known to be correct. We discuss how the correctness of a parsing schema can be proven and how parsing schemata relate to some well-known classes of parsers, viz. chart parsers and LR-type parsers.
    Original languageUndefined
    Article number10.1016/S0304-3975(97)00269-7
    Pages (from-to)87-103
    Number of pages17
    JournalTheoretical computer science
    Volume199
    Issue number1-2
    DOIs
    Publication statusPublished - 15 Jun 1998

    Keywords

    • SCS-Services
    • IR-61821
    • EWI-10594
    • Correctness proof
    • Parsing schemata
    • Chart parsers

    Cite this