Parallel Parsing for Unification Grammars

1. Introduction

Unifi cation grammars have the power of a Turing machine, and one can easily prove this by showing that a unification grammar can simulate any Prolog program It follows that the problem of finding all possible parses of a sentence in a given unifi cation grammar is unsolvable . The best we can do IS an algorithm that sometimes finds a set of parses and somet1mes goes into an infinite loop. The top-down, left-to-nght parser used with definite clause gram mars is of this kind - if the grammar c-ontains left rec-ursion the parser may run forever . If we want to wnte a parallel parsing algorithm for unification grammar , we first need to find a subset of unification grammar for which the parsing problem is solvable . Indeed th1s is the hard part of the problem. We shall see that once we have a parsing algorithm, finding the parallelism 1s strai-ghtforward.

Part 1 rev1ews the algorithm of Cocke. Kasami and Younger for parsing context - free grammars · in Chomsky normal form . This algorithm is beautifully simple and easily extends to a parsmg algorithlll for unific-ation grammars m Chomsky normal form. Therefore the parsing problem is solvable for unification _ grammars in Chomsky normal form. Unfortunately th1s subset of unification grammar is too restricted to describe human language. Part 2 therefore considers an extens1on of Chomsky Normal Form which allows chain rules - rules having one non - terminal symbol on the right side . We generalize the CKY algorithm to handle context-free grammars with chain rules , and extend this algorithm to unification grammars . The extension works only if one places a restriction on the use of chain rules in _ a unification grammar, and that restnction is one mam pomt of the paper . Once we have the parsing algorithm for unific ation grammars with chain rules , we can eas1ly extend it to unification grammars with any number of symbols on the right side of a rule . Finally we consider the possibilities of parallelism m the new parsmg algorithm .

2 . Parsing in Chomsky Normal Form

A context-free grammar m Chomsky normal form contains two kinds of rules . Terminal rules have a single terminal on the right side; branching rules have exactly two non-terminal symbols on the right s1de .

type . A term is well-formed 1f <:very argument of P.&ch funcl ion Jetter has the correct type for 1ts position. We use the capital letters X,Y ,Z,W, somet1mes with prime marks . as variables rangmg over well-formed terms of a unification grammar A umfication grammar is a finite set of rules of the form (X - > Yl Yn), where X is a well-formed term and Yl through Yn are either terms or terminal symbols . If G IS a unification grammar , the ground grammar G' derived from G is the set of well-formed ground instances of rules m G. To define the language generated by a ground grammar we use the standard definition of the language generated by a context-free grammar, assuming that the start symbol is always S. It is possible that the ground grammar is infinite , and therefore is not a context­ free grammar . This does not create a problem, because the definition of the language generated by a context­ free grammar does not rely on the finiteness of the grammar in any way. Finally we define the language generated by a unification grammar G to be the language generated by the ground grammar derived from G.

Consider a trivial example. Let the type Person contain the variable .p and the constants 1st , 2nd and 3rd. Let the type Number contain the variable :n and the constants Singular and Plural. Suppose NP and VP are function letters with two arguments , a person and a number . Then the rule

(S) -> (NP :p : n) (VP : p : n)

says that a sentence may cons1st of a noun phrase and a ve rb phrase that agree in person and number . Th1s rule has 6 ground instances , as follows :

(S) -> (NP 11\ S i ngular) (VP 111 Singular) (S) -> (NP 2nd Singular) (VP 2nd Singular) (S) -> (NP 3rd Singular) (VP 3rd Singular) (S) -> (NP 1st Plurol) (VP 11\ Plural) (S) -> (NP 2nd Plural) (VP 2nd Plurol) (S) -> (NP 3rd Plurol) (VP 3rd Plurol)

In this case the ground grammar is finite . so this rule is only an abbreviation for a context-free grammar . It appears that most of the syntax of natural language . IS context-free; therefore unihcat1on grammars w1th hmte ground grammars have almost the formal power needed to descr ibe natural language. Still there are constructions that cannot be described by context-free grammar . The crossed serial dependencies in Dutch and Swiss German are examples (Bresnan 1962) . We can describe these constructions usmg a unification grammar whose ground grammar is infinite. As an illustration of the technique we give a grammar for the language (atn}(btn}(cm}, which no context-free grammar can generate . The function letters A, B and C each take a single argument of type Integer . The variable :n , the function Jetter s (for "successor") and the constant 0 are of type Integer ; s takes a single argument of type Int eger . The rules are

