The terminology that is used in the rest of the book is set up in this chapter which is, albeit technical, easy to read. In particular, the first parsing scheme is shown, a tree-based one for context free grammars. Parsing schema are defined as a specification of the more general notion of deduction systems, that are formally defined in this chapter. In particular, the notion of correctness is formally introduced, anticipating a later discussion of correctness of parsing schemata. A refined parsing scheme has, roughly, more items and more deduction steps.
Generalization is an extension of a schema to a larger class of grammars.
For example, it is shown that bottom-up Earley parsing is a generalization of the CYK algorithm. Filtering is an optimization that reduces the number of deduction steps in a parsing system. Once such relations among schemata are established, they can be used for proving the correctness of a certain scheme, given the correctness of others. This is a very useful tool in formally verifying the correctness of parsing schemata. Related to each other by the above-mentioned relations, these schemata form a grid of mathematically defined objects.