,啊,啊,Part2,高级语言及其语法描述,授课：胡静,内容提要,程序语言的定义,程序语言的语法定义,程序语言的语义定义,高级语言的一般特性,高级语言的程序结构,数据类型和操作,语句与控制结构,程序语言的文法,关于文法的定义,文法的类型,上下文无关文法及其语法树,有关文法实用中的一些说明,程序语言的定义,程序语言的语法定义,任何语言程序都可以看成是一定字符集（称为字母表）上的一字符串（有限序列）。,所谓一个语言的语法是指这样一组规则，用它可以形成和产生一个合式的程序。这些规则一部分称为词法规则则，另一部分称为语法规则（或产生规则）,词法规则：词法规则规定了字母表中哪样的字符串是一个单词符号，是单词符号的形成规则,语法规则：语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法规则是语法单位的形成规则,程序语言的定义,程序语言的语义定义,所谓一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义。,我们将要介绍的是目前大多数编译程序普遍采用的一种方法，即基于属性文法的语法制导翻译方法，虽然还不是形式系统，但是比较接近形式化的。,高级语言的一般特征,高级语言的程序结构,程序,子程序,或,分程序,语句,表达式,数据引用,算符,函数调用,数据类型和操作,数据类型的要素：,用于区别这种类型的数据对象的属性；,这种类型的数据对象可以具有的值；,可以作用于这种类型的数据对象的操作；,数据类型分类：,初等数据类型：数值数据、逻辑数据、字符数据、指针类型,数据结构：数组、记录、字符串、表格、栈、队列和抽象数据类型（,Ada,通过程序包,package,提供，其余通过类,class,提供）,语句与控制结构,表达式：一个表达式是由运算量（操作数，即数据引用或函数调用）和算符组成的。,语句：不同程序语言含有不同形式和功能的各种语句,执行语句：描述程序的动作，分为赋值语句、控制语句、输入,/,输出语句；,说明性语句：定义各种不同数据类型的变量或运算,从形式上分，语句可以分为简单句、复合句和分程序等。,程序语言的文法,相关定义,字母表：,字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此，字母表也称为符号集，记做,字符串：,由符号表中的符号组成的任何有穷序列称为符号串，不包含任何符号的序列称为空串，记为,，,表示不含任何元素的空集。,*,符号串的长度：,如果某符号串,x,中有,m,个符号，则称其长度为,m,，表示为,|x|=m,，即,|=0,。,符号串的连接：,设,x,和,y,是符号串，它们的连接,xy,是把,y,的符号写在,x,的符号之后得到的符号串。,符号串的方幂：,设,x,是符号串，把,x,自身连接,n,次得到的符号串,z,称为符号串,x,的方幂，写成,z=x,n,。,程序语言的文法,相关定义（续）,符号串集合：,若集合,A,中的一切元素都是某字母表上的符号串，则称,A,为该字母表上的符号串集合。用,*,表示上的所有有穷长的串的集合，空串也包含在内。,*,的子集,U,和,V,的,（连接）积,定义为：,UV=,|,U,&,V,，一般而言，,UVVU,V,的,n,次（连接）积,记为,V,n,，规定,V,0,=,V,*,称为,V,的,闭包,，,V,+,=V V,*,，是,V,的,正则闭包,更多的概念和一些约定,A,B,C,用来表示,非终结符,a,b,c,表示,终结符,X,Y,Z,可以用来表示,终结符或者非终结符,w,x,y,z,表示,终结符号串,表示由,终结符或非终结符构成的符号串,在产生式,A,中，,A,是产生式的左边,(,lefthand side,LHS),是产生式的右边,(righthand side,RHS),A,1,|,n,表示产生式,A,1,A,n,文法的直观概念,EBNF(,扩充的巴科斯瑙尔范式,),表示的句子的构成规则,句子,：,=,主语,谓语,主语,：,=,代词,|,名词,代词,：,=,我,|,你,|,他,名词,：,=,王明,|,大学生,|,工人,|,英语,谓语,：,=,动词,直接宾语,动词,：,=,是,|,学习,直接宾语,：,=,代词,|,名词,“,我是大学生,”,的推导过程,句子,主语,谓语,代词,谓语,我,谓语,我,动词,直接宾语,我是,直接宾语,我是,名词,我是,大学生,关于文法的定义,定义,3.1,文法,G,定义为四元组（,V,N,V,T,P,S,）。,其中,V,N,为非终结符号（或语法实体，或变量）集；,V,T,为终结符号集；,P,为产生式（也称规则）的集合；,V,N,V,T,和,P,是非空有穷集。,S,称做识别符号或开始符号，它是一个非终结符，至少要在一条规则中作为左部出现。,V,N,和,V,T,不含公共元素，即,V,N,V,T,=,。通常,V,表示,V,N,V,T,，,V,称为文法,G,的字母表或字汇表。,例,3.1,文法,G=,（,V,N,，,V,T,，,P,，,S,）,V,N,=S,V,T,=0,1,P=S0S1,S01,S,为开始符号,关于文法的定义（续）,定义,3.2,如,是文法,G=(V,N,V,T,P,S),的规则,(,或说是,P,中第一个产生式,),，,和,是,V,*,中的任意符号，若有符号串,v,，,w,满足：,v=,，,w=,，则说,v,（应用规则,）直接产生,w,，或说,w,是,v,的直接推导。,例：,G,：,S0S1,，,S01,S,0S1 00S11 000S111 00001111,关于文法的定义（续）,定义,3.3,如果存在直接推导的序列：,v=w,0,=w,1,=w,2,=w,n,=w,，,(n0),，则称,v,推导出（产生）,w,（推导长度为,n,）。记做,v=,+,w,。,定义,3.4,若有,v=,+,w,，或,v=w,，则记做,v=,*,w,。,关于文法的定义（续）,定义,3.5,设,GS,是一文法，如果符号串,x,是从识别符号推导出来的，即有,S=,*,x,，则称,x,是文法,GS,的句型。若,x,只由终结符号组成，则称,x,为,GS,的句子。,定义,3.6,文法,G,所产生的语言定义为集合,x|S=,*,x,，其中,S,为文法的开始符号，且,xV,T,*,。可用,L(G),表示该集合。,例：,G,：,S0S1,，,S01,S,0S1 00S11 000S111 00001111,L(G)=0,n,1,n,|n,1,关于文法的定义（续）,定义,3.7,若,L(G1)=L(G2),，则称文法,G1,和,G2,是等价的。,例,1,：如文法,G,1,A,：,A0R,与,G,2,S,：,S0S1,等价,A01 S01,RA1,例,2,：,G,1,E:E i,与,G,2,E,：,E T|E+T,等价,E E+E T F|T*F,E E*E F,（,E,）,|i,E (E),文法的类型,Chomsky,将文法分为四种类型：,0,型文法：对任一产生式,，都有,(V,N,V,T,),+,，,(V,N,V,T,),*,1,型文法：对任一产生式,，都有,|,|,|,，仅仅,S,除外,2,型文法：对任一产生式,，都有,V,N,，,(V,N,V,T,),*,3,型文法：任一产生式,的形式都为,AaB,或,Aa,，其中,AV,N,，,BV,N,，,aV,T,。上述叫做右线性文法，另有左线性文法，二者等价。,文法的类型举例,1,型（上下文有关）文法,文法,GS,：,SCD,AbbA,CaCA,BaaB,CbCB,BbbB,ADaD,C,BDbD,D,AabD,L(G)=,ww|wa,b,*,文法的类型举例,2,型（上下文无关）文法,文法,GS,：,SaB|bA,Aa|aS|bAA,Bb|bS|aBB,文法,GS,：,S0A|1B|0,A0A|1B|0S,B1B|1|0,文法的类型举例,定义标识符的,3,型（正规）文法,文法,GI,：,I,lT,I l,T,lT,T,dT,T l,T d,文法和语言,0,型文法,0,型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何,0,型语言都是递归可枚举的,1,型文法（上下文有关文法）,产生式的形式为,1,A,2,1,2,，即只有,A,出现在,1,和,2,的上下文中时，才允许,取代,A,。其识别系统是线性界限自动机。,2,型文法（上下文无关文法）,产生式的形式为,A,，,取代,A,时与,A,的上下文无关。其识别系统是不确定的下推自动机。,3,型文法（正则文法）,产生的语言是有穷自动机（,FA,）所接受的集合,上下文无关文法,上下文无关文法有足够的能力描述现今程序设计语言的语法结构,算术表达式,语句,赋值语句,条件语句,读语句,文法,G=(E,+,*,I,(,),P,E ifthen P:E i|ifthenelse,E E+E,E E*E,E (E),上下文无关文法的语法树,用于描述上下文无关文法的,句型推导,的直观方法,例,:GS:,S,aAS,A,SbA,A,SS,S,a,A,ba,S,a A S,S b A,b a,句型,aabbaa,的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,a,a,上下文无关文法的语法树,推导过程中施用产生式的,顺序,例,:GS:,S,aAS,A,SbA,A,SS,S,a,A,ba,S,a A S,S b A a,a b a,S,aASaAaaSbAaaSbbaaaabbaa,SaASaSbASaabASaabbaSaabbaa,SaASaSbASaSbAaaabAaaabbaa,文法的二义性,最左（最右）推导：在推导的任何一步,，其中,、,是句型，都是对,中的最左（右）非终结符进行替换,最右推导被称为规范推导。,由规范推导所得的句型称为规范句型,文法的二义性,例：,GE:E i,E E+E,E E*E,E (E),E,E+E,E*E i,i i,E,E*E,i E+E,i i,句型,i*i+i,的两个不同的最左推导：,推导,1,：,E,E+E E*E+E i*E+E i*i+E i*i+i,推导2：,E E*E i*E i*E+E i*i+E i*i+i,文法的二义性,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是,二义,的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是,二义,的。,部分二义文法可以改造为无二义文法,GE:E i GE,：,E T|E+T,E E+E T F|T*F,E E*E F,（,E,）,|i,E (E),规定优先顺序（,T,）和结合律（左递归）,Thanks for your time!,Questions&Answers,