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

Sikkel, Nicolaas. / Parsing Schemata and Correctness of Parsing Algorithms. In: Theoretical computer science. 1998 ; Vol. 199, No. 1-2. pp. 87-103.
@article{cc91961d1ca541f2be6ef3b0897b8b09,
title = "Parsing Schemata and Correctness of Parsing Algorithms",
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.",
keywords = "SCS-Services, IR-61821, EWI-10594, Correctness proof, Parsing schemata, Chart parsers",
author = "Nicolaas Sikkel",
year = "1998",
month = "6",
day = "15",
doi = "10.1016/S0304-3975(97)00269-7",
language = "Undefined",
volume = "199",
pages = "87--103",
journal = "Theoretical computer science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-2",

}

Parsing Schemata and Correctness of Parsing Algorithms. / Sikkel, Nicolaas.

In: Theoretical computer science, Vol. 199, No. 1-2, 10.1016/S0304-3975(97)00269-7, 15.06.1998, p. 87-103.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Parsing Schemata and Correctness of Parsing Algorithms

AU - Sikkel, Nicolaas

PY - 1998/6/15

Y1 - 1998/6/15

N2 - 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.

AB - 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.

KW - SCS-Services

KW - IR-61821

KW - EWI-10594

KW - Correctness proof

KW - Parsing schemata

KW - Chart parsers

U2 - 10.1016/S0304-3975(97)00269-7

DO - 10.1016/S0304-3975(97)00269-7

M3 - Article

VL - 199

SP - 87

EP - 103

JO - Theoretical computer science

JF - Theoretical computer science

SN - 0304-3975

IS - 1-2

M1 - 10.1016/S0304-3975(97)00269-7

ER -