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

《计算引论7 上下文无关语言课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算引论第三章文法与语言第三章文法与语言3.1语言的基本概念3.2有限自动机3.3上下文无关语言3.4上下文无关语言识别算法3.3上下文无关语言引子Thecatisinthehat.Hatthetheiniscat.语言识别器:一个接受有效字符串(至少语法正确)的装置,如有限自动机语言产生器:根据一个起始符号构造字符串的装置3.3上下文无关语言如何设计出关于自然语言的大量子集,在过去几十年中一直是个前沿问题.语言产生器的出现推动了对人类语言的探讨.尤其是形式的,人工的语言的产生器理论,如正规语言及上下文无关语言.该理论是对自动机的补充,也是对计算机语言进行说

2、明和分析的结果.3.3上下文无关语言正规表达式可视为语言的产生器.例如,正规表达式a(a*b*)b先输出a;输出一串a或输出一串b;最后输出b.用这种方法就可以将该表达式表示的字符串全部产生出来3.3上下文无关语言更复杂的语言产生器,上下文无关文法,是对语言的字符串的结构进行深入理解的理论.a(a*b*)b头部中间部分尾部3.3上下文无关语言若令S为语言的字符串,符号M表示中间部分,则上面的描述可以表示为SaMb其中读做“可以为”,并且称该表达式为规则.Ma组成的串和Mb组成的串MA和MB3.3上下文无关语言A为a组成的串,如何用a表示A?A

3、eAaABe及BbB3.3上下文无关语言由上述规则组成的规则集合就是一个语言产生器.从单个符号S开始,在当前字符串中找出出现在其中一个规则的号左端的一个符号,用同一个规则右端的字符串代替该符号.重复该过程,直到找不出该符号为止.3.3上下文无关语言例：产生字符串aaab,从S开始3.3上下文无关语言例：产生字符串aaab,从S开始S3.3上下文无关语言例：产生字符串aaab,从S开始aMb3.3上下文无关语言例：产生字符串aaab,从S开始aAb3.3上下文无关语言例：产生字符串aaab,从S开始aaAb3.3上下文无关语言例：产生字符串aaab

4、,从S开始aaaAb3.3上下文无关语言例：产生字符串aaab,从S开始aaab3.3上下文无关语言上下文无关:考虑字符串aaAb为产生aaab的中间阶段3.3上下文无关语言aaAb上下文(context)3.3上下文无关语言AaA表示A可以被字符串aA代替,无论A周围的字符串是什么,也就是说与A的上下文无关3.3上下文无关语言在上下文无关文法中,有一些符号出现在的左端,如S,M,A和B,有些符号出现在的右端,如a和b.称出现在右端的符号为终结符(terminals),当产生的字符串全部都是由这种符号组成时表示产生的过程结束.3.3上下文无关语言定义:

5、上下文无关文法G为一个四元组(V,T,P,S),其中V为非终结符集合,T为终结符的集合,P为规则有限集合,PV×(VT)*S为起始符号,SV3.3上下文无关语言非终极符号表示语法概念（如主、谓、宾等）或语法范畴。终极符号表示语言的基本符号，例如26个字母（大、小写）及标点符号等。S是非终极符中的一个语法概念，是最关心的语法概念。3.3上下文无关语言P是语法规则，例如：＜句子＞＜主语＞＜谓语＞＜宾语＞＜句子＞＜主语＞＜系词＞＜表语＞等等，称为产生式3.3上下文无关语言即由＜主语＞＜谓语＞＜宾语＞可以产生＜句子＞产生式表示一条语法规则，P为产生式集合。

6、（尖括号指非终极符，是语法范畴）3.3上下文无关语言语言的识别问题：要让计算机自动识别语言（自然语言或机器语言或程序设计语言），必须先用形式化的方法来表示语言。3.3上下文无关语言对于给定串ω，判定是否有：SU1U2…ω，简记为：Sω，即ω可由S闭包推导而得。3.3上下文无关语言文法生成的句子：由终极符组成的串，以数学语言表示如下：ω∈T*，说明ω是一个句子。如果ω∈T+，说明ω是一个句子，但不是空句子。3.3上下文无关语言句型是由终极及非终极符组成的串，设有一个串，有：∈(V∪T)*，是一个句型∈(V∪T)+，是一个句型，但不是空句型产生式P

7、：，其中、∈(V∪T)*3.3上下文无关语言句型推导关系：，其中、∈(V∪T)*，即可由推导出来。，推导闭包，经过多步（包括0步）推导。当＝时，称为0步推导。，多步推导，至少一步推导。给定文法G，串ω是满足文法G的句子，则Sω，且ω∈T*，（即ω是句子，不是句型），还有S，即由S可以闭包推导出句型。3.3上下文无关语言定义：文法G规定的语言：L(G)={ω

8、Sω且ω∈T*}若对某上下文无关文法G,语言L=L(G),则称L为上下文无关语言.3.3上下文无关语言高级程序设计语言属于上下文无关语言各类协议（如七层或SOAP）属于上、下

9、文无关语言数据库中的查询语言定义属于上、下文无关语言