编译2高级语言及其语法描述(zss).ppt

资源描述

《编译2高级语言及其语法描述(zss).ppt》由会员分享，可在线阅读，更多相关《编译2高级语言及其语法描述(zss).ppt（75页珍藏版）》请在三一办公上搜索。

1、编译原理(第三版)陈火旺等编著,（2012年9月-12月）主讲：朱世松计算机学院,2,2023/10/8,第二章高级语言及其语法描述,常用的高级语言 FORTRAN数值计算 COBOL事务处理 PASCAL结构程序设计 ADA大型程序、嵌入式实时系统 PROLOG逻辑程序设计 ALGOL算法语言 C/C+系统程序设计 JavaInternet程序设计,3,2023/10/8,与机器语言或汇编语言比较，高级语言的优点：较接近于数学语言和工程语言，比较直观、自然和易于理解;便于验证其正确性，易于改错;编写效率高;易于移植.,4,2023/10/8,2.1 程序语言的定义,程序语言由两方面定义：语

2、法语义(语用-语言成分的使用方法),5,2023/10/8,一.语法,程序本质上是一定字符集上的字符串。语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序。,6,2023/10/8,词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：有限自动机语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;描述工具：上下文无关文法,7,2023/10/8,EiEE+EEE*EE(E)语法规则和词法规则定义了程序的的形式结构。定义语法单位的意义属于语义问题。,8,2023

3、/10/8,二.语义,语义：一组规则，用它可以定义一个程序的意义。描述方法：自然语言描述：隐藏错误、二义性和不完整性形式描述：操作语义(PL/1)指称语义(ADA)代数语义(PASCAL),9,2023/10/8,三程序语言的基本功能和层次结构,程序语言的基本功能：描述数据和对数据的运算。所谓程序，本质上说是描述一定数据的处理过程。,10,2023/10/8,程序的层次结构：,程序|子程序或分程序、过程、函数|语句|表达式|数据引用算符函数调用,11,2023/10/8,程序语言每个组成成分的逻辑和实现意义,抽象的逻辑的意义数学意义计算机实现的意义具体实现,12,2023/10/8,2.

4、2 高级语言的一般特性,2.2.1 高级语言的分类强制式语言(Imperative Languge)也称过程式语言：命令驱动，面向语句FORTRAN、C、Pascal，Ada 应用式语言（Applicative Language）：注重程序所表示的功能，而不是一个语句接一个语句地执行LISP、ML,13,2023/10/8,基于规则的语言（Rule-based Language）：检查一定的条件，当它满足值，则执行适当的动作Prolog 面向对象语言（Object-Oriented Language）：封装性、继承性和多态性Smalltalk，C+，Java,14,2023/10/8,2.2

5、.2 程序结构 FORTRAN一个程序由一个主程序段和若干辅程序段组成。辅程序段可以是子程序、函数段或数据块。每个程序段有一系列的说明语句和执行语句组成。各段可以独立编译。模块结构，没有嵌套和递归各程序段中的名字相互独立，同一个标识符在不同的程序段中代表不同的名字。,15,2023/10/8,主程序 PROGRAM end辅程序1 SUBROUTINE end辅程序2 FUNCTION end,16,2023/10/8,PASCALPASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。一个PASCAL过程：过程头；说明段（由一系列的说明语句组成）；begin执行体（由一系

6、列的执行语句组成）；end,17,2023/10/8,作用域：一个名字能被使用的区域范围称作这个名字的作用域。允许同一个标识符在不同的过程中代表不同的名字。名字作用域规则-最近嵌套原则一个在子程序B1中说明的名字X只在B1中有效（局部于B1）；如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X。,18,2023/10/8,program main var A,B:real;procedure P1 var B:boolean;begin end procedure P2 var

7、 A:integer;begin endbegin end,A(real),B(real),B(bool),A(integer),19,2023/10/8,PASCAL提供了丰富的数据类型和运算方式，它允许用户动态地申请和退还存贮空间。,20,2023/10/8,ADA程序包(package)：把数据和操作代码封装在一起，支持数据抽象。一个程序包分为两部分：可见的规范说明部分，它定义了程序包外面可以访问的对象。程序包体，它实际定义程序包的实现细节。,21,2023/10/8,package STACKS is type ELEM is private;type STACK is limited

