编译原理第二章：高级语言及其语法描述

第二章高级语言及其语法描述2.1程序语言的定义2.2高级语言的一般特性

2.3程序语言的语法描述

复习题2.1程序语言的定义高级程序语言是用来描述算法和计算机实现这双重目的的。从语言范型来分，高级程序语言可分为强制式语言（过程式语言）作用式语言（函数式语言）基于规则的语言面向对象语言任何语言实现的基础是语言的定义一个程序语言是一个记号系统，通常包括语法、语义和语用三个方面

一、语法

1.

词法规则：单词符号形成规则，规定字母表中哪样的字符串是一个单词符号（基本字、标识符、常数、算符、界符）。正规式和有限自动机理论是描述词法结构和进行词法分析的有效工具2.语法规则：语法单位形成规则（表达式、语句、分程序、函数、过程、程序）,规定如何从单词符号形成更大的结构。二、语义

语义：单词符号和语法单位的意义。

语义规则：使语言的一个合式程序具备含义的一组规则。三、程序的层次结构一个程序语言的基本功能是描述数据和对数据的运算。程序从本质上来说是描述一定数据的处理过程。程序语言的每个组成成分都有（抽象的）逻辑和计算机实现两方面的意义。2.2高级语言的一般特性一、 高级语言的分类强制式语言（过程式语言）

命令驱动，面向语句如Pascal、FORTRAN应用式语言（函数式语言）

注重程序所表示的功能如LISP

基于规则的语言检查一定的条件，满足值则执行如Prolog面向对象语言（封装性、继承性、多态性）

如Java、C++、SmallTalk二、程序结构FORTRAN语言由一个主程序段和若干个辅程序段组成

PROGRAMMAIN…ENDSUBROUTINESUB1…END…SUBROUTINESUBn…END

辅程序段可以是子程序、函数段或数据块２．Pascal语言Pascal是一个允许子程序嵌套定义的语言Programmain……ProcedureP1;……ProcedureP11;……begin……end;begin……end;ProcedureP2;……begin……end;begin……end.３．C++语言

#include<iostream.h>……voidmain(){……}

具有面向对象特征如：封装性、继承性、多态性等４．Java语言Java语言是一种面向对象高级语言。

classCar{int

color_number;

int

door_number;

intspeed;……

push_break(){……}

Add_oil(){……}}classTrash_Carextendscar{doubleamount;

fill_trash(){……}}三、数据类型与操作数据类型三要素：

用于区别这种类型的数据对象的属性这种类型的数据对象可以具有的值可以作用于这种类型的数据对象的操作1.初等数据类型2.标识符和名字标识符由字母或数字组成的以字母开头的一个字符串，是一个没有意义的字符序列。名字有明确的意义和属性的字符串。值、属性一个名字的属性包括类型和作用域名字的类型决定它能具有什么样的值，值在计算机内的表示形式，以及对它能施加什么运算。作用域表示值的存在范围。3.数据结构(1)数组数组是同一类型数据所组成的某种n维矩形结构。确定数组一个数组所需存储空间大小在编译时已知可变数组在编译过程中才知道数组所需存储空间大小数组存储方式按行存放Pascal，C，C++

按列存放FORTRAN

内情向量表维数、各维的上下限、首地址、数组元素类型、地址不变量等

l1u1d1l2u2d2……

lnun

dnnCtypea（2）记录

记录结构是由已知类型的数据组合起来的一种结构。一个记录结构通常含有若干个分量，每个分量称为记录的一个栏（域）。每个分量都是一个确定类型的数据，不同分量的数据类型可以不同。存储方式为连续存放。记录结构每个分量（域）所需占用的存储单元（字节）数称为该域的长度。（3）字符串、表格、栈和队列4．抽象数据类型数据对象的一个集合，作用于这些数据对象的抽象运算的集合，这种类型对象的封装。四、语句与控制结构1.表达式表达式由算符连接运算量构成的有意义的式子表达式形式前缀－X，B

中缀X+Y

后缀P↑

表达式形成规则变量（包括下标变量），常数是表达式。若E1、E2为表达式，θ是一个二元算符，则E1θE2是表达式若E为表达式，θ为一元算符，则θE（或Eθ）是表达式若E是表达式，则（E）是表达式。算符优先顺序乘幂**或↑一元负—

乘、除*/÷

加、减+—

关系符<≤＞≥＝≠

非not·NOT·

与∧&and·AND·

或∨|or·OR·

隐含imp

等值≡~equi结合顺序左结合、右结合2.语句从功能分类执行性语句赋值语句、控制语句、输入/输出语句说明性语句

从形式分类简单句、复合句、分程序（1）赋值语句

A:=B左值代表一定的存储单元，一个名字所代表的那个单元地址右值以该单元的内容作为值，一个名字的值出现在赋值号左边的表达式必须持有左值，出现在赋值号右边的表达式只需持有右值。（2）控制语句无条件转移语句gotoL

条件语句ifBthenSifBthenS1elseS2

循环语句whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS

过程调用语句callP(x1,x2,…,xn)

返回语句return(E)（3）说明语句定义名字的性质（4）简单句和复合句作业：P353，42.3程序语言的语法描述二、上下文无关文法1.文法

描述语言语法结构的形式规则（语法规则）

2.文法的基本组成终结符号：组成语言的基本符号（基本字、标识符、常数、算符、界符），用小写字母a,b,c非终结符号（语法变量）：代表语法范畴，表示一定符号串的集合，用大写字母A，B，C开始符号：一种特殊的非终结符号产生式（产生规则、规则）：形如A→

，A是一个非终结符，是由终结符或非终结符号组成的一个符号串3.引例

Hegavemeabook.<句子>→<主语><谓语><间接宾语><直接宾语><主语>→<代词><谓语>→<动词><间接宾语>→<代词><直接宾语>→<冠词><名词><代词>→he<代词>→me<冠词>→a<动词>→gave<名词>→book三、语法分析树与二义性1．语法分析树（语法树）表示某一句型推导过程的树，称为语法树。一棵语法树表示了一个句型种种可能的不同推导过程。一个句型并不一定只有唯一的一个最左（右）推导。2．文法二义性、句子二义性、语言二义性

文法二义性：如果一个文法存在某个句子对应两棵不同的语法树，称这个文法是二义的。即若一个文法中存在某个句子，有两个不同的最左（右）推导，称该文法是二义的。

句子二义性：若一个句子有两个不同的规范推导，则称该句子是二义的。

语言二义性：存在二义性文法的语言。

二义性问题是不可判定的。即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否为二义的。3．作为描述程序语言的上下文无关文法的几点限制（1）不含形如P→P的产生式。（2）每个非终结符P必须有用。四、形式