Parsing of Context-Free Languages

Parsing is the process of assigning structure to sentences. The structure is obtained from the grammatical description of the language. Both in Computer Science and in Computational Linguistics, context-free grammars and associated parsing algorithms are among the most useful tools. Numerous parsing algorithms have been developed. Special subclasses of the context-free grammars have been introduced in order to allow and induce efficient parsing algorithms. Special superclasses of the context-free grammars have been introduced in order to allow use of variants of efficient parsing methods that had been developed for context-free grammars. At first sight many parsing algorithms seem to be different, but nevertheless related. Some unifying approaches have been attempted in the past, but none survived the changing field. This report introduces a unifying approach at a level between grammars and algorithms, introducing so-called parsing schemata. In the parsing schemata framework the essentials of different parsing algorithms can be compared and it can be shown how to derive an algorithm from another one. The insight that is obtained this way also allows the derivation of new algorithms and it allows less tedious observations about correctness than usual. The framework can also be applied to grammar formalisms beyond the context-free grammars.