,啊,啊,Part2高级语言及其语法描述,授课：胡静,内容提要,预备知识形式语言基础,程序语言的定义（语法定义、语义定义）,高级语言的一般特性（程序结构、数据类型和操作、语句与控制结构）,程序语言的文法,文法的类型,上下文无关文法及其语法树,有关文法实用中的一些说明,预备知识,更多的概念和一些约定,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,Chomsky将文法分为四种类型：,Aa|aS|bAA,2型（上下文无关）文法,将单词看做符号，则句子就是符号串，而所有句子的集合（语言）就是符号串的集合,可以作用于这种类型的数据对象的操作；,例2：G1E:E i 与 G2E：E T|E+T等价,我们将要介绍的是目前大多数编译程序普遍采用的一种方法，即基于属性文法的语法制导翻译方法，虽然还不是形式系统，但是比较接近形式化的。,P=S0S1,S01,预备知识形式语言基础,S b A a,上下文无关文法及其语法树,其识别系统是不确定的下推自动机。,a A S,符号串和符号串集合的运算,符号串和符号串集合的运算,将字符看做符号，则单词就是符号串，单词集合就是符号串的集合,将单词看做符号，则句子就是符号串，而所有句子的集合（语言）就是符号串的集合,程序语言的定义,程序语言的语法定义,所谓一个语言的语法是指这样一组规则，用它可以形成和产生一个合式的程序。这些规则一部分称为词法规则则，另一部分称为语法规则（或产生规则）,词法规则：词法规则规定了字母表中哪样的字符串是一个单词符号，是单词符号的形成规则,语法规则：语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法规则是语法单位的形成规则,程序语言的定义,程序语言的语义定义,所谓一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义。,我们将要介绍的是目前大多数编译程序普遍采用的一种方法，即基于属性文法的语法制导翻译方法，虽然还不是形式系统，但是比较接近形式化的。,高级语言的一般特征,高级语言的程序结构,程序,子程序,或,分程序,语句,表达式,数据引用,算符,函数调用,数据类型和操作,数据类型的要素：,用于区别这种类型的数据对象的属性；,这种类型的数据对象可以具有的值；,可以作用于这种类型的数据对象的操作；,数据类型分类：,初等数据类型：数值数据、逻辑数据、字符数据、指针类型,数据结构：数组、记录、字符串、表格、栈、队列和抽象数据类型（Ada通过程序包package提供，其余通过类class提供）,语句与控制结构,表达式：一个表达式是由运算量（操作数，即数据引用或函数调用）和算符组成的。,语句：不同程序语言含有不同形式和功能的各种语句,执行语句：描述程序的动作，分为赋值语句、控制语句、输入/输出语句；,说明性语句：定义各种不同数据类型的变量或运算,从形式上分，语句可以分为简单句、复合句和分程序等。,文法的直观概念,VN,VT和P是非空有穷集。,预备知识形式语言基础,VN和VT不含公共元素，即VNVT=。,将字符看做符号，则单词就是符号串，单词集合就是符号串的集合,E (E),1型文法：对任一产生式，都有|，仅仅 S除外,程序语言的定义（语法定义、语义定义）,高级语言的一般特性（程序结构、数据类型和操作、语句与控制结构）,S b A,通常V表示VNVT，V称为文法G的字母表或字汇表。,其中VN为非终结符号（或语法实体，或变量）集；,上下文无关文法及其语法树,由规范推导所得的句型称为规范句型,所谓一个语言的语法是指这样一组规则，用它可以形成和产生一个合式的程序。,例2：G1E:E i 与 G2E：E T|E+T等价,预备知识形式语言基础,关于文法的定义,文法G定义为四元组（V,N,V,T,P,S）。,其中V,N,为非终结符号（或语法实体，或变量）集；V,T,为终结符号集；P为产生式（也称规则）的集合；V,N,V,T,和P是非空有穷集。S称做识别符号或开始符号，是一个非终结符（S,V,N,），至少要在一条规则中作为左部出现。,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为开始符号,文法可以简写，只需要指出开始符号和产生式即可。,S b A,文法GS：SaB|bA,例2：G1E:E i 与 G2E：E T|E+T等价,a,b,c,表示终结符,A01 S01,Chomsky将文法分为四种类型：,S称做识别符号或开始符号，是一个非终结符（S VN），至少要在一条规则中作为左部出现。,由规范推导所得的句型称为规范句型,上下文无关文法有足够的能力描述现今程序设计语言的语法结构,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。,S b A a,文法GS：S0A|1B|0,a,b,c,表示终结符,Part2高级语言及其语法描述,B1B|1|0,CaCABaaB,如果存在直接推导的序列：v=w0=w1=w2=wn=w，(n0)，则称v推导出（产生）w（推导长度为n）。,关于文法的定义（续）,如是文法G=(V,N,V,T,P,S)的规则(或说是P中第一个产生式)，和是V,*,中的任意符号串，若有符号串v，w满足：v=，w=，则说v（应用规则）直接产生w，或说w是v的直接推导。,（v=w）,例：GS：S0S1，S01,S,0S1 00S11 000S111 00001111,G,关于文法的定义（续）,如果存在直接推导的序列：v=w,0,=w,1,=w,2,=w,n,=w，(n0)，则称v推导出（产生）w（推导长度为n）。记做v=,+,w。,若有v=,+,w，或v=w，则记做v=,*,w。,规范推导（最右推导）,最左推导：若规则右端符号串中有两个以上的非终结符时，先推导左边的。,最右推导：若规则右端符号串中有两个以上的非终结符时，先推导右边的。,关于文法的定义（续）,设GS是一文法，如果符号串x是从识别符号推导出来的，即有S=,*,x，则称x是文法GS的句型。若x只由终结符号组成，则称x为GS的句子。,文法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,关于文法的定义（续）,若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：SCDAbbA,CaCABaaB,CbCBBbbB,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,