---

Ph.D. THESIS

AN EVALUATION SYSTEM FOR PARSING AND GENERATION ALGORITHMS 

---

This thesis addresses a challenging and significant problem of evaluating and ranking of different grammar processing algorithms (parsers or generators). Recently, with the advent of logic programming, which has been widely accepted as a paradigm for parser and generator design, it became possible to compare various competing approaches to the problem. The need for their evaluation has been felt strongly in both Linguistics and Computational Linguistics, since both have been thus far predominantly empirical, and it became difficult to measure the actual progress. This work sets up a formal apparatus for ranking grammar evaluation algorithms with respect to the following criteria: completeness, soundness, efficiency, optimality and reversibility. The method is based on the general principle of traversal of derivation trees, and is therefore independent of a particular grammar or execution strategy. It is also demonstrated how this formalism can be applied to evaluate specific algorithms, using as an example two well-known recent natural language generation algorithms. This work also rigorously defines the concept of logic grammars and a number of other related notions. Concepts lacking formal definitions, while used informally by many researchers, are formally and uniformly defined. Also, the equivalence of Definite Clause Grammars (DCG's) and type 0 Chomsky-an grammars, and DCG's and  Turing machines is proven, using an original constructive method.