A Logical Version of Functional Grammar

A LOGICAL VERSION OF FUNCTIONAL GRAMMAR William C. Rounds University of Michigan Xerox PARC Alexis Manaster-Ramer IBM T.J. Watson Research Center Wayne State University I Abstract Kay's functional-unification grammar notation [5] is a way of expressing grammars which relies on very few primitive notions. The primary syntactic structure is the feature structure, which can be visualised as a directed graph with arcs labeled by attributes of a constituent, and the primary structure-building operation is unification. In this paper we propose a mathematical formulation of FUG, using logic to give a precise account of the strings and the structures defined by any grammar written in this notation. 2 Introduction Our basic approach to the problem of syntactic de- scription is to use logical formulas to put conditions or constraints on ordering of constituents, ancestor and de- scendant relations, and feature attribute information in syntactic structures. The present version of our logic has predicates specifically designed for these purposes. A grammar can be considered as just a logical formula, and the structures satisfying the formula are the syntactic structures for the sentences of the language. This notion goes back to DCG's [0], but our formulation is quite dif- ferent. In particular, it builds on the logic of Kasper and Rounds [3], a logic intended specifically to describe fea- ture structures. The formulation has several new aspects. First, it introduces the oriented feature structure as the primary syntactic structure. One can think of these structures as parse trees superimposed on directed graphs, although the general definition allows much more flexibility. In fact, our notation does away with the parse tree alto- gether. A second aspect of the notation is its treatment of word order. Our logic allows small grammars to define free-word order languages over large vocabularies in a way not possible with standard ID/LP rules. It is not clear whether or not this treatment of word order was intended by Kay, but the issue naturally arose during the process of making this model precise. (Joshi [1] has adopted much the same conventions in tree adjunct grammar.) A third aspect of our treatment is the use of fixed- point formulas to introduce recursion into grammars. This idea is implicit in DCG's, and has been made explicit in the logics CLFP and ILFP [9]. We give a simple way of expressing the semantics of these formulas which corre- sponds closely to the usual notion of grammatical deriva- tions. There is an interesting use of type ~ariables to describe syntactic categories and/or constructions. We illustrate the power of the notation by sketching how the constructions of relational grammar [7] can be formulated in the logic. To our knowledge, this is the first attempt to interpret the relational ideas in a fully mathematical framework. Although relational networks themselves have been precisely specified, there does not seem to be a precise statement of how relational deriva- tions take place. We do not claim that our formalization is the one intended by Postal and Perlmutter, but we do …

Content truncated to 500 words