自然语言理解讲义第二章课件.ppt

1、自然语言理解讲义自然语言理解讲义第二章第二章 句法与句法分析句法与句法分析(1):形式语言与自动机形式语言与自动机第1页，共39页。内容提要内容提要o如何描述语言如何描述语言o形式文法定义形式文法定义o乔姆斯基的文法层级乔姆斯基的文法层级o索引文法索引文法o范畴文法范畴文法o自动机自动机o文法判定的复杂度文法判定的复杂度o用形式文法描述自然语言用形式文法描述自然语言o文法、语言与自动机的关系文法、语言与自动机的关系第2页，共39页。如何描述一种语言如何描述一种语言o枚举枚举 给出语言中的所有句子给出语言中的所有句子 对于含无限多个句子的语言不合适对于含无限多个句子的语言不合适o文法文法(语法语

2、法)给出生成语言中所有句子的方法给出生成语言中所有句子的方法 当且仅当能够用该方法产生的句子才属于该语言当且仅当能够用该方法产生的句子才属于该语言o自动机自动机 给出识别该语言中句子的机械方法给出识别该语言中句子的机械方法第3页，共39页。形式文法形式文法(1)o形式文法：四元组形式文法：四元组G=o终结符（终结符（Terminals）的有限集合）的有限集合VT 终结符是句子中实际出现的符号终结符是句子中实际出现的符号 相当于单词表（有时也称为字母表）相当于单词表（有时也称为字母表）o非终结符（非终结符（Non-terminals）的有限集合）的有限集合VN 非终结符在句子中不实际出现非终结符

3、在句子中不实际出现 但在推导中起变量作用但在推导中起变量作用 相当于语言中的语法范畴相当于语言中的语法范畴第4页，共39页。形式文法形式文法(2)o起始符起始符S S属于属于VN 相当于句法范畴中的句子相当于句法范畴中的句子o重写式规则重写式规则(Rewriting Rules)的有限集合的有限集合P或或 产生式规则产生式规则(Production Rules)的有限集合的有限集合P 基本形式：基本形式：含义：将含义：将 改写成改写成 和和 是终结符和非终结符组成的串是终结符和非终结符组成的串 非空，非空，可以为空可以为空()第5页，共39页。形式文法形式文法(3)o定义定义 V*=(VN V

4、T)*，V*。V*是是VN和和VT上的任意字符串，包括空串上的任意字符串，包括空串()。V+=V*-。o直接推导：直接推导：x y 如果如果xy是是P中的一条规则中的一条规则o推导：推导：*如果如果 可以经过多次直接推导得到可以经过多次直接推导得到 o语言：语言：L(G)=|VT*；S*GGG第6页，共39页。一个例子一个例子例例：设形式文法G的VT=the,John,ate,apple，VN=S,NP,VP,ART,N,V,NAME,P=1.SNP VP,2.VPV NP,3.NPNAME,4.NPART N,5.NAMEJohn,6.Vate,7.ARTthe,8.Ncat，其中NP代表名

5、词短语、VP代表动词短语等等。则句子“John ate the apple”的生成过程如下 SNP VP (重写S)NAME VP (重写NP)John VP (重写NAME)John V NP (重写VP)John ate NP (重写V)John ate ART N (重写NP)John ate the N (重写ART)John ate the apple (重写N)第7页，共39页。乔姆斯基的文法层级乔姆斯基的文法层级0型文法型文法1型文法型文法2型文法型文法3型文法型文法第8页，共39页。乔姆斯基乔姆斯基0型文法型文法o短语结构文法，无限制重写文法短语结构文法，无限制重写文法 PSG

6、：Phrasal Structure Grammaro对规则形式的约束对规则形式的约束对于规则形式没有任何限制对于规则形式没有任何限制第9页，共39页。乔姆斯基乔姆斯基1型文法型文法o上下文有关语法，上下文敏感语法上下文有关语法，上下文敏感语法CSG：Context Sensitive Grammaro对规则形式的约束：对规则形式的约束：，是任意串，且是任意串，且 的长度小于的长度小于 的长度的长度 A A是非终结符，是非终结符，、是任意串是任意串 以上两种形式等价以上两种形式等价 敏感：在一定的上下文环境下敏感：在一定的上下文环境下A可改写为可改写为 第10页，共39页。乔姆斯基乔姆斯基2型

