Parsing With Logical Variables

PARSING WITH LOGICAL VARIABLES Timothy W. Finln and Martha Stone Palmer Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 ABSTRACT Logic based programming systems have enjoyed an increasing popularity in applied AI work in the last few years. One of the contributions to Computational Linguistics made by the Logic Programming Paradigm has been the Definite Clause Grammar. In comparing DCG's wlth previous parsing mechanisms such as ATN's, certain clear advantages are seen. We feel that the most important of these advantages are due to the use of Logical Variables with Unification as the fundamental operation on them. To illustrate the power of the Logical Variable, we have implemented an experimental ATN system which treats ATN registers as Logical Variables and provides a unification operation over them. We would llke to simultaneously encourage the use of the powerful mechanisms available in DCG's, and demonstrate that some of these techniques can be captured without reference to a resolution theorem prover. [. Introduction Logic based programming systems have enjoyed an increasing popularity in applied AI work in the last few years. One of the contributions to Computational Linguistics made by the Logic Programming Paradigm has been the Deflnite Clause Grammar. An excellent introduction to this formalism can be found in [Perelra] in which the authors present the formalism and make a detailed comparison to Augmented Transition Networks as a means of both specifying a language and parsing sentences in a language. We feel Chat the major strengths offered by the DCG formalism arise from its use of Logical variables with Unification as the fundamental operation on them. These techniques can be abstracted from the theorem proving paradigm and adapted to other parsing systems (see [Kay] and [Bossie] ). We have implemented an experimental ATN system which treats ATN registers as Logic variables and provides a unification operation over them. The DCG formalism provides a powerful mechanism for parsing based on a context free grammar. The grammar rule S -> NP VP can be seen as the universally quantified logical statement, For all x, y, and z : N'P(x) /\ VP(y) /\ Concatenate(x,y,z) -> S(z). where "x" and "y" represent sequences of words which can be concatenated together to produce a sentence, "S." Prolog, a progra~mulng language baaed on predicate calculus, allows logical statements to be input as Horn clauses in the foilowlng (reversed) form: s(Z) <- np(X),vp(Y),Concatenate(X,Y,Z). The resolution theorem prover that "interprets" the Prolog clauses would take the oegatlon of S as the goal and try and produce the null clause. Thus the preceding clause can be interpreted procedurally as, "To establish goal S, try and establish subgoals, NP, VP and Concatenate." DCG's provide syntactic sugar on top of Prolog so that the arrow can be reversed and the "Concatenate" predicate can be dispensed with. The words in the input string are looked at sequentially each time a "[Word]" predicate is executed which implicitly tests for concatenation (see figure [). DCG's allow grammar rules to be expressed very …

Content truncated to 500 words