ѧ
JOURNAL OF SOFTWARE
1999ꡡ109ڡVol.10No.91999



LR㷨﷨ϵ*
ܻƽͦ»
ժҪΪ˻ȡ֮﷨ϵԴﵽ׼ȷĿģ¸һֻڴLR.
ؼʡ룬ķ޹ķмԣLR㷨.
ͼšTP18
Using LR Algorithm to Analyze the Grammar Relations of Chinese
ZHOU Hui-ping,WANG Ting,CHEN Huo-wang
(Department of Computer Science Changsha Institute of Technology Changsha 410073)
AbstractIn order to obtain the grammar relations between the words in Chinese sentences and analyze Chinese correctly, the authors present an extended LR algorithm based on phrases in this paper.
Key wordsMachine translation, dependency grammar, context-free grammar, interlingua, LR algorithm.
ǹ﷨ǳ.磬ʳͱ⣬νͶ.ʺݴʼȿν״Ҳ.һӿ԰νʣʺݴʣҺ﷨ûṩκα־֮Ĺϵ.ˣȷи֮ĹϵǺһǳͷۣҲȷǷǳѵ.
﷨ϵԴķеϵ֮ڵϵ.﷨ϵ֮ҲűȽϼ򵥵ĶӦϵ.ǲһLR㷨ʼ﷨ϵĿǰ,㷨ӦһмԵĺӢϵͳ(interlingua-based Chinese-English natural-language translation,ICENT)1Уȡ˱ȽĽ.
1ʼ﷨ϵ
ķ(dependency grammar)Tesniere21959һ﷨.1965,Gaifman3ݶʽʽѧ.ķֱ֮ĹϵϵĴδʡʩ֮ܶĹϵ.üͷʾϵӡķֱ֮ĹϵĽṹͼ1ʾ.
ͼ1ԿǾӵĴʣֱĴ3УķϵǱֱӡδ.ֱڡķĴֻС桱δ.

ͼ1ӡķֱ
֮Ĺϵ֮ϵ
ͳķֻ˴֮ϵûκ﷨Ϣ.ֱʾͷӣԵ̫֣̫Ϣ.Ƕ˸ĽмһЩ﷨֮ܺ﷨ϵ.ǽд
fA(XA),
X,AǾеʷṹfAXA֮﷨ϵsent, pred-obj, man-predֵ.,Ծӡķֱ֮ĹϵͿ£
(1) att-obj棬ķ(2) man-predֱӣ(3) quan-objʣ
(4) obj-dir3֮䣩 (5) obj-aux4ģ(6) att-obj5ϵ
(7) pred-obj26 (8) agent-pred17(9) end8
Ľ﷨ϵ˾и֮ĹϵԼھе﷨ܣʹӵĿһĿȻ.﷨ܺϵͳмԽṹԴʻ﷨ܵһһӦģڴ﷨ϵıʾмԽṹֱת.ICENTͨʵд޹ķʹϵͳڵõͬʱþӴʼ﷨ϵ. 
2LR
LR㷨ԭΪƵģһŷݾһĶƽ߹Լ.Դһ޹ضͨ㷨Զ.ͳLR㷨ֻܴ򵥵޹ķڷеΪ.ָ,ڷĳһͬʱƽ͹ԼԼ.֮Tomita4ݶԻ޹ķLR㷨䣬ʹܹƽԼ,ҲƽԼʱƷջÿջȥɷеһֿԣɶ.Ϊ˷дICENTķʹõ޹ķûκƣݹ.磬µһķ1ʾ.
(1) STARTS(2) Spron VP(3) SVP(4) VPverb S
(5) VPLOC VP(6) VPVP noun (7) VPverb aux (8) LOC noun direc
1ķɵķ

ƽԼGOTO
Statepronverbnounauxdirec#SVPLOC
0sh1sh2
sh3sh456
78
1sh2
sh3sh47
98
2sh10
3sh1sh2
sh3sh4116
78
4sh12
5acc
6re3re3re3re3re3re3
7sh13
8sh2
sh3sh47
148
9re2re2re2re2re2re2
10re7re7re7re7re7re7
11re4re4re4re4re4re4
12re8re8re8re8re8re8
13re6re6re6re6re6re6
14re5re5re5re5re5re5

