+ ~ -' " " ! ~.- :' yo .... 
3u~>ictri 'F.mdii~ }¢,~kiyoshi M~ti;o 
'k'm)ji/keda, Makoto Nag;u> 
Dept;~ o\[ },;lectrica,l G:,@ne, ering, 
iglyc4;o U ~fiver~;it;y, 
Yoshida,--h(~,w-,achi, ~a,kyo, Kyof;c.b 606, JAPAN 
'Phi, papet: dev, ceilm.,~ a in~xsing p~,G~:am called KGW-kp 
whk:}~ i:~ desig~md £)~ i~}~G~O,h~g various sorts of knowledge 
{.:3 get niosl, p,e\[m:l~d el, r~c~.u~ai deacdpdoli~ of ~,extt,qaices. 
'\['he ~;y~atem a(:ce, p~s *tot oaiy ,~ ,..'ei of rules specifyit~g (on: 
a~;~i~!;,~ ;~'hh:h z~ty desc.dp~\[m~s of sentence;; should sailsfy~ 
bug ;~1:m l)~'cic'~e~tJ;d ;Me,~* which a~e ~.ttil~zed ht seie(:;;ia/; 
:,t~(}t~ ~}~'l;{e}:~{:d &~acdp~.i(m,'t among possible one.q. I)~t~- 
i~tg ~.he pc,.vsing ptocess~ ghe p~efexetiM tales axe utilized 
*o seic,:~, J:ca~ible palshtg paths. Fut'thenuore, KG'W \],p 
;~g~t~c~,t~a~ descdptiou~; of sea~ettce,~ if ~equired.. The de- 
scrip~iotta ~,~e gener~,h~d iu ;~ p~'efe~entiat o~de~. 
One of the ~noat crucial problems in natmal langaag(: process- 
ing i.s h,w ~o c(mquer ~,Ile p~oblem of combinatorial " ' { XitiOSlOtlS In 
,--~ente.nee am, ly:fis\[bbrd82\]\[Tsujii84\]i~iirsh84\]\[Pereit ~.851. ,i aguis;-. 
¢i(: coztsttaini,s so far lormuh4ed by theoretical linguists are too 
weak to preve:at l,t&ny possible in¢eri)retaiion~; from being gener.- 
ate<l. They have eoueentruted oMy on Rn'mtd~;tilig of sy'Maclic 
co'a'a{raau,% which are "ol)vio~mly immllicierit lbr selcctiug :tingle 
interpretations of input se.ntences. 
.¢)~! the otiter hand, various methods have bees proposed, by 
~esea~.chers i~ Artilicial XnteHigence and Computational Li~g~lis.. 
~ics for elimiq~zting possible il~terpretatlons by ret>rring to other 
:iort~ of knoe.dedge such e,~ .~;emanti<:, pragmatic ones, etc. How 
ever, these methods are not satisfactory either, becau:3e moat ol/ 
them prem~pposc, very restricted subject tields and c~,~ano~ deM 
with the openness, the <~sential property of natural languages{ 
'Fhey al,';o lbrmulated semantic mM pragmatie lmowldge re; cos: 
aeraiats which interpretations should satisfy, 
i ilowever, hamav reader's utilize various cue~ as preferential. 
!1'hat is, there are many sorts of knowledge which scent to be 
better fon-ua~ized in the lbrm o1' rulc.~ tb*' selecting t~.as;ible inter- 
pretations. 
In ordinacy reading situations, In, mart readers cams:,* expect 
~o have a\]l infonnatlon neceasa~y for deciding interpretations. On 
lbe <:out, sty, lhcy wonhl have only incomplete, pad.ial (!uowlcdge 
' t abow;; ,::o~#;e>:is oatd s~bject fields. Eve, so, they ,:~.u e~sily tix 
single ink~rpretatknm for given sentences. They might ;;elect oue 
interpretatior~ for q s~w Mary with a telescope' based (m semautic 
i,~temaey be,;ween %0 see and 'a tele.seopeL 'Fhe.y might also 
select o~e i~tterpret~ti(ut ibr 'John wa~; given t~ book by his uncle'~ 
~3uch sclectlot~s caunot be explained by constr~ni rule.% because' 
othe* in,clip:*eta*ions are atso possible. 
\[u, this p~l)er, we propo:-;e a new l)arser called b.(,W-FI) iu 
which consh,,dn~ *'ales and lrcefe're'~¢lai# rules can be ~:eparately 
d<asrcM>ed ix* modular \[t rms an~!.-integrgted it, tit(: pa.csing process 
both e/feet;rely aml eiliciently \[Hmda86\]\[Muto88\]. 
KGYW. p i~ implemented o\[t Symbolics 3600 by using the favor 
Fig.1 shows the (uganizatiou of KOW-t.p. KCW4 p consist.s ~,\[ 
~hree separg~te composes*.% the structure b/filding coml,o,c,t 
(~BC), the prelbrence rating component (PI{C), and the :~ched-. 
uler. '1'he SBC accepL,; coustriant rules in the lbrm o|" CFG rule.~; 
with lea*are augmentations, a*~d applies them to generate sy,,- 
~aetically po:;sible struetm'es of sentences. The rule:; the SIR; 
accepts are the rules in uaification grammars. 
The SBC is a b<>ttom--Ul) aml brea<lth..iirst parser with top- 
down tiltcring 5 o,nd eonstrncts patrtial parse trees (PI)T:~) 5"o,.a 
left to right. Withont the PR,C aud the scheduler, the S\]t|C 
produces all samtaetie structures compatible with a given set o1" 
c.onstraii~t ):ides. 
0~i the other haAtd, the Pt\[(\] cotllpilt(\]:g pla, usibility wdn,:!s 
(PVs) of PP'£s geuerated by the SBC, and tlle ~,eheduler loo,~x!ly 
controls the whole parsing protest; based on PVs. 'Fhe sched- 
uler suspen(ts less prei~r~-ed patsiag paths, ~md resm,c.q ¢\]l<:m ii 
the preR.'rred oues go to deadend in the later ,~:tages of i)roccs,% 
ing. Though KOW+p works at l/romis~sing parsing paths tbs,t, it. 
can gcrerate, if required, all structural description.,; by ~c:s,mitqg 
suspended paths: 
COllstralllt Rules I)rcferonce Rtlle:; 
..... T .................. ~ - 
........ ~- ........ 8--List 
stic t 
breadth-first 
parser} 
Created i'PTs 
Fig. 1 The 0rgauization of KGig~l) 
PRC 
(Cm,lpu t a tloa 
of 
the PVs of PPrs) 
3 A~gori~hm of ~he. S}3C 
Maximal flexibility in controlling CFG parsing can be obtained in 
!,tie active (:hart parser \[Kay80\]\[WinogrM8a\]. h~ this algorith,,/ 
qchemata, ~, parsing p,'ocGqs i,':; taken as a sequence of attaching 
an active or inactive arc to Chmq, one at each time. 
Though each attachment of an arc creates a set of arc.': to 
be ~ttached, the churl parser in a/~eneral foJm does not atttmh 
6}~3 
them'in{mediately, but registers them in Agenda , A scheduler 
decides which arc in Agenda is to be attchcd next. Because no 
a priori ordering of arc attachment is assumed, one can realize 
abitrary, flexible control mechanisms in this schemata. 
llowever, such a maximal flexibility is obtained at the cost of 
efficiency. The scheduler has to be invoked at each cycle to decide 
which arc to be attached, l:'urthermore, when arcs are created, 
we have to take away tile arcs which exist in Agenda or in Chart, 
before re.gistering them in Agenda. The same ares may exist to 
the arcs only whose leftmost constituents are filled by inactive 
arcs. Because of lhe reachabilily eondilion, we also have to check 
applicability of rules to all the inactive arcs in the right neighbor, 
whenever an active arc is attached. Such repeated cheekings can 
be avoided in more restricted algorithms. 
ht KGW-t-p, we use an Agenda°like list (S-list- suspending 
list) but unlike the Agenda in the active chart parser, it only 
keeps tile arcs which will be tried after the prelerred ones fail. 
The other created arcs are attached immediately, instead of 
tlle scheduler, the SBC has its own control scheme for building 
PPTs mechanically from left to right. The scheduler of KGW-I-p 
is more like a demon watching the SBC. When it finds less 
preferred PPTs (arcs) generated, it jumps out to store them in 
the S-list. Or when it finds the SBC goes to deadend, it decides 
which suspended PPTs in the S-list should be resumed. 
The SBC in KGW+p uses two data structures, one for inac- 
. tive arcs and the other for active arcs in Chart. As in Fig. 2, 
the inactive arcs from vertex i to j are stored ill P(i, j)and the 
active arcs with ending vertices i are stored in G(i). We call the 
arcs in P(i, j) inactive PPTs and the arcs iu G(i) active PPTs. 
Both P(i, j) and G(i) are realized as flavor instances of each type 
(P-Flavor and G-Flavor). 
V, _Vj 
a~l 
a~ 
\[ of the sentence~ aa 
aa 
a5 
G(2} kepps the active PPTs whose 
uaiting constituents ~II1 be filled 
t)L t2 2 a c,ye 2: !)_ ?L !. ?_ '27_ ..... 
Fig. 2 T'~o Data Str.etures ill I(GW+p 
We also realize active and inactive PPTs as instances of the 
PPT-flavor, each of Which keeps the following items (e°PPT in 
the following means the PPT which is expressed by the flavor 
instance) 
(1)starting and ending vertices of c-PPT 
(2)syntactic category and features of the top node of 
e-PPT 
(3)completed constituents: a list of inactive PPT.. 
instances filling the child nodes of e-PPT 
(4)remainders: a list of constituents to be filled. If 
c~.PI'T is inactive, the remainders is an empty list. 
We call the leftmost constituent of the remainders 
the waili'ng constiluenL Note that the waiting con- 
stituents of PPTs in G(i) are to be filled by inactive 
t'PTs with starting vertex i. 
(5)pairs of a larger PPT which incorporates c-PPT 
as the leftmost constituent and the rule which ww~J 
used to create the larger PPT. 
'Because PPT-instances keep (1)., (4) as the arcs in Char~, 
they can be suspended ill the S-list (not immediately sLored in 
P(i, j) or G(i )) and resumed afterwards freely. (5) is used to 
avoid redundant processings in the retrial phases (see Seclion 4). 
The basic cycle of parsing is implemented as a set of method,~ 
el P--Flavor When P(i, j)-instanee is triggered,, the methods in 
P-Flavor perform the following operations for each PPT stored 
in p(i ,j). 
o (Extension of Aclive PPTs)look for active PPTs in G(i) 
which can incorporate the PPT as the leftmost constituent 
of the remainders, and create new PPTs 
© (New Rule Applicalion)look for rules wimse leftmost con- 
stituents in rhs can be unified with the PPT and whose 
nonterminals in lhs can reach to the nonterminals of the 
waiting constituents of active PPTs in G(i), and applies 
them to create new PPTs 
By storing newly created PPTs in the corresponding P(i', j') 
or G(j ~ ) immediately, a naive bottom-up, breadth-first and left-- 
to-right parsing with top-down filtering can be easily realized as 
follows. 
(1)After completion of the basic cycle, P(i, j)-instance 
triggers the execution of the basic cycle in P(i-1, j)- 
instance 
(2)A trigger to P(0, j)-instance is taken as a trig- 
ger to the SBC-manager. The manager creates new 
PPTs by using the rules A ~ aj+i (aj+l is the j+l 
th words), stores them in P(j+I, j+l) and triggers 
P(j+ I, j+ l)oinstance 
(3)Parsing is started by triggering P(0,/0)-intance 
(This leads to the triggering of P(1, 1) in (2)). 
The basic control scheme of the SBC is the same as the above 
one. However, in KGWTp, after each basic cycle of creating 
new PPTs, newly created PPTs are rated by the PRC and the 
scheduler suspends less preferred (active or inactive) PPTs by 
storing them in the S-list. Only preferred ones are stored in 
C0rrgsponding P(i', j") or G(j" ) m parallel. Thus, though the 
scheduler loosely controls the whole process, the SBC analyzes 
sentences basically from left to right in a breadth-first manner 
by its own efficient control scheme. Note that the basic control 
scheme is an extended one of the algorithm proposed by V. Pratt 
\[Pratt?5\] to deal with n-sty rules. 
684 
4. 3\[Lemi_~nix~g {}he a~_tspended PP'Pa 
Whet, all r,f preferred paths lifil, the sdleduler resumes some of 
suspended PPTs. This can be done simply by traaferring them 
(--~ . ti'om the Sdist to the corresponding P(i, j ) or u(l) aud triggering 
P(j'~ j' ). liere, .i' is the smallest one among j of P(i, j) att(l 
(J(j) iil which the resumed PPTs iu'e transferred. 
Afro: r,...'~tm'ilig the suspended PPTs, the same bottom-up, 
leR.to.righ.; a.~t(l breadth-tits, parsing is performed flora the j'oth 
word. However, special care is taken in KGW-I-p to reuse PPTs 
ah'eady constructed in the preceding trials to aw)id duplicated 
proceafing~:. 
We cat, reduce necessary processings in the ',l~lh retrial plii,~e 
.'~s lbllows. 
(Ca~',:.. 0 P(i, j) (:on,at,is no PPTs newly ereadted in 
the li-.gh retrial phase, and (1(i) contains :an active 
PPT~ ~tcwly created in the u.-ih rettiM phase : 
wc can completely skip the basic cycle for P(i, j). 
((2,,(.2) It'(/, j) coati,ins no PPTs created i, the 
u4h :etrial phase, but G(i) has ,,clive PP'Fs newly 
created in tile u-ih retrial phase: 
Whil(~ we have to perform the Ex&uaiou o/Aciiw, 
PPT~. operation in the basic cycle for each PPT in 
P(i, \]), we only have to consider the new active PPT.'~ 
iu O(i). This operatkm niay lead to creation of new 
PI.<Fs in the u-*h retrial phase. 
'We a!so have to perform tile New Rule Appliealio'~,, 
operation of the basic cycle, because the reachability 
cmtdi;imi may change, ltowever, it rn;~y happen that 
the some rules have already applied to the PP'Fs iti 
the Ibrmer trials. In this ease, because each PI'T 
keeps ~ list o\[ pairs of the larger PPTs and the rules 
(see Iteclio'a 3), we call reuse the larger lq)'l's and 
avoid creating new PPTs in tile u..lh retriM phase. 
I~t order to minimize the redundaut processings in the retrial 
phases, P- i,,nd (/--flavors provide ditlierent slots for PPTs created 
,in the u.4h trill and for those created in the former trials (sec 
l,'ig.3). '1'1,(: analysis proceeds in the retrial phases in exactly the 
s~me way as in the first trail, but the duplication of operation:: 
~re carefully avoided° 
(1) I'-l~' I a so r 
iloT.i-p|ii, ti: ll0,..ps the Inactive PP-f~.liiatailces created 
II1 the II~:th retrial ,)halle. 
re--ppts: kueps the, Inactive PPT--I,~tance,s uhlcli 
aro gro~n Is the s..th ratrlal I}hast~. Ilut 
tho saale Pl'~'~iilSialleOS Ilavo beuli created 
Is tho rotifer trial phases. 
uld-gi*ts: l~ool)s tlio l.aetlw) PP'l'~lltstianea~ ere,sled 
1tl llio (oi'i¢te,t trial plia~o~. 
(;~) (I-F I a,/or 
n~w--ppl~: ilO~l~S lho actlw t~P'f-.iilStallCoS ¢l'~alod 
Ill tll{i n-th retrial plisso+ 
olli-pptl~: k~ar~ps th0 active PPl'-tastaseos cl0atcti 
lit ,tie, for~er trial pllsses. 
Fit~.a internal Slraetare.s of the P-'~'lavor anti the t;.-Flavbr 
S ~i'k)x~scssal; of Px~efex.ence i~,uXes and ~he 
FV Calcuiati(m 
in the basic cycle, for eadt PPT in P(i, j), the SBC creates a 
set of new PP'Ps which ',corporate the PPT. These new PP't's 
represent different hypotheses b~se(l on the same l)ottom.-up ev- 
idence, the incorporated PP'j'. 
The PR,(II computes the PVs (plausibility vMues) of these dif 
fereat hypotheses by invoking a package of preferet,ce rules. A 
rule package is defined for computing the l'Vs of larger PI'Ts 
incorpratiug the same inactive PPT. That is, ~ rule package is 
delined for each syntactic category (noutermit~u.l) of a PPT to 
be iitcorporated. A set of rules tot PP-attachment, tbr examt.{!e , 
are defined in a package which is iuvoked when the incorporated 
PPT is a prepositional phrase. 
hi order to compute PVs, we can refer ia preference rains to 
various sorts of inibrmatiou as follows (we use lree and TI~EE for 
the incorporated PI'T and the iacorprating I'PT, respectively). 
(!i:)the top node of tree 
(2)the top node of TREE 
(3)eonstitnents o1: TREE already incorporated (the 
left brothers of tree in TIIEE) 
(4)sequence of active PI'Ts which eventually predict 
Tlg15'l'; (uote that each PPT keeps the larger PPTs 
which will incorprate the PPT when it is completed 
- ar.e Seclio~ 3) 
(5)lexieal inh)rma,tion of words which appear in the 
right unanalyzed portion of sentences (look-ahead) 
(4) and (~) indicate the global nature o\[ prefer(race rules of 
I~(gW-/'p in the sense thr~t tit(.' l'Vs of TREEs ~Lre eompttt¢~d 
ant ouly from the coast',seats of TREEs but also l'ront their 
suroundiag contexts (l)'igA). 
Fig.4 
lcx)k ahead (5) 
IllfOYuiltJoll referred ~n Pre\[et-elrc(! Rule.~; 
Fig.5 shows the tbrmat of preference rules. \[Incompatible- 
Gases\] enmnerates different relationships between tree and 5l'I\[I~,15 ' 
• in the package for l'P-.attaehment, we mmmerate as iucompat-- 
ible cases different types of PP-attachments such as PPs filling 
one of tile valences of verbs, PPs as adjuncts, etc. A set of 
,Independent-Evidences\] is defined lot e~,.cll incompatible case. 
Wheli a set of created PPTs with the same incorporated PP'I' 
are given, the PRC ilivokes a package, and for each created PI'T, 
it determines which e:eclusive ease matches with it. Then, the 
set of iudepeudenl evidences h)r the case is ew~luatcd. 
Each independent evidence is expressed it, a condition-w*lue 
pair and, if the condition matches with the created PPT, it re- 
turns the specified value. The PRO gets a set of values from the 
independent evidences, each of which is a primitive PV based o,t 
a certain aspect of the PPT such as semantic intimacy of words, 
welbtbrmedness of syntactic trees, etc. By combining the values 
with a certain function (currently~ we use simple addition as this 
685 
function), the PRC determines the PV for the incorporation of 
tree into TREE. 
(PRUI, E 
:CAT {one of the syntactic Categories} 
:TYPE Inon-head. |lead} Depending on whether tile category 
is the ~awl~al bar-leveI (head) or not. 
?i~o~5;;~ Ti~:?-~sE .................................... 
(:tree-cond ((eonditlon of ¢asel}) 
:independent-evidences l 
lcondition of ovidnacell Ivalue}) 
(condition of ovidenceZ} Ival~le\]) 
{condition of evidence3} (value}) 
:tree-toad (Icondltion of case2}) 
:independent-evidences 
Fig. 5 Format of the Preference Rules 
Tile actual PV of tile created PPT is deterilniued by tile 
combination of 
(1) PV in the above which is given to the combina- 
tion of tree and TREE 
(2) PV of tree 
(3) PV of TREE : TREE has already incorporated 
left constituents and have accumulated their PVs 
(4) PV of the larger PPTs which incorporate TREE 
when it is completed 
Though oue can consider any functions for integrating the 
above set of PVs, we use simple addition in the present experi- 
ments. And we do not use (4) (the PV from top-down) in this 
addition. 
In the present experilnent~ after the PRC computes the PVs 
of larger PPTs incorporating the same PPT, the scheduler sus- 
pends PPTs which have low PVs cornpared with the most prefer- 
able PPT. That is, if the difference between the highest PV and 
the PV of a PPT exceeds a certain (predetermined) threshold, 
the PPuC suspends the PPT. 
6 Experiments 
We conducted various experiments by using KGW+p. In this 
section, we will show the experiment of disambiguating sentences 
containing the word that. That can be taken as a pronoun, a 
detenninner, a relative pronoun, a complementizer, a noun as an 
antecedent of a relative clause, a conjunction for an appositional 
clause or adverbial clause, an adverb, etc. 
The followings are examples we realize as preference rules in 
the experiment. (Note that, in the present experiment, the PVs 
6iven by independent evidences are classified into 5 ranks, most 
preferred (+2), more preferred (+1), neutral (0), less preferred 
(-1) aud least preferred (-2)). 
686 
( prul e 
: cat, that 
: type head 
: t ncor~oatt b| e-cases (( I ncomp-case 
:U'ee-cond (:node-test (= hi. cat gtthat)) 
:e~ist=9oal (:cg (=cat ~tbatc) 
:bg ((:Cat Ympt) 
(: node,-test ( n~ember abs ~el f. nst:m)) 1 
:~J (:cat Xnpl)) 
: t ndepeedent-evl donees (( 1 od=evt : vtype sere 
( tr, con~-ca~e : value +1))} 
:tree-Good (:node,-test (~ .Lode ~4*that)) :exist-goal 
(:cg (:cat gthatc) 
:bg ((:cat ~.*v)) 
:n~g (:cat ~,vp)) 
:trtdependenL-evldennes ((|ed-~v| :vtype S~ 
( t ncolro-case : val oe "} 1 ) ) ) 
:tree-cond (:node~test (. re. cat ~4*IHATa)) 
:exist*goal (:cg (:cat %advc) 
:bg ((:cat ~sdec) 
(rhode-test (. aeiF. so ¢))) 
:~J (:cat ~sdec)) 
t t ndepend~ot-evl dencus ( ( I nd- evi : vt~oe prg 
(tncomp-cese : value +1))) 
:tree-cond (:node~teat (- n),cat g*ceotdet)) 
: tndependenL-evidene~s (( Ind-ev| 
vtype pr 9 
: value -2))) 
Fig.6 Ex~nple of Preference Rules 
(1) Nouns such as fact, news, etc. are often collo- 
cated with appositional clauses. When the head of a 
noun phrase preceding that is one of su& nouns, the 
apposilional clause interpolation is more preferred. 
(2) Wheat the verb in the sentence is one of the verbs 
subcategorized by that-clause, the complemeMizer ino 
terpretation is most preferrred. 
(3) When the word so or such appears iu the preced- 
ing part of the sentence, tile adverbial phrase inter- 
prelation is most preferred. 
(4) PP.-attachments over clauses are less preferred. 
(5) Omission of relative pronouns is less preferred. 
(6) The pronoun and determiner interprelaliou of 
that are less preferred in written texts. 
(7) Different usages of a verb have different prefer- 
ences. The verb to fell, for example, has five usages, 
'to tell sth to *b', 'to tell slh', 'to tell sb sth', 'to tell sb 
lhaf-cl' and 'to tell'. The last usage (the intransitive 
usage) has the least preference. 
etc. 
An example of actuM preference rules is given in Fig. 6. The 
sentences in the following are used in the experinmr, t. 
1. I told the fact that sulfuric acid dissolves the metal. 
2. I told the man that sulfuric acid dissolves the metal. 
3. I was so tired that I could not move. 
4. I was so surprised at the fact that John told us. 
5. I told the fact that sulfuric acid dissolves the metal to John. 
For 1 and 2, the SBC generates seven descriptions as follows, 
(a) \[s '" \[vp tell \[npthe \[n 1 fact lapp-el that sulfuric ..\]\]\]\]\] 
(l))\[o ... \[vptell \[npthe fact~ \[that ca that sulfuric '..\]l\] 
(c)C..\[vpteU \[npthe fact \[rel_cl\[npthat sulfmic\] ..\]\] \[npthe metallll 
(d)\[s ""\[vp teu \[np the \[npl fact \[app-cl \[np that sulfuric\] ..\]\]\]\]t 
(e)\[ \[ tell\[ the fact\] \[ \[ that sulfurm\] \]\]\] s'" vp np ' that-el np ' " "" 
(0\[.~...\[vptell \[npthe fact \[rel_clthat sulfuric ..\]\]\]\[npthe metal\]\]\] 
' (g)\[s'"\[vp tell \[np tile fact \[app_clthat sulfuric ..\]\]\[npthe metal\]\]\] 
(c)- (g) are rated low because they contain less preferred co,,-- 
structions. \]~klr example, (c) contains tile ommision of a l'elative 
pronoun, the determiner interpretation of that, a PP-attachment 
over a clause (the phrase lhe metal), etc. As tl,e result, (c) be-. 
comes tile least preferred one among the interpretations. 
(a) and (b) are most prelL>rable for 1 and 2, respectively. The 
PVs of (~;) t~a~d (b) in these sentences differ by the semantic con.. 
dillon that the usage ~to tell *b UtaVcl' prefers human as sb and 
hy the collocation condition that the noun \[ec~ is often eollo- 
c~ted with in! appositional that-clause but the noun man is not. 
For the sentences 1 and 2, gGW4'p succeeds in integrating such 
different soils of preferential cues to give the highest PVs to the 
interpretations most preti~rable for till.sna,ii readers, t,'urthermore, 
because the p~.ths which lead to these interpretations htwe the 
highest PV.,; during the whole parsing process, ~my thrrmhold vt~.l 
ues can be used for suspending less pret.~rred interpretations. 
KCW-.I p t~iso predates the valid interpretation for the sen- 
tence ~1 in i~ straightforward way, lint it erieounters certain difli- 
rallies in 4 and 5. 
At the i;ime when tl, e word ~hat is analyzed iti the sentence 
4, the tale.tire pronoun interpretation, which leads to the va.lid 
atia.lysis, h. a lower PV than the other two interpretaions. '1;'I~,,.> 
~dverbiM clause interpretation supported by the word no, and 
the ~ppositionM clause interpretation supported |)3' the word \]'acl 
have high;~.,: P'V~. Therefore, if the t!@shold value is low, the 
valid lnteri.~retatum is suspended, l, urthermore> both interprets-- 
lions sucee?d, though they contain siieh a semlmtieally less pre- 
ferred struetm'e as \[s lap a°hnl\[vp \[v telll\[n i, Its\]l} arid tile woiile 
interpretations are rated low. 
In the sentence 5, because the interpretation most preferable 
to human readers contains a PP-attaehment over a clause, it is 
rated less preferable than the one which contMns lap the \[npl. 
metal \[pp to Johnlll. 
The:se ex~i,nrples, especially the sentence 4, show |.haA, we need 
a mechanism to notice that the selected parsing pv~ths become 
less feasible (even though they do riot fail) thlm the snspendc<t 
paths. This mechanism reqnires a ~lobal method lot comparing 
colnpletely remote PPTs. We ~dso h~'we to devise a sophisticated 
method foi deciding the threshold wdue appropriately. 
'l.'~ble 71. shows the erect of the threshold values in the analysis 
of the sententce 5. In the ease when the threshold is 2, only a 
single ~nalysis result is obtained at the first trial, but the result 
is not the most fetusil)le erie foi hulnan readers 
.................... 15Z222;ii \];,ill -; ..... , ......... .... i:iEEico;~;-ii,(li,~\[t~.04 7i7i 1~.~ lS. 6~ H.~.4 
TI,, ~o~ the ,',, / 4. og " ~.~;- 
CoPapu tat Ion ....... 
No. of Suspended ..... 7,- 13 
H". ......... 7 ....... ,o. of ~.,.~o T,-oo~ -----K ..... i7 ..... i~ ~; ..... ~J 
1 I). ttle. 1~ tff_r.!jt 1.~2 .. i_ ........ 
Table 1. The Bffeet of Dlfformlt Threshold Valae~ 
7 Coati astoria 
in this paper, we de~;cribe the organization and the baMc algo- 
rithm of K(\].W+p. KGW+p allows one to prepare knowledge for 
~latural language parsing in two separate forms. One is for the 
conMrai'al type of knowledge and the other is for the preference 
type of .knowledge. 
By nsing the conslraiut type of knowledge, tile Sl-iC (Struc-- 
tme Bnikling Component) in I(GW+p produces partial parse 
trees mechanically from left to right in a breadth-llrst real> 
her. 'Phe scheduler, which is a kind of demo's watching the 
SBC, loosely controls the whole parsing process by utilizing PVs 
(Plausibility Values) given by the PRC (Preference Rating Con> 
ponent). The PRC uses the preference type of knowledge to 
compute the PVs. 
KGW+p prepares a ti'amework in which we can obtain the 
flezibiliiy of control, ilte modurarily i~ knowledge preparation , 
a.nd lhe efficiency aild completencs.~ of parsing at the same ~ime. 
I~ is a w.~ry delicate and difficnlt problem to decide the actual 
PVs of interpretations and the threshohl value for suspending 
PPTs. Because w~rious different sorts of factors may contribute 
to the PVs with different strengths, we certainly have to coin- 
brae conventional NLP techniques with appropriate statistical 
and stoeha.stie models. We hope that KGW-I p giw:s us a good 
starting imint for such future researches. 

References

\[Ford82\] Ford, M., Bresnan, J., Kaplan, it. : A Competence 
Based Theory of Syntactic Ck)sure, inThe Mental l{epresen- 
tafiou of Grammatical RelaLions (ed: Bresnan), MIT Press, 
1982. 

\[Itirst8,t\] tiisrt, G.J. : Sen,~nLic Ambiguity against Ambiguity, 
phi) thesis, B~own /0~dvertdty> J984. 

\[Ikeda86\] lked% Y., Tsujii, J., Nagao, M.: Unillcation based 
Grammar and its Control in Parsing, SI(\] on Communica- 
tion and Natural Language Processing, JSECE, 1987 (in 
Jap~mese). 

\[Kay80\] Kay, M.: Algorithm Schemata and Data Structures m 
Syntactic Processing, Technical Report CS1,-80-12, Xerox 
I'AI\[C, 1986. 

\[lVluto88\] Mute, Y., Tsujii, J., Nagao, M.: Preference Rule and 
their Application Mechanism in KGW+p, SIG on Commu- 
nieatiov and Natural Language Preceding, JSECI';, 1988 (in 
Japanese). 

\[Pereira85\] Pereira, F.: A New Characterization of Attachment 
Preferences, in Natural Language Parsing (eds: l)owty, Kart- 
tunen, Zwicky), Cambridge University Press, 1985. 

\[Pratt75\] Pratt, V.tL: A Progress Report, Prec. of 4th LICAI, 
1.975. 

\[Tsujii8,1\] Tsujii, 'J., Nakamura, J., Nagao, M.: Analysis Gram 
mar of Japanese in the MII Project, Prec. of Coling 84, 
Stanford~ 1984. 

\[Winograd83\] Winograd, q'.: Language as a Cognitive l'roeess, 
Addison-Wesley, 198;! 
