《计算引论7 上下文无关语言课件》由会员分享，可在线阅读，更多相关《计算引论7 上下文无关语言课件（39页珍藏版）》请在金锄头文库上搜索。
1、计算引论,第三章 文法与语言,第三章 文法与语言,3.1 语言的基本概念 3.2 有限自动机 3.3 上下文无关语言 3.4 上下文无关语言识别算法,3.3 上下文无关语言,引子 The cat is in the hat. Hat the the in is cat. 语言识别器: 一个接受有效字符串(至少语法正确)的装置, 如有限自动机 语言产生器: 根据一个起始符号构造字符串的装置,3.3 上下文无关语言,如何设计出关于自然语言的大量子集, 在过去几十年中一直是个前沿问题. 语言产生器的出现推动了对人类语言的探讨. 尤其是形式的, 人工的语言的产生器理论, 如正规语言及上下文无关语言.
2、该理论是对自动机的补充, 也是对计算机语言进行说明和分析的结果.,3.3 上下文无关语言,正规表达式可视为语言的产生器. 例如, 正规表达式a(a*b*)b 先输出a; 输出一串a或输出一串b; 最后输出b. 用这种方法就可以将该表达式表示的字符串全部产生出来,3.3 上下文无关语言,更复杂的语言产生器, 上下文无关文法, 是对语言的字符串的结构进行深入理解的理论.,a (a*b*) b,头部,中间部分,尾部,3.3 上下文无关语言,若令S为语言的字符串, 符号M表示中间部分, 则上面的描述可以表示为 SaMb 其中读做“可以为”, 并且称该表达式为规则. Ma组成的串和Mb组成的串 MA和M
3、B,3.3 上下文无关语言,A为a组成的串, 如何用a表示A? Ae AaA Be及BbB,3.3 上下文无关语言,由上述规则组成的规则集合就是一个语言产生器. 从单个符号S开始, 在当前字符串中找出出现在其中一个规则的号左端的一个符号, 用同一个规则右端的字符串代替该符号.重复该过程, 直到找不出该符号为止.,3.3 上下文无关语言,例： 产生字符串aaab, 从S开始,3.3 上下文无关语言,例：产生字符串aaab, 从S开始 S,3.3 上下文无关语言,例： 产生字符串aaab, 从S开始 aMb,3.3 上下文无关语言,例：产生字符串aaab, 从S开始 aAb,3.3 上下文无关语言
4、,例： 产生字符串aaab, 从S开始 aaAb,3.3 上下文无关语言,例： 产生字符串aaab, 从S开始 aaaAb,3.3 上下文无关语言,例： 产生字符串aaab, 从S开始 aaab,3.3 上下文无关语言,上下文无关: 考虑字符串aaAb为产生aaab的中间阶段,3.3 上下文无关语言,aa A b,上下文(context),3.3 上下文无关语言,AaA表示A可以被字符串aA代替, 无论A周围的字符串是什么, 也就是说与A的上下文无关,3.3 上下文无关语言,在上下文无关文法中, 有一些符号出现在的左端, 如S, M, A和B, 有些符号出现在的右端, 如a和b. 称出现在右端
5、的符号为终结符(terminals), 当产生的字符串全部都是由这种符号组成时表示产生的过程结束.,3.3 上下文无关语言,定义: 上下文无关文法G为一个四元组(V,T, P, S), 其中 V为非终结符集合, T为终结符的集合, P为规则有限集合, P V(VT)* S为起始符号, SV,3.3 上下文无关语言,非终极符号表示语法概念（如主、谓、宾等）或语法范畴。 终极符号表示语言的基本符号，例如26个字母（大、小写）及标点符号等。 S是非终极符中的一个语法概念，是最关心的语法概念。,3.3 上下文无关语言,P是语法规则，例如： 句子主语谓语宾语 句子主语系词表语 等等，称为产生式,3.3
6、上下文无关语言,即由 主语谓语宾语 可以产生 句子 产生式表示一条语法规则，P为产生式集合。 （尖括号指非终极符，是语法范畴）,3.3 上下文无关语言,语言的识别问题：要让计算机自动识别语言（自然语言或机器语言或程序设计语言），必须先用形式化的方法来表示语言。,3.3 上下文无关语言,对于给定串，判定是否有： SU1U2， 简记为：S ，即可由S闭包推导而得。,3.3 上下文无关语言,文法生成的句子： 由终极符组成的串，以数学语言表示如下：T*，说明是一个句子。如果T+，说明是一个句子，但不是空句子。,3.3 上下文无关语言,句型是由终极及非终极符组成的串，设有一个串，有： (VT)*，是一个
7、句型 (VT)+，是一个句型，但不是空句型 产生式P：，其中、(VT)*,3.3 上下文无关语言,句型推导关系：，其中、(VT)*，即可由推导出来。 ，推导闭包，经过多步（包括0步）推导。当时，称为0步推导。 ，多步推导，至少一步推导。 给定文法G，串是满足文法G的句子，则 S ，且T*，（即是句子，不是句型），还有S ，即由S可以闭包推导出句型。,3.3 上下文无关语言,定义：文法G规定的语言： L(G) = |S 且T* 若对某上下文无关文法G, 语言L=L(G), 则称L为上下文无关语言.,3.3 上下文无关语言,高级程序设计语言属于上下文无关语言 各类协议（如七层或SOAP）属于上、下
8、文无关语言 数据库中的查询语言定义属于上、下文无关语言,3.3 上下文无关语言,例：某语言有文法G： 字母数字标识符 终极符T： 0, 1, 2, , 9, a, b, , z, A, B, , Z, _,3.3 上下文无关语言,P中的产生式有： 字母 a 字母 b 字母 z 数字 0 数字 1 数字 9,3.3 上下文无关语言,则可以形式化地表示标识符为： 标识符 字母（可以是单个字母） 标识符 标识符字母（可以是字母与字母） 标识符 标识符数字（可以是字母与数字） 通过递归来定义出标识符：任意长度，以字母开头。,3.3 上下文无关语言,例：G=(A, B, C, S, a, b, P, S
9、) 其中：P中的产生式集合为： SAB, S BC, B CC, B b, C AB, C a, A BA, A a 试证明给定串baabaT*，且S baaba，即可以由文法规则推导出该串.,3.3 上下文无关语言,证明：因为baaba串中的每一个字符均属于T，故baabaT* S BC bC bAB baB baCC baCa baABa baaBa baaba.,3.3 上下文无关语言,语法分析是指根据指定文法通过一定算法来自动推导（证明）目标串的过程。其推导过程不唯一，结果不唯一。,3.3 上下文无关语言,上、下文无关的文法范式：在上述P的产生式集合中，都是上、下文无关的文法（CFG）范式，左边是一个非终极符，右边是两个非终极符或是一个终极符。即G中P的产生式形为： ABC 或 Aa， 其中：A，B，CV，aT 定义此范式为乔姆斯范式，可以以二叉树的形式来表述这种范式，非终极符为树枝，终极符为树叶。乔姆斯是美国语言学家。,3.3 上下文无关语言,定理：任给一个CFG均可以转换为乔姆斯范式。 因为该范式是二叉树形式，对于任意给定的串，将非终极符为树枝，终极符为树叶，则该串可以认为是树，根据树的理论，可以将任何树转换为二叉树。,
