Parsing Schemata and Correctness of Parsing Algorithms

Nicolaas Sikkel

doi:10.1016/S0304-3975(97)00269-7

Parsing Schemata and Correctness of Parsing Algorithms

Nicolaas Sikkel

Research output: Contribution to journal › Article › Academic › peer-review

9 Citations (Scopus)

2 Downloads (Pure)

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 language	Undefined
Article number	10.1016/S0304-3975(97)00269-7
Pages (from-to)	87-103
Number of pages	17
Journal	Theoretical computer science
Volume	199
Issue number	1-2
DOIs	https://doi.org/10.1016/S0304-3975(97)00269-7
Publication status	Published - 15 Jun 1998

Keywords

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

Access to Document

10.1016/S0304-3975(97)00269-7

http://eprints.eemcs.utwente.nl/secure2/10594/01/sikkel-TCS.pdf

Cite this

@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 = jun,

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 B.V.",

number = "1-2",

}

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

SN - 0304-3975

VL - 199

SP - 87

EP - 103

JO - Theoretical computer science

JF - Theoretical computer science

IS - 1-2

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

ER -