A UNIFICATION–BASED ID/LP PARSING SCHEMA

Frank Morawietz^{∗}

Universität Tübingen Wilhelmstr. 113 72074 Tübingen Germany

                       frank@sfs.nphil.uni-tuebingen.de

Abstract

In contemporary natural language formalisms like HPSG (Pollard and Sag 1994) the ID/LP format is used to separate the information on dominance from the one on linear precedence thereby allowing significant generalizations on word order. In this paper, we define unification ID/LP grammars. But as mentioned in Seiffert (1991) there are problems concerning the locality of the information determining LP acceptability during parsing. Since one is dealing with partially specified data, the information that is relevant to decide whether the local tree under construction is LP acceptable might be instantiated further during processing. In this paper we propose a modification of the Earley/Shieber algorithm on direct parsing of ID/LP grammars. We extend the items involved to include the relevant underspecified information using it in the completion steps to ensure the acceptability of the resulting structure. Following Sikkel (1993) we define it not as an algorithm, but as a parsing schema to allow the most abstract representation.

1 Introduction

The immediate dominance/linear precedence distinction was introduced into linguistic formalisms to encode word order generalizations by Gazdar, Klein, Pullum and Sag (1985) for GPSG and contemporary formalisms like HPSG (Pollard and Sag 1994) still want to express linearization facts with LP rules. But HPSG does not provide definitions for how to incorporate the ID/LP format into the formalism. This paper tries to handle the ID/LP distinction on another level. Instead of incorporating it into the theory, the information will be used during processing to determine validity of structures.

The simplest approach to parsing of ID/LP grammars is to fully expand the grammar into the underlying phrase structure grammar. But the expansion creates a huge number of grammar rules^{1} which dominates the parsing complexity and can therefore not be a basis for a reasonable implementation. This parsing with the object grammar is called indirect parsing. On the other hand, there are approaches, called direct parsing which try to interleave the use of ID and LP rules. The approach taken in this paper is a result of augmenting this paradigm.

The concept of direct parsing was developed by Shieber (1984). He modifies Earley’s algorithm (Earley 1970) to cope with ID/LP grammars. (Context–free) ID/LP grammars are defined by treating the formerly context–free rules as ID rules and by adding LP rules. The modification to the algorithm consists of two parts. The right hand side of a rule has no longer a fixed order, but is treated as a multiset. The predictor and the completer are limited to the LP acceptable structures by testing LP acceptability on the considered local trees, i.e. a nonterminal is extracted from the multiset and tested whether it may precede the remaining categories. The LP rules are taken and matched directly against proposed structures. Since this proposal obviously does not suffice to handle HPSG style grammars, it has to be augmented to feature based grammars as is done in Seiffert (1991).

∗The research presented in this paper was sponsored by Teilprojekt A8 of the SFB 340 of the Deutsche Forschungsgemeinschaft. I want to thank Tom Cornell, Dale Gerdemann, Thilo Götz, Frank Richter and Klaas Sikkel for helpful discussion. Needless to say, all errors and infelicities that remain are my own.

1For unification grammars the number of rules may even be infinite.

Unification based ID/LP grammars are defined by augmenting the domain of the nonterminals to feature structures and by formalizing when an LP rules applies. This happens in case the LP elements subsume two categories contained in a local tree. A violation occurs if the category which is subsumed by the first LP element follows the category which is subsumed by the second LP element. The Earley/Shieber parser is then used almost unchanged. The only change is that nonterminals are not longer identical, so that application of rules is determined by unification. But consider the grammar in figure 1 (taken from Seiffert (1991)).^{2}

Lexicon  = \{ \begin{matrix}[^{cat}^{d} ] & → & h \\ [^{cat}^{e} ] & → & i \\ [\begin{matrix}cat & f \\ f1 & one \end{matrix} ] & → & j \\ [\begin{matrix}cat & g \\ f2 & two \end{matrix} ] & → & k \end{matrix} \}

ID–Rules  = \{ \begin{matrix}[^{cat}^{a} ] & → & [\begin{matrix}cat & b \\ f & 1 \end{matrix} ], [\begin{matrix}cat & c \\ f & 1 \end{matrix} ] \\ [\begin{matrix}cat & b \\ f & [\begin{matrix}f1 & 2 \\ f2 & 3 \end{matrix} ] \end{matrix} ] & → & [\begin{matrix}cat & d \\ f1 & 2 \end{matrix} ], [\begin{matrix}cat & e \\ f2 & 3 \end{matrix} ] \\ [\begin{matrix}cat & c \\ f & [\begin{matrix}f1 & 4 \\ f2 & 5 \end{matrix} ] \end{matrix} ] & → & [\begin{matrix}cat & f \\ f1 & & 4 \end{matrix} ], [\begin{matrix}cat & g \\ f2 & 5 \end{matrix} ] \end{matrix} \}

