《自然语言理解讲义.ppt》由会员分享，可在线阅读，更多相关《自然语言理解讲义.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、自然语言理解讲义自然语言理解讲义第二章第二章 句法与句法分析句法与句法分析(1): 形式语言与自动机形式语言与自动机内容提要内容提要o 如何描述语言如何描述语言o 形式文法定义形式文法定义o 乔姆斯基的文法层级乔姆斯基的文法层级o 索引文法索引文法o 范畴文法范畴文法o 自动机自动机o 文法判定的复杂度文法判定的复杂度o 用形式文法描述自然语言用形式文法描述自然语言o 文法、语言与自动机的关系文法、语言与自动机的关系如何描述一种语言如何描述一种语言o 枚举枚举 给出语言中的所有句子给出语言中的所有句子 对于含无限多个句子的语言不合适对于含无限多个句子的语言不合适o 文法文法(语法语法) 给出生
2、成语言中所有句子的方法给出生成语言中所有句子的方法 当且仅当能够用该方法产生的句子才属于该语言当且仅当能够用该方法产生的句子才属于该语言o 自动机自动机 给出识别该语言中句子的机械方法给出识别该语言中句子的机械方法形式文法形式文法(1)o 形式文法：四元组形式文法：四元组G = o 终结符（终结符（Terminals）的有限集合）的有限集合VT 终结符是句子中实际出现的符号终结符是句子中实际出现的符号 相当于单词表（有时也称为字母表）相当于单词表（有时也称为字母表）o 非终结符（非终结符（Non-terminals）的有限集合）的有限集合VN 非终结符在句子中不实际出现非终结符在句子中不实际出
3、现 但在推导中起变量作用但在推导中起变量作用 相当于语言中的语法范畴相当于语言中的语法范畴形式文法形式文法(2)o 起始符起始符S S属于属于VN 相当于句法范畴中的句子相当于句法范畴中的句子o 重写式规则重写式规则(Rewriting Rules)的有限集合的有限集合P或或 产生式规则产生式规则(Production Rules)的有限集合的有限集合P 基本形式：基本形式： 含义：将含义：将 改写成改写成 和和 是终结符和非终结符组成的串是终结符和非终结符组成的串 非空，非空， 可以为空可以为空( ) 形式文法形式文法(3)o 定义定义 V*=(VN VT)*，V*。V*是是VN和和VT上的
4、任意字符串，包括空串上的任意字符串，包括空串( )。 V+ =V*- 。 o 直接推导：直接推导： x y 如果如果xy是是P中的一条规则中的一条规则o 推导：推导： * 如果如果 可以经过多次直接推导得到可以经过多次直接推导得到 o 语言：语言：L(G)= | VT*；S * GGG一个例子一个例子例例：设形式文法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.
5、Ncat，其中NP代表名词短语、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) 乔姆斯基的文法层级乔姆斯基的文法层级0型文法型文法1型文法型文法2型文法型文法3型文法型文法乔姆斯基乔姆斯基0型文法型文法o 短语结构文法，无限制重写文法短语结构文法，无限制重写文法
6、PSG：Phrasal Structure Grammaro 对规则形式的约束对规则形式的约束对于规则形式没有任何限制对于规则形式没有任何限制乔姆斯基乔姆斯基1型文法型文法o 上下文有关语法，上下文敏感语法上下文有关语法，上下文敏感语法CSG：Context Sensitive Grammaro 对规则形式的约束：对规则形式的约束： ， 是任意串，且是任意串，且 的长度小于的长度小于 的长度的长度 A A是非终结符，是非终结符， 、 、 是任意串是任意串 以上两种形式等价以上两种形式等价 敏感：在一定的上下文环境下敏感：在一定的上下文环境下A可改写为可改写为 乔姆斯基乔姆斯基2型文法型文法o
7、上下文无关文法，上下文自由文法上下文无关文法，上下文自由文法 CFG：Context Free Grammaro 对规则形式的约束：对规则形式的约束： A ：A是非终结符，是非终结符， 是任意串是任意串 在任何上下文环境下在任何上下文环境下A可改写为可改写为 上下文无关文法的一个例子上下文无关文法的一个例子SaASSaASbAAba文法中一个句子的推导过程如下：文法中一个句子的推导过程如下：SaASaAaaSbAaaabAaaabbaa上下文无关文法的一个例子上下文无关文法的一个例子SaASSaASbAAbaSaASaAaaSbAaaabAaaabbaa句子结句子结构可表构可表示为树示为树的形
8、式的形式乔姆斯基乔姆斯基3型文法型文法o 正规文法，正则文法正规文法，正则文法 RG：Regular Grammaro 对规则形式的约束对规则形式的约束 ABx或者或者Ax，A,B是非终结符，是非终结符，x是终结是终结符符o 一部正则文法可以表示为一个正则表达式一部正则文法可以表示为一个正则表达式 例子：例子：ab|c*+d|ef|g|h+乔姆斯基层级以外的文法类别乔姆斯基层级以外的文法类别o 介于介于CFG和和CSG之间的语法类别之间的语法类别 索引文法（索引文法（IG: Index Grammar） 可以生成可以生成anbncn形式的语言形式的语言 树粘接文法树粘接文法 TAG：Tree
9、Adjoining Grammaro 与乔姆斯基语法层级相交叉的语法类别与乔姆斯基语法层级相交叉的语法类别索引文法索引文法(1)o 索引文法是一个五元组（索引文法是一个五元组（VN, VT,VI,P,S)o VN,VT,S与前面的定义相同与前面的定义相同o VI是索引的有限集合是索引的有限集合o P是重写规则的有限集合，规则形式为：是重写规则的有限集合，规则形式为：1) A2) AB(f)3) A(f)A , B VN, f VI, (VNVT)*索引文法索引文法(2)o 直接推导直接推导()的定义的定义如果如果AX1X2Xk是规则集中具有是规则集中具有1)形式的规则，那么：形式的规则，那么：
10、A()X1(1) X2(2)Xk(k)其中，其中，XiVN时，时，i；XiVT时，时，i如果如果AB(f)是规则集中具有是规则集中具有2)形式的规则，那么形式的规则，那么A()B(f) 如果如果A(f)X1X2Xk是规则集中具有是规则集中具有3)形式的规则，那形式的规则，那么：么：A(f)X1(1) X2(2)Xk(k)其中，其中，XiVN时，时，i；XiVT时，时，io 推导推导(*)的定义和语言的定义与前面类似的定义和语言的定义与前面类似索引文法索引文法(3) 例子例子（规则集）S S()S ABCA() aAB() bBC() cCA aB bC c 推导推导SS() S() S() A
11、()B()C() aA()B()C() aaA()B()C() aaaaB()C() aaaabbbbcccc可以生成可以生成anbncn形式的语言，不是形式的语言，不是CFG其他文法其他文法o 链文法（链文法（Link Grammar）o 依存文法（依存文法（Dependency Grammar）o 范畴文法（范畴文法（CategorialGrammar）范畴文法范畴文法(1)o Montague,1970。邹崇理。邹崇理,1995。蒋严。蒋严&潘海华潘海华,1998。白硕。白硕,1998o 范畴文法的核心思想是把语言中的各种成分范畴文法的核心思想是把语言中的各种成分对应为某种对应为某种“类
12、型类型”/“范畴范畴”，把语言结构，把语言结构的构造过程对应为的构造过程对应为“类型类型”/“范畴范畴”之间的之间的演算过程。演算过程。o http:/www.cs.man.ac.uk/ai/CG/范畴文法范畴文法(2)：基本概念：基本概念o 范畴文法里面有两种基本范畴：范畴文法里面有两种基本范畴：S和和N。粗略地理。粗略地理解，解，S相当于相当于句子句子，N相当于相当于名词名词。o 一个语言成分的范畴（类型）由基本范畴一个语言成分的范畴（类型）由基本范畴S,N加上加上范畴表达式构造符范畴表达式构造符“”，“/”，括号，括号“（”，和，和“）”构成。构成。o 范畴构造符范畴构造符“”表示表示“
13、左缺左缺”；“/”表示表示“右右缺缺”，直观上，可以把它们设想为除号，相应地，直观上，可以把它们设想为除号，相应地，范畴的构造就可以看成是带有方向的除法运算。括范畴的构造就可以看成是带有方向的除法运算。括号表示结合顺序。号表示结合顺序。o 当两个语言成分之间发生结合关系时，它们相应的当两个语言成分之间发生结合关系时，它们相应的范畴则发生对应的范畴则发生对应的“乘法乘法”运算。运算中最关键的运算。运算中最关键的操作就是操作就是“约分约分”。范畴文法范畴文法(3)：词的范畴类型：词的范畴类型o 如果有某个词B，其后面的词C的句法类型是，而词序列BC的功能与相同，则B的句法类型记为/；o 如果有某个
14、词B，其前面的词A的句法类型是，而词序列AB的功能与相同，则B的句法类型记为；o 如果有某个词B，其前面的词A的句法类型是，其后面的词C的句法类型是，而词序列ABC的功能与相同，则B的句法类型记为/；o 注注：上面讲的词是一个宽泛的概念，可以是短语、句子等范畴文法范畴文法(4)：词的范畴类型：词的范畴类型o 例子：例子：在英语中，John的句法类型为N。npoor John中的poor，它后面出现名词John，而整个串poor John的功能与名词相同，故poor的句法类型为N/N。nJohn likes Jane中的likes，它前面为名词John，后面为名词Jane，而所构成的John l
15、ikes Jane，功能与句子相同，故其句法类型为NS/N。nJohn slept soundly中的soundly，它前面的slept 为NS，而它所构成的slept soundly，功能与NS相同，故其句法类型为(NS)NS。nJohn never works中，由于John的句法类型为N，故never works的句法类型为NS，而works的句法类型也是NS，故never 的句法类型为NS/(NS)范畴文法范畴文法(5)：词的范畴类型：词的范畴类型o 例子例子(续续)nJohn works for Jane中， for 前面的John works是句子类型， for 后面的Jane的类
16、型为N，故for的句法类型为SS/N。nJohn works here中，here能把一个句子John works 转换成一个新的句子John works here，故here的句法类型为SS。o 练习：给出and、that的范畴类型表达式范畴文法范畴文法(6)：英语词类的范畴表示：英语词类的范畴表示词类 范畴标注 说明句子 S 基本范畴名词 N 基本范畴不及物动词 NS 左方缺少主语及物动词 (NS)/N或者N(S/N) 左方少主语，右方少宾语形容词(做定语) N/N 右方少中心语形容词(做表语) (S/N)S 左方少“缺宾语句子”副词(做前置状语) (NS)/(NS) 右方少中心语副词(做
17、后置状语) (NS)(NS) 左方少中心语介词(做后置状语) (NS)(NS)/N 右方少介词宾语介词(做后置定语) (NN)/N 右方少介词宾语冠词 N/N 右方少名词代词(主格) S/(NS) 右方少不及物动词代词(宾格) (S/N)S 左方少“缺宾语句子”范畴文法范畴文法(7)：范畴演算：范畴演算o 句子的构造过程就是语言成分所对应的范畴的演算过程。o 一个单词串的演算的结果或者是S，或者不是S，前者即为合法的句子，后者则是不合法的句子。o 演算的具体操作分为两种：一种叫做“应用”(Application)，简记为A；一种叫做“合成”(Composition)，简记为C。o 应用就是完整
18、的约分，即分母被约掉，只剩下分子作为结果；比如： S/N N S N NS S 合成就是约分后范畴表达式仍然带着分母。比如： S/(NS) (NS)/N S/N范畴文法范畴文法(8)：范畴词典：范畴词典he S/(NS)is (NS)/Na N/Nclever N/Nboy N范畴文法范畴文法(9)：范畴词典：范畴词典He is a clever boy.S/(NS) (NS)/N N/N N/N N-CS/N -C S/N -C S/N -A S范畴演算的语言学假设范畴演算的语言学假设o 假设了所有结构都是由词汇负载的，这样才能从词汇的范畴标记推导出各个上级结构成分的范畴标记；o 假设了所有
19、结合必定是邻接成分的结合，而不可能有跨越邻接成分的超距结合，这样才能依托邻接关系实现范畴标记的约分计算；o 假设了严格的语序关系，这样才能从确定方向上找到约分的对象；o 假设了每个结构必须填项完备，这样才能在最后获得一个分母约干净了的S标记。范畴文法存在的问题范畴文法存在的问题1 范畴标记和词类不是一一对应的，要在具体的语流中确定具体词的范畴标记有相当的难度，甚至无异于先要理解。2 不负载在词上面的结构（如汉语中的联合结构、连谓结构等）就很难纳入范畴语法的框架中去表达。3 超距相关的成分（如“王冕死了父亲”中的“王冕”和“父亲”）在范畴文法的框架中无法建立约分关系。4 象汉语这样语序灵活、填项
20、经常不完备（省略）的语言，用范畴文法去描述会遇到许多麻烦问题。图灵机图灵机(1)：直观描述：直观描述B B B B a1 a2 ai an B B B B B B有限状态有限状态控制器控制器双向可读写纸带在每一个时刻，可以定义图灵机的格局为在每一个时刻，可以定义图灵机的格局为(q,a,i)其中其中q为当前状态，为当前状态，a为当前纸带上的字符串，为当前纸带上的字符串，i为当前读写头的位置。为当前读写头的位置。B为空白字符。为空白字符。图灵机图灵机(2)：形式定义：形式定义o 图灵机是一个六元组 M= ( Q, , , , q0, F) Q为自动机状态的有限集合 一个有限的字符集合，其中空白字符
21、B , 为输入字符集合，B 是一个状态转移函数：QQR,L,S R,L,S分布表示读写头左移、右移或者不动 q0Q为初始状态 FQ为终止状态集图灵机图灵机(3)：能接受的字符串：能接受的字符串o 开始时，纸带中间有开始时，纸带中间有n个字符构成输入串，个字符构成输入串，余下的无穷多个字符为空白字符，空白字符余下的无穷多个字符为空白字符，空白字符不是输入符号不是输入符号o 开始时，读写头处于输入串的最左端，图灵开始时，读写头处于输入串的最左端，图灵机的状态为机的状态为q0o 如果图灵机如果图灵机M对于字符串对于字符串在执行过程中进在执行过程中进入某个接受状态，称为入某个接受状态，称为M接受字符串
22、接受字符串；如；如果执行过程中遇到一个格局在状态转移函数果执行过程中遇到一个格局在状态转移函数中没有定义，那么称中没有定义，那么称M不接受字符串不接受字符串线性有界自动机线性有界自动机o 线性有界自动机的构造与图灵机完全一致线性有界自动机的构造与图灵机完全一致o 对图灵机的限制：纸带存在一个左右边界对图灵机的限制：纸带存在一个左右边界（用两个特殊符号来标识），图灵机的执行（用两个特殊符号来标识），图灵机的执行过程中读写头位置不能超出边界过程中读写头位置不能超出边界o 线性有界自动机所识别的语言等价于线性有界自动机所识别的语言等价于1型语型语法所生成的语言法所生成的语言下推自动机下推自动机o 下
23、推自动机是一个七元组M=( Q, , , , q0, Z0, F ) Q为自动机状态的有限集合 为输入纸带上字符的有限集合 为堆栈字符的有限集合 q0Q为初始状态 Z0是堆栈中的一个特殊符号，表示栈底 FQ为终止状态集是一个状态转移函数：Q()Q*有限状态自动机有限状态自动机o 有限状态自动机是一个七元组M=( Q, I, U, , , q0, F ) Q为自动机状态的有限集合I为输入字符的有限集合O为输出字符的有限集合是一个状态转移函数：QIQ是一个输出函数：QIUq0Q为初始状态FQ为终止状态集两种有限状态自动机两种有限状态自动机o 有限状态接收机有限状态接收机（Acceptor）是一个五
24、元组M=( Q, I, , q0, F ) 。是没有输出的有限状态自动机。o 有限状态转录机有限状态转录机（Transducer）是一个六元组M=( Q, I, U, , , q0) 。有输出，但没有终止状态的有限状态自动机。有限状态自动机的应用有限状态自动机的应用o 有限状态自动机具有简单、直观、高效的特点，在很多领域中得到了广泛的应用词典构造（Xerox Europe）机器翻译（Alshiwiswork）o 有限状态机自动机通过递归（输入另一个自动机的识别结果）可以实现上下文无关语法的描述能力o 有限状态转录机可以进行翻译文法的判定复杂度文法的判定复杂度o PSG：半可判定对于一个属于0型
25、语言的句子L，总可以在确定步内判断出“是”；但对于一个不属于0型语言的句子L，不存在一个算法，可以在确定步内判断出“否”。o CSG：可判定，复杂度：NP完全o CFG：可判定，复杂度：多项式o RG：可判定，复杂度：线性文法、自动机和语言文法、自动机和语言文法自动机语言复杂度0型 无约束短语结构文法图灵机递归可枚举语言 半可判定 1型 上下文有关文法线性有界自动机 上下文有关语言 NP完全 2型 上下文无关文法下推自动机 上下文无关语言 多项式 3型 正则文法有限自动机 正则语言 线形用什么文法描述自然语言用什么文法描述自然语言o 正则语法描述能力太弱、上下文有关语法计算复杂度太高，上下文无
26、关语法使用最为普遍o 从描述能力上说，上下文无关语法不足以描述自然语言自然语言中上下文相关的情况非常常见o 从计算复杂度来说，上下文无关语法的复杂度是多项式的，其复杂度可以忍受o 为弥补上下文无关语法描述能力的不足，需要加上一些其他手段扩充其描述能力上下文无关文法与句子结构上下文无关文法与句子结构o 上下文无关文法的二分特性与人类心理思维规律比较接近。o 上下文无关文法能反映自然语言句子的层次特性，从而得到句子的句法结构。 SNPVPNAMEVNPJohnateARTNtheapple上下文无关文法与句子结构上下文无关文法与句子结构o 上下文无关文法能表示句法歧义。例例4：“They are flying planes.”可有两种句法结构 TheySNPVPVNPare flyingplanesTheySNPVPVNPareplanesADJflyingN