ڱ1У״̬1϶ʱͻƽ.ʱϵͳԭķջһΪֱƽм.ӡҶ桱,ȫƽջ״̬ʾ.
(1) 0pron1verb2
(2) 0pron1verb3LOC8VP7noun13
(3) 0pron1VP7noun13
(4) 0S5
(5) 0pron1verb3VP7noun13
(6) 0pron1verb3LOC8verb3
Ϸ̿ԿȺ5ƽԼ壬5ζջ˸ƣ6е3ջ(146)ڳز.ICENTLRкԻȡӵ. 
3ͨLR㷨ȡӵ﷨ϵ
LRֻ˾д֮Ĳιϵû㹻õ﷨Ϣ.磬ʿԹԼһʴ飬ⲿֹLR.ڷӽṹʱǸҪ˽֮﷨ϵƫǲйϵ.ûд֮﷨ϢԾӵķǲܵ.ˣǽ޹ķ﷨ϵLRڻȡӷͬʱȡӴ֮﷨ϵ.
Ҫķ֮﷨ϵķĽṹͲ̫.ICENTķʽʷλ֮ĹϵNounywordadj nounNounywordʷλadjnoun֮Ĺϵͺ.ʹּ򵥵ķȻᵼ·ԷǳɷڷĹвϵزµջһЩӵľӾͻ൱ķпܲϱը.ˣϵͳṩһЩȥֹһЩĲ.
ICENT޹ķʽ䣬ķʽһԪʽ
G=(VT,VN,VD,VF,S,)
VTսϣһǿ޼VNǷսϣһǿ޼VTVN=VD﷨ϵϣһǿ޼VFǲϣһǿ޼acceptVFSǿʼţSVN һʽϣÿʽʽP,,áPVN(VTVN)+¡VDáVF.˦иԱ֮﷨ϵǲʽԼֻеĵǰ״̬úʱʽЧģʹøòʽйԼ.
ICENTʹ㷨ݲʽԶ4ű񣬵1ƽԼڵǰ״̬һսҪĶǽսƽǶԵǰջԪؽйԼһıһпԺжƽԼͨջ.2GOTOڵǰ״̬ԵǰսսҪһ״̬.Ҳһıе״̬ĳЩսʱжͬ״̬ѡ.ҲͨջƵķʽGOTO.3ǹ﷨ԱʹĳһйԼʱԼĸԪ֮﷨ϵ.һж﷨ϵ֮Ĳкιϵ.ͬһڶֲͬ﷨ϵϵͳоͱΪͬĹ򣬲ƽԼ͹﷨Աжͬ.NPnoun noun,and-noun,NULLNPnoun noun,att-obj,NULL,ȻǴʹԼһʴ飬ǵ﷨ԲͬICENTͬĹ.4űԼƽԼеÿһԼҪһǰŻЧ.ЩǰԼеĺΪգպ棩ϵͳЩĶֹԴļ.
4 
ڸһʹLR޹ķȡӴ﷨ϵʵ.ʹõķɵ2еķʾ.
(1) START  S,end,accept  (2) S  pron VP,agent-pred,subpron
(3) S  VP,sent,nosub (4) VP  verb S,pred-obj,takesent
(5) VP  LOC VP,loc-pred,NULL (6) VP  VP noun,pred-obj,verbobj
(7) VP  verb aux,pred-aux,auxfverb (8) LOC noun direc,obj-dir,NULL
﷨ϵеendʾõagent-predԼԪνʽṹ֮Ĺϵpred-objνʽṹ֮Ĺϵloc-predص״νʽṹĹϵobj-dirλĴ뷽λ֮Ĺϵ.ĺϵͳԶģʹøùǰ纯accept˽һӵǰֻеʱսSܱԼSTART.ϵͳʹͼ5еķԾӡҶ桱ĹԼ.
ʼϵͳջ״̬ʼΪ0ʾʼ.ϵͳĵǰǡpronĶƽҴGOTOв鵽״̬0սpronʱת״̬1.ƽջ״̬Ϊ
Next Word=(1) 0 - pron - 1
ĶʹͳLRͬ״̬1ƽGOTOвҪת״̬ʱ壬и״ֱ̬23.ϵͳջиƣ
Next Word=Ҷӡ(1) 0 - pron - 1 - verb - 2
(2) 0 - pron - 1 - verb - 3
1ջʡҶӡʱУ
Next Word=ϡ(1) 0 - pron - 1 - verb - 3 - noun - 4
ƽϡ״̬12
Next Word=(1) 0 - pron - 1 - verb - 3 - noun - 4 - direc - 12
״̬12ڵǰǶʱʹù8ԼϵͳȲѯ8ԼΪNULL.8﷨ϵobj-dirڹԼͬʱϵͳ¼˱Լĸ﷨ṹ֮﷨ϵ
Next Word=(1) 0 - pron -1 - verb - 3 - LOC - 8
(1) obj-dirҶӣϣ
ƽʱ壬ֱת״̬23
Next Word=š(1) 0 - pron -1 - verb - 3 - LOC - 8 - verb - 2
(1) obj-dirҶӣϣ
(2) 0 - pron -1 - verb - 3 - LOC - 8 - verb - 3
﷨ϵͬ(1)
ƽšʱ2÷
Next Word=桱(1) 0 - pron -1 - verb - 3 - LOC - 8 - verb - 2 - aux -10
(1) obj-dirҶӣϣ
״̬10ʱҪù7йԼ.ϵͳù7Լauxfverb鶯ʡʡš﷨ԣһνʽṹ򷵻.Լͬʱ¼֮﷨ϵԼѯGOTO壬ֱת״̬714
Next Word=桱(1) 0 - pron -1 - verb - 3 - LOC - 8 - VP - 7
(1) obj-dirҶӣϣ
(2) pred-auxţ
(2) 0 - pron -1 - verb - 3 - LOC - 8 - VP - 14
﷨ϵͬ(1)
״̬7ڵǰʱƽƽӽǰǽ硱.״̬14ڵǰʱԼԼʱԼΪNULLֱ֮ת״̬67
Next Word=$(1) 0 - pron -1 - verb - 3 - LOC - 8 - VP - 7 - noun - 13
(1) obj-dirҶӣϣ
(2) pred-auxţ
Next Word=桱(2) 0 - pron -1 - verb - 3 - VP - 6
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) loc-pred12
Next Word=桱(3) 0 - pron -1 - verb - 3 - VP - 7
﷨ϵͬ(2)
һ1ջĶù6йԼԼverbobjԼ״̬714.2ջĶù3ԼԼnosub鵱ǰνʽṹǷʺϹԼɾӽṹΪ٣.3ջĶƽ
Next Word=$(1) 0 - pron -1 - verb - 3 - LOC - 8 - VP - 7
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) pred-obj2棩
Next Word=$(2) 0 - pron -1 - verb - 3 - LOC - 8 - VP - 14
﷨ϵͬ(1)
Next Word=$(3) 0 - pron -1 - verb - 3 - VP - 7 - noun -13
﷨ϵͬ(1)
һ1ջջֱù56йԼ֮󶼲壬ֱת״̬67
Next Word=$(1) 0 - pron -1 - verb - 3 - VP - 6
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) pred-obj2棩
(4) loc-pred13
Next Word=$(2) 0 - pron -1 - verb - 3 - VP - 7
﷨ϵͬ(1)
Next Word=$(3) 0 - pron -1 - verb - 3 - VP - 6
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) loc-pred12
(4) pred-obj3棩
Next Word=$(4) 0 - pron -1 - verb - 3 - VP - 7
﷨ϵͬ(3)
һ24ջ13ջù3ԼȻת״̬11
Next Word=$(1) 0 - pron -1 - verb - 3 - S - 11
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) pred-obj2棩
(4) loc-pred13
(5) sent4
Next Word=$(2) 0 - pron -1 - verb - 3 - S - 11
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) loc-pred12
(4) pred-obj3棩
(5) sent4
һջĶù4ԼԼtakesentж϶ʽṹܷӾ䣬Լ󶼲壬ֱת״̬79
Next Word=$(1) 0 - pron -1 - VP - 7
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) pred-obj2棩
(4) loc-pred13
(5) sent4
(6) pred-obj5
Next Word=$(2) 0 - pron -1 - VP - 9
﷨ϵͬ(1)
Next Word=$(3) 0 - pron -1 - VP - 7
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) loc-pred12
(4) pred-obj3棩
(5) sent4
(6) pred-obj5
Next Word=$(4) 0 - pron -1 - VP - 9
﷨ϵͬ(3)
һ13ջ24ջù2Լ.Լsubpronжϴʡܷ򷵻.
Next Word=$(1) 0 - S - 5
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) pred-obj2棩
(4) loc-pred13
(5) sent4
(6) pred-obj5
(7) agent-pred6
Next Word=$(2) 0 - S - 5
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) loc-pred12
(4) pred-obj3棩
(5) sent4
(6) pred-obj5
(7) agent-pred6
ջù1йԼԼacceptջΪɹķ
Next Word=$(1) 0 - Start
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) pred-obj2棩
(4) loc-pred13
(5) sent4
(6) pred-obj5
(7) agent-pred6
(8) end7
Next Word=$(2) 0 - Start
(1) obj-dirҶӣϣ
(2) pred-auxţ
(3) loc-pred12
(4) pred-obj3棩
(5) sent4
(6) pred-obj5
(7) agent-pred6
(8) end7
ˣϵͳõȷķͬʱγʱд֮﷨ϵȷһӵĽṹȱٵϢ.
5ᡡ
˴ͳ޹ķʹ֮﷨ϵӶʹӵĽṹһĿȻɵÿһӵмԱʾṹٴ﷨ϵ.ϵͳķмԼĶʹϵͳһЩϵͳҪĿͬʱҲмԵ.Ŀǰ÷ӦICENTϵͳȡ˽ΪĽ.
*оõȻѧ͹863߿ƼĿ.
ͨѶϵˣܻƽɳ410073ɳѧԺϵ
߼飺ܻƽ1972ʿҪоΪ˹ܣ.
ͦ1970ʿʦҪоΪѧ.
»1936ڣʿʦйԺԺʿҪоΪ˹ܣ.
ߵλɳѧԺϵɳ410073
οף
1ܻƽ.һмԵĺӢϵͳ.ѧ1998,25(5):5155
(Zhou Hui-ping et al. An interlingua-based Chinese-English machine translation system. Computer Science, 1998,25(5):5155)
2Tesniere L. Element de Syntaxe Structurals. Paris: Klincksieck, 1959
3Gaifman H. Dependency systems and phrase-structure systems. Information and Control 8, 1965,6(2):303337
4Masaru Tomita. An efficient augmented-context-free parsing algorithm. Computational Linguistics, 1987,13(12):3146
ոڣ1998-07-18޸ڣ1998-10-09
