资源描述:
《计算引论4文法与语言》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、计算引论第三章文法与语言求解问题与识别语言问题抽象为符号串的集合;符号串称为句子,问题是句子的集合;求解问题抽象为识别语言。问题提出:如何构造可以接受及产生一个语言的计算模型?语言识别器:对一个已经存在的字符串集合,如何判断它就是符合条件的语言?解决接受的问题。语言产生器:怎样产生一个语言?解决产生的问题。语言的识别问题:要让计算机自动识别语言(自然语言或机器语言或程序设计语言),必须先用形式化的方法来表示语言。文法能清晰描述语言的语法构成,。文法能自动构造有效的语言识别器。文法G定义为四元组(V,T,S,P),其中V是有限的非终极符集合;T是有限的终极符
2、集合;S是开始符,ST。必须在某个产生式的左边出现一次;P是产生式的集合,且具有下面的形式:,其中,(VT)*非终极符号表示语法概念(如主、谓、宾等)或语法范畴。终极符号表示语言的基本符号,例如26个字母(大、小写)及标点符号等。S是非终极符中的一个语法概念,是最关心的语法概念。P是语法规则,例如:<句子>定义为<主语><谓语><宾语>或<句子>定义为<主语><系词><表语>称为产生式,即由<主语><谓语><宾语>可以产生<句子>产生式表示一条语法规则,P为产生式集合。文法分类:A,BV,aT。对文法中的产生式→:O型文法:短语文法
3、。中至少含一个非终极符。1型文法:上下文有关文法。它是0型文法的特例,要求
4、
5、
6、
7、(S→例外,S不得出现于产生式右部)。2型文法:上下文无关文法。它是1型文法的特例,要求产生式左部是一个非终极符:A→。3型文法:正则文法。它是2型文法的特例,要求产生式具有下面形式之一:A→a,A→aB。文法的乔姆斯基体系正则文法上下文无关文法上下文有关文法短语文法相关定义定义(字符串):设A是基本符号表(字母表),A={a1,a2,…,an},则A上字符串集合表示为:A*=A0∪A1∪A2∪…∪Ak∪…A+=A1∪A2∪…∪Ak∪…其中:Ai是长度为i的字符串
8、。A*=A0∪A+推导:如果A是一个产生式,则对字符串A,有A,表示一步推导(用A→)。+:表示通过一步或多步可推导出*:表示通过0步或多步可推导出句型:如果有S*,则称符号串为相应文法的句型,其中S是文法的开始符。句子:如果只包含终极符,则称为相应文法的句子。语言:L(G)={u
9、S+u,uT*}。文法G所定义的语言是其开始符所能推导的所有终极符号串(句子)的集合。例:某语言有文法G:<字母><数学><标识符>,尖括号指非终极符。终极符T:{0,1,2,…,9,a,b,…,z,A,B,…,Z,_}
10、。P中的产生式有:<数字>0<数字>1…<数字>9<字母>a<字母>b…<字母>z标识符可以形式化地表示为:<标识符><字母><标识符><标识符><字母><标识符><标识符><数字>例:G=({A,B,C,S},{a,b},P,S),其中:P中的产生式集合为:SAB,SBCBCC,BbCAB,CaABA,Aa试证明给定串baaba∈T*,且Sbaaba,即是否可以由文法规则推导出该串。证明:因为baaba串中的每一个字符均属于T,故baaba∈T*SBCbCbABbaBbaCCbaCabaABabaaBa
11、baaba.3.2正则语言的识别正则文法定义:G(V,T,P,S),P中的产生式形如Aa,或AaB,a∈T,A,B∈V。右范式:形如AaB称为右范式,其中非终极符于终极符的右边。左范式:形如ABa称为左范式,其中非终极符于终极符的左边。正则语言正则文法G生成的语言:L(G)={ω
12、ω∈T*且S+ω}正则语言的识别对文法S,任给串ω∈T*,S+ω成立否。识别步骤:任给串ω∈T*,S+ω成立否。任给串ω,ω中所有的元素是否为给定终极符集中的元素构成。可否由非终极符中的S经过多步推导得到串ω。识别算法:设:ω=a1…an,ai∈T。若n=1,问题
13、等价于检查Sa1∈P?若n≥2,则需要证明Sa1B1+a1a2…an,问题变为:B1+a2…an是否成立。递推下去,B1a2B2?+a2…anB2a3B3?+a3…an…Bn-1an?即检查上述表达式是否均在文法集合P中。正则运算:设A和B是两个正则语言,并:AB={x
14、xA或xB}连接∘:A∘B={xy
15、xA且yB}星号*:A*={x1…xk
16、k≥0且xiAi}定理1:正则语言在正则运算下封闭。即:如果A和B是正则语言,则AB,A∘B,A*也是正则语言。3.3有限自动机有限自动机的结构abababab有限控制器q0q5q
17、4q3q1q2输入带读头特点:以字符串作为输入,通过输入带传送字符