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.
- Correctness proof
- Parsing schemata
- Chart parsers
Sikkel, N. (1998). Parsing Schemata and Correctness of Parsing Algorithms. Theoretical computer science, 199(1-2), 87-103. [10.1016/S0304-3975(97)00269-7]. https://doi.org/10.1016/S0304-3975(97)00269-7