资源描述:
《第8讲 句法分析_ii(2013)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第8讲句法分析_IIsyntacticparsing广东外语外贸大学信息学院李霞2013统计句法分析基于规则句法分析的优点¢可以利用手工编写的语法规则分析出输入句子所有可能的句法结构¢对特定的领域,手工编写规则具有针对性,可较好测处理歧义问题基于规则句法分析的缺点¢对于较长的句子,利用大覆盖度的语法规则分析出所有可能的句子结构非常困难¢无法进行有效的消歧¢手工编写的规则带有主观性,无法覆盖大领域的所有复杂语言¢手工编写规则工作量大统计句法分析¢CFG(contextfreegrammar)¾上下
2、文无关文法¢PCFG(probabilitycontextfreegrammar)PCFG(probabilitycontextfreegrammar)¾概率上下文无关文法短语结构语法(phrasestructuregrammar)画出该句子的短语结构树图!CFG(上下文无关文法)ß形式语法G=ßV:非终端语符集(辅助词汇的有限集合)NßV:终端语符集(基本词汇的有限集合)TßP:一组由有限个重写规则组成的规则集ßS:表示起始符ß句子:由语法G0从起始符S可派生出来的终端语
3、符列构成由G0生成的句子ß语言:所有由语法G0从起始符S可派生出来的终端语符列构成G0生成的语言。CFG(上下文无关文法)ß形式语法G=ßS:表示起始符,S∈V,V:非终端语符集,V:终NNT端语符集,P表示重写规则集,S:表示起始符,V=V∪V.NTß如果P每个产生式可以描述为A→xß其中A是非终结符,x是空或多个终结符和非终结符的序列CFG(上下文无关文法)例1.V={S,NP,VP,ART,N,V}N2V2.V={the,a,boy,sees,catdit}t,dir
4、ty}T3.P包含以下几条重写规则:a.S→NPVPb.NP→ARTNARTNc.NP→ARTADJNd.VP→VNPVNPe.ART→the
5、af.N→boy
6、catg.V→sawh.ADJ→dirtyPhrasestructuredgrammar=CFGPCFG(概率上下文无关文法)PCFG例¢S->NPVP1.0¢NP->NPPP04>NPPP0.4¢PP->PNP1.0¢VP->VPPP>VPPP003.3¢VP->VNP0.7¢NP->astronomers01>astronomers
7、0.1¢NP->ears0.18¢NP->saw0004.04¢P->with1.0¢NP->stars0.18¢NP->telescopes0.1¢V->saw1.0¢ART->a1.0PCFG例添加概率的句法树添加概率的句法树句法树的概率¢PCFG中定义一棵句法树的概率为所有用到的规则概率的乘积¾P(t1)=¾P(t2)=¢一般来说,概率值大的更可能是正确的句法树分析句子:Isawstarswithears更可能是哪个句法树?句子的概率利用句子S的所有可能的句法分析树来统计句子的概率:P(S
8、)=∑P(S,T)T句子的概率概率上下文无法语法的本质¢无概率的CFG分析符合语法的句子,答案只有两个:是或不是;¢PCFG不是分析句子是否合法,而是一个概率值,即可能性。CNF(Chomskynormalform)¢CNF是具有Chomsky范式的CFG¾如果一个上下文无关文法的每个产生式的形式为:A->BC或A->a,•即规则的右部或者是两个非终结符或者是一个终结符¢任何CFG都可以转变成一个弱等价的Chomsky范式语法CNF(Chomskynormalform)¢Allrulesareo
9、ftheformX→YZorX→w¾X,Y,Z∈Nandw∈T¢AtransformationtothisformdoesnAtransformationtothisformdoesn’tchangetchangetheweakgenerativecapacityofaCFG¾ThtiitThatis,itrecognizesthesamelanguage•ButmaybewithdifferenttreesCNF(Chomskynormalform)¢Transformationmethods
10、:¢S1EiStep1:Emptiesareremoveddrecursilively¢Step2:unariesareremovedrecursively¢Step3:n-aryrulesaredividedbyintroducingnewnonterminals(()n>2)AphrasestructuregrammarS→NPVPN→peopleVP→VNPN→fishVP→VNPPPVNPPPN→tanksNP→NPNPN→rodsNP→NPPPV→peopleNP→NV→fishNP→