LP–Rules  = \{ \begin{matrix}[^{f1}^{one} ] & ≺ & [^{f2}^{two} ] \\ [^{cat}^{b} ] & ≺ & [^{cat}^{c} ] \end{matrix} \}
Start Symbol = [^{cat}^{a} ]

Fig. 1. Seiffert’s example grammar

On input ihjk – which is not well formed – Seiffert’s parser can not determine on the first pass whether the local tree (cat b, (cat e, cat d)) is well formed since the information that is relevant for the LP rule, namely that one has to precede two, is not available yet. Only after the local trees (cat c, (cat f, cat g)) and (cat a, (cat b, cat c)) have been constructed, the information becomes accessible through structure sharing. The nonlocal flow can be seen in the parse tree given in figure 2.^{3} The information one and two comes from the lexical entries for f and g and is passed to e and d via c and b. Only then is the information that the value for f2 at e is two and that the value for f1 at d is one available and the local tree (cat b, (cat e, cat d)) has to be ruled out since the LP rule [^{f1}^{one} ] ≺ [^{f2}^{two} ] is violated.

This phenomenon makes it necessary for Seiffert to take the resulting parse tree and check it for any remaining LP violations. Clearly this is inefficient and not desired.

Although this paper is not concerned with linguistics, we nevertheless try to argue to some extent that the problem is indeed not only a technical one. Nonlocality is a well known phenomenon in natural language, but so far without any influence on word order. This section tries to sketch the fact that in a reasonably large fragment for German such nonlocal word order phenomena do exist. Since this is not the main goal of the paper, the presentation needs to be brief. It can be understood without an exact knowledge of the linguistic theories involved if one accepts the claims made during the discussion. But for a complete understanding of the details involved, we assume some knowledge of the analysis of partial verb phrases by Hinrichs and Nakazawa (1993), on word order by Lenerz (1977) and the empirical analyses by Richter and Sailer (1995).

Some data on word order in German sentences seem to suggest that there exists a connection between the main verb and the order of its complements. The example sentences in 1 do indicate

2To simplify notation, we are going to represent the trees of categories in the discussion of this example in term notation with just the category feature present.

3For readability reasons the arrows are drawn just for one value, namely two.

[^{cat}^{a} ]

[\begin{matrix}cat & b \\ f & 1 [\begin{matrix}f1 & 2 \\ f2 & 3 \end{matrix} ] \end{matrix} ]  [\begin{matrix}cat & c \\ f & 1 [\begin{matrix}f1 & 4 \\ f2 & 5 \end{matrix} ] \end{matrix} ]

[\begin{matrix}cat & e \\ f2 & 3 \end{matrix} ]  [\begin{matrix}cat & d \\ f1 & 2 \end{matrix} ]  [\begin{matrix}cat & f \\ f1 & & 4 one \end{matrix} ]  [\begin{matrix}cat & g \\ f2 & 5 two \end{matrix} ]

Fig. 2. The parse tree for input ^{∗}ihjk and Seiffert’s grammar (see figure 1)

the different behaviour of the verbs geben (to give) and überlassen (to leave). 1 Example Sentences

(1) a.

Karl wird dem Kind das Geschenk geben wollen.
Karl will the child the present give want.

Karl will want to give the child the present.

b. ^{∗}Karl wird das Geschenk [\begin{matrix}rhem & plus \\ case & acc \end{matrix} ] dem Kind [\begin{matrix}rhem & minus \\ case & dat \end{matrix} ] geben wollen.

(2) a.

Karl wird das Geschenk dem Kind überlassen wollen.
Karl will the present the child leave  want.

Karl will want to leave the child the present.

b. ^{∗}Karl wird dem Kind [\begin{matrix}rhem & plus \\ case & dat \end{matrix} ] das Geschenk [\begin{matrix}rhem & minus \\ case & acc \end{matrix} ] überlassen wollen.

The (a) versions of the sentences do not exhibit any limitation on the order of the complements. The (b) versions reflect the fact that they do not allow the first NP to be rhematic in the sense of Lenerz (1977). With the verb geben this disallows the order of the accusative rhematic NP preceding the dative not rhematic NP, and in the case of überlassen the dative rhematic NP must not precede the accusative not rhematic NP. So the acceptance of the word order of the accusative and dative object seems to depend on the main verb and whether the first of those objects is to be rhematic. To express this in a grammar, one would have to ensure that there exists some connection from the main verb to the complements. We do not go into any detail how this connection could be formulated since it suffices to know that one has to exist. We do give a sketch for a parse tree for one of the example sentences in figure 3; V_{a} stands for an auxiliary verb, V_{m} for the main verb and V_{k} for a verbal complex. These parse trees rely on the analysis of German verb phrases in Hinrichs and Nakazawa (1993).