7、文法型文法o上下文无关文法，上下文自由文法上下文无关文法，上下文自由文法 CFG：Context Free Grammaro对规则形式的约束：对规则形式的约束：A：A是非终结符，是非终结符，是任意串是任意串 在任何上下文环境下在任何上下文环境下A可改写为可改写为 第11页，共39页。上下文无关文法的一个例子上下文无关文法的一个例子SaASSaASbAAbaSaASaAaaSbAaaabAaaabbaa第12页，共39页。乔姆斯基乔姆斯基3型文法型文法o正规文法，正则文法正规文法，正则文法 RG：Regular Grammaro对规则形式的约束对规则形式的约束 ABx或者或者Ax，A,B是非终结

8、符，是非终结符，x是终结是终结符符o一部正则文法可以表示为一个正则表达式一部正则文法可以表示为一个正则表达式 例子：例子：ab|c*+d|ef|g|h+第13页，共39页。乔姆斯基层级以外的文法类别乔姆斯基层级以外的文法类别o介于介于CFG和和CSG之间的语法类别之间的语法类别 索引文法（索引文法（IG:Index Grammar）可以生成可以生成anbncn形式的语言形式的语言 树粘接文法树粘接文法 TAG：Tree Adjoining Grammaro与乔姆斯基语法层级相交叉的语法类别与乔姆斯基语法层级相交叉的语法类别第14页，共39页。索引文法索引文法(1)o索引文法是一个五元组（索引文

9、法是一个五元组（VN,VT,VI,P,S)oVN,VT,S与前面的定义相同与前面的定义相同oVI是索引的有限集合是索引的有限集合oP是重写规则的有限集合，规则形式为：是重写规则的有限集合，规则形式为：1)A2)AB(f)3)A(f)A,B VN,f VI,(VNVT)*第15页，共39页。索引文法索引文法(2)o直接推导直接推导()的定义的定义如果如果AX1X2Xk是规则集中具有是规则集中具有1)形式的规则，那么：形式的规则，那么：A()X1(1)X2(2)Xk(k)其中，其中，XiVN时，时，i；XiVT时，时，i如果如果AB(f)是规则集中具有是规则集中具有2)形式的规则，那么形式的规则，

10、那么A()B(f)如果如果A(f)X1X2Xk是规则集中具有是规则集中具有3)形式的规则，那么：形式的规则，那么：A(f)X1(1)X2(2)Xk(k)其中，其中，XiVN时，时，i；XiVT时，时，io推导推导(*)的定义和语言的定义与前面类似的定义和语言的定义与前面类似第16页，共39页。索引文法索引文法(3)例子例子（规则集）S S()S ABCA()aAB()bBC()cCA aB bC c 推导推导SS()S()S()A()B()C()aA()B()C()aaA()B()C()aaaaB()C()aaaabbbbcccc可以生成可以生成anbncn形式的语言，不是形式的语言，不是CF

11、G第17页，共39页。其他文法其他文法o链文法（链文法（Link Grammar）o依存文法（依存文法（Dependency Grammar）o范畴文法（范畴文法（CategorialGrammar）第18页，共39页。范畴文法范畴文法(1)oMontague,1970。邹崇理。邹崇理,1995。蒋严。蒋严&潘海华潘海华,1998。白硕。白硕,1998o范畴文法的核心思想是把语言中的各种成分范畴文法的核心思想是把语言中的各种成分对应为某种对应为某种“类型类型”/“范畴范畴”，把语言结构，把语言结构的构造过程对应为的构造过程对应为“类型类型”/“范畴范畴”之间的之间的演算过程。演算过程。ohtt

12、p:/www.cs.man.ac.uk/ai/CG/第19页，共39页。范畴文法范畴文法(2)：基本概念：基本概念o范畴文法里面有两种基本范畴：范畴文法里面有两种基本范畴：S和和N。粗略地理解，。粗略地理解，S相相当于当于句子句子，N相当于相当于名词名词。o一个语言成分的范畴（类型）由基本范畴一个语言成分的范畴（类型）由基本范畴S,N加上范畴加上范畴表达式构造符表达式构造符“”，“/”，括号，括号“（”，和，和“）”构构成。成。o范畴构造符范畴构造符“”表示表示“左缺左缺”；“/”表示表示“右缺右缺”，直观，直观上，可以把它们设想为除号，相应地，范畴的构造就可以看上，可以把它们设想为除号，相应

