《高级语言和语法描述》由会员分享，可在线阅读，更多相关《高级语言和语法描述（48页珍藏版）》请在金锄头文库上搜索。
1、国防科技大学计算机系602教研室第二章高级语言及其语法描述n程序语言的定义n高级语言的一般特性国防科技大学计算机系602教研室2.1程序语言的定义n程序语言由两方面定义：语法语义国防科技大学计算机系602教研室一.语法n程序本质上是一定字符集上的字符串。n语法：一组规则，用它可以形成和产生一个合式(well-ed)的程序。国防科技大学计算机系602教研室语法n词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：有限自动机n语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、过程、函数、程序等描述工具：
2、上下文无关文法国防科技大学计算机系602教研室二.语义n语义：一组规则，用它可以定义一个程序的意义。n描述方法：自然语言描述：隐藏错误、二义性和不完整性形式描述：F操作语义(PL1)F指称语义(ADA)F代数语义(PASCAL)国防科技大学计算机系602教研室三程序语言的基本功能和层次结构n程序语言的基本功能：描述数据和对数据的运算。n所谓程序，本质上说是描述一定数据的处理过程。国防科技大学计算机系602教研室程序的层次结构程序|子程序或分程序、过程、函数|语句|表达式|数据引用算符函数调用国防科技大学计算机系602教研室程序语言每个组成成分的逻辑和实现意义n抽象的逻辑的意义数学意义n计算机实
3、现的意义具体实现国防科技大学计算机系602教研室2.2高级语言的一般特性n高级语言的分类强制式语言(ImperativeLanguge)也称过程式语言：命令驱动，面向语句nFORTRAN、C、Pascal，Ada应用式语言（ApplicativeLanguage）：注重程序所表示的功能，而不是一个语句接一个语句地执行nLISP、ML国防科技大学计算机系602教研室2.2高级语言的一般特性2.2.1高级语言的分类基于规则的语言（Rule-basedLanguage）：检查一定的条件，当它满足值，则执行适当的动作nProlog面向对象语言（Object-OrientedLanguage）：封装性、
4、继承性和多态性nSmalltalk，C+，Java国防科技大学计算机系602教研室2.2高级语言的一般特性2.2.2程序结构nFORTRAN国防科技大学计算机系602教研室主程序PROGRAMend辅程序1SUBROUTINEend辅程序2FUNCTIONend国防科技大学计算机系602教研室nPASCALPASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。一个PASCAL过程：过程头；说明段（由一系列的说明语句组成）；begin执行体（由一系列的执行语句组成）；end国防科技大学计算机系602教研室作用域：一个名字能被使用的区域范围称作这个名字的作用域。允许同一个标识
5、符在不同的过程中代表不同的名字。名字作用域规则-最近嵌套原则n一个在子程序B1中说明的名字X只在B1中有效（局部于B1）；n如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X。国防科技大学计算机系602教研室PASCAL提供了丰富的数据类型和运算方式，它允许用户动态地申请和退还存贮空间。国防科技大学计算机系602教研室nADA程序包(package)：把数据和操作代码封装在一起，支持数据抽象。一个程序包分为两部分：n可见的规范说明部分，它定义了程序包外面可以访问的对象。n程序包
6、体，它实际定义程序包的实现细节。国防科技大学计算机系602教研室nJAVAJava是一种面向对象的高级语言n类（Class）n继承(Inheritance)n多态性(Polymorphism)和动态绑定(Dynamicbinding)国防科技大学计算机系602教研室2.2.3数据类型与操作一初等数据类型数值类型：整型、实型、复数、双精度，运算：+，-，等逻辑类型：布尔运算：，字符类型：符号处理指针类型国防科技大学计算机系602教研室标识符与名字n标识符：以字母开头的，由字母数字组成的字符串。n标识符与名字两者有本质区别：标识符是语法概念名字有确切的意义和属性国防科技大学计算机系602教研室标识
7、符与名字n名字：值：单元中的内容属性：类型和作用域n名字的性质的说明方式：由说明语句来明确规定的隐含说明：FORTRAN以IJKN为首的名字代表整型，否则为实型。动态确定：走到哪里，是什么，算什么国防科技大学计算机系602教研室二数据结构1数组n逻辑上，数组是由同一类型数据所组成的某种n维矩形结构，沿着每一维的距离，称为下标。数组可变与不可变：编译时能否确定其存贮空间的大小。访问：给出数组名和下标值存放方式:按行存放按列存放国防科技大学计算机系602教研室2记录n逻辑上说，记录结构由已知类型的数据组合在一起的一种结构。recordcharNAME20integerAGEboolMARRIEDC
8、ARD1000n访问：复合名CARDk.NAMEn存储：连续存放n域的地址计算：相对于记录结构起点的相对数OFFSET。国防科技大学计算机系602教研室3字符串、表格、栈n字符串：符号处理、公式处理n表格：本质上是一种记录结构n线性表：一组顺序化的记录结构n栈：一种线性表，后进先出，POPPUSH国防科技大学计算机系602教研室三抽象数据类型n一个抽象数据类型包括：数据对象的一个集合；作用于这些数据对象的抽象运算的集合；这种类型对象的封装，即，除了使用类型中所定义的运算外，用户不能对这些对象进行操作。n程序设计语言对抽象数据类型的支持Ada语言通过程序包（package）提供了数据封装的支持S
9、malltalk、C+和Java语言则通过类（Class）对抽象数据类型提供支持。国防科技大学计算机系602教研室2.2.4语句与控制结构一表达式表达式由运算量（也称操作数，即数据引用或函数调用）和算符（操作符）组成。形式：中缀、前缀、后缀XY-AP表达式形成规则算符的优先次序代数性质国防科技大学计算机系602教研室二语句n功能：执行性语句vs.说明性语句n形式：简单句vs.复杂句国防科技大学计算机系602教研室l赋值语句A=Bl无条件转移语句gotoLl条件语句ifBthenSifBthenS1elseS2l循环语句whileBdoSrepeatSuntilBfori:=E1stepE2un
10、tilE3doSl过程调用语句callP(X1X2.Xn)l返回语句return(E)n执行性语句国防科技大学计算机系602教研室n说明语句：定义各种不同数据类型的变量或运算，定义名字的性质。国防科技大学计算机系602教研室简单句和复合句n简单句：不包含其他语句成分的基本句n复合句：句中有句的语句国防科技大学计算机系602教研室2.3程序语言的语法描述n几个概念:考虑一个有穷字母表字符集其中每一个元素称为一个字符上的字(也叫字符串)是指由中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为用表示上的所有字的全体包含空字例如:设=a，b，则=abaaabbabbaaa.国防科技大学计算
11、机系602教研室n的子集U和V的连接（积）定义为UV|U&VV自身的n次积记为Vn=VVVn规定V0=，令V=V0V1V2V3称V是V的闭包n记VVV，称V+是V的正规闭包。国防科技大学计算机系602教研室2.3.1上下文无关文法n文法：描述语言的语法结构的形式规则n上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VTVN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VTVN)开始符S至少必须在某个产生式的左部出现一次。国防科技大学计算机系602教研室n几点规定：“”
12、也可以用“:=表示，这种表示称为巴科斯范式(BNF)P1P2可缩写为P1|2|nPn其中，“|”读成“或”，称为P的一个候选式。表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为：G(E)：Ei|E+E|EE|(E)国防科技大学计算机系602教研室n定义：称A直接推出，即A仅当A是一个产生式，且，(VTVN)。n如果12n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。n例：对文法(1)E(E)(E+E)(i+E)(i+i)国防科技大学计算机系602教研室n通常，用表示：从1出发，经过一步或若干步，可以推出n。用表示：从1出发，经过0步或若干步，
13、可以推出n。所以：即或q定义：假定G是一个文法，S是它的开始符号。如果，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。国防科技大学计算机系602教研室n从一个句型到另一个句型的推导往往不唯一。E+Ei+Ei+iE+EE+ii+in最左推导：任何一步都是对中的最左非终结符进行替换。最右推导：任何一步都是对中的最右非终结符进行替换。国防科技大学计算机系602教研室2.3.2语法树与二义性n用一张图表示一个句型的推导称为语法树。n(ii+i)的语法树E(E)(E+E)(EE+E)(iE+E)(ii+E)(ii+i)E(E)(E+E)(E+i)(E
14、E+i)(Ei+i)(ii+i)一棵语法树是不同推导过程的共性抽象。国防科技大学计算机系602教研室n如果使用最左(右)推导，则一个最左(右)推导与语法树一一对应。n一个句型是否只对应唯一一棵语法树？国防科技大学计算机系602教研室n定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。G(E)：Ei|E+E|EE|(E)是二义文法。n语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。可能存在G和G，一个为二义的，一个为无二义的。但L(G)=L(G)国防科技大学计算机系602教研室二义文法：G(E)：Ei|E+E|EE|(E)表达式项|表达式+项项因子|项因子
15、因子(表达式)|i无二义文法：G(E)：ET|E+TTF|TFF(E)|i国防科技大学计算机系602教研室)EEEFFTTTTi+(EFiiETF(E)(E+T)(T+T)(TF+T)(FF+T)(iF+T)(ii+T)(ii+F)(ii+i)考虑句子(ii+i)国防科技大学计算机系602教研室n描述程序设计语言时，对于上下文无关文法的限制：1不含PP形式的产生式2每个非终结符P必须有用处即：国防科技大学计算机系602教研室2.3.3形式语言鸟瞰nChomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。n与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。国防科技大学计算机系602教研室0型(短语文法，图灵机)：产生式形如：其中：(VTVN)且至少含有一个非终结符；(VTVN)1型(上下文有关文法，线性界限自动机)：产生式形如：其中：|，仅S例外。国防科技大学计算机系602教研室2型(上下文无关文法，非确定下推自动机)：产生式形如：A其中：AVN；(VTVN)。3型(正规文法，有限自动机)：产生式形如：AB或A其中：VT；A，BVN产生式形如：AB或A其中：VT；A，B