8、 private;procedure push(S:in out STACK;E:in ELEM);procedure pop(S:in out STACK;E:out ELEM);end STACK;package body STACKS is procedure push(S:in out STACK;E:in ELEM);begin 实现细节 end push;procedure pop(S:in out STACK;E:out ELEM);begin 实现细节 end pop;end;,22,2023/10/8,JAVAJava是一种面向对象的高级语言类（Class）继承(Inheri

9、tance)多态性(Polymorphism)和动态绑定(Dynamic binding),23,2023/10/8,class Car int color_number;int door_number;int speed;push_break()add_oil()class Trash_Car extends car double amount;fill_trash(),24,2023/10/8,2.2.3 数据类型与操作,一个数据类型通常包括以下三种要素：用于区别这种类型数据对象的属性这种类型的数据对象可以具有的值可以作用于这种类型的数据对象的操作,25,2023/10/8,2.2.3 数

10、据类型与操作,一初等数据类型数值类型：整型、实型、复数、双精度，运算：+，-，*，/等逻辑类型：布尔运算：，字符类型：符号处理指针类型,26,2023/10/8,标识符与名字,标识符：以字母开头的，由字母数字组成的字符串。标识符与名字两者有本质区别：标识符是语法概念名字有确切的意义和属性,27,2023/10/8,标识符与名字,名字：值：单元中的内容属性：类型和作用域名字的性质的说明方式：由说明语句来明确规定的隐含说明：FORTRAN 以I,J,K,N为首的名字代表整型，否则为实型。动态确定：“走到哪里，是什么，算什么”（运行时才能确定）,28,2023/10/8,二数据结构,1 数组逻辑上

11、，数组是由同一类型数据所组成的某种n维矩形结构，沿着每一维的距离，称为下标。数组可变与不可变：编译时能否确定其存贮空间的大小。访问：给出数组名和下标值存放方式:按行存放,按列存放,29,2023/10/8,数组元素地址计算,数组A10,20的A1，1为a，各维下标为1，按行存放，那么Ai，j地址为：a+(i-1)*20+(j-1),30,2023/10/8,内情向量,把数组的有关信息记录在一个“内情向量”中，每个数组的内情向量必须包括：维数，各维的上、下限，首地址，以及数组（元素）的类型。,31,2023/10/8,2 记录,逻辑上说，记录结构由已知类型的数据组合在一起的一种结构。record

12、 char NAME20;integer AGE;bool MARRIED;CARD1000访问：复合名 CARDk.NAME存储：连续存放域的地址计算：相对于记录结构起点的相对数OFFSET。,32,2023/10/8,3 字符串、表格、栈,字符串：符号处理、公式处理表格：本质上是一种记录结构线性表：一组顺序化的记录结构栈：一种线性表，后进先出，POP,PUSH,33,2023/10/8,三抽象数据类型,一个抽象数据类型包括：数据对象的一个集合；作用于这些数据对象的抽象运算的集合；这种类型对象的封装，即，除了使用类型中所定义的运算外，用户不能对这些对象进行操作。程序设计语言对抽象数据类型的

13、支持Ada语言通过程序包（package）提供了数据封装的支持Smalltalk、C+和Java语言则通过类（Class）对抽象数据类型提供支持。,34,2023/10/8,2.2.4 语句与控制结构,一表达式表达式由运算量（也称操作数，即数据引用或函数调用）和算符（操作符）组成。形式：中缀、前缀、后缀 X*Y-A P,35,2023/10/8,表达式形成规则（p23）（1）变量（包括下标变量）、常数是表达式；（2）若E1、E2为表达式，为二元算符，则 E1 E2 为表达式；（3）若E为表达式，为一元算符，则E为表达式；（4）若E为表达式，则（E)是表达式。,36,2023/10/8,算符的优