13、地，范畴的构造就可以看成是带有方向的除法运算。括号表示结合顺序。成是带有方向的除法运算。括号表示结合顺序。o当两个语言成分之间发生结合关系时，它们相应的范畴则发当两个语言成分之间发生结合关系时，它们相应的范畴则发生对应的生对应的“乘法乘法”运算。运算中最关键的操作就是运算。运算中最关键的操作就是“约分约分”。第20页，共39页。范畴文法范畴文法(3)：英语词类的范畴表示：英语词类的范畴表示词类 范畴标注 说明句子 S 基本范畴名词 N 基本范畴不及物动词 NS 左方缺少主语及物动词 (NS)/N或者N(S/N)左方少主语，右方少宾语形容词(做定语)N/N 右方少中心语形容词(做表语)(S/N)

14、S 左方少“缺宾语句子”副词(做前置状语)(NS)/(NS)右方少中心语副词(做后置状语)(NS)(NS)左方少中心语介词(做后置状语)(NS)(NS)/N 右方少介词宾语介词(做后置定语)(NN)/N 右方少介词宾语冠词 N/N 右方少名词代词(主格)S/(NS)右方少不及物动词代词(宾格)(S/N)S 左方少“缺宾语句子”第21页，共39页。范畴文法范畴文法(4)：范畴演算：范畴演算o句子的构造过程就是语言成分所对应的范畴的演算过程。o一个单词串的演算的结果或者是S，或者不是S，前者即为合法的句子，后者则是不合法的句子。o演算的具体操作分为两种：一种叫做“应用”(Application)，

15、简记为A；一种叫做“合成”(Composition)，简记为C。o应用就是完整的约分，即分母被约掉，只剩下分子作为结果；比如：S/N N S N NS S 合成就是约分后范畴表达式仍然带着分母。比如：S/(NS)(NS)/N S/N第22页，共39页。范畴文法范畴文法(5)：范畴词典：范畴词典he S/(NS)is (NS)/Na N/Nclever N/Nboy N第23页，共39页。范畴文法范畴文法(6)：范畴词典：范畴词典He is a clever boy.S/(NS)(NS)/N N/N N/N N-CS/N -C S/N -C S/N -A S第24页，共39页。范畴演算的语言学假

16、设范畴演算的语言学假设o假设了所有结构都是由词汇负载的，这样才能从词汇的范畴标记推导出各个上级结构成分的范畴标记；o假设了所有结合必定是邻接成分的结合，而不可能有跨越邻接成分的超距结合，这样才能依托邻接关系实现范畴标记的约分计算；o假设了严格的语序关系，这样才能从确定方向上找到约分的对象；o假设了每个结构必须填项完备，这样才能在最后获得一个分母约干净了的S标记。第25页，共39页。范畴文法存在的问题范畴文法存在的问题1 范畴标记和词类不是一一对应的，要在具体的语流中确定具体词的范畴标记有相当的难度，甚至无异于先要理解。2 不负载在词上面的结构（如汉语中的联合结构、连谓结构等）就很难纳入范畴语法

17、的框架中去表达。3 超距相关的成分（如“王冕死了父亲”中的“王冕”和“父亲”）在范畴文法的框架中无法建立约分关系。4 象汉语这样语序灵活、填项经常不完备（省略）的语言，用范畴文法去描述会遇到许多麻烦问题。第26页，共39页。图灵机图灵机(1)：直观描述：直观描述B B B B a1 a2 ai an B B B B B B有限状态控有限状态控制器制器双向可读写纸带在每一个时刻，可以定义图灵机的格局为在每一个时刻，可以定义图灵机的格局为(q,a,i)其中其中q为当前状态，为当前状态，a为当前纸带上的字符串，为当前纸带上的字符串，i为当前读为当前读写头的位置。写头的位置。B为空白字符。为空白字符。

18、第27页，共39页。图灵机图灵机(2)：形式定义：形式定义o图灵机是一个六元组 M=(Q,q0,F)Q为自动机状态的有限集合 一个有限的字符集合，其中空白字符B ,为输入字符集合，B 是一个状态转移函数：QQR,L,S R,L,S分布表示读写头左移、右移或者不动 q0Q为初始状态 FQ为终止状态集第28页，共39页。图灵机图灵机(3)：能接受的字符串：能接受的字符串o开始时，纸带中间有开始时，纸带中间有n个字符构成输入串，个字符构成输入串，余下的无穷多个字符为空白字符，空白字符余下的无穷多个字符为空白字符，空白字符不是输入符号不是输入符号o开始时，读写头处于输入串的最左端，图灵开始时，读写头处

