PARSING SCHEMATA AND CORRECTNESS OF PARSING ALGORITHMS

Parsing schemata give a high-level formal description of parsers. Thes e can be used, among others, as an intermediate level of abstraction f or 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 d iscuss how the correctness of a parsing schema can be proven and how p arsing schemata relate to some well-known classes of parsers, viz. cha rt parsers and LR-type parsers. (C) 1998 - Elsevier Science B.V. All r ights reserved.