14、先次序,一般的规定PASCAL：左结合A+B+C=(A+B)+CFORTRAN：对于满足左、右结合的算符可任取一种，如A+B+C就可以处理成(A+B)+C，也可以处理成A+(B+C)。注意两点：代数性质能引用到什么程度视具体的语言不同而不同；在数学上成立的代数性质在计算机上未必完全成立。,37,2023/10/8,二语句,赋值语句：A:=B 名字特征：(了解)左值：该名字代表的那个单元（地址）称为该名字的左值。(所代表的存贮单元的地址)右值：一个名字的值称为该名字的右值。(所代表的存贮单元的内容),38,2023/10/8,控制语句：,无条件转移语句 goto L,条件语句 if B then

15、 S if B then S1 else S2,循环语句 while B do S repeat S until B for i:=E1 step E2 until E3 do S,过程调用语句 call P(X1,X2,.,Xn),返回语句 return(E),39,2023/10/8,说明语句：定义各种不同数据类型的变量或运算，定义名字的性质。,40,2023/10/8,简单句和复合句,简单句：不包含其他语句成分的基本句复合句：句中有句的语句,41,2023/10/8,复习：程序语言的定义,程序语言由两方面定义：语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序词法

16、规则：单词符号的形成规则。常数、标识符、基本字、算符、界符等。有限自动机语法规则：语法单位的形成规则。表达式、语句、分程序、过程、函数、程序等;上下文无关文法语义:一组规则，用它可以定义一个程序的意义,42,2023/10/8,复习：程序语言的基本功能和层次结构,程序语言的基本功能：描述数据和对数据的运算。所谓程序，本质上说是描述一定数据的处理过程。,程序|子程序或分程序、过程、函数|语句|表达式|数据引用算符函数调用,43,2023/10/8,复习：高级语言的一般特性,高级语言的分类程序结构数据类型与操作初等数据类型数据结构抽象数据类型语句与控制结构,44,2023/10/8,2.3

17、程序语言的语法描述,几个概念:考虑一个有穷字母表字符集其中每一个元素称为一个字符上的字(也叫字符串)是指由中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为用*表示上的所有字的全体,包含空字例如:设=a，b，则*=,a,b,aa,ab,ba,bb,aaa,.,45,2023/10/8,*的子集U和V的连接（积）定义为UV|U&V 设：U a,aa V b,bb 那么：UV=ab,abb,aab,aabb VU=？,46,2023/10/8,*的子集U和V的连接（积）定义为UV|U 记 VVV*，称V+是V的正规闭包。,47,2023/10/8,设：U a,aa 那么：U*=,a

18、,aa,aaa,aaaa,U=a,aa,aaa,aaaa,注意：空集、|,48,2023/10/8,2.3.1 上下文无关文法,文法：描述语言的语法结构的形式规则He gave me a book.He me book a gave,49,2023/10/8,He me book a gave,He He He gave He gave He gave me He gave me He gave me a He gave me a book,50,2023/10/8,上下文无关文法的定义：一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集

19、合(非空)，且VT VN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VT VN)*开始符S至少必须在某个产生式的左部出现一次。,组成语言的不可再分基本符号,能派生出符号或符号串的那些符号,51,2023/10/8,例，定义只含+，*的算术表达式的文法 G=，其中，P由下列产生式组成：E iE E+EE E*EE(E),52,2023/10/8,几点规定：“”也可以用“:=表示，这种表示称为巴科斯范式(BNF)P 1 P 2 可缩写为 P 1|2|n P n 其中，“|”读成“或”，称为P的一个候选式。表示一个文法时，通常只给出开始符号和产生式，如上例，可表

20、示为：G(E)：E i|E+E|E*E|(E),53,2023/10/8,几点规定：“”也可以用“:=表示，这种表示称为巴科斯范式(BNF)P 1 P 2 可缩写为 P 1|2|n P n 其中，“|”读成“或”，称为P的一个候选式。表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为：G(E)：E i|E+E|E*E|(E),例，定义只含+，*的算术表达式的文法 G=，其中，P由下列产生式组成：E iE E+EE E*EE(E),54,2023/10/8,定义：称A直接推出，即A 仅当A 是一个产生式，且，(VT VN)*。如果1 2 n，则我们称这个序列是从1到n的一个推导。若存在