As one can see, the NP complements are not in one local tree with the main verb due to the necessary argument raising induced by the auxiliary in the verbal complex. But this is not sufficient to cause the problem presented previously. If one considers direct parsing of such a sentence, the local tree labeled VP in the figure 3 which has to decide on the LP acceptability of the order of the two NP complements is not completed unless the local tree of the verbal complex has been recognized. And by this, the necessary connection of the NP complements to the main verb can be validated so that the local tree containing the NP complements would not be completed.

A further complication is necessary to cause the problem – the topicalization of the verbal complex. The data to support the claim is not as sharp as for the non topicalized sentences, S

VP

V_{k}
NP  V_{a}  NP  NP  V_{m}  V_{a}
Karl  wird dem Kind das Geschenk geben wollen

Fig. 3. A sketched parse tree for the sentence Karl wird dem Kind das Geschenk geben wollen.

although it is plausible that topicalization does not alter the behaviour of the main verbs concerning the word order of their complements. The examples are given below. 2 Example Sentences

(3) a. Geben wollen wird Karl dem Kind das Geschenk.

b. ^{∗}Geben wollen wird Karl das Geschenk [\begin{matrix}rhem & plus \\ case & acc \end{matrix} ] dem Kind [\begin{matrix}rhem & minus \\ case & dat \end{matrix} ].

(4) a. Überlassen wollen wird Karl das Geschenk dem Kind.

b. ^{∗}Überlassen wollen wird Karl dem Kind [\begin{matrix}rhem & plus \\ case & dat \end{matrix} ] das Geschenk [\begin{matrix}rhem & minus \\ case & acc \end{matrix} ].

As can be seen in the sketched parse tree in figure 4, the verbal complex is completely independent of the local tree containing the NP complements. This creates the desired constellation. If one considers right to left traversal of the input string for parsing, as is done for example in Ale (Carpenter 1993), the local tree whose mother is labeled VP has to be completed before the verbal complex is parsed. Therefore the information which main verb appears in the verbal complex is not yet known. The local tree would be LP acceptable although the whole parse tree may later contain information that the VP in question was not LP acceptable.

S

V_{k}  VP
V_{m}  V_{a}  V_{a} NP  NP  NP
Geben wollen wird Karl dem Kind das Geschenk

Fig. 4. A sketched parse tree for the sentence Geben wollen wird Karl dem Kind das Geschenk.

Although the presentation is somewhat sketchy, we showed that in natural language there may well be cases where the technical problem noted by Seiffert does indeed occur. Since all the mechanisms involved are present in current HPSG analyses of German and their interaction is complex, one may conclude that such phenomena are not easily detected by the grammar writer and can not necessarily be avoided. Therefore each parser dealing with unification based ID/LP grammars has to take care of those nonlocal phenomena.

2 Unification ID/LP Grammars

We are going to formalize unification ID/LP grammars very similarly to the approach taken in Sikkel (1993), because this seems close to a minimal definition which can be extended to almost all the versions of unification grammars. We use the notation and the feature machinery developed there, see chapter 8. This assumes disjoint, linearly ordered sets F eat of features and Const of constants. A standard representation of DAGs is used to define feature structures and from there it is straightforward to define a feature lattice. The definitions are augmented to deal with composite feature structures, i.e. multiply rooted feature structures and composite feature lattices to allow for the representation of phrase structure rules. The formalization assumes a context free backbone, but nothing in the treatment of the problem hinges on that. 3 Definition (Unification ID/LP Grammar) A Unification ID/LP grammar is a tuple G = (G, Φ, φ_{0}, ς_{0}, W, Lex) such that:

G = ⟨N, Σ, ID, LP, S⟩ is a (context free) ID/LP grammar. Φ = ϕ(F eat, Const) is the lattice of feature structures. φ_{0} : ID → Φ is a function that assigns a composite feature structure to each rule in ID. ς_{0} : LP → Φ is a function that assigns a composite feature structure to each rule in LP. W is the set of the word forms, i.e. lexical entries. Lex : W → ℘(Φ) is a function that assigns a set of feature structures to each lexical entry.

