《国防科大 编译原理 第二章》由会员分享，可在线阅读，更多相关《国防科大 编译原理 第二章（33页珍藏版）》请在金锄头文库上搜索。
1、第二章:高级语言机器语法描述,2.1 程序语言的定义2.2 高级语言的一般特性2.3 程序语言的语法描述,2.1 程序语言的定义-关于语言的一些概念,语言语法语义+语用。,一、字母表和符号串字母表：符号的非空有限集 例：=a，b，c符号：字母表中的元素 例： a，b，c符号串：符号的有穷序列 例：a, aa, ac, abc，.空符号串：无任何符号的符号串()符号串集合：由符号串构成的集合。,二、单词符号和词法规则单词符号：语言中具有独立意义的最基本结构。词法规则：单词符号的形成规则。,2.1.1 语法：一个程序设计语言是一个符号系统。,语言的词法规则和语法规则定义了程序的结构形式,是判断输入
2、字符串是否构成一个形式上正确程序的依据。,三、语法单位和语法规则语法单位：由单词符号形成的具有更大的独立语法意义结构。如表达式:0.5*X1+C,一般的程序语言的语法单位有表达式、语句、分程序、函数、过程和程序等。语法规则：语法单位的形成规则。,2.1.2 语义,一、语义问题语义定义一个语言单词符号和语法单位的意义。离开语义,语言只不过是一堆符号的集合。对于编译来说,只有了解程序的语义，我们才能知道把它翻译成什么样的目标指令代码。,二、语义规则和程序语义规则：程序语言的语义是指这样一组规则，使用它可以定义一个程序的意义，这些规则称为语义规则。程序：从本质(语义)上说,一个程序是描述一定数据的处
3、理过程。 (从语法上看)程序设计语言中的程序和其他语法单位形成 一定层次结构。程序的语法/语义问题： 层次结构中有哪些语法单位，其语义如何？ -2.2节如何描述这些语法单位？ -2.3节。,2.2 高级语言的一般特性,2.1.1 高级语言的分类：,一、强制式语言过程式语言。特点是命令驱动，面向语句。如C、PASCAL等。二、应用式语言函数式语言。特点是注重程序功能,从已有函数出发构造新的函数，构造新函数的过程中对初始数据进行计算得到最终结果。如LISP等。三、基于规则的语言逻辑程序设计语言。特点是规则驱动,从事实出发,运用逻辑规则,推导出问题的结果。程序基本结构包括事实和规则两部份。如PROL
4、OG等四、面向对象语言把数据和对数据的操作封装在一起,构成对象。支持封装性、继承性和多态性。,本课程主要讲解过程式语言程序的编译，因此涉及的语法和语义以过程式语言的为主。构造其他类型语言程序的编译程序与之类似。,2.2.2 程序结构,高级语言程序通常由若干子程序段构造，一些语言还引入类、程序包等更高级的结构。一、FORTRAN语言程序由主程序和若干个辅助程序段(子程序、函数段或数据块)构成。二、PASCAL语言允许子程序嵌套。一个PASCAL程序可以看作是操作系统调用的子程序。三、JAVA语言面向对象高级语言，支持面向对象的特性，重要概念为类和继承。程序由类定义和实现构成。一个JAVA程序可看
5、作是一个特定类的实例化。,过程式语言程序的层次结构。P14,2.2.3 数据类型和操作,“数据”表示外部事务的属性，是大多数程序数据语言的最基本的概念。程序运行过程就是对计算机存储器中的数据加工的过程，而变量是数据存储地址的抽象。数据的含义包括数据的值和数据的类型。 数据类型的三要素：（1）用于区别这种类型的数据对象的属性。（一个实数由三部份组成）（2）这种类型的数据对象可以具有的值。(取值范围、精度）（3）可以作用于这种类型的数据对象的操作。（+、-、*、/）,一、初等数据类型：数值数据：整数、实数等。可对其施行算术运算（+、-、*、/等）逻辑数据：布尔型数据。可对其施行逻辑运算(and,o
6、r,not等）字符数据：字符型或字符串型数据。用于符号处理。指针类型：指针类型的数据对象的值指向另一些数据。,名字和标识符名字：用来表示数据对象、函数和过程。具有一定的内涵，如代表数据时，其涵义涉及该数据的值、类型等。又可看成是一个抽象的存储单元的代表，如变量(int count)。标识符：字母和数字组成,以字母开头的字符串,用来表示名字。名字的属性包括类型和作用域，类型决定名字具有什么样的值，值在计算机内的表示方式，以及可以对它施加的运算。作用域规定名字的值的存在范围。“静态”名字：通过说明语句或隐性规则约定名字的类型。 可在编译时对其合法性进行检查。(无需在运行时检查或转换)“动态”名字：
7、名字的类型只有在程序运行时才能确定。需在程序运行时收集、确定其性质，并进行必要的类型转换。,二、数据结构相互之间存在一种或多种特定关系的数据元素的集合。由初等数据定义复杂数据结构的常见方式有：1.数组：一个数组是由同一类型数据组成的n维矩形结构。沿着每一维的距离称为一个下标，数组的每个元素位置可通过每一维的下标来确定，每个数组元素占用同样大小的存储空间，同时数组元素由数组名连同下标值来命名，如A1,2,3,.,x。确定数组：编译时已确定数组占用空间大小。可变数组：可在运行时动态改变数组占用空间的大小。 数组的存储和数组元素的地址计算：按行或按列存储。 编译程序要（1）在见到数组说明时，记录数组
8、的有关信息。 （2）在见到数组元素名时，正确计算数组元素的地址。,2.记录：由已知类型的数据组合起来的一种结构。域：记录通常包括若干个分量，记录的一个分量称为记录的 一个域。不同域的数据类型可以不同，一个域占用的存储 单元数叫域的长度。如：card:record name:array 1.20 of char; 长度为20 age: integer; 长度为4 married:boolean; 长度为1 end;记录的存储和各个域的地址的计算：连续存放。 如:card首地址为a。则card.name的地址为a。 则card.age的地址为 a+20。则card.married的地址为a+24。
9、,思考：比较c语言中的struct和union。,3.字符串、表格、栈、队列 一些语言支持以上某些数据类型是为了方便对特殊应用的数据的处理。体现了该语言的特点。,二、抽象数据类型为了增加程序的可读性和可理解性，提高可维护性、 降低软件设计的复杂性。抽象数据类型包括：一个数据对象的集合。作用于这些数据对象的抽象运算的集合。这种类型对象的封装，即用户只能使用类型中定义的运算对 对象进行操作。C+和java通过类class对抽象数据类型进行支持。,2.2.4 语句与控制结构,一般程序设计语言提供：（1）数据的表示、构造及运算设施（2）可执行语句控制结构定义可执行语句的执行次序，对程序编写非常重要。,
10、一、表达式：由操作数和算符组成，是可执行语句的重要组成部分。两个概念：二元（二目）算符：X+Y中的+号。相关概念：一元算符(-X)、左右操作数X、Y表达式的前、中、后缀形式：+XY、X+Y、XY+多数程序语言来说，表达式的形成规则可概括为：(1)变量（包括下标变量）、常数是表达式；(2)若E1、E2是表达式，是二元算符，则E1 E2是表达式；(3)若E是表达式，是一元算符，则E或E是表达式；,表达式表达式的运算顺序和结合性：(1)表达式的计值过程遵循高级的算符先运算规则，算符的优先顺序： 乘幂 一元负 等值(2)同级算符，根据算符结合性不同来计算表达式的值。 (2.1)左结合:先左后右 (2.
11、2)右结合:先右后左例：X*Y-Z (1) X-Y+Z (2.1) X*Y*Z (2.2),一、语句：功能上分为说明性语句和执行语句两大类。说明语句定义各种不同数据类型的变量或运算(过程)。执行语句描述程序动作。赋值句：A:=B 把B的值送入A所代表的单元 概念：A的左值：名字A代表的存储单元地址 B的右值： 名字B的值 区分表示一个名字的两种特性。控制语句： 控制程序的执行顺序。 无条件转移： 条件语句： 循环语句： 过程调用语句： 返回语句：说明句：定义名字的性质：包括变量和过程说明等。,语句按其语法的结构特点分，可分为：简单句和复合句简单句：不包含其他语句成分的基本句。如赋值、GOTO语
12、句。复合句：句中有句。如条件、循环语句。,概念：字母表和符号串字母表：符号的非空有限集 例：=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.符号串集合的闭包运算：
13、设V是符号串集合，定义 V * V0 V1 V2 V3 Vn 称为集合V的闭包。 V V V * 称为集合V的正则闭包。,例：V=x,y V？ 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, V1 V2 V3, x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, V0 V1 V2 V3,2.3.1 上下文无关文法,什么是文法：文法是对语言结构的定义与描述，用形式的方法描述和规定语言的语法规则（通过定义语法单位的结构）。 什么是上下文无关文法：是这样一种文法，它所定义的语法范畴(单位、概念)是完全独立于这种范畴的环境的。 以后，简称“上下文无关文法”为“文法”。,(一)例：分析英文例句He gave me a book,(1)定义语法规则: 表示“由什么组成”或“定义为” He me a gave book,规则定义语言可这样理解：表示符号串的集合句子，则句子=主语谓语间接宾语直接宾语,