21、一个从1到n的推导，则称1可以推导出n。对文法G(E)：E i|E+E|E*E|(E)E(E)(E+E)(i+E)(i+i),55,2023/10/8,通常，用表示：从1出发，经过一步或若干步，可以推出n。（推导）,用表示：从1出发，经过0步或若干步，可以推出n。（广义推导）,所以：即或,56,2023/10/8,定义：假定G是一个文法，S 是它的开始符号。如果，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为 L(G)。,57,2023/10/8,例：(i*i+i)是文法 G(E)：E i|E+E|E*E|(E)的一个句子。证明：E(E)(E+

23、2023/10/8,从一个句型到另一个句型的推导往往不唯一。E+Ei+Ei+i E+EE+ii+i最左推导：任何一步都是对中的最左非终结符进行替换。最右推导：任何一步都是对中的最右非终结符进行替换。,63,2023/10/8,2.3.2 语法树与二义性,用一张图表示一个句型的推导,称为语法树。(i*i+i)的语法树,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)(E*i+i)(i*i+i),一棵语法树是不同推导过程的共性抽象。,G(E)：E i|E+E|E*E|(E)(i*i+i),64,2023/10/8,如果使用最

24、左(右)推导，则一个最左(右)推导与语法树一一对应。一个句型是否只对应唯一一棵语法树？,65,2023/10/8,定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。G(E)：E i|E+E|E*E|(E)是二义文法。语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。可能存在G和G，一个为二义的，一个为无二义的。但L(G)=L(G)二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。可以找到一组无二义文法的充分条件。,66,2023/10/8,二义文法：G(E)：E i|E+E|E*E|(E),表达式项|表达式+项

25、项因子|项*因子因子(表达式)|i,无二义文法：G(E)：E T|E+T T F|T*F F(E)|i,67,2023/10/8,E T F(E)(E+T)(T+T)(T*F+T)(F*F+T)(i*F+T)(i*i+T)(i*i+F)(i*i+i),考虑句子(i*i+i),68,2023/10/8,描述程序设计语言时，对于上下文无关文法的限制：1 不含PP形式的产生式2 每个非终结符P必须有用处即：,69,2023/10/8,2.3.3 形式语言鸟瞰,Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。与上下文无关文法一样，它们都由四部分组成，但对产生式的限

26、制有所不同。,70,2023/10/8,0型(短语文法，图灵机)：产生式形如：其中：(VT VN)*且至少含有一个非终结符；(VT VN)*1型(上下文有关文法，线性界限自动机)：产生式形如：其中：|，仅 S 例外。(A),71,2023/10/8,2型(上下文无关文法，非确定下推自动机)：产生式形如：A 其中：A VN；(VT VN)*。3型(正规文法，有限自动机)：产生式形如：A B 或 A 其中：VT*；A，BVN 产生式形如：A B 或 A 其中：VT*；A，BVN,右线性文法,左线性文法,72,2023/10/8,四种类型描述能力比较,0型,1型,2型,3型,73,2023/10/8

27、,L5=anbn|n1 不能由正规文法产生，但可由上下文无关文法产生：G5(S)：S aSb|abL6=anbncn|n1不能由上下文无关文法产生，但可由上下文有关文法产生：G6(S)：S aSBC|aBC CB BC aB ab bB bb bC bc cC cc,74,2023/10/8,程序设计语言不是上下文无关语言，甚至不是上下文有关语言。L7=c|(a|b)*不能由上下文无关文法产生，甚至连上下文有关文法也不能产生，只能由0型文法产生。标识符引用过程调用过程中，形-实参数地对应性(如个数，顺序和类型一致性)现今程序设计语言的语言结构，用上下文无关文法描述就足够了。,75,2023/10/8,作业,P36-6，7，8，9，10，11,

展开阅读全文