We write V for N ∪ Σ, φ_{0}(X_{i}) for φ_{0}(X_{0} → X_{1}, …, X_{k})|_{X_{i}}, ς_{0}(A) for ς_{0}(A ≺ B)|_{A} in case of the LP rules, and a, b, … for elements of W. It is assumed that cat ∈ F eat, V ⊆ Const and V ∩ W = Ø. ID and LP are multisets of rules to allow different feature structures to occur with the same context free backbone. Take ς(LP) to be the set of all the ς_{0}(X_{i}), then ⟨ς(LP), ≺⟩ is a transitive, asymmetric, irreflexive relation. Furthermore it is required that ∀ 0 ≤ i ≤ k φ_{0}(X_{i}).cat = X_{i} for each production X_{0} → X_{1}, …, X_{k} and likewise for the LP rules and the lexical entries. Additionally we demand that φ(a).cat ∈ Σ. The class of unification ID/LP grammars is denoted as G_{ID/LP}.

As already mentioned in the previous section, an LP rule applies under subsumption. We assume a sequence of categories and check whether they are informative enough to determine applicability of the LP rules. 4 Definition (applies) An LP rule A ≺ B applies to a sequence σ = σ_{1} … σ_{n}, σ_{k} ∈ V iff there exist i, j, i ≠ j, 1 ≤ i, j ≤ n such that ς_{0}(A) ⊑ φ(σ_{i}) and ς_{0}(B) ⊑ φ(σ_{j}).

If no LP rule applies to a structure such that it causes a violation of the imposed order, it has to be LP acceptable. 5 Definition (LP acceptable) A sequence σ is LP acceptable iff no LP rule applies to it with j < i.

We overload the definition of LP acceptability in the sense that we use it on sets of sequences of feature structures as well. The need for this will become clear later.

A requirement for the definition of parse trees is the ability to generate ordered sequences from the multisets which represent the right hand sides of ID rules. Therefore we assume a permutation function on sequences of nonterminals called permute. We can define parse trees for ID/LP grammars by including the demand that each local tree conforms to the LP rules. We assume a standard tree formalization like the one from Partee, ter Meulen and Wall (1990) and augment it by a composite feature structure for the parse tree.^{4} 6 Definition (parse tree) A grammar G = (G, Φ, φ_{0}, ς_{0}, W, Lex) generates a parse tree ⟨τ, φ(τ)⟩ for the sentence a_{1} … a_{n} iff

the root is labeled with the initial symbol S of G and φ_{0}(S) ⊑ φ(S); ∀i 1 ≤ i ≤ n a_{i} ∈ W and φ′(a_{i}) ∈ Lex(a_{i}) such that φ′(a_{i}) ⊑ φ(a_{i}); for all subtrees τ_{i} ∈ τ, where T_{0} immediately dominates T_{1} … T_{n}, there is a rule T_{0} → α in ID such that T_{1} … T_{n} ∈ permute(α) and ∀i 1 ≤ i ≤ n φ_{0}(T_{i}) ⊑ φ(T_{i}) and the yield of the local tree τ_{i} is LP acceptable.

4Note that structure sharing is indicated with a plain =, whereas equality is denoted with ≐.

