Technical Reports

The ICICS/CS Reading Room

UBC CS TR-84-11 Summary

Definite Clause Translation Grammars \& the Logical Specification of Data Types as Unambiguous Context Free Grammars, August 1984 Harvey Abramson

Data types may be considered as unambiguous context free grammars. The elements of such a data type are the derivation trees of sentences generated by the grammars. Furthermore, the generators and recognizers of non-terminals specified by such grammars provide the composition and decomposition operators which can be used to define functions or predicates over such data types. We present a modification of our Definite Clause Translation Grammars (Abramson 1984) which is used to logically specify data types as unambiguous context free grammars. For example, here is a grammatical specification of binary trees: \begin{center} string.$ \\ "(" , left :tree, " ,", right :tree, " )".$ \end{center} The decomposition ``operators'', left, right, and (implicitly) string, are semantic attributes generated by the compiler which translates these grammar rules to Prolog clauses; these operators, together with the parser for $tree$s, and the predicates $leaf$ and $branch$, can be used to construct more complex predicates over the data type $tree$. We show how such grammars can be used to impose a typing system on logic programs; and indicate how such grammars can be used to implement Kaviar, a functional programming language based on data types as context tree grammars.

If you have any questions or comments regarding this page please send mail to