资源预览内容
第1页 / 共187页
第2页 / 共187页
第3页 / 共187页
第4页 / 共187页
第5页 / 共187页
第6页 / 共187页
第7页 / 共187页
第8页 / 共187页
第9页 / 共187页
第10页 / 共187页
亲,该文档总共187页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第二章 文法与语言l一个语言的定义可以从两个方面进行:l 从语言产生的角度;(形式语言) l 从接收(识别)语言的角度。(自动机) l设是一个字母表,L *, L称为 字母表上的一个语言(language), x L, x叫做L的一个句子。2.1 例子语言l例1:括号匹配的语言(该语言是指 所有的左、右括号相匹配的串的集 合)。l问题:如何产生该语言?即如何生 成该集合中的所有的串?l自然语言的描述方式,采用如下的递归规则: ( )是合法的该语言的最基本的串; 若S是一个合法的串,则(S)是合法串 ; 若S是一个合法的串,则SS是合法串 ;l这些规则称为形成规则,根据这些规 则,可以l(1)产生任意合法(即符合规则)的该 集合中的串;l(2)判断某个串是否是合法的该集合的 串(即合法的句子)。l例如: 可以产生串();而推断串()不是合法的串。l规则(的个数)是有限的,但 可以产生无限个串和无限长 度的串;l因为规则是递归的。l巴科斯和诺尔采用的巴科斯-诺尔范式(BNF- Backus-Naur Form)描述规则:l:= ( )l:= l:=()l使用尖括号“”包括起来的部分,作为 一个整体来看待,表示某个语法成分,最终 ,需要使用字母表中的字母来定义。l符号“:=”是BNF本身的符号(元符号),代 表“定义为”或“就是”。l符号“( ”和“ )”是字母表的元素。lChomsky采用的符号化(形式化)的 描述方式,运用如下的规则(这些规 则被称为产生式): S( ) S(S) SSS l”读作“定义为”或者“是” , 它的左边和右边分别称为该产生式的 左边和右边; l根据这些规则,也可以生 成任意合法的串;可以判 断一个串是否为合法的串 。l产生串的过程为:从S开始,反 复利用产生式的右边代替产生 式的左边(称之为推导过程) ,最后,可以得到匹配的() 组成的串。例:串( )( )( )的产生过程lS=SS=(S)S=( )S=( )(S)=( )(SS)=( )( )S)= ( )( )( )l其中:“=”表示单步推导过程。l虽然产生式的个数是有限的, 但是规则是递归的,因而,所 有的小括号匹配的串(有无限 个)均可以由它们产生,它们 组成的集合就称为一个语言。lS称为非终结符,在推导过程中,可 以被代替的符号。l(和)称为终结符,在推导过程中,不 可以被代替的符号。l 是产生式系统的元符号,不属于 非终结符,也不属于非终结符。 l例2-2:由偶数个0组成的串的语言。l自然语言的描述方式: 00是合法的该语言的基本的串; 若S是合法的串,则SS是合法的串;l形式化的描述方式: S00 SSS 问题:l将产生式SSS换成S0S0或者S00S, 是否还产生相同的语言? l同一个语言,可以使用不同的产 生式组合来产生。l考虑: 由奇数个1组成串的语言的产生。l例2-3:包含有+、-、*、/ 、()的算术表达式的语 言。自然语言的描述方式单个变量是合法的最基本的串; 若S是一个合法的串,则SAS是一 个合法的串( 其中A代表运算符+ 、-、*、/) 若S是一个合法的串,则(S)是合法 的串;形式语言的描述方式 S i (i代表单个变量) SSAS S( S ) A+ A- A* A/l其中 : lA+,A-,A*,A/ 四个产生 式的左边是相同的符号,可以合并 为A+|-|*|/+、-、*、/ 称为A的侯选式。注意:l这组产生式没有表示出运 算符的优先级。l表示出运算符的优先级的产生 式:EE+T|E-T|TTT*F|T/F|FF(E)|il其中:E代表表达式,T代表项,F代 表因子,(E)代表的是带小括号的表 达式。该组产生式表示出先算因子, 再*、/,最后+、-。l如果使用%代表模运算(即取余数运算 )、使用代表指数运算,则有l EE+T|E-T|TlTT*F|T/F|T%F|Al AFA|F l F(E)|il注意:l还需要考虑运算的结合性:是右结 合的。l例2-4 标识符(以字母开头的字母、 数字的串)的产生(仅考虑小写字母) 。 l ILIILIIDLa |b|c|zD0|1|2|9将I的定义加入到表达式中: EE+T|E-T|TTT*F |T/F|FF (E)|IIL|IL|IDLa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z D0|1|2|3|4|5|6|7|8|9 l考虑:其他类型的表达式 (如关系表达式等)的定 义例2-5lC语言中简单变量的说明语句的定义 。C语言中的说明语句形式为: lTYPE 变量名表;lTYPE 变量名表;llTYPE 变量名表;产生式为:SSS|PPT V;Tint|char|floatVV,V|IIL|IL|IDLa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|zD0|1|2|3|4|5|6|7|8|9l其中:S代表简单变量的说明语句(可 以由一个或多个的单个说明语句构成 ),P代表单个的说明语句,T代表类 型,V代表变量名表(由,隔开的 多个变量),I代表单个变量。l思考:l PASCAL语言的简单变量的说明语 句的形成。2.2 文法和语言的关系l介绍语言的定义。l介绍文法的定义。l介绍文法与语言的关系。l语言就是某个字母表上的字符串组成的一 个集合。语言中的字符串称为句子。l文法的作用就是产生一个语言。l有穷语言的表示较容易,即使语言中的句 子的组成没有什么规律,也可以使用枚举 的方式列出语言中的所有句子。l对于无穷语言,使用有穷描述的方式表达 。需要从语言包含的句子的一般构成规律 去考虑问题。这种从语言的有穷描述来表 达语言的方法对一般的语言都是有效的。 尤其在使用计算机判断一个字符串是否是 某个语言的句子时,从句子和语言的结构 特征上着手是非常重要的。l对于一类语言,可以在字母表上,按 照一定的构成规则,根据语言的结构 特点,定义一个文法。使用文法作为 相应语言的有穷描述,不仅可以描述 出语言的结构特征,而且可以产生这 个语言的所有句子。短语结构文法(文法)的定义文法G是一个四元式(由四个部分组成) ,即G=(,V,S,P); l是一个有限字符的集合(字母表), 它的元素称为字母或者终结符; lV是一个有限字符的集合,叫做非终 结符集合,它的元素称为变量或者非 终结符;lSV,称为文法的开始符号;lP是有序偶对(,)的集合,其中是集 合(UV)上的字符串,但至少包含一个 非终结符;是集合(UV)*的元素。一 般,将有序偶对(,)记为,称为 产生式;l如果有,称之为空串产生 式或者产生式。l如果有AB,称之为单产生式。l一个产生式的左边可能不只一 个符号;第一个产生式的左边 只能有一个符号,就是开始符 号S。l文法的作用就是产 生一个语言。约定:如果没有特别说明第一个产生式左边的符号,就是开始符号,可以不为S; 大写的英文字母代表非终结符;推导(派生)的定义2-2l给定文法G,和是集合(UV)上的 串,若,分别可以写成pvr 和 pur(p和r可能同时为空串),而vu是 文法G的一个产生式,则称串可以直 接推导出串 ,记为= ,或 pvr =pur。l推导的实质是用产生式的右边代 替产生式的左边。(非终结符代表 在推导的过程中可以被替代的符 号,而终结符代表在推导的过程 中不可以被替代的符号)。l推导的逆过程称为归约。l用符号y=*z表示y可以经 过任意步(包括0步)推导 出z,即 l y=z;或者l存在一个序列1,2 ,3 ,nl有 y=1,z=n,且i=i+1;对所有i1。l用符号y=+z表示y可以经 过多步(至少一步),推导 出z,即l存在一个序列 1,2 ,3 ,n 有y=1 ,z=n,且i=i+1;对所有 i1。思考:l对于任意文法G:lS=*S 和lS=+S l一定都成立吗?l如果在推导的过程中,每一步都是将 推导产生的串的最左边的非终结符代 替掉,称之为最左推导,如果每一步 都是将推导产生的串的最右边的非终 结符代替掉,称之为最右推导(也称 之为规范推导),l当然,还有其它方式的推 导过程(例如混合),而 最左推导和最右推导是比 较常用的推导方式。l对于文法G,如果S=*,则 称是文法的一个句型,若 中包含的字符全是终结符,称 是句子。语言的定义l给定文法G,有开始符号S,则把S 可以推导出的所有的终结符串的集 合(即所有句子的集合),称为由 文法产生的语言,记为L(G),即lL(G)=|S=*,且*。l例如:产生括号匹配的语言的文法是: G=(,),S,S, S( ), S(S), SSS )l一般,对于文法G,可以只给出它的产生式的 集合即可。上述文法可以简写为:S( )S(S)SSSl对于文法和语言,可以从一个文 法得到该文法产生的语言;也可 以根据语言,写出产生该语言的 某个文法;还可以判断一个语言 是否由某一个文法产生。l考虑:文法 SaSa|bSb|c|产生的语言是什么?考虑:l产生语言L的文法,lL= wwT|wa,b,c+l其中:wT是w的逆(反序)。考虑:l产生下列语言的文法:L1=anbn|n=0;L2=anbn|n0;l文法S0B|1AA0|0S|1AAB1|1S|0BBl产生的语言是l0,1上包含相等个数0和1的串的 语言;即L(G)=|0,1+,且中有相同多的0和1。l一个文法确实产生语言L(G),必须 确定两个命题:l该文法推导出的串都在语言中;l所有语言中的串都可以由该文法 产生。l注意:一个语言可能由多个不同 的文法产生。l如果文法G1和文法G2产生同一 个语言,则称文法G1和G2是等价 的文法。记为L(G1)= L(G2)。l例2-9 构造文法G,使L(G)=0,1,00,11 。lG1: S0|1|00|11lG2: SA|B|AA|BB A0 B1lG3: S0|1|0A|1B A0 B1l有0,1,00,11=L(G1)=L(G2)=L(G3)l注意:l 两个文法G1和G2等价和两个文法 G1和G2相同的区别。 2.3Chomsky对文法的分类l本节介绍Chomsky对文法和语言进行的分类。l语言是由文法产生的,对语言的分类,是根 据产生语言的文法的分类而进行的。短语结构文法l对于一般的短语结构文法PSG,G=(,V ,S,P),产生式的形式是vw,其中: v(V)+,且至少包含一个非终结符; w(V)*。l如果一个语言L可以由短语结构文法产生 ,则该语言是短语结构语言PSL。定义2-4:右线性文法的定义l对于文法G=( ,V,S,P),若它的 每个产生式都是下列形式之一:lAbC或者Aa;l其中:A,CV,aXU,b ;则文法G是右线性文法(RLG,也称 为正则文法RG)。l如果一个语言L可以由右线性文法 产生,则该语言是右线性语言( RLL或RL)。l右线性文法自然地对应于句子的 推导过程。 左线性文法l对于文法G,若每个产生式都是: :lACb或者Aa;其中A,CV, aXU,bX;则文法G是左 线性文法。如果一个语言L可以由 左线性文法产生,则该语言是左 线形语言。l左线性文法自
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号