(S) -> (,lo, : n) (B : n) (C : n) (" e) -> (" (s : n)) -> 0 (" : n) (B e) -> (B (o : n)) -> (B : n) (c e) -> (C (s : n)) -> c (C : n)

(A :n} represents a strmg of n a 's , (B :n) a string of n b 's , and (C :n} a string of n c 's . The hrst rule says that a sentence consists of n a 's , n b's, and n c 's .

It IS important to understand that our parsmg algorithm does not construct the ground grammar , nor does it construct the set of ground non - termmals that generate input[i k) . Instead it represents sets of ground non-terminals indirectly. If Sl 1s a set of terms in a unif1cat1on &rammar. let (ground ~II be the set of ground insttmC'es of terms in S!. The parsl'r sets M[1 k) to a set of terms so that (ground M[i k)) = I A I A = >· input[i k) 1.

A unification &rammar in Chomsky normal form has two kinds of rules . Terminal rules have a single terminal symbol on the nght side , branching rules have two well-formed terms on the right side. Unification is defined for pairs of terms as well as individual terms - the most &eneral unifier of [X Y) and [X' Y') is the most general substitution that umfies X with X' and Y with Y'. As usual it is neccesary to rename variables before unifying. For this purpose assume that for any term X and integer n, (rename X n) is an alphabetic variant of X, and if m is not equal to n then (rename X n ) and (rename · Y m) have no variables in common. Note that renaming a term or rule does not change its set of ground instances. For this reason we use the term "rule" for any alphabetic variant of a rule in G.

If Sl and S2 are sets of terms in a unification grammar, the product of Sl and S2, Sl · · S2 , is defmed as follows :

51 · · 52 - I (1 X) I (uiot Y' in (renomo 51 1), Z' i n ( re nome 52 2) , (X-> Y Z) in (renome G 3) . a ia the moet 9enerol unifier of the poiro [Y Z] ond [Y' Z']

Loosely speaking, this product is like the product used in the CKY algorithm except that instead of testing symbols for equality, it makes the symbols equal by substitution - if possible.

Unification Parsing Lemma . Suppose that i < k and for all j such that i < j < k, (ground M[i j]} = I A I A =>· input[i j) I. and (ground M[j k]} = I A I A =>· input[j k) 1. Then A =>· input[i k) iff for some j such that i < j < k, A is in (ground M[i J) · · M[j k]}.

The parser for umhcation gr·ammars in Chomsky normal form is then as follows .

for i f r0111 e to (N - 1) do M[i i+1] :· I X I (X-> input[i i+1]) is o rule I : for L :· 2 to N do for oil i,k ouch \hot i + L · k do M[i k] :· union M[i j] ·' M[j k] i < j < k

Theorem. When the unification parser halts , (ground M[i k)) = lA I A => input[i k)l .

Unification grammars in Chomsky normal form are more powerful than context-free grammars ; they can generate languages that no context-free grammar can generate, and they can capture generalizations that cannot be captured with context - free grammars . Despite this difference in the power of the two formalisms , one can parse these unification grammars usin& a very straightforward generalization of the Cl\'Y al&orithm. This is a good example of the power and simphcity of unification.

3. Parsing with Chain Rules

Unfortunately one cannot describe natural language syntax with a unification grammar in Chomsky normal form. For example, any intransitive verb can form a sentence by itself - "Run'" and "Stop!" are such sentences. If we restrict ourselves to grammars in Chomsky normal form we must have a rule for each of these sentences - (S -> run) , (S - > stop}, and so on . The rule we really want is something like (S - > (VP (2nd) :n)} - a verb phrase that agrees with a second person subJect can form a sentence by Itself . As a second example , many theories hold that m "Who did Mary like?" there is a trace after "like" - a noun phrase with no words under it . (NP - > ) is not allowed in Chomsky normal form . We therefore consider the problem of parsing a unification grammar that allows chain rules - rules with exactly one non-terminal on the right side . The solution of this problem includes the essential ideas needed to parse grammars with any number of symbols on the right sides of their rules .

Let us first consider the context-free case. How can we parse a grammar that allows chain rules , branching rules , and terminal rules? We stressed above that the Basic Parsing Lemma is useful because it allows us to find all possible parses of a substring if we are given all possible parses of shorter substrmgs . This allows us to look at substrings in order of length, knowing that at each stage we have the information we need. The chain rule (A - > B) tells us that if B = > · input[i k] , so does A. input[i k] is not shorter than itself, so we could repeat this process indefinitely without ever getting to a longer substring . Then what guarantees termination?

In the case of context-free grammar , we can easily build a table of all pairs [A B) such that A =>' B. This table is finite because the set of non-terminals is finite . Define (close S) to be the set of all non­ terminals A such that A = >' B for some B in S. Since A =>' A, (close S) contains S.

Second Parsing Lemma : Let G be a context-free grammar containing only terminal rules, branching rules, and chain rules . Suppose that i < k and for all j such that i < j < k, M[i j) = l A I A =>' input[i j) I and M[j k] = l A I A =>' input[j k] 1- Then for all A, A =>' input[i k] iff A is in (clqse M[i j) · M[j k]) for some j with i < j < k .

Using this observation we extend the CKY algorithm to handle grammars with chain rules .

A Igor i t hm 2 . Context-free parser with chain table .

for from 0 to (N- 1) do M[i i+1] : · (close input[i i+1]); for : · 2 to N do for all i,k such that i + L · k do M[i k] : · union (close M[i j) · M[j k]) i < j < k

Theorem 3 . Suppose the grammar G contains only terminal rules , branching rules and chain rules . After algorithm 2 halts, M[i k]. = jA I A =>' input[i k]! .

If one tries to generalize this algorithm to unification grammars with chain rules , a serious problem appears . The argument above relies crucially on the finite number of non-terminals in the context-free grammar . A unification grammar may generate an infinite ground grammar , so the chain table for a unification grammar might be infinite. For example, suppose (f :x) - > (f (f :x)) is a rule . Then the sequence (f :x) - > (f (f :x)) - > (f (f (f :x))) .. is an infinite derivation using only chain rules . We propose a straightforward solution : we require that for every unification grammar G there is an integer n such that every chain derivation in G is shorter than n .

Does this restriction stop us from describing natural languages? We claim the answer is no . This claim is based on experience - we have written a grammar that is not trivial and contains no chain longer than 4 . If this restriction holds , a simple algorithm will generate a chain table for a unification grammar . That is , it will generate a finite set C of pairs of terms such that A =>' B in the ground grammar iff [A B) is in (ground C) . The method is to construct a series of sets C(k) such that (ground C(k)) = j [A B) I A =>' B m exactly k steps 1- Clearly C(1) is the set of pairs [X Y] such that (X - > Y) 1s a rule . If we can construct C(k+ 1) from C(k) , we can build the chain table by constructing C(k) for successive values of k until we find a C(k) that is empty. If the grammar contains unbounded chains this algorithm will run forever, and it IS up to the grammar writer to fix this . In practice this is not likely to be a problem . In any case it is better than having the parser go into an infinite loop - which can happen with the depth-first , left-to-right parser used with definite clause grammars .

In order to construct C(k) from C(k+ 1) we define a new product . Let S 1 and S2 be sets of pairs of terms . Define

51 52 - I (s [X Z]) (exist [X Y] in (rename 51 1), [Y ' Z] in (rename 52 2) . s is the most general unifier of Y andY')

Lemma . (ground S1 " S2) = j[A B) I (exist C. [A C) is in (ground S1) and [C B) is in (ground S2))1 .

Lemma . If (ground C(k)) = j[A B]l A => ' B in exactly k steps!, then C(k) " j[X Y] I (X - > Y) is a rule! = ![A B) I A =>' B in exactly k + 1 steps! .

In order to extend our second context-free parser to a unification parser , we now define

(close' 5) ·

I (s X) I [X Y] is in (rename Chain 1), Y' is in (rename 52), and s is the mgu of Y andY' j .

We then rewrite the parser by adding "close "', just as we did for the CKY algorithm:

Algorithm 4 .

for i from e to (N - 1) do M[i i+1] (close' I X (X -> input [ i i+1]) is 0 ru I e I); for L : · 2 to N do for all i , k such that i + L · k do M[ i k] union (close' M[i j] ·' M[j k]) i < j < k

Once again, the proof of soundness and completeness requires only a proof for the corresponding context­ free algorithm along with the basic properties of unification.

The parser that was actually implemented allows any number of symbols on the right side of a rule . In order to handle rules with an empty right side , we must make another restriction similar to the first one : for every grammar G there is an integer n such that every derivation of the empty string in G is shorter than n . In order to handle rules with more than two symbols on the right side , we use dotted rules as described in (Graham 1984). Indeed our parser was inspired by the context-free parser of Graham, Harrison and Ruzzo . The implemented parser also uses left context to reject some of the hypotheses that are generated bottom-up; the technique 1s similar to Shieber 's notion of restriction (Shieber 1985) .

4. Parallel Parsing

We claim that in practice, the time for a unification or a substitution is dependent on the grammar but not on the sentence . If the ground grammar is finite , there is a finite bound on the largest term that can be constructed by the parser - it is no larger than the largest term m the gr ound grammar . Sometimes a grammar will mc lude features that take on an infimte set of values . but these features are few and their values do not get very large for ordinary sentences. So to a good approximation, the size of the terms constructed dunng a parse is independent of the sentence . Therefore the time taken for a unification or a substitution is independent of the sentence.

Therefore Jet U be the maximum time for a unification or substitution. Assume that an unlimited number of processors are- available and the time to set up tasks for parallel exe.cution is negligible . In computing a product Sl · S2 , we can consider each combination of an X' in S 1, a Y' m S2 and a rule (X - > Y Z) in parallel. This allows us to compute the product in time 3U, regardless of the size of Sl or S2 or the number of branching rules in the grammar . By similar reasoning we can compute (close Sl) in time 2U, regardless of the size of Sl. Then we can compute M(i i+ 1] for all i in time 2U. Suppose we have computed M[i k] for all substrings shor ter t han L. To compute M[i k] for a substring of length L, we can compute M[i j] · M(j k] in parallel for all j such that i < j < k, and then compute the closure . This gives a total time of 5U for each length from 1 to the length of the sentence ; thus the parser should be able to run in time linear in the length of the sentence.

In pr actice it is essential to remove from M[i k] any terms that are substitution ins tances of other terms in M( i k] . In pars ing cerain constructions (tor example, sequences of noun modifiers or prepositional phrases) , this makes the difference between a matrix of size polynomial m the input , and a matrix of s1ze exponential in the input. A simple parallel algorithm Will do th1s m time 2U; the number of processors needed is the square of the number of elements in M[ i k]. Note that if X is the first term in M[i k] to be comput ed, it might be a substitutiOn instance of the last t e rm to be computed. Thus one cannot be certain that X belongs in M[i k] until all the potential elements of M[i k] have been computed. This limits the parallelism in the algorithm. There is no such limitation in the case of a context-free parser because an oc.curence of a non-terminal A in M[1 k] IS redundant only If there is another occurence of A in M[i k]. When the algorithm finds the first occurence of A, it can keep that one and throw away all later occurences.

This algorithm achieves speed by wasting processors . In many cases we can use left context to show that even though A =>' input[i k] , there is no derivation of the whole sentence in which A is the interpretation for M[i k]. For example , suppose our grammar includes a rule (Trace - > ). A simple bottom-up parser will conclude that Trace =>' input[i i] tor each i; but left context will eliminate most of these hypotheses . An algorithm that uses left context may therefore manage with fewer processors , but it will not run in linear time in the worst case. It must work from . left to right ; after reading the n- t h word it computes M[i n] for all i < n . It i < j it must compute M[i n] before M[J n] because M(j n] is a proper substring of M[i n]. Then the time to read the n - th word is proportional to n, and the total time is O(n t 2) .

Of course this worst-case time may not be reahzed tor natural grammars and natural sent ences . This raises the question of testing the implemented parser . Our current grammar concentrates on clause- level phenomena. There is a large set of subcategorization frames for verbs , and the grammar describes raising, control, passive, subject-aux inversion and wh­ movement . Noun phrases , adjective phrases and prepositional phrases are described only as much as needed to illustrate the clause-level phenomena. The program was first tested with a Butterfly simulator running on a VAX; it was then moved to a real .Butterfly and ran the first time . Tests have shown that the program is reliable but slow; we have not yet attempted to speed it up or to measure the gain from parallelism.

6. Concluaion

We propose to restrict unification grammars by requiring that for each grammar G there is a constant N such that every derivation of a string of length 0 or 1 is shorter than N. Essentially this says that the size of a parse tree is bounded by the size of the sentence; one cannot build arbitrarily large structures that are not realized in the surface string. Given this requirement one can parse unification grammars by an algorithm related to the CKY algorithm. In principle such an algorithm should be able to parse in linear time on an ideal parallel machine . In practice it is probably desirable to use left context, raising the worst case time to O(nt2). In any case it should be possible to parse in time independent of the size of the grammar. Natural sentences are seldom over 50 words , while natural grammars are likely to contain many hundreds of rules, so this is an encouraging result.

references

• Bresnan, Joan, Kaplan, Ronald M .· Peters , Stanley, and Zaenen, Annie . Crossed Serial Dependencies in Dutch. Unguistic Inquiry, volume 13, number 4, pp. 613-635.
• Graham, Susan L., Harrison, Michael A., and Ruzzo, Walter L. An Improved Context - Free Recognizer . Transactions on Programming Languages and Systems , volume 2, number 3 , pp. 415-461.
• Shieber , Stuart . Using Restriction to Extend Parsing Algorithms for Complex-Feature - Based Formalisms . Proceedings of the 23rd Annual Meeting of the Association for Computational Unguistics , pp. 145-152.