19、于输入串的最左端，图灵机的状态为机的状态为q0o如果图灵机如果图灵机M对于字符串对于字符串在执行过程中进在执行过程中进入某个接受状态，称为入某个接受状态，称为M接受字符串接受字符串；如；如果执行过程中遇到一个格局在状态转移函数果执行过程中遇到一个格局在状态转移函数中没有定义，那么称中没有定义，那么称M不接受字符串不接受字符串第29页，共39页。线性有界自动机线性有界自动机o线性有界自动机的构造与图灵机完全一致线性有界自动机的构造与图灵机完全一致o对图灵机的限制：纸带存在一个左右边界对图灵机的限制：纸带存在一个左右边界（用两个特殊符号来标识），图灵机的执行（用两个特殊符号来标识），图灵机的执行过

20、程中读写头位置不能超出边界过程中读写头位置不能超出边界o线性有界自动机所识别的语言等价于线性有界自动机所识别的语言等价于1型语型语法所生成的语言法所生成的语言第30页，共39页。下推自动机下推自动机o下推自动机是一个七元组M=(Q,q0,Z0,F)Q为自动机状态的有限集合 为输入纸带上字符的有限集合 为堆栈字符的有限集合 q0Q为初始状态 Z0是堆栈中的一个特殊符号，表示栈底 FQ为终止状态集是一个状态转移函数：Q()Q*第31页，共39页。有限状态自动机有限状态自动机o有限状态自动机是一个七元组M=(Q,I,U,q0,F)Q为自动机状态的有限集合I为输入字符的有限集合O为输出字符的有限集合是

21、一个状态转移函数：QIQ是一个输出函数：QIUq0Q为初始状态FQ为终止状态集第32页，共39页。两种有限状态自动机两种有限状态自动机o有限状态接收机有限状态接收机（Acceptor）是一个五元组M=(Q,I,q0,F)。是没有输出的有限状态自动机。o有限状态转录机有限状态转录机（Transducer）是一个六元组M=(Q,I,U,q0)。有输出，但没有终止状态的有限状态自动机。第33页，共39页。有限状态自动机的应用有限状态自动机的应用o有限状态自动机具有简单、直观、高效的特点，在很多领域中得到了广泛的应用词典构造（Xerox Europe）机器翻译（Alshiwiswork）o有限状态机自

22、动机通过递归（输入另一个自动机的识别结果）可以实现上下文无关语法的描述能力o有限状态转录机可以进行翻译第34页，共39页。文法的判定复杂度文法的判定复杂度oPSG：半可判定对于一个属于0型语言的句子L，总可以在确定步内判断出“是”；但对于一个不属于0型语言的句子L，不存在一个算法，可以在确定步内判断出“否”。oCSG：可判定，复杂度：NP完全oCFG：可判定，复杂度：多项式oRG：可判定，复杂度：线性第35页，共39页。文法、自动机和语言文法、自动机和语言文法自动机语言复杂度0型 无约束短语结构文法图灵机递归可枚举语言 半可判定 1型 上下文有关文法线性有界自动机 上下文有关语言 NP完全 2

23、型 上下文无关文法下推自动机 上下文无关语言 多项式 3型 正则文法有限自动机 正则语言 线形第36页，共39页。用什么文法描述自然语言用什么文法描述自然语言o正则语法描述能力太弱、上下文有关语法计算复杂度太高，上下文无关语法使用最为普遍o从描述能力上说，上下文无关语法不足以描述自然语言自然语言中上下文相关的情况非常常见o从计算复杂度来说，上下文无关语法的复杂度是多项式的，其复杂度可以忍受o为弥补上下文无关语法描述能力的不足，需要加上一些其他手段扩充其描述能力第37页，共39页。上下文无关文法与句子结构上下文无关文法与句子结构o上下文无关文法的二分特性与人类心理思维规律比较接近。o上下文无关文法能反映自然语言句子的层次特性，从而得到句子的句法结构。SNPVPNAMEVNPJohnateARTNtheapple第38页，共39页。上下文无关文法与句子结构上下文无关文法与句子结构o上下文无关文法能表示句法歧义。例例4：“They are flying planes.”可有两种句法结构 TheySNPVPVNPare flyingplanesTheySNPVPVNPareplanesADJflyingN第39页，共39页。