高级语言及其语法描述2.ppt

第二章 高级语言及其语法描述,2.1程序语言的定义 引言：关于形式语言,1、词法规则、语法规则P12-13,2、语义P14,2.2高级语言的一般特性P14-15,2.3 程序语言的语法描述P25,2.3 程序语言的语法描述,一、符号和符号串 字母表：字母表是符号元素的非空集合。,符号：字母表中的元素。,符号串：字母表中的符号所组成的任何有穷序列。,例如，若有字母表=a,b,则a，b是字母表中的元素(符号);,a，b，aa，ab，ba都是符号串。,注意：符号串中的符号与顺序有关，ab和ba是不同的符号串,特别定义:空符号串不含任何符号的符号串，用 表示。,符号串的运算：,符号串的连接（联结、乘积）：符号串x和y的连接是指x和y的符号按先后顺序排列在一起组成一个新的符号串，用xy表示。,例，若字母表=a,b，符号串x=ab，y=ba,则xy=abba,符号串的长度：符号串中符号的个数为符号串的长度。,注意: (1)连接运算不满足交换律，即xyyx (2)任何符号串x与空串的连接都等于x，即： x=x=x。,若ab是符号串，则|ab|表示符号串的长度。 |ab|=2,同理：|aabb|=,4,注意：特别规定 |=0。,符号串的前缀与后缀(头和尾)：若有符号串 z=xy(x,y是符号串),我们称x为z的前缀，y为z的后缀。,例z=abcd 则：z的头有， , a , ab , abc , abcd z的尾有， ,d , cd , bcd , abcd,符号串的幂运算：设X是一个符号串，则： X0=，X1=X，X2=XX，Xn=XX=Xn,例：若有符号串x=ab，则：,x0=,x1=,ab,x2=,abab,x3=,ababab,显然，若n0,则Xn=XXn-1 =Xn-1X。 即：符号串的幂运算服从结合律,若有两个符号串x=ab,y=cde,那么，|xy|=?,5,符号串集合的运算：,符号串集合的乘积运算：设A、B为符号串集合（集合中各元素都是字母表上的字符串），两个字符串集合的乘积定义为：AB=xy|xA , yB（笛卡儿乘积）,设有字母表=a,b,c,d，令A=aa,bb，B=cc,dd 则AB=aacc,aadd,bbcc,bbdd， BA=ccaa,ccbb,ddaa,ddbb。 显然 AB BA，即符号串集合乘积不满足交换律。,注意：因x = x故，A=A=A,特别定义：空符号集合： 空集合：=,A = A= ,符号串集合的幂运算：设A为符号串集合，则集合的幂运算定义如下:,A0=,A1=A,A2=AA,A=,=AAn-1,=An-1A,符号串集合的闭包：设A为符号串集合，则集合的闭包定义如下:,A的正闭包： A+=A1A2,A的闭包： A*=A0A1A2,设集合A=a,b，则 A+=a,b,aa,ab,ba,bb,aaa, A*=,a,b,aa,ab,ba,bb,aaa, ,显然： A*=A0A+ A+=AA*,设有字母表=az, 09, type, var, const, if, then, else, for, to, do, case, begin, end, 各种运算符和其它特殊符号， 则，由这些字母表中的元素(符号)可以组成不同的符号串：,Program example;,Var,sum,I: integer;,Begin,Sum := 0;,For I:=1 to 10 do sum:=sum+I;,12345:=sum;,End.,Write(sum=,sum);,二、上下文无关文法 (p26),文法(Grammar):是描述语言的语法结构的形式规则（即语法规则）。,The big elephant ate the peanut.,语法树(Parse Tree):句子结构的图形表示方式,规则：规则又叫产生式(production rule)，它是句子结构的另一种表示结构，它引入了符号“:=”或“”表示“由组成”，上述句子的结构可以表示如下：, the big ate elephant peanut,句子的推导：用规则(产生式)按一定方式去推导或产生句子的过程。,The ,The big ,The big elephant ,The big elephant ,The big elephant ate ,The big elephant ate ,The big elephant ate the ,The big elephant ate the peanut,The big elephant ate the peanut,三、文法和语言的形式定义,定义2 文法是一个四元组：GS=(VN, VT, P, S),其中：,VN为非终结符集合；,VT为终结符集合； VNVT =，一般令 V= VNVT ，V中的符号称为文法符号；(V字汇表）,P为产生式集合； P中的每个产生式写为：或=。,S为开始符号(或称根符号，识别符号)。,定义1 产生式(或规则)是一有序对(A, )，通常写为： A 或A= 其中A是一个符号作为产生式左部， 为有穷符号串作为产生式的右部，“ ”或“=”表示“定义为”或“由组成”。,另外：GS也可简写为G,在规则左部出现的符号称为非终结符，它们的全体形成VN,在规则中只在右部出现的符号称为终结符，它们的全体形成VT,例 G1 =(N,0，1,N0N,N1N,N0,N1,N）,其中: 非终结符 VN =N,终结符VT =0，1,P=N0N，N1N，N0，N1,开始符号S 为N,通常情况下，文法只用产生式集合表示：,G1N: N0N N1N N0 N1,定义3 符号串的推导与归约：已给文法G=(VN,VT,P,S)， V= VNVT，令x,y,V*，且P，此时，由符号串xy能够直接产生出符号串xy，我们称：,符号串xy是符号串xy的直接推导；,符号串xy是符号串xy的直接归约；,记作: xy xy,对于上例中文法：,G1N: N0N N1N N0 N1,存在以下直接推导：,N, 1N, 11,若有1，2，nV* 且1 2 ，n-1 n则称n是1的推导,记作： 1,n,特别约定：若在推导关系1,n中允许1=n，,引用巴科斯范式(BNF)表示文法：,对于具有相同左部的那些产生式，如：Ux, Uy, Uz可以缩写为：Ux|y|z (“|”可理解为“或”),(1) (2) (3) (4) 0 (5) 1 (6) 2 (7) 3 (8) 4 (9) 5 (10) 6 (11) 7 (12) 8 (13) 9,(1) (2) | (3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|,用此文法和直接推导的定义可以推导出任一无符号整数(56), 5 5 56,可表示为:,定义4 句型和句子:设G=(VN,VT,P,S)是一文法,那么，句型和句子的区别是什么?,例:前面提到的文法G = VN，VT，P，无符号整数 其中，VT =0，1，2，3，4，5，6，7，8，9 VN =无符号整数，数字串，数字 P： 0123456789, 5 5 56,试给出该文法的句型、句子举例，并说明它所确定的语言。,由此我们可以看出，文法和语言是密切相关的，根据文法可以推导出任一句型和句子，而所有句子的集合则为该文法所对应的语言，即语言是所有句子构成的集合，它是所有终结符号串所组成的集合VT*的子集：,L(G) VT*,定义5 规范推导(归约):对于直接推导xy xy，如果y只包含终结符号或为空符号串，那么就把这种直接推导称为规范(最右)推导，跟其对应的归约称为规范(最右)归约，且记作：,下面的推导是否规范推导: 5 5 56, 6 6 656,每次对符号串最右非终结符号进行替换,形式语言理论可以证明以下两点：,(1)给定一个文法G，就可以从结构上唯一地确定其语言：,GL(G),(2)给定一种语言L，能确定其文法，但这种文法可能不是唯一的：,LG1或G2,例1：有文法GZ: (1)ZaZb (2)Z ab 它确定的语言是什么？,用BNF表示： Z aZb|ab,由产生式(2)知： zab 故ab是文法的一个句子,用产生式(1)(2)：zaZba2b2 故a2b2是文法的一个句子,反复使用产生式(1)： zaZba2Zb2 an-1Zbn-1 anbn,所以，文法所确定的语言为：L(GZ)=anbn | n1,同样，可给出最左推导及例子。P30-31,例2：已知语言为 L(G)=abna | n1 试给出其文法。,G1Z: Z aBa B bB|b,G2Z: Z aBa B Bb|b,定义6 等价文法：如果L(G1)=L(G2) ，那么称G1和G2为等价文法。,定义7 递归产生式和递归文法：设给定文法G=(VN,VT,P,S),(1)若存在产生式AP 且有 AxAy成立，则称产生式A是递归产生式；,若x=且y,则称产生式A是左递归产生式；,若x且y=,则称产生式A是右递归产生式。,B Bb,B bB,(2)递归文法： 若文法中至少存在一条递归产生式则称该文法是直接递归的文法；,则称文法为间接递归的文法。,可见，对于文法中任一非终结符号，若能建立一个推导过程，在推导所得的符号串中又出现了该非终结符号本身，则文法是递归的。应当注意，一般的文法都是递归的，文法G只有递归定义，L(G)中句子才是无穷的 。,例：有文法GS: S aB|bB B a|b,是否是递归文法，确定什么语言？,非递归文法，L(GS)=aa,ab,ba,bb,例：有文法G (1) (2) | (3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|,该文法中有直接左递归产生式： 所以是递归文法。,它是否为递归文法，确定的语言是什么？,所确定的语言为：所有无符号整数。L(G)=VT*,若不用递归规则表示文法，就要用到无穷多条产生式： | | |,总之，使用递归文法，可用有穷的产生式来描述无穷的语言，反之，一个语言若是无穷的，则描述语言的文法必定是递归的。(程序设计语言一般是无穷的)。,定义8 短语、简单短语和句柄：设文法 G=(VN,VT,P,S) ，且 UVN，x,y,u V*,则u称为句型xuy的相对于U的短语 ；,则u称为句型xuy的相对于U的简单(直接)短语；,例：有文法G (1) (2) | (3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|,因有： ,6,U= u= 6 x,y=,6是句型 6相对于的短语,(3)任一句型的最左简单短语称为该句型的句柄.,因有： ,6,6是句型6相对于的短语，且为简单短语,说明：当句型有两个以上的简单短语同时存在时，我们把位于最左边的那个简单短语称为“最左简单短语”，即该句型的句柄；若句型只有一个简单短语，那么，它就是最左简单短语，即句柄。,例1：在“6”中，6是句型6中唯一的一个简单短语，所以它是句柄.,例2：在“ 78”中，7和8都是是句型简单短语，所以位于左边的7是句柄. 注意：可从语法树的角度理解短语和句柄。P31,2.4文法的分类,按照文法中产生式的不同情况，Chomsky把文法分成四种类型，四种类型的文法对应着四种类型的语言。,0型文法： 产生式形式为: u v 且 uV+ v V* u中应至少含有一个非终结符号，这种文法又叫短语文法，它所确定的语言称为0型语言。,1型文法: 产生式形式为 xUy xuy 且 UVN uV+ x,y V* 则称该文法为1型文法，也称为上下文敏感文法或上下文有关文法。,即只有在U的左部为符号串x而右部为符号串y时，才允许把非终结符U用符号串u来代替，即U必须在上下文xy中才行。这种文法所对应的语言为1型语言。,2型文法: 产生式形式为 U u 且 UVN uV*则称该文法为2型文法，也称为上下文无关文法。2型文法所确定的语言为2型语言，大部分程序设计语言都是2型语言。,例: 文法G =（S，a,b，SaSb, Sab，S）,3型文法: 产生式形式为 UxV|y 或 U Vx|y 且 U,VVN，x,yVT+ 则称该文法为3型文法，也称线性文法、正则文法或正规文法。这种文法所对应的语言称为3型语言(正则语言、正规语言)，大多数程序设计语言的单词 (标识符、无符号整数) 的文法都是3型文法。,从0型文法到3型文法是逐渐增加限制的，而它们所确定的语言是逐步缩小的。,u v xUy xuy U u UxV|y,2.5语法树和文法的二义性,语法树: 设文法G=(VN,VT,P,S) ，所谓语法树是一张图，这张图表示一个句型的推导过程。语法树结构是一棵倒立的树结构，其中，结点的名字NV，根结点的名字S是文法G的根符号，树中的中间结点是句型推导过程中使用的非终结符 ，树的端末结点自左向右排列就是所给句型。,例2.7 文法GE: EE+TT TT*FF F（E）i 句型E+F*i对应的语法树如右图所示：,可以看出，语法树的生成过程直观的给出了句型的推导过程。,子树：由语法树的某个结点(子树的根)连同它下面射出的部分组成语法树的子树。只含有单层分支的子树为简单子树。,子树与短语：在句型所对应的语法树中，若某些符号按从左到右的顺序组成某棵子树的末端结点，那么由这些末端结点所组成的符号串是相对于子树根结点的短语。,例如：F是句型相对于T的短语，且为简单短语; i是句型相对于F的短语，且为简单短语; F*i 是句型相对于T的短语; E+F*i是句型相对于E的短语.,原则上语法树有多少棵子树，就有多少个短语,哪个是句柄？,文法的二义性：若一个文法存在某个句子对应两棵不同的语法树，则称此文法是二义性文法，运用文法描述程序设计语言的语句成份，一般希望所给文法是非二义文法，但是，有时候采用二义性文法比非二义文法要简单的多，所以，经常用二义性文法描述程序设计语言。,例1： 文法GE : EE+E | E*E | (E) | i 试为符号串E*E+i构造