计算引论7 上下文无关语言.ppt

计算引论 第三章 文法与语言 第三章 文法与语言 3.1 语言的基本概念 3.2 有限自动机 3.3 上下文无关语言 3.4 上下文无关语言识别算法 3.3 上下文无关语言 引子 The cat is in the hat. Hat the the in is cat. 语言识别器: 一个接受有效字符串(至少语法正确)的装置, 如有限自动机 语言产生器: 根据一个起始符号构造字符串的装置 3.3 上下文无关语言 如何设计出关于自然语言的大量子集, 在过去几十年中一直是个前沿问题. 语言产生器的出现推动了对人类语言的探讨. 尤其是形式的, 人工的语言的产生器理论, 如正规语言及上下文无关语言. 该理论是对自动机的补充, 也是对计算机语言进行说明和分析的结果. 3.3 上下文无关语言 正规表达式可视为语言的产生器. 例如, 正规表达式a(a*?b*)b 先输出a; 输出一串a或输出一串b; 最后输出b. 用这种方法就可以将该表达式表示的字符串全部产生出来 3.3 上下文无关语言 更复杂的语言产生器, 上下文无关文法, 是对语言的字符串的结构进行深入理解的理论. 3.3 上下文无关语言 若令S为语言的字符串, 符号M表示中间部分, 则上面的描述可以表示为 S?aMb 其中?读做“可以为”, 并且称该表达式为规则. M?a组成的串和M?b组成的串 M?A和M?B 3.3 上下文无关语言 A为a组成的串, 如何用a表示A? A?e A?aA B?e及B?bB 3.3 上下文无关语言 由上述规则组成的规则集合就是一个语言产生器. 从单个符号S开始, 在当前字符串中找出出现在其中一个规则的?号左端的一个符号, 用同一个规则?右端的字符串代替该符号.重复该过程, 直到找不出该符号为止. 3.3 上下文无关语言 例： 产生字符串aaab, 从S开始 3.3 上下文无关语言 例：产生字符串aaab, 从S开始 S 3.3 上下文无关语言 例： 产生字符串aaab, 从S开始 aMb 3.3 上下文无关语言 例：产生字符串aaab, 从S开始 aAb 3.3 上下文无关语言 例： 产生字符串aaab, 从S开始 aaAb 3.3 上下文无关语言 例： 产生字符串aaab, 从S开始 aaaAb 3.3 上下文无关语言 例： 产生字符串aaab, 从S开始 aaab 3.3 上下文无关语言 上下文无关: 考虑字符串aaAb为产生aaab的中间阶段 3.3 上下文无关语言 3.3 上下文无关语言 A?aA表示A可以被字符串aA代替, 无论A周围的字符串是什么, 也就是说与A的上下文无关 3.3 上下文无关语言 在上下文无关文法中, 有一些符号出现在?的左端, 如S, M, A和B, 有些符号出现在?的右端, 如a和b. 称出现在右端的符号为终结符(terminals), 当产生的字符串全部都是由这种符号组成时表示产生的过程结束. 3.3 上下文无关语言 定义: 上下文无关文法G为一个四元组(V,T, P, S), 其中 V为非终结符集合, T为终结符的集合, P为规则有限集合, P? V×(V?T)* S为起始符号, S?V 3.3 上下文无关语言 非终极符号表示语法概念（如主、谓、宾等）或语法范畴。 终极符号表示语言的基本符号，例如26个字母（大、小写）及标点符号等。 S是非终极符中的一个语法概念，是最关心的语法概念。 3.3 上下文无关语言 P是语法规则，例如： ＜句子＞?＜主语＞＜谓语＞＜宾语＞ ＜句子＞?＜主语＞＜系词＞＜表语＞ 等等，称为产生式 3.3 上下文无关语言 即由 ＜主语＞＜谓语＞＜宾语＞ 可以产生 ＜句子＞ 产生式表示一条语法规则，P为产生式集合。 （尖括号指非终极符，是语法范畴） 3.3 上下文无关语言 语言的识别问题：要让计算机自动识别语言（自然语言或机器语言或程序设计语言），必须先用形式化的方法来表示语言。 3.3 上下文无关语言 对于给定串ω，判定是否有： S?U1?U2?…?ω， 简记为：S ω，即ω可由S闭包推导而得。 3.3 上下文无关语言 文法生成的句子： 由终极符组成的串，以数学语言表示如下：ω∈T*，说明ω是一个句子。如果ω∈T+，说明ω是一个句子，但不是空句子。 3.3 上下文无关语言 句型是由终极及非终极符组成的串，设有一个串?，有： ?∈(V∪T)*，是一个句型 ?∈(V∪T)+，是一个句型，但不是空句型 产生式P：???，其中?、?∈(V∪T)* 3.3 上下文无关语言 句型推导关系：???，