DIRECT PARSING WITH METARUI~ES 
Wilhelm WEISWEBER, Susanne PREUB 
Technical University of Berlin 
Institute for Software and Thcx)retical Computer Science 
Project KIT-FAST, Sekr. FR 5-12 
Franklinstr. 28/29, D-1000 Berlin 10 
E-mail: ww@kit.es.tu-berlin.de and preuss@kit.cs.tu-berlin.de 
Abstract 
In this paper we argue for the direct application of 
metarules ill the parsing prlx;ess and intrurluce a slight 
restriction on metarules. This restriction relies ml 
theoretical results alxmt the ternfiluation of term-rewrite 
systems and does not retinue tile expressive power of 
metarules as much as previous restrictions. We prove 
the termination for a ~t of metarnles used in our 
German gramnlar and show \[low nletarules can be 
integrated into the parer. 
1 Introduction 
1tie metarules within the theory of Genendized Phrase 
Structure Grammar (GPSG) are a very interesting 
device to express generalizations on a basic set of 
immediate dominance (ID) rules. A short introduction 
to the theory of metarules is given in the following 
section. Metarules are used to generate an object 
gnanmar from a set of basic ID rules. One of the first 
discussions about the application time of metarules 
within the GPSG theory, which has strongly inlhlenced 
the succeeding research ill this field, has been 
published by \[Thompson 821. In his article Thompson 
argued fi~r applying the metarules all at once in a 
preprocessing step (compile-tilne application). How- 
ever, our parer applies file metarules during tile 
parsing process (run-time aPldication or direct 
application). A discussion why we prefer file direct 
application is given in section 3. No matter when tile 
metarules are applied to tile basic set of ID rules, we 
have to care for tile termination of the recursive 
application of metarules. \[Thompson 82\] made a 
propo~l to guarantee termination by the definition of a 
Finite Closure (FC). This approach restricts the 
application of nlctarulcs such that one metarule can 
only be applied once in the derivation of an ID rule and 
prevents it from recnrsive al)l)licatiou. This restriction 
has been taken over by the authors of \[G~dar et Ill. 85\] 
and they gave a further restriction. They restricted the 
application of ntetarules to lexical ID rules, even 
though they knew that this restriction ulay prove to Ix; 
incompatible with the descriptive lx)wer needed for 
natural language gramnmrs (p. 59). But we think that 
there is nu need to restrict the application of mekarules 
only to lexical ID rules, even if there are proposals to 
elimi~mte file u~ of metarules and to use lexical rules 
like in LFG and HPSG (see \[Jacobson 87\]). But to do 
so with GPSG would involve crucial changes u~ tile 
theory, and therefore we preserved file metarule 
component ill our machine translation (MT) system aml 
tried to find an adequate criterion h)l tile termination of 
melarules. In our approach die granlnlar writer is lice 
to decide whether a metarule is to be applied to lexical 
ID rules or to another type of rule. 
Tile Finite Closure (FC) is too restricive, \[w.,cause in 
some cases (see tile examples of IUszkoreit 87\] and 
\[G~dar et ill. 851 in tile sections 3 and 4, respectively) 
re.cursive application is needed. In section 4 we 
present all alternative constraint on die basis of results 
in the lield of term-rewriting. "l-lais constraint is less 
restrictive than the FC. It 'allows for the definition of 
recursive metarules which may be applied freely and 
guarantees the termination. In section 5 the metarules 
of the German GPSG grammar used in our MT system 
are outlined and, with the help of the constraint in 
section 4, we show that their application is terminating. 
hi section 6 we give an outline of how to modify the 
parsing process in a way that nretarules can be applied 
directly rather than at compile-time. In the last section 
we draw sonre conclusions for future work in this field. 
2 Metarules in GPSG 
Metamles are one of file most criticized devices of the 
GPSG lonnalisnl. GPSG is a grmnmar fomvalism that 
states most ol ils generalizations on the level of local 
trees. Melarules were introduced to capture 
generalizations on tile mt of 1D rules. An ID rule states 
tile d()ulinance relation bctweA~n tile mother category 
and a umltiset of (laughter categories in a local tree 
with()ut fixing the linear precedence relation of tile 
(laughters. ID rules have the following torrent: 
Co) - ~ Cl, C2 ..... C~ 
Melarutes define a relation on ID rules. They have the 
lollowing tk~rlnat: 
'input ll) rule scheme' ~ 'output ID rule scheme' 
and can be read as: If tile ~t of \[D rules contains an ID 
rule which is nlatched by 'input ID rule scheme', then it 
also contains an Ill rule that matches 'output ID nile 
seheule', where the feature SlW.cifications of the input 
ID rnle are tanled over to file output ID rule if not 
specilied otherwise by the melarule, For example the 
metamle VP\[-PAS\] --~ W, NP\[acc\] ~ VP\[+PAS\] --) 
W, (PPIby\]) states the connection between active and 
passive, where W is a vltriablc ranging over a (possibly 
empty) nmltiset of categories. The major point of 
criticism against mcumdes is tlmt they increase the 
generative power of GPSG ill an undesirable way when 
they are recursively applicable, because this may lead 
to arl infinite set of ID rules. The resulting grammar 
need not be context free. Ill order to remedy the 
situation, suggestions of varying radicality were made. 
The pruposal of \[Thompson 82\] and \[Gazdar et al. 85\], 
which tries to maintain metarules, was simply to apply 
a nleulrule ill most once in the generation of an ID rule. 
This stipulation is somewhat strange, because it allows 
for recursive metarules and just prevents them from 
being applied recnrsively. 
\[Kilbury 861 suggested to eliminate nletarules by using 
category co~K;cnrrence restrictions. 
The most radical prolxlsal was to dispense with 
metarules. Bnt our aim was to stay within the 
ti'amework of GPSG, and it would be a loss to dispense 
with melarules, beeanse GPSG formulates for example 
valency of verbs and other constituents on the level of 
ID rules aud nm'tarules are the means to capture 
generalisations on diat level. 
For this rca.son we formalize the properties of 
metarules that terulhiate recursive application and state 
ACTES I)E COLING-92, NANTI.:S, 23 28 AOL'I 1992 l 1 l 1 I)ROC. Of U.OLING-92. NANTES, Au(i. 23-28, 1992 
them as a condition that a set of metarules narst fulfil. 
Metarules can then be applied freely. 
3 Application time 
There are two possibilities for the time to apply the 
metarules. The first is to compile the basic set of ID 
rules (compile-time application) in a preprocessing 
step. Thompson calls it all-at-once approach. The 
other possibility is to apply the metarules during the 
parsing process (run-time application or direct applica- 
tion), which Thompsoo calls as-needed approach. 
Thompson argued for the compile-time application 
because the direct application of metarules has the 
following disadvantages (see \['/homlrson 82\]: p.5): 
(1) If a metarule can be applied to an ID rule during 
the parsing process, the metarule has to be applied 
again when the ~me ID rule is involved in the 
same or a subsequent parse. 
(2) To store the structures generated by ID rules 
which are the result of the application of a 
metarnle is just another instanoe of the compile- 
time application. 
(3) Derivations of ID rtdes of length greater than one, 
i.e. ID rules which are the results of applying 
more than one metarule to one basic ID rule, will 
rapidly expand the .search slmme. 
In order to look a little bit closer to Thompson's 
arguments and to stay on his line, we presuppose that a 
kind of top-down parsing method is used and there are 
n basic ID rules and m ID rules, generated by the 
. application of the metarules. 
Wheu looking to argument (1), we see that it is an 
argument lor the ran-time approach. If the metarules 
are applied at compile-time a huge set of ID rules is 
compiled from the basic set. For exanlple if we would 
apply the metarules of our MT system (see section 5) 
to our basic set of 80 ID rules at compile-time, wc 
wonld get about 240 ID rules in the object grammar. 
Let us assume that some category C has to be expanded 
m~d there are i ID rules in our grammar with mother 
category C. In the compile-time approach the parser 
would have to check (n+m)/n*i ID rules on average, 
whereas in the run-time approach i ID rules and 
(n+m)/u metandes ((n+m)/n+i rules) have to be 
checked for application to these ID rules. In the normal 
case that are less than in the compile-time approach. 
Argument (2) is indeed an argument for the run-time 
approach. Let as again consider the above example 
and each of the i ID rules has d daughters on average. 
If the category C is expanded according to all ID rules, 
in the worst case (n+m)/n*d*i (partial) structures have 
to he stored ou average in the compile-time approach. 
These structures are very similar, because in general 
the metarules modify the ID rules slightly. The run- 
time approach can make use of this fact and stores only 
approximately d*i (partial) structures and additionally 
(n+m)/n*i structures after the application of the 
metarules. That makes ((n+m)/n+d)*i sn-netures to be 
stored in the run-time approach. The common parts of 
die ID rules generated by metarules need not to be 
stored, that are (n+m)/n*(d-1)*i-d*i partial structures 
less. For example if n = 80, m = 160, d = 3 and i = 10 
then Otis would mean that on average 30 partial 
structures less have to he stored for the corresponding 
constituent. 
Conceruing argument (3), \[Barton et al. 87\]: p.226 
showed that the computation of the Finite Closure (FC) 
of a GPSG G with x ID rules and y metarules can 
increase the number of the ID rules worse than 
exponentially, namely from x to more than X 2y, i.e. 
there is no difference between the compile-time and 
run-time approach. 
In order to sum up fltis discussion, we can say that 
there is no difference in complexity between the com- 
plile-time and file run-time approach with respect to the 
arguments in \['lltompson 821. The direct approach is 
even preferable to the eomplile time approach when 
looking at the arguments (1) and (2), which are indeed 
arguments for direct application of metarules. 
There is another argument for direct application of 
metarules. The FC in \['lltompson 82\] states that every 
metarule can apply at most once in the derivation of 
any given object grammar rule from one basic rule. An 
example for the recursive application of a metarule has 
been proposed in \[Uszkoreit 87\]: p.145 in his German 
grammar. It makes the adverbial phrase (AdvP) a sister 
node of the verb and its arguments: 
V2\[-AUX\] --~ V, W ~ V2\[-AUX\] --~ V, W, AdvP 
This metarule is to solve the problem that adverbial 
phrases can be interspersed freely among the 
arguments of the verb and the number of AdvPs in a 
verb phrase is not limited (but it is finite) and the 
metarule has to be applied recursively. This fact would 
rule out the definition of this metarule with respect to 
the definition of the FC wltich has been adopted also in 
\[Gazdar et al. 85\] to avoid the production of an infinite 
number of ID rules. Uszkoreit tried to circumvent the 
l~rublem in redefining the above metarule such that it 
fits the requirements of the FC. It employs the Kleene 
star operator:. 
V2\[-AUX\] -+ V, W :=~ V2\[-AUX\] --~ V, W, AdvP* 
This change of the memrule is not uecessary if the 
metarules are applied directly during the parsing 
process and the above melarule without the Kleene star 
can be applied freely, because the termination is 
determined by tile finiteness of the input string. 
4 Termination 
No matter whether the metarules are applied directly or 
at compile-time, we have to cam for the termination. 
We think that the restriction on the application of 
metarules imposed by the Finite Closure (FC) is too 
strong. That may have crucial consequences for some 
metarnles. Look for example at the Complement 
Omission Metarule from the English grammar in 
\[G~dar et al. 85\], which is \[+N, BAR 1\] --~ N °, W :=2, 
\[+N, BAR 1\] --~ N °. This metarule deletes optional 
complements of nouns. For example the noun gift may 
have two optional prepositional phrases as comple- 
ments, i.e. N I ~ N o , (PP\[of\]), (PP\[to\]). The 
prepositions of add to are fixed but either of the PPs or 
both may be left out: the gift, the gift of John, the gift 
to Paul, the gift of John to Paul. The above metarule 
only allows for the gift and the gift of John to Paul, 
because it deletes all complements of the noun. The 
correct me "tarule would be: 
\[+N, BAR 1\] --~ N °, X, W :::*, \[+N, BAR 1\] --~ N d, W 
\[(;~dar et al. 85\] have not been able to define this 
metarule, because it has to be applied recarsively add 
the FC does not allow recursive application. For this 
reason we decided to define another constraint which is 
not so restrictive. 
As it Ires turned out, most of the metarules which have 
been defined within the fragment of English in \[Gazdar 
et al. 85\] or of German (see the .section below for a 
more detailed diseussion) are or can be defined in a 
ACRES DE COI.1NG-92, NANIES, 23-28 AO~r 1992 1 l 1 2 PRO(:. OF COLING-92, NANTES, AUG. 23-28, 1992 
way that guarantees rite termination of the recursive 
application of metarules. In order to prove the 
termination, some research results within the field of 
term-rewriting can be applied (see \[Dershowitz 82 and 
85\] for general results and \[Weisweber 89\], \[Weiswe- 
bet/ llanen~hild 901 and \[Weisweber 92\] for an 
application to mappiugs within machiue translation). 
ID rules can be viewed as tenns and metarales can be 
viewed as term-rewrite rules, because they derive one 
ID rule from another. A set of term-rewrite rules 
terufinates if an ordering '>' on the terms of the left- 
hand and right-hand sides (lhs and rhs, respectively) of 
the rewrite rules can be defined. This may be a 
quantitative ordering, e.g. a category occuring on the 
lhs of a metarule is deleted on its rhs, or a qualitative 
ordering, e.g. art operator precedeuce. We think that a 
mixture of both types of orderings is needed to prove 
the termination of sets of metarules. If a qualitative and 
a quantitative ordering are merged, the resulting 
ordering guarantees termination (see \[Dershowi~ 82 
and 85\]). The operator precedence that is nsed in our 
MT system is in fact a precedence ordering on feature 
values occurring at rite categories of the lhs and rhs of 
the metarules. 
Termination condition for metarule application 
For every metarule lhs ::> rhs, Ihs > rhs. lhs > rhs 
(it a daughter category occnrriug on the lhs is 
deleted on the rhs and/or 
(it) an operator precedence >or. on feature values 
occurring at the categories of the lhs and rhs can 
lye defined, which is not contradictory for the 
whole set of metarules and 
(iii) every variable for (multisets of) categories 
occurring on the rhs occtws on the lhs. 
Melarnles have to fulfil the conditions (it and (iii) or 
(it) attd (iii). The condition (it is a quantitative 
ordering and the termination of melarules which fulfil 
(it is obvious, because everytime such a meuu'alc is 
applied one category is deleted aud the number of 
daughter categories in an ID rule is finite. 
The condition (it) is a qualitative orderiug. The termi- 
nation of metarules which fulfil (it) is not as obvious as 
in (it. It means that a feature value of a category h,'ts to 
be changed and there must not be another melarule, 
which reverses the change of this feature value. It 
allows\[br not haviug to delete categories, addiug 
categories or adding values to a list, which may be a 
feature value, on the rhs of a metarule, if a feature 
value is changed on another category. This is the 
reason why we decided to impose cotttrol on the 
definition of metarules and not to move away frum 
such devices ,as recent research iu coutputational lin- 
guistics does. If a metarulc fulfils condition (it) it can- 
not be applied for a second time iu a derivation of an 
ID rule, because once a feature value has been cluanged 
it will never be reversed and the metarule will not be 
applicable again, qhis part of the termination condition 
simulates the tenninatiou condition of the FC. 
~lhe condition (iii) prohibits the introdnetion or 
doubling of variables for (mnltisets of) categories on 
the rhs. 
Thus the termination of a certain set of metarules can 
be guaranteed, iff for all metarules either the metarule 
deletes a category occuring on its Ihs and/or a non-con- 
tradicting precedence on operators (feature values of 
the categories occurring iu the metarule) can be defined 
and all variables occurring on the rhs occur on the lhs. 
qt~e application of the termination condition is demon- 
strated with the melarules for Germm~ in the next 
.section. 
5 Metarules for German 
Our GPSG syutax of German is based on the grammar 
developed in \[Uszkoreit 87\]. We assume a fiat 
structure for the verb and its complements including 
the subject. Subeategorization of verbs is staled in ID 
rules of the following form: 
V3 "4' V°\[ SUBCAT (~n\], C1 ..... C.. 
V 3 is a ~ntential category and SUBCAT f~ means the 
fixed value for the subeategorization feature in the 1D 
rule with n arguments, but for every subeategorization 
there is a seperate rule. The subject of main verbs is 
included in the rhs of the rule. Unlike Uszkoreit's 
approach we do not add the subject to the complements 
of a verb phrase via metarule application but reduce a 
sentential category to a verb phrase and delete the 
subject. The following Subject Deletion Metarule 
fulfils the termination cottditions (i) and (iii), because it 
deletes the category DP\[nom\].t 
Subject Deletion Metarule: 
V3\[-AUXI --~ V °, W, DP{nom\] 
V2\[-AUX\] -~ V °, W 
Additionally, the operator precedence 'BAR 3' >oP 
'BAt/2' has to be defined, because the feature BAR at 
the mother category is changed on the rhs. This 
additional definition is needed in order to get a non- 
contradicting set of operator preeexlence definitions out 
of the whole set of mctarules in the grammar. 
"lhe Slash "fermination Metarule is responsible for 
ending (or from the bottom-up view, for the introduc- 
tion of) a long distance relationship that is handled in 
GPSG via the category-valued feature SLASIt. Unlike 
\[Gazdar et al. 85\] we do artt have a trace. Traces cause 
problents in fiat structures without fixed word order, 
becau~ there are multiple analyses that are only 
different with respect to the position of the trace. 
Slash Termination Metarulesi 
V3\[-AUX\] ~. V 0, W, X 2 
V3\[-AUX, SLASH X 2\] --) V °, W 
V~\[-AUX\] -~ V °, W, V 3 
V31-AUX, SLASH V 3\] -). V °, W. 
Here the tenninatiotL conditions (it and (iii) are al~ 
fulfilled, because a category of the rhs of the ID rule is 
deleted. The operator precedence definitions are 
'SLASH ~,2 >o~, 'SLASH X 2' and 'SLASH ~' >oP 
'SLASH V 9', respectively. 
"lt~e Extraposition Metarule handles complement sen- 
tences and infinitive constructions that we treat as 
dislocated when they appear in the fianl position of a 
sentence. Another category-vahted feature, SLASHI, is 
The category DP is a determiner phrase according to the 
X-Bar-Schema in the Government and Binding Theory. 
'F ~' means that the feature F has the value '~' (see 
\[Busemann/ Hauenschikl 88\] and \[Busemaan/ Hauen- 
schild 89\]). This is equivalent to file notation -\[F\] of \[Gazdar et at. 85\] mad means that the value for F is 
always undefined, i.e. the corresponding category does 
not take a value for F. "lqm value '7' is sw~ially treated by 
the unification and the feature instaariation principles. 
AcrEs DE COLING-92, NA1Vn:.s, 23-28 not',~r 1992 1 1 1 3 PROC. OF COL1NG 92, NANTES. Anti. 23-28, 1992 
introduced for them. The feature specification 
-COH(erent) marks categories that can be extraposed. 
This metarule fulfils the termination conditions (i) and 
(iii) and 'SLASH1 ~' >op 'SLASH1 X\[-COH\]' has to be 
defined. 
Extraposition Metarule: 
V 3 ---) V °, W, X\[-COH\] 
V3\[SLASH1 XI-COH\]\] ~ V °, W 
The metarule for passive is an example in which the 
termination conditions (ii) and (iii) are necessary, 
because no category is deleted and an optional 
prepositio~ml phrase is introduced that replaces the 
accusative determiner phrase: 
Passive Metarule: 
V3\[-PAS\] -~ V o, W, DP\[acc\] 
V3\[+PASI -~ V °, W, (PP\[von\]). 
Here the change of the feature specification of PAS at 
the mother category can be used for terminating 
melarule application and we have to define '-PAS' >or, 
'+PAS '3 and "DP\[acc\] >oP PP\[vonl ".4 
The Auxiliary Metarule is similar to the Passive 
Metarule in that feature values of some categories are 
changed and the termination conditions (ii) and (iii) are 
fulfilled. Here it is the BAR level of the mother and 
V3-daughter that are lowered in analogy to to the 
Subject Deletion Metarule. The operator precedence to 
be defined is 'BAR 3' >oe 'BAR 2', which already has 
been defined in connection with that metarule. 
A uxUiary Metarule: 
V3\[+AUX\] --4. V 0, V 3 ~ VPI+AUX\] --4 V °, VP 
AS we have seen, the Subject Deletion, the Slash 
Termination and the Extraposition Metarule fulfil the 
criterion of deleting a category on the rhs of the 1D 
rule; the Passive and the Auxiliary Metarule change 
feature values at the categories. For all metarules a 
non-contradictory set of operator precedences can be 
defined and the application of the whole set of 
metanfies will terminate in every case. 
Even the AdvP-metarule in section 3 proposed by 
\[Uszkoreit 87\] can be treated when the me 'tarules are 
applied directly, because we can give a proof for its 
termination, which is guaranteed by the finite length of 
the input string in connection with direct application. 
This is another argument for the direct application of 
metarales. 
6 The parsing process 
In our parser, which is a part of an experimental 
machine translation system (see \[Weisweber 87\] for a 
3 Treating passive, one has to say a word about semantics. We do not adopt the semantics of \[Gazdar et al. 85\] 
because of its shortcomings (see \[Urnbach 87\]), but developed a semantic level of our own that captures file 
functor argument structures (FAS, see \[Busemann/Hau- enschild 891 and \[Hanan~hild/Umbach 88\]) of sentences 
and is derived from the syntactic strucnlre via term- rewrite rules. Here an explicit assignment of semantic 
roles to complements of verbs takes place that is dependent on the subcategorization of the verb and its 
voice. 
4 In this case we have to define a procedence for all feature values which are changed. 
detailed description of file parser without direct 
application of metandes), the metarules are defined 
according to the following scheme: 
Co ~ Co, W, Cd ~ C6 ~ C~, W, (C~) 
Co, Cc and Cd arc categories and W is a variable for a 
(possibly empty) multiset of categories. The categories 
C6 and C~ correspond to Co and Co, respectively, in 
terms of {Gazdar et at. 85\]. The category C~ can be 
viewed as a condition category for the application of 
the metarule. Cd is the category which is to be deleted 
or modified. This is indicated by the brackets arround 
C~, If Cd is to be deleted, C,~ is left out on the rhs of the 
metarule. If C d is to be modified, C d is replaced by C,~. 
The feature values of the categories are cospecified on 
the lhs and rhs of a metarule, if not specified otherwise. 
This causes the values to be carried over to the rhs. If 
the metarule should only be applied to lexical ID rules 
as proposed in \[Gazdar eta!. 85\], the category Cc has to 
be Ihe lexical head with respect to Co. 
The proof for the termination of .sets of such metarules 
is simple. At first we look at the case in which C~ is 
deleted, then the termination condition (i) holds. 
The second case is that the category CA is replaced by 
the category C,~ and the number of categories is not 
reduced. Now the termination condition (ii) has to be 
applied and at least one feature value of the categories 
{Co, C~},~ Um W has to be changed, which must not be 
reversed by another metarule. 
The termination condition (iii) holds in every case, 
because the variable W occurs on both sides of the 
metarule. 
In order to apply the metarules directly during the 
parsing process, all the categories of an ID rule, which 
are matched by the multiset {C~},,, t.-)m W, have to be 
collected by the parser. This is done for example by the 
Completer of the modified Earley algorithut (see 
\[Earley 70\], \[Shieber 84\], \[Kilbury 84\] and \[IMirre/ 
Momma 85\]). Suppose the Completer tries to complete 
with the inactive edge (C~, i, j, T'{},~), which is 
spanning li'om node i to node j of the chart, where ~' is 
a multiset of daughter categories which have already 
been analysed and the remainder, i.e. the tnultiset of 
daughter categories still to be analysed, is empty and 
C,~ is the mother category of the ID rule, which is 
licensing this edge. M is the ~t of metarules. 
If (Co, h, j, (x.\[~) is an inactive edge and ~ 
Cc, W,C,~ :=:, C;~ ~ C~, W) ~ Mand 
\[Cd}~ and 
fee (~ t..Jm 1~ 
then the Completer introduces a new inactive edge 
(C;~, h, j, (Z'{}m) and computes its closure. The 
category C~ in O~ t..3~ ~ is replaced by C~. 
If (Co, h, i, ¢z-13 ) is an inactive edge and 
(C0~C~,W, Cd ::~ C6 ~C'o,W,C,~) ~ Mand 
C~ c ~ L) m ~ and 
Cd E D and 
C~ is consistent to the categories in ~/{C,l}m with 
respect to linear precedence 
then the Completer introduces a new edge (C6, h, j. 0¢ 
u,,, (C~}~-~/{C,j}m) and the category C~ in O~ t.J~ 13 
is replaced by C~. If the remainder \[~/{Cd},, = { }m then 
the closure of this edge has to be computed. 
The advantage of direct parsing with melarules is an 
increase of efficiency, because all the inactive edges 
which are licensed by ID rules indroduced by 
metarules need not to be stored seperately and the 
number of inactive edges generated by the Earley 
parer is reduced considerably. 
ACRES DI~ COL1NG-92, NAN'IX.S, 23-28 Ao(rr 1992 1 1 1 4 I'ROC. Ol: COLING-92, NANTES, AUG. 23-28, 1992 
Another interesting approach to direct parsing with 
metamles, in which the metarules are treated as special 
kinds of context-free roles, is presented in \[Kay 83\]. 
7 Conclusion 
Metarules are an interesting device to express some 
important generalizations on phrase structure rules of a 
uatural language granlmar. If they are used in 
preprocessing to compile a huge set of rules out of a 
small set of basic ones, file parsing process may 
become very inefficient, because it has to care for the 
set of basic rules and additionally for the rules which 
have been derived from them and are very similar to 
the basic ones. When metarules are applied directly 
during the parsing process, only the set of basic rules in 
connection with the mctarules have to be considered by 
the parser. This reduces the set of intermediate 
~fiutions (inactive edges) to be stored considerably. 
lu order to apply mEtarulcs directly, it has to be 
guaranteed that the given set of meturules will 
temlinate if all metarules fulfil the tcrraination criterion 
in section 4. We gavc tile termination proof for the 
metarules of our German grammar in secdon 5. We 
think that with file help of this criterion the termination 
of every relevant set of ioelarules can be proven, 
because a metarule is defined to change something in 
an ID rule, either to delete a category, to modify Sonic 
feature values, to add a category or to do a combination 
of all. With the termination criterion it is possible to 
construct a device which automatically proves the 
- termination of a given set of metarules. This algorithm 
computes the set of operator precedences from the 
feature values which are changed on the categories of a 
metarule. 
To enable the parser to process metarules like Uszko- 
reit's tor AdvPs in section 3, which add categories to 
basic ID rules and for which the termination can be 
proven, will be suhject to future work. 
8 References 
\[Barton et al. 87\]: G. ~lward Barton, Robert C. 
Berwick and Eric Sven Ristad: "Computational 
Complexity and Natural Language", MIT Press, 
Cambridge (Massachusetts), London ~ngland) 1987 
\[Basemann/Hauenschild 88\]: S. Busemann, Ch. 
Hauensehild: "A Constructive View of GPSG or How 
to Make it Work", in: Prcxzs. of Coling 88, Budapest 
1988, pp. 77-82 
\[Basemann/Hauen~hild 89\]: S. Busemann, Ch. 
Hauenschild: "From FAS Representudons to GPSG 
Structures", in: S. Busemann, Ch. Hauenschild and C. 
Ombach (eds.): "Views of the Syntax/Semantics 
Interface", in: Precs. of the Workshop "GPSG mid 
Semantics", KIT-Report 74, Technical University of 
Berlin 1989, pp. 17-43 
\[Dershowitz 82\]: N. Dershowitz: "Orderings for Term- 
REwriting Systems", Thcorelical Computer Science 17 
(1982), North-Holland, pp. 279-301 
\[Dershowitz 85\]: N. Dershowi~: "Termination", in: 
G.Goos, J. Hartmanis (eds.): "Rewriting Techniques 
and Applications", LNCS 202, Dijon, France 1985, pp. 
180-224 
\[Drrre/Momma 85\]: J. D0rfe, S. Momma: 
"Mtxlifikationen des Earley-Algorithmus und ihre 
Verwendnng ffir ID/LP-Grammatiken", Mmarscript of 
the Institute for Computational Language Proce, ssing 
(IMS) at ate University of Stuttgart 1985 
IEarley 70\]: J. Earley: "An Efficient Context-Free 
Parsing Algorithm", Communications of the ACM 13 
(2) 1970, pp. 94-102 
\[Gazdar et al. 85\]: G. G~dar, E. Klein, G. Pullum and 
I. Sag: "Generalized Phrase Structure Grammar", 
Oxford, Blackwell 1985 
\[Hauenschild/Umbach 88\]: Ch. tlauenschild, C. 
Umbach: "Funktor-Argument-Struktur, Die 
~tzsemantische Repraseutatious- und Transferebene 
im Projekt KIT-FAST", iu: J. Schlitz (ed.): "Workshop 
Semantik trod Transfer", EUROTRA-D Working 
Papers No.6, Saarbr~icken 1988, pp. 16-35 
IJacob~u 871: P. Jacobson: Review of \[Gazdar et al. 
85\], in: Linguistics and Philosophy 10, 1987, pp. 
389-426 
\[Kay 83\]: M. Kay: "When Meta-rules are not Meta- 
rules", in: K. Sparck Jones. Y. Wilks (eds.): "Auto- 
matte Natural Language l'arsing", Ellis Horwood 
Limite.d, West Sussex, England 1983, pp. 94-117 
\[Kilbury 84\]: J. Kilbury: "Earley-basierte Algorithmen 
fiir direktes Parsen mit ID/LP-Grummatiken", KIT- 
Report 16, Technical University of Berlin 1984 
\[Kilhury 86\]: J. Kilbury: "Category Coocurrenee 
Restrictions and the Elimination of Metarules", in: 
Procs. of Coling 86, Bonn 1986, pp. 50-55 
\[Shieber 84\]: S.M. Shieber: "Direct Parsing of ID/LP 
Grammars", Linguistics aod Philomphy 7 1984, pp. 
135-154 
\[Thomt)son 821: H. Thompson: "Handling Melarules 
in a Parer for GPSG", I).A.I. Research Paper No. 175, 
University of Edinburgh 
\[Umbach 87\]: C. Umbach: "Zur semantischen 
Interpretation in der Tbeorie der GPSG", KIT-lAB 19, 
Technical University of Berlin 1987. 
\[Uszkoreit 87\]: H. Uszkoreit: "Word Order mid 
Constituent Structure in German", CSLI Lecture Notes 
Nmnber 8, Stanlord University 1987 
\[Weisweber 87\]: W. Weisweber: "Ein Dominmlz-Chart 
Parser fiir generalisierte Phrasenstruktnrgrammatiken", 
KIT-Report 45, Technical University of Berlin 1987 
\[Weisweber 89\]: W. Weisweber: "Transfer in Machine 
Translation by Non-Confluent Term-Rewrite Systems", 
in: Procs. of the 13th German Workshop on Artificial 
Intelligence (GWAI-89), Eringerfeld, September 1989, 
pp. 264-269 
\[Wcisweber/Hauenschild 90\]: W. Weisweber, Ch. 
tlauenschild: "A model of Multi-Level Transfer for 
Machine Translation and Its Partial Realization", KIT- 
Report 77, Technical University of Berlin 1990 and to 
appear in: Procs. of the Seminar "Computers & 
Translation '89", Tiflis 1989 
\[Weisweber 92\]: W. Weiswebev. "Term-Rewriting as a 
Basis for a Uniform Architecture in Machine 
Translation", in: Procs. of Coling 92, Nantes 1992 
Aclv:s DE COLING.92. NAICrES, 23-28 hot'rr 1992 1 ! 1 5 t'Jtoc:. O1: COLING-92, NANTEs, AUO. 23-28. 1992 
