《编译原理高级语言及其语法描述陈火旺版》由会员分享，可在线阅读，更多相关《编译原理高级语言及其语法描述陈火旺版（32页珍藏版）》请在金锄头文库上搜索。
1、第二章 高级语言及其语法描述2.1 程序语言的定义 2.2 高级语言的一般特性 2.3 程序语言的语法描述 复习题,2.1 程序语言的定义高级程序语言是用来描述算法和计算机实现这双重目的的。 从语言范型来分，高级程序语言可分为 强制式语言（过程式语言）作用式语言（函数式语言）基于规则的语言面向对象语言 任何语言实现的基础是语言的定义一个程序语言是一个记号系统，通常包括语法、语义和语用三个方面,一、语法1. 词法规则：单词符号形成规则，规定字母表中哪 样的字符串是一个单词符号（基本字、标识符、常数、算符、界符）。 正规式和有限自动机理论是描述词法结构和进行词法分析的有效工具 2. 语法规则：语法
2、单位形成规则（表达式、语句、分程序、函数、过程、程序）,规定如何从单词符号形成更大的结构。,二、语义语义：单词符号和语法单位的意义。语义规则：使语言的一个合式程序具备含义的一组规则。,三、程序的层次结构 一个程序语言的基本功能是描述数据和对数据的运算。 程序从本质上来说是描述一定数据的处理过程。程序语言的每个组成成分都有（抽象的）逻辑和计算机实现两方面的意义。,2.2 高级语言的一般特性一、 高级语言的分类 强制式语言（过程式语言） 命令驱动，面向语句如Pascal、FORTRAN 应用式语言（函数式语言） 注重程序所表示的功能 如LISP 基于规则的语言 检查一定的条件，满足值则执行 如Pr
3、olog 面向对象语言（封装性、继承性、多态性） 如Java、C+、SmallTalk,二、程序结构 FORTRAN 语言 由一个主程序段和若干个辅程序段组成PROGRAM MAIN ENDSUBROUTINE SUB1ENDSUBROUTINE SUBnEND 辅程序段可以是子程序、函数段或数据块,Pascal语言 Pascal是一个允许子程序嵌套定义的语言 Program main Procedure P1; Procedure P11;beginend; begin end; Procedure P2; beginend;beginend.,C+语言#include void main(
4、)具有面向对象特征如：封装性、继承性、多态性等,Java语言 Java语言是一种面向对象高级语言。class Car int color_number;int door_number;int speed;push_break( )Add_oil( ) class Trash_Car extends cardouble amount;fill_trash( ),三、数据类型与操作 数据类型三要素：用于区别这种类型的数据对象的属性这种类型的数据对象可以具有的值可以作用于这种类型的数据对象的操作 1. 初等数据类型,2. 标识符和名字 标识符 由字母或数字组成的以字母开头的一个字符串，是一个没有意义
5、的字符序列。 名字 有明确的意义和属性的字符串。 值、属性一个名字的属性包括类型和作用域名字的类型决定它能具有什么样的值，值在计算机内的表示 形式，以及对它能施加什么运算。作用域表示值的存在范围。,3. 数据结构 (1) 数组 数组是同一类型数据所组成的某种n维矩形结构。确定数组 一个数组所需存储空间大小在编译时已知可变数组 在编译过程中才知道数组所需存储空间大小数组存储方式 按行存放 Pascal ， C ， C+按列存放 FORTRAN内情向量表 维数、各维的上下限、首地址、数组元素类型、地址不变量等l1 u1 d1l2 u2 d2ln un dnn Ctype a,（2）记录记录结构是由
6、已知类型的数据组合起来的一种结构。一个记录结构通常含有若干个分量，每个分量称为记录的一个栏（域）。每个分量都是一个确定类型的数据，不同分量的数据类型可以不同。存储方式为连续存放。记录结构每个分量（域）所需占用的存储单元（字节）数称为该域的长度。 （3）字符串、表格、栈和队列 4抽象数据类型数据对象的一个集合，作用于这些数据对象的抽象运算的集合，这种类型对象的封装。,四、语句与控制结构 1. 表达式 表达式 由算符连接运算量构成的有意义的式子 表达式形式 前缀 X， B中缀 X+Y后缀 P表达式形成规则 变量（包括下标变量），常数是表达式。 若E1、E2为表达式，是一个二元算符，则E1E2是表达
7、式 若E为表达式，为一元算符，则E（或E）是表达式 若E是表达式，则（E）是表达式。,算符优先顺序 乘幂 *或一元负 乘、除 * / 加、减 + 关系符 非 not NOT与 & and AND或 | or OR 隐含 imp等值 equi 结合顺序 左结合、右结合,2. 语句 从功能分类 执行性语句 赋值语句、控制语句、输入/输出语句 说明性语句从形式分类 简单句、复合句、分程序（1）赋值语句 A:=B 左值 代表一定的存储单元，一个名字所代表的那个单元地址 右值 以该单元的内容作为值，一个名字的值出现在赋值号左边的表达式必须持有左值，出现在赋值号右边的表达式只需持有右值。,（2）控制语句无
8、条件转移语句 goto L条件语句 if B then Sif B then S1 else S2循环语句 while B do Srepeat S until Bfor i:=E1 step E2 until E3 do S过程调用语句 call P(x1,x2, ,xn)返回语句 return (E) （3）说明语句 定义名字的性质（4）简单句和复合句 作业： P35 3，4,2.3 程序语言的语法描述,二、上下文无关文法 1.文法 描述语言语法结构的形式规则（语法规则）2.文法的基本组成 终结符号：组成语言的基本符号（基本字、标识符、常数、算符、界符），用小写字母a,b,c 非终结符号（
9、语法变量）：代表语法范畴，表示一定符号串的集合，用大写字母A，B，C 开始符号：一种特殊的非终结符号 产生式（产生规则、规则）：形如A ，A是一个非终结符， 是由终结符或非终结符号组成的一个符号串,3.引例He gave me a book. he me a gave book,三、语法分析树与二义性1语法分析树（语法树）表示某一句型推导过程的树，称为语法树。一棵语法树表示了一个句型种种可能的不同推导过程。一个句型并不一定只有唯一的一个最左（右）推导。2文法二义性、句子二义性、语言二义性文法二义性：如果一个文法存在某个句子对应两棵不同的语法树，称这个文法是二义的。即若一个文法中存在某个句子，有
10、两个不同的最左（右）推导，称该文法是二义的。句子二义性：若一个句子有两个不同的规范推导，则称该句子是二义的。语言二义性：存在二义性文法的语言。二义性问题是不可判定的。即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否为二义的。,3作为描述程序语言的上下文无关文法的几点限制 （1）不含形如PP的产生式。 （2）每个非终结符P必须有用。 四、形式语言分类 Chomsky 1956年建立形式语言描述 文法分四种类型：0型 短语文法/普通文法1型 上下文有关文法2型 上下文无关文法3型 线性文法/正规文法,第二章 复习题 名词解释词法规则、语法规则、语义规则、文法、短语文法、上下文无关文法、上下文有关文法、正规文法、直接推导、推导、句型、句子、语言、最左推导、最右推导（规范推导）、二义性 什么是表达式？简述表达式形成规则。 数组存储方式？内情向量表表项有哪些？,
