资源描述
第二章:高级语言机器语法描述,2.1程序语言的定义2.2高级语言的一般特性2.3程序语言的语法描述,2.1程序语言的定义-关于语言的一些概念,语言语法语义+语用。,一、字母表和符号串字母表：符号的非空有限集例：=a，b，c符号：字母表中的元素例：a，b，c符号串：符号的有穷序列例：a,aa,ac,abc，.空符号串：无任何符号的符号串()符号串集合：由符号串构成的集合。,二、单词符号和词法规则单词符号：语言中具有独立意义的最基本结构。词法规则：单词符号的形成规则。,2.1.1语法：一个程序设计语言是一个符号系统。,语言的词法规则和语法规则定义了程序的结构形式,是判断输入字符串是否构成一个形式上正确程序的依据。,三、语法单位和语法规则语法单位：由单词符号形成的具有更大的独立语法意义结构。如表达式:0.5*X1+C,一般的程序语言的语法单位有表达式、语句、分程序、函数、过程和程序等。语法规则：语法单位的形成规则。,2.1.2语义,一、语义问题语义定义一个语言单词符号和语法单位的意义。离开语义,语言只不过是一堆符号的集合。对于编译来说,只有了解程序的语义，我们才能知道把它翻译成什么样的目标指令代码。,二、语义规则和程序语义规则：程序语言的语义是指这样一组规则，使用它可以定义一个程序的意义，这些规则称为语义规则。程序：从本质(语义)上说,一个程序是描述一定数据的处理过程。(从语法上看)程序设计语言中的程序和其他语法单位形成一定层次结构。程序的语法/语义问题：层次结构中有哪些语法单位，其语义如何？-2.2节如何描述这些语法单位？-2.3节。,2.2高级语言的一般特性,2.1.1高级语言的分类：,一、强制式语言过程式语言。特点是命令驱动，面向语句。如C、PASCAL等。二、应用式语言函数式语言。特点是注重程序功能,从已有函数出发构造新的函数，构造新函数的过程中对初始数据进行计算得到最终结果。如LISP等。三、基于规则的语言逻辑程序设计语言。特点是规则驱动,从事实出发,运用逻辑规则,推导出问题的结果。程序基本结构包括事实和规则两部份。如PROLOG等四、面向对象语言把数据和对数据的操作封装在一起,构成对象。支持封装性、继承性和多态性。,本课程主要讲解过程式语言程序的编译，因此涉及的语法和语义以过程式语言的为主。构造其他类型语言程序的编译程序与之类似。,2.2.2程序结构,高级语言程序通常由若干子程序段构造，一些语言还引入类、程序包等更高级的结构。一、FORTRAN语言程序由主程序和若干个辅助程序段(子程序、函数段或数据块)构成。二、PASCAL语言允许子程序嵌套。一个PASCAL程序可以看作是操作系统调用的子程序。三、JAVA语言面向对象高级语言，支持面向对象的特性，重要概念为类和继承。程序由类定义和实现构成。一个JAVA程序可看作是一个特定类的实例化。,过程式语言程序的层次结构。P14,2.2.3数据类型和操作,“数据”表示外部事务的属性，是大多数程序数据语言的最基本的概念。程序运行过程就是对计算机存储器中的数据加工的过程，而变量是数据存储地址的抽象。数据的含义包括数据的值和数据的类型。数据类型的三要素：（1）用于区别这种类型的数据对象的属性。（一个实数由三部份组成）（2）这种类型的数据对象可以具有的值。(取值范围、精度）（3）可以作用于这种类型的数据对象的操作。（+、-、*、/）,一、初等数据类型：数值数据：整数、实数等。可对其施行算术运算（+、-、*、/等）逻辑数据：布尔型数据。可对其施行逻辑运算(and,or,not等）字符数据：字符型或字符串型数据。用于符号处理。指针类型：指针类型的数据对象的值指向另一些数据。,名字和标识符名字：用来表示数据对象、函数和过程。具有一定的内涵，如代表数据时，其涵义涉及该数据的值、类型等。又可看成是一个抽象的存储单元的代表，如变量(intcount)。标识符：字母和数字组成,以字母开头的字符串,用来表示名字。名字的属性包括类型和作用域，类型决定名字具有什么样的值，值在计算机内的表示方式，以及可以对它施加的运算。作用域规定名字的值的存在范围。“静态”名字：通过说明语句或隐性规则约定名字的类型。可在编译时对其合法性进行检查。(无需在运行时检查或转换)“动态”名字：名字的类型只有在程序运行时才能确定。需在程序运行时收集、确定其性质，并进行必要的类型转换。,二、数据结构相互之间存在一种或多种特定关系的数据元素的集合。由初等数据定义复杂数据结构的常见方式有：1.数组：一个数组是由同一类型数据组成的n维矩形结构。沿着每一维的距离称为一个下标，数组的每个元素位置可通过每一维的下标来确定，每个数组元素占用同样大小的存储空间，同时数组元素由数组名连同下标值来命名，如A1,2,3,.,x。确定数组：编译时已确定数组占用空间大小。可变数组：可在运行时动态改变数组占用空间的大小。数组的存储和数组元素的地址计算：按行或按列存储。编译程序要（1）在见到数组说明时，记录数组的有关信息。（2）在见到数组元素名时，正确计算数组元素的地址。,2.记录：由已知类型的数据组合起来的一种结构。域：记录通常包括若干个分量，记录的一个分量称为记录的一个域。不同域的数据类型可以不同，一个域占用的存储单元数叫域的长度。如：card:recordname:array1.20ofchar;长度为20age:integer;长度为4married:boolean;长度为1end;记录的存储和各个域的地址的计算：连续存放。如:card首地址为a。则card.name的地址为a。则card.age的地址为a+20。则card.married的地址为a+24。,思考：比较c语言中的struct和union。,3.字符串、表格、栈、队列一些语言支持以上某些数据类型是为了方便对特殊应用的数据的处理。体现了该语言的特点。,二、抽象数据类型为了增加程序的可读性和可理解性，提高可维护性、降低软件设计的复杂性。抽象数据类型包括：一个数据对象的集合。作用于这些数据对象的抽象运算的集合。这种类型对象的封装，即用户只能使用类型中定义的运算对对象进行操作。C+和java通过类class对抽象数据类型进行支持。,2.2.4语句与控制结构,一般程序设计语言提供：（1）数据的表示、构造及运算设施（2）可执行语句控制结构定义可执行语句的执行次序，对程序编写非常重要。,一、表达式：由操作数和算符组成，是可执行语句的重要组成部分。两个概念：二元（二目）算符：X+Y中的+号。相关概念：一元算符(-X)、左右操作数X、Y表达式的前、中、后缀形式：+XY、X+Y、XY+多数程序语言来说，表达式的形成规则可概括为：(1)变量（包括下标变量）、常数是表达式；(2)若E1、E2是表达式，是二元算符，则E1E2是表达式；(3)若E是表达式，是一元算符，则E或E是表达式；,表达式表达式的运算顺序和结合性：(1)表达式的计值过程遵循高级的算符先运算规则，算符的优先顺序：乘幂一元负等值(2)同级算符，根据算符结合性不同来计算表达式的值。(2.1)左结合:先左后右(2.2)右结合:先右后左例：X*Y-Z(1)X-Y+Z(2.1)X*Y*Z(2.2),一、语句：功能上分为说明性语句和执行语句两大类。说明语句定义各种不同数据类型的变量或运算(过程)。执行语句描述程序动作。赋值句：A:=B把B的值送入A所代表的单元概念：A的左值：名字A代表的存储单元地址B的右值：名字B的值区分表示一个名字的两种特性。控制语句：控制程序的执行顺序。无条件转移：条件语句：循环语句：过程调用语句：返回语句：说明句：定义名字的性质：包括变量和过程说明等。,语句按其语法的结构特点分，可分为：简单句和复合句简单句：不包含其他语句成分的基本句。如赋值、GOTO语句。复合句：句中有句。如条件、循环语句。,概念：字母表和符号串字母表：符号的非空有限集例：=a，b，c符号：字母表中的元素例：a，b，c符号串：符号的有穷序列例：a,aa,ac,abc，.空字/空符号串：无任何符号的符号串符号串的连接：例：abcd=abcd符号串集合*：由符号串(包括)构成的集合。空集：,预备知识：几个概念,1.除了一般集合运算外，还可定义符号串集合的乘积(连接)运算：令U、V为符号串集合，定义UV|U,V,ac，ad，bc，bd因为xxx，所以U=U=U,例：Ua,b,V=c,d,UV=？,2.3程序语言的语法描述,3.符号串集合的闭包运算：设V是符号串集合，定义V*V0V1V2V3Vn称为集合V的闭包。VVV*称为集合V的正则闭包。,例：V=x,yV？V*？,2.符号串集合的幂运算：有符号串集合V，定义V0=,V1=V,V2=VV,V3=VVV,VnVn-1V=VVn-1，n0,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,V1V2V3,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,V0V1V2V3,2.3.1上下文无关文法,什么是文法：文法是对语言结构的定义与描述，用形式的方法描述和规定语言的语法规则（通过定义语法单位的结构）。什么是上下文无关文法：是这样一种文法，它所定义的语法范畴(单位、概念)是完全独立于这种范畴的环境的。以后，简称“上下文无关文法”为“文法”。,(一)例：分析英文例句Hegavemeabook,(1)定义语法规则:表示“由什么组成”或“定义为”Hemeagavebook,规则定义语言可这样理解：表示符号串的集合句子，则句子=主语谓语间接宾语直接宾语,续例：(2)运用(1)规则推导出句子:=He=He=Hegave=Hegave=Hegaveme=Hegaveme=Hegavemea=Hegavemeabook,从出发，反复把上述规则中的左部替换成右边的成分。,续例：(2)用图形表示(2)的推导过程:语法分析树,单词符号（在形式语言中又称“终结符号”),语法变量（在形式语言中又称“非终结符”）,二、上下文无关文法，推导及语言的形式定义上下文无关文法由一组终结符号,一组非终结符号,一个开始符号,以及一组产生式组成。记作G=（Vn，Vt，P，S）Vn：非终结符号集Vt：终结符号集P：产生式或规则的集合S：开始符号SVn终结符：组成语言的基本符号，程序语言中即单词符号。如上例中的“He”。程序语言中的“基本字”。非终结符：代表语法范畴(概念)。代表一个类记号，表示一定符号串的集合。如上例中的“主语”，程序语言中的“过程”。开始符号：是一个特殊的非终结符，代表语言中最终的(我们最感兴趣的)语法范畴。如上例中的“句子”，程序语言中的“程序”。注：本书约定：A,B,代表非终结符号。a,b,c代表终结符号。,代表终结符号和/或非终结符组成的符号串。,产生式：是定义语法规则的一种书写规则，形式是：A有时读作“A是关于A的一条产生规则”。A:非终结符,称为产生式的左部。:非终结符或/与终结符组成的符号串,称为产生式的右部。*注：若干个左部相同的产生式,可合并成一个,中间用|分开,读作“或”。如P1|2|n每个i称为P的一个候选式。和|是元语言符号。例：多个产生式定义一个语法范畴算术表达式：Ei一个变量i是一个算术表达式EE+E一个算术表达式“+”一个算术表达式是一个算术表达式EE*E一个算术表达式“*”一个算术表达式是一个算术表达式E(E)“(”一个算术表达式“)”是一个算术表达式递归产生式：产生式右部有与左部相同的符号。,推导:上下文无关文法如何定义一个语言？中心思想：从文法的开始符号出发，反复连续使用产生式，对非终结符号施行替换和展开，直至符号串中不含非终结符号为一个句子。句子的集合=语言。常用符号和术语：符号=:表示推导一步，直接推出。直接推导:A=当且仅当A是一个产生式。如1=2=n,称该序列是从1到n的一个推导,1可推导出n。1=n表示从1出发经一或若干步可推导n,1=n表示从1出发经0或若干步可推导n。若G是一个文法，S是G的开始符号。如S=,则称是G的一个句型。仅含终结符的句型是一个句子。G产生的句子全体是一个语言,记做L(G),L(G)=|S=,VT*。,+,*,*,一个文法如何定义一个语言？,最左推导:任意一步=都是对中的最左非终结符进行替换。E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i)最右推导:任意一步=都是对中的最左非终结符进行替换。E=(E)=(E+E)=(E+i)=(E*E+i)=(i*E+i)=(i*i+i)文法例:(1)文法G1:SbAAaA|a定义了一个什么样的语言？S=bA=baS=bA=bAa=baaS=bA=baa归纳得出L(G1)=ban|n1(3)构造一个文法G3使得L(G3)=anbn|n1a,b个数相同：SaSb|ab,2.3.2语法分析树和二义性,语法分析树（简称语法树）：如果用一张图表示一个句型的推导，可以帮助我们理解一个句子语法结构的层次，这张图看起来就是一棵倒立的树，我们把它称为。,例：E=(E)=(E+E)=(E+i)=(E*E+i)=(i*E+i)=(i*i+i),语法树不反映句型中的非终结符被替代的顺序，对一句型的最左和最右推导过程可得出同一棵语法树。,例：E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i),二义文法：如果对于一个文法，存在某个句子对应两棵不同的语法树，我们把它称为。如文法2.1,例：E=(E)=(E*E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i),对比上例可知：对由文法2.1产生的句子(i*i+i)我们有不同的最左推导和语法树。（二义文法）,关于二义文法的几个问题：文法二义性影响语言的翻译。文法二义性和语言的二义性是两个不同概念。二义性问题是不可判定的。可通过改写文法消除某些二义文法的二义性。可通过规定优先顺序和结合规则等方式有效利用某些二义文法。,改写文法2.1:EE+E|E*E|(E)|i无二义文法2.6：ET|E+TEF|T*FF(E)|I练习：从文法2.6推导出句子(i*i+i)，并用语法分析树表示该推导,表达式项|表达式+项项因子|项*因子因子(表达式)|i,关于描述程序设计语言的上下文无关文法的几点限制：不含以下形式的产生式：PP每个非终结符P都有用处。即存在推导：S=P以及P=，VT*,+,*,练习：根据以下mini语言的语法说明(部分)写出其文法Mini语言的程序由语句块构成；语句块由一到多条语句构成，语句用分号分隔；语句分为赋值语句、条件语句和循环语句；赋值语句左部为变量(用var表示)，右部为算术表达式，中间用等号连接；算术表达式为整数常量(用int表示)或变量，或由算术表达式通过加、减运算符连接而成；条件语句由if关键字后跟左括号、条件表达式、右括号、then关键字、语句块、end关键字构成；循环语句由while关键字后跟左括号、条件表达式、右括号、语句块、end关键字构成；,2.3.3形式语言鸟瞰,形式化方式定义语言。,1、文法分类：0型文法：短语文法（0型语言递归可枚举语言）产生式形式:,(VNVT)*且至少含一个非终结符,(VNVT)*1型文法：上下文有关文法产生式形式：,(VNVT)*且至少含一个非终结符,(VNVT)*,S不能出现在产生式的右部,除S外，其他,|例：A2型文法：上下文无关文法（足以定义大多数程序设计语言)产生式形式：A,AVN,(VNVT)*。3型文法：正规文法右线性文法：AB,或A,A、BVN,VT*左线性文法：AB,或A,A、BVN,VT*,2、文法和计算模型：文法所描述的语言可以用与之能力相当的“计算机”所识别。反之，“计算机”所能计算出来的问题或者说，所识别的语言可以用与之能力相当的文法所描述。文法类型计算模型0型文法图灵机（RAM机）1型文法线性界限机2型文法下推自动机3型文法有限状态机,
展开阅读全文