The parse trees defined thus are not necessarily adequately decorated, i.e. might have some features and values that do not derive from the application of the rules and lexical entries. The formalization of this can be taken from Sikkel (1993). We just demand that parse trees are minimal in this sense. This allows the specification of the language generated by a unification ID/LP grammar. 7 Definition (Language of the Grammar (L(G)) The language generated by G is defined as L(G) = {w = w_{1} … w_{n}| there exists a parse tree ⟨τ, φ(τ)⟩ with yield w_{1} … w_{n} & φ(τ) ≐ ⊥̸}.

The parsing problem for the class of grammars in G_{ID/LP} can now be stated as follows. 8 The Parsing Problem Given a sentence a_{1} … a_{n} ∈ W^{∗} and a grammar G ∈ G_{ID/LP}, find all the parse trees for the sentence with result φ(S).

This completes the definitions which present unification ID/LP grammars. But for the solution to the problem of nonlocal feature passing, we need some additional auxiliary definitions.

Since it may happen that a structure is not specific enough to determine LP acceptability, we have to formalize when these cases do occur. This is done by weak application. It tests for the success of a unification, i.e. whether the information could be there. 9 Definition (weakly applies) An LP rule A ≺ B weakly applies to a sequence σ = σ_{1} … σ_{n}, σ_{k} ∈ V iff there exist i, j, i ≠ j, 1 ≤ i, j ≤ n such that ς_{0}(A) ⊔ φ(σ_{i}) and ς_{0}(B) ⊔ φ(σ_{j}).

Since we now can tell when there might be enough information to determine LP acceptability, it is straightforward to define possible LP violation. If a feature structure is subsumed by an element of an LP rule, it unifies with it as well. So we can not exclude the cases of application of an LP rule from our definition of weak application. So our definition has to presuppose that the structure is LP acceptable, under definition 5, i.e. that no LP rule applies to it and is violated. In that case we do not need to check for further (possible) violations since the sequence is ruled out anyway. If we could exclude application from weak application, this would not be necessary. And additionally, the weak application has to result in a violation if it is to be relevant at all. 10 Definition (possibly LP violated) A sequence σ is possibly LP violated iff it is LP acceptable, but an LP rule weakly applies to it with j < i.

Furthermore we have to add some bookkeeping device, the LP store. This is a list of the pending structures, i.e. those that are not specific enough to be determined yet^{5}. The LP store is assumed to be part of each feature structure that is assigned to a rule. The formalism presented in Sikkel (1993) can be extended by demanding that every composite feature structure that represents a rule includes a list representation of the LP store. The following defines the union of two such stores. It will be used in the deduction steps. 11 Definition (Store union (⋈)) The union of an LP store Θ with another LP store Ω with resulting LP store Δ (φ(Θ) ⋈ φ(Ω) ≐ φ(Δ)) is recursivly defined as φ(Δ) ≐ φ(Ω) if φ(Θ).hd ≐ e list φ(Δ) ≐ φ(Θ).tl ⋈ φ(Ω) if φ(Θ).hd ≐ φ(A) ∧ φ(A) ∈ φ(Ω) φ(Δ).hd ≐ φ(A) ∧ φ(Δ).tl ≐ φ(Θ).tl ⋈ φ(Ω) if φ(Θ).hd ≐ φ(A) ∧ φ(A) ∉ φ(Ω)

3 An ID/LP Parsing Schema

Sikkel (1993) develops a framework called parsing schemata for comparing parsing algorithms by abstracting from control information and data structures contained in their specifications. We are going to use this framework because it is general enough to allow the specification of nontrivial algorithms without requiring implementation specific details. The presentation of a parsing schema is done in three steps: firstly we define two kinds of parsing systems which then allow the specification of the parsing schema. A parsing system is restricted to a single given grammar and a single given sentence. For those we define a logical deduction system, called a parsing system. 12 Parsing System A parsing system for some grammar G and input string a_{1}, …, a_{n} is a triple P(I, H, D) with I a set of items; H a finite set of items (not necessarily a subset of I), the hypotheses; and D a set of deduction steps η_{1}, …, η_{m} ⊢ ξ with η_{i} ∈ I ∪ H for 0 ≤ i ≤ m and ξ ∈ I.

5This is necessary since the feature logic does not support set valued feature structures.

There can be several kinds of items. But in the following, we are using an expanded version of the familiar items of an Earley or chart parser, e.g. [A → α • β, i, j]. Now we extend this definition to an uninstantiated parsing system. This obviates the need for a fixed input string. 13 Uninstantiated Parsing System An uninstantiated parsing system for a grammar G is a triple ⟨I, H, D⟩ with H a function that assigns a set of hypotheses to each string a_{1}, …, a_{n} ∈ Σ^{∗} such that ⟨I, H(a_{1}, …, a_{n}), D⟩ is a parsing system.

It can easily be seen that in all our examples the function H is defined as follows: H(a_{1}, …, a_{n}) = {[a, i − 1, i] | a = a_{i}, 1 ≤ i ≤ n }. Therefore we are not going to make a difference in the following between uninstantiated parsing systems and parsing systems. 14 Parsing Schema A parsing schema for a class of grammars G is a function that assigns an (uninstantiated) parsing system to every grammar in G.

In the ID/LP parsing schema, we will interleave the two steps of generation via permute and testing via LP acceptability completely so that acceptance can be determined in just one traversal of the input. To achieve this, the deduction steps allowed by the direct parsing algorithm have to be modified. Augmenting Seiffert’s and Shieber’s definitions in the last section, we defined a relation that tells when an LP rule weakly applies to a sequence. Whenever this occurs, we add a sequence of feature structures to the LP store. This store may be thought of as information how further instantiation of the rule in question may be restricted. The restriction is not immediately obvious, but as soon as the rule is further instantiated, a test for LP acceptability is performed and the hypothesis discarded if the structure contained an LP violation. This added sequence of categories is structure shared with the sequence the parser assumes to be LP acceptable. So any changes that are made to the sequence via structure sharing are present on the LP store as well. In each deduction step the elements on the LP store have to be LP acceptable which achieves the desired effect. Since this LP violation can only happen in completion, this completion is ruled out, thereby preventing the parser from constructing invalid structures. The old structure is not discarded since it may be used in some other way which does not lead to an LP violation. Additionally, the algorithm has to percolate the LP stores via store union to ensure that all the edges do contain the pending LP information of their subcomponents.^{6}

Before proceding to the presentation of the ID/LP parsing schema, a short remark on notation. The items have been augmented by the LP store Δ. We abbreviate in the following the notation of items by indexing them with lowercase greek letters and then refering to the index, i.e. [A → α • β, i, j, Δ]_{ξ} is referred to as ξ. φ(ξ) refers to the composite feature structure of the item, naturally excluding the string indices. 15 ID/LP Parsing System A parsing system P(I_{ID/LP} , H_{ID/LP} , D_{ID/LP}) for a unification ID/LP grammar G = (G, Φ, φ_{0}, ς_{0}, W, Lex) ∈ G_{ID/LP} is defined by

6These processes may be improved upon in an actual implementation, see Morawietz (1995) for the implementation in Troll (Gerdemann, Götz and Morawietz forthcoming).

I_{ID/LP} = \{[A → α • β, i, j, Δ]_{ξ} | \begin{matrix}A → αβ ∈ ID \\ 0 ≤ i ≤ j \\ φ_{0}(A → αβ) ⊑ φ(ξ) \\ φ(ξ) ≐ ⊥̸ \\ α and Δ are LP acceptable \end{matrix} \}

H_{ID/LP} = { [a, j − 1, j, {}] | φ(a) ∈ Lex(a_{j}) }
D^{Init}  = { ⊢ [S → •γ, 0, 0, {}]_{ξ} | φ(ξ) ≐ φ_{0}(S → γ) }

D^{Scan}  = \{ \begin{matrix}[A → α • βaδ, i, j, Δ]_{η}, [a, j, j + 1, \{\}]_{ζ} ⊢ \\ [A → αa • βδ, i, j + 1, Δ]_{ξ} \end{matrix} | φ(ξ) ≐ φ(η) ⊔ φ(ζ) \}
D^{Compl1} =
\{ \begin{matrix}[A → α • βBδ, i, j, Δ]_{η}, [B → γ•, j, k, Ω]_{ζ} ⊢ \\ [A → αB • βδ, i, k, Θ]_{ξ} \end{matrix} | \begin{matrix}φ(ξ) ≐ φ(η) ⊔ φ(ζ) \\ φ(Θ_{ξ}) ≐ φ(Δ_{η}) ⋈ φ(Ω_{ζ}) \\ φ((αB)_{ξ}) is not possibly LP violated \end{matrix} \}

D^{Compl2} =

\{ \begin{matrix}[A → α • βBδ, i, j, Δ]_{η}, [B → γ•, j, k, Ω]_{ζ} ⊢ \\ [A → αB • βδ, i, k, Θ]_{ξ} \end{matrix} | \begin{matrix}φ(ξ) ≐ φ(η) ⊔ φ(ζ) \\ φ((αB)_{ξ}) is possibly LP violated \\ φ(Θ_{ξ}) ≐ φ((αB)_{ξ}) ⋈ φ(Δ_{η}) ⋈ φ(Ω_{ζ}) \\ φ((αB)_{Θ}) = φ((αB)_{ξ}) \end{matrix} \}

D^{P red}  = \{ \begin{matrix}[A → α • βBδ, i, j, Δ]_{η} ⊢ \\ [B → •γ, j, j, \{\}]_{ξ} \end{matrix} | φ(ξ) ≐ φ(B_{η})^{}Ψ̸_{0}(B) ⊔ φ_{0}(B → γ) \}
D_{ID/LP} = D^{Init} ∪ D^{Scan} ∪ D^{Compl1} ∪ D^{Compl2} ∪ D^{P red}

Note that our item definition demands that both the recognized sequence of categories and the LP store have to be LP acceptable. Therefore we do not have to include these demands in the deduction steps. The sequence of feature structures to the right of the bullet is treated as a multiset. This is indicated by picking a random element from it, i.e. both β and δ in the deduction steps can be empty or of any other cardinality. Furthermore it is important that in the definition of D^{Compl2} the new LP store is the result of the union of the old stores plus the sequence of categories found. This sequence is reentrant with the recognized one before the bullet. In the definition of D^{P red}, we included a restrictor (^{}Ψ̸_{0}(B)) to deal with the nontermination of the predictor. For the definition of a default restrictor, see again Sikkel (1993). Since this can be generated automatically, we did not have to include the definition of a restrictor in our grammar. 16 ID/LP Parsing Schema A parsing schema P for the class of grammars G_{ID/LP} is a function that assigns an ID/LP parsing system P to every grammar G ∈ G_{ID/LP}.

Next, we are going to present the crucial steps an algorithm along the lines of the proposed schema takes to solve the problem of nonlocal feature passing. We simplify the notation in the sense that we do not differentiate between the context–free backbone and the corresponding feature structures any more. This gives us the following format for the edges. First comes the left hand side of the rule, followed by an arrow and the categories which have been recognized already, enclosed in square brackets. The dot separates those from the set of the categories yet to be found which is enclosed in curly brackets. Next are the start and end position of the recognized part of the edge. And last there is the LP store, again in curly brackets. The whole edge is enclosed in square brackets. We are going to write the values of tags, if there are any, only behind the crucial occurences.

The edges of interest are depicted in figure 5. We assume that the algorithm is supposed to recognize the input ihjk with the grammar given in figure 1. At some point in the computation

1. [ [\begin{matrix}cat & b \\ f & [\begin{matrix}f1 & 2 \\ f2 & 3 \end{matrix} ] \end{matrix} ] → [ x [\begin{matrix}cat & e \\ f2 & 3 \end{matrix} ][\begin{matrix}cat & d \\ f1 & 2 \end{matrix} ]] • \{\} , 0 , 2 ,\{ x [\begin{matrix}cat & e \\ f2 & 3 \end{matrix} ][\begin{matrix}cat & d \\ f1 & 2 \end{matrix} ]\} ]

2. [ [cat a ] → [[\begin{matrix}cat & b \\ f & 1 \end{matrix} ]] • \{[\begin{matrix}cat & c \\ f & 1 [\begin{matrix}f1 & 2 \\ f2 & 3 \end{matrix} ] \end{matrix} ]\} , 0 , 2 ,\{[\begin{matrix}cat & e \\ f2 & 3 \end{matrix} ][\begin{matrix}cat & d \\ f1 & 2 \end{matrix} ]\} ]

3. [ [\begin{matrix}cat & c \\ f & [\begin{matrix}f1 & 6 one \\ f2 & 7 two \end{matrix} ] \end{matrix} ] → [[\begin{matrix}cat & f \\ f1 & & 6 one \end{matrix} ][\begin{matrix}cat & g \\ f2 & 7 two \end{matrix} ]] • \{\} , 2 , 4 ,\{\} ]

∗4. [ [cat a ] → [[\begin{matrix}cat & b \\ f & 1 \end{matrix} ][\begin{matrix}cat & c \\ f & 1 [\begin{matrix}f1 & 2 one \\ f2 & 3 two \end{matrix} ] \end{matrix} ]] • \{\} , 0 , 4 ,\{[\begin{matrix}cat & e \\ f2 & 3 two \end{matrix} ][\begin{matrix}cat & d \\ f1 & 2 one \end{matrix} ]\} ]

Fig. 5. Edges from the chart for input word ihjk and Seiffert’s grammar (see figure 1)

it has to create the local tree represented by the edge in 1. Note that since the algorithm cannot decide on the LP acceptability of the recognized structure and because it is possibly LP violated, it adds the sequence of categories to the LP store via structure sharing (tag x ).^{7} This information is percolated to further edges which rely on the computation of 1, for example the one in 2. Independently we construct the local tree represented by the edge in 3. At some point it becomes necessary for the algorithm to complete those two edges 2 and 3. But this can not be done as shown by the edge in 4. It is included in this chart only for the reason to illustrate the point. It would not be constructed by the algorithm. The reason for this is as follows. The completer would try to build the edge from the edges 2 and 3 by moving the recognized feature structure with the cat feature c to the list to the left of the dot. This feature structure is the result of the unification between those two feature structures from the edges 2 and 3 which have the category c. The unification forces identity between the reentrancies 2 and 6 and 3 and 7 respectivly. This results in the values one and two on the elements of the LP store which violates the LP rule [^{f1}^{one} ] ≺ [^{f2}^{two} ]. Since it is not possible to construct a parse tree in another way, the sentence is not in the language of Seiffert’s grammar.

4 Conclusions

In this paper, we defined unification ID/LP grammars and gave instructions for a parsing algorithm, thereby solving the problem of nonlocal feature passing. This enables linguists to write ID/LP grammars and gives the computational linguists a clear formalization and the means to directly parse such grammars in one pass.

Our approach presents a local solution to a nonlocal phenomenon. It uses the existing mechanism of the test for LP acceptability to detect the violations as early as they can be discovered. No complex backtracking into the chart or of the whole process is necessary, since it is not the local tree where the LP violation occurs that is seen as being invalid, but rather the combination of the information from this local tree with another local tree. It is acceptable to combine the local tree with another structure in a way that does not lead to failure.

Furthermore, the solution is neutral toward processing direction, i.e. bottom up versus top down, and processing mode, i.e. parsing versus generation. The way the solution is presented here is for a top down parser, but nothing in the way the problem is handled requires any of the special mechanisms involved with top down parsing. In fact, the first prototype to be implemented was a bottom up parser. One can just leave out the deduction steps that represent prediction. And since Earley’s algorithm may be used for generation as well as for parsing (Gerdemann 1991), it seems straightforward to incorporate our treatment of the ID/LP formalism for generation.

7This tag is special in the sense that it denotes sharing of a sequence rather than a single feature structure.

So the tag is a simplification for a number of tags which would indicate the sharing of all the roots of the categories involved.

Nevertheless, some open questions remain. Some are induced by linguistic needs and some by formal considerations. Although we are not really concerned with it, from a linguistic point of view there are some demands that have not been met by the proposed approach. In some linguistic analyses, only binary branching structures are considered, for example in Uszkoreit (1984). This would lead to problems with direct parsing from a linguistic point of view because in our approach only local trees can be ordered by LP rules. If one is dealing with these binary structures, the domain of application of LP rules has to be enlarged, for example to something along the lines of a head domain, as in Engelkamp, Erbach and Uszkoreit (1992). In our approach, this would have to be done by some extra mechanism that collects the categories in the list under the recognized feature until the projection becomes itself the argument.

A technical problem that remains to be tackled is the incorporation of set–valued feature structures into the formalization. This would simplify the definitions since we would not have to use store union in the combination of two edges but could simply unify them. But since this is a new issue and an open problem, we cannot solve it here.

The implementation of the schema for the typed feature system Troll (Gerdemann et al. forthcoming) shows that a system may use this kind of approach to provide the means for a concise representation of ID/LP grammars. The other approaches found in the literature such as for example Engelkamp et al. (1992) who incorporate a treatment of ID/LP into an HPSG style formalism by altering the ID schemata and by the creation of principles, cannot deal with the problem of nonlocal feature passing. Since in their approach the lexical items determine what must or must not appear to their left and right respectivly, they suffer from further instatiation of LP relevant information in the same way that the parser proposed by Seiffert does. All other proposed treatments of the ID/LP paradigm try to incorporate it into the formalism of HPSG directly. This reflects the different viewpoints between a rigid (denotational) formalization of HPSG and (operational) considerations which use unification grammars. Our approach defines ID/LP grammars in the latter sense.

References

Carpenter, B. (1993). ALE: The attribute logic engine, User manual, Laboratory for Computational Linguistics, Philosophy Department, Carnegie Mellon University, Pittsburgh, PA 15213.

Earley, J. (1970). An efficient context-free parsing algorithm, Comm. ACM 13.2 pp. 94–102.

Engelkamp, J., Erbach, G. and Uszkoreit, H. (1992). Handling linear precedence constraints by unification, ACL Proceedings, 23th Annual Meeting, pp. 201—208.

Gazdar, G., Klein, E., Pullum, G. K. and Sag, I. A. (1985). Generalized Phrase Structure Grammar, Harvard University Press, Cambridge, Massachusetts.

Gerdemann, D. D. (1991). Parsing and Generation of Unification Grammars, PhD thesis, University of Illinois.

Gerdemann, D. D., Götz, T. W. and Morawietz, F. (forthcoming). Troll – Type Resolution System – Fundamental Principles & User’s Guide, Universität Tübingen.

Hinrichs, E. W., Meurers D. and Nakazawa, T. (1993). Partial-VP and Split-NP Topicalization in German - An HPSG Analysis -, Arbeitspapiere des SFB 340 58, Universität Tübingen.

Lenerz, J. (1977). Zur Abfolge nominaler Satzglieder im Deutschen, TBL Verlag Gunter Narr, Tübingen.

Morawietz, F. (1995). Formalization and Parsing of Unification–Based ID/LP Grammars, Arbeitspapiere des SFB 340 68, Universität Tübingen. (Available in the World Wide Web under “http://www.sfs.nphil.uni-tuebingen.de/˜ frank/”).

Partee, B. H., ter Meulen, A. and Wall, R. E. (1990). Mathematical Methods in Linguistics, Vol. 30 of Studies in Linguistics and Philosophy, Kluwer Academic Publishers, Dordrecht/Boston/London.

Pollard, C. J. and Sag, I. A. (1994). Head-Driven Phrase Structure Grammar, University of Chicago Press and CSLI Publications.

Richter, F. and Sailer, M. (1995). Remarks on Linearization, Master’s thesis, Universität Tübingen.

Seiffert, R. (1991). Unification–ID/LP grammars: Formalization and Parsing, in O. Herzog and C.-R. Rollinger (eds), Text Understanding in LILOG, Springer, Berlin, pp. 63–73.

Shieber, S. M. (1984). Direct Parsing of ID/LP Grammars, Linguistics and Philosophy 7: 135– 154.

Sikkel, K. (1993). Parsing Schemata, PhD thesis, University of Twente, Enschede, The Netherlands.

Uszkoreit, H. (1984). Word Order and Constituent Structure in German, PhD thesis, University of Texas, Austin. Published in revised form in 1987 as Lecture Notes No. 8, CSLI Lecture Notes Series.