FROM CONTEXT-FREE TO DEFINITE-CLAUSE GRAMMARS - A TYPE-THEORETIC APPROACH

We discuss the mechanical transformation of an unambiguous context-fre e grammar (CFG) into a definite-clause grammar (DCG) using a finite se t of examples, each of which is a pair [s, m], where s is a sentence b elonging to the language defined by the CFG and mis the semantic repre sentation (meaning) of s. The resulting DCG would be such that it coul d be executed to compute the semantics for every sentence of the origi nal DCG. The motivation for our work comes from the observation that i t is not easy to manually augment a CFG with semantic attributes to ob tain a DCG because the task of building a correct and efficient DCG re quires a fair amount of search, especially when the semantic represent ations involve quantified terms, as in natural languages. Our proposed approach is based upon two key assumptions: (1) the semantic represen tation language is the simply typed lambda-calculus, and (2) the seman tic representation of a sentence is a function (expressed in the typed lambda-calculus) of the semantic representations of its parts (compos itionality). With these assumptions, we show how a higher-order DCG ca n be systematically constructed using a matching procedure for simply typed lambda-terms. We then show how to translate the constructed high er-order DCG into. first-order DCG by a partial-execution procedure. W e have applied our methodology to the synthesis of the semantics of a small query language, and we believe that this methodology could be a useful tool for generating natural query language front-ends for vario us applications. (C) Elsevier Science Inc., 1997