编译原理-陈火旺版-第二章.ppt

1,编译方法,中国人民大学信息学院陈文萍,2,第二章 高级语言及其语法描述,高级程序语言:描述算法和计算机实现不同的应用侧重点不同:数值计算-FORTRAN 系统程序设计-C事务处理-COBOL VLSI设计-VHDL人工智能-PROLOG大型嵌入式实时处理-Ada 符号处理-SNOBOL,3,内容,2.1 程序语言的定义2.2 高级语言的一般特性2.3 程序语言的语法描述,4,2.1 程序语言的定义,程序设计语言：是由一组记号所构成的集合。语言的定义语言用户：语言的成分，使用意义编译程序：语言的规则，语法单位对应的含义组成部分语法（Syntax）语义（Semantics）语用（Pragmatics）,5,语法,语法（Syntax）：程序构成的一组规则词法规则：单词符号的形成规则单词符号：语言中具有独立意义的最基本的结构类型：常数，标识符，基本字，算符，界符例如：字符串 100-(8a)*0.5100，8：整型常数；0.5：实型常数；-,=,*：算符；(,)：界符分析工具：正规式和有限自动机,6,语法,语法规则：语法单位的形成规则语法单位：比单词符号更大的语法结构例如：表达式，语句，分程序，函数，过程，程序分析工具：上下文无关文法,7,语义,语义（Semantics）定义程序的含义的一组规则例如：C 语句a=18+b;分析方法：基于属性文法的语法制导翻译方法语用（Pragmatics）程序设计技术和语言成分的使用方法,8,程序的层次结构,程序,子程序,语句,表达式,数据引用,算符,函数调用,9,2.2 高级语言的一般特性,高级高级语言的分类：按语言范型强制式语言，应用式语言，基于规则的语言，面向对象的语言强制式语言：命令驱动，面向语句。一个强制式语言程序由一系列的语句组成，每个语句的执行引起若干存储单元中的值的改变，这种语言的语法形式通常具有如下形式：语句1；语句2；语句n；例如-C,Fortran,Pascal,10,应用式语言,注重程序所表示的功能，而不是一个语句接一个语句地执行程序的开发过程是从前面已有的函数出发构造出更复杂的函数这种语言通常的语法形式是：Function n(function2(function1(data)程序执行：执行一个个函数，得到数据上的变换，最终得到的结果例如：ML，Lisp,11,基于规则的语言,程序的执行过程：检查一定的条件，当它满足值，则执行适当的动作。也称逻辑程序设计语言：基本允许条件是谓词逻辑表达式。这类语言的语法形式通常为：条件1 动作1条件2 动作2条件3 动作3例如：Prolog,12,面向对象的语言,主要特征：封装性，继承性和多态性例如：C+,JAVA,13,程序结构,不同的语言，如 Fortran,Pascal，Ada，Java程序结构不同名字的作用域不同例如：Pascal 的最近嵌套原则 procedure P;var x:interger;procedure Q;var x:real;begin x:=1.2;end;begin x:=5;end;,14,数据类型,数据类型的三要素：属性，值，操作属性：包括类型和作用域类型：决定数据可以是什么样的值，允许的运算，计算机内如何表示作用域：值的有效范围初等数据类型数值数据：如整型，实型逻辑数据：布尔型字符数据：字符型（字符串型）指针类型：指向另一种数据类型,15,数据类型,数据结构：从初级数据定义的复杂（高级）数据数组内情向量：便于计算数据元素的地址，包括：维数，各维的上、下限，首地址，数组元素类型等。例如：Pascal的说明 var a:array1.50 of char 是一个下标从1至50的字符数组记录：由已知类型的数据组合而成例如：Pascal 语言中Student:record name:array 120 of char;age:integer;id:array 18 of char;major:integer;classid:integer;end;字符串，表格，栈，队列抽象数据类型：数据对象，运算，封装,16,语句与控制结构,表达式：由操作数和算符组成例如：x-y,-x通常的形成规则变量，常数是表达式若E1,E2是表达式，是二元算符，则E1E2是表达式若E是表达式，是一元算符，则E或 E是表达式若E是表达式，则(E)是表达式算符的优先级,17,语句,分类：按功能说明性语句：定义名字的性质执行性语句：描述程序动作赋值语句控制语句转移语句：goto条件语句：如 if then else循环 语句：如while do过程调用语句：如 call返回语句：如 return输入/输出语句:如 read,write,18,2.3 程序语言的语法描述,预备知识上下文无关文法语法分析与二义性形式语言概述,19,预备知识,符号：可以相互区别的记号（元素）字母表：符号（元素）的非空有穷集合，用表示符号串：由字母表中的符号组成的任何有穷序列1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3.y是上的符号串,当且仅当它可以由1和2导出。例如，字母表=a,b，则,a,b,aa,ab,ba,bb,aaa,aab,都是上的符号串,20,预备知识,符号串的运算符号串的长度：符号串中符号的个数.符号串s的长度记为|s|，的长度为0连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=cd 则 xy=abcd 有a=a 方幂：符号串自身连接n次得到的符号串 an 定义为 aaaa（n个a）a1=a,a2=aa a0=,21,预备知识,符号串的集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。*：表示上的所有符号串的全体空集：，不含任何元素符号串集合的运算：积（连接）：两个符号串集合A和B的积定义为 AB=xy|xA且yB 例如：集合A=ab,cde B=0,1，则 AB=ab1,ab0,cde0,cde1闭包：V*=V 0 V 1 V 2 V 3.,*称为的闭包V 0=,22,预备知识,正则闭包：V+=V 1 V 2 V 3.,V*=V+，+称为的正闭包。例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,23,上下文无关文法,语言的表示语言有穷：将句子逐一列出语言无穷：找出语言的有穷表示，两个途径：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”；若不属于，要么能停止并回答“不是”，要么永远继续下去,24,上下文无关文法,文法：描述语言的语法结构的形式规则。形式数学系统：可由下列基本成分来刻画：一组基本符号，一组形成规则，一组公理，一组推理规则上下文无关文法：所定义的语法范畴完全独立于语法范畴可能出现的环境。例如：语法规则：I am a student,25,上下文无关文法,分析句子：I am a student句子 主语 谓语 宾语 代词 谓语 宾语 I 谓语 宾语 I 动词 宾语 I am 宾语 I am 冠词 名词 I am a student语法树：如右图,26,上下文无关文法,四个组成部分：四元式（VT,VN,S,P）终结符号：VT,不可再分的基本符号，如基本字、标识符、常数、算符、界符等词法符号。非终结符号：VN,语法范畴，表示类记号，不是个体记号。VN和VT不含公共的元素，即VN VT=,用V表示VN VT，称为文法G的字母表或字汇表开始符号：S,特殊的非终结符号，至少要在一条产生式中作为左部出现。产生式：P，定义语法范畴的一种书写规则。形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。例如：E i|E+E|E*E|(E)候选式,27,上下文无关文法,举例文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号习惯上只将产生式写出，并有如下约定：第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成GS，S是开始符号G：SaAb Aab AaAb AGS：SaAb Aab AaAb A缩写形式 GS：SaAb Aab|aAb|,28,上下文无关文法,直接推出：“”定义：是文法G的产生式，若有v,w满足：v=,w=,其中,（VTVN），则称v直接推出到w,记作 v w推导：若存在v w0 w1.wn=w,(n0)，则称此序列为v到w的一个推导记为：经过至少一步推导：经0步或若干步推导每前进一步总是引用文法中的一个产生式 若有 则或 v=wn，或,29,上下文无关文法,句型对文法G，若，则称是文法G的句型。句子有文法G，若，且VT*，则称是文法G的句子。例：G：S0S1，S01S 0S1 00S11 000S111 00001111G的句型：S,0S1,00S11,000S111,00001111G的句子：00001111,01由文法G生成的语言记为L(G),它是文法G的一切句子的集合:,30,上下文无关文法,例：文法G:SAB，AaA|a，BbB|b从开始符号出发，可以推出如下句子：所以，最左推导：任何一步推导，都对右部最左非终结符进行替换最右推导：任何一步推导，都对右部最右非终结符进行替换,31,思考,1，文法G：S0S1，S01，L(G)？2，文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEeeL(G)？,32,上下文无关文法,已知语言描述，写出文法例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法G(A)A 0B|1CB 1|1A|0BBC 0|0A|1CC,33,上下文无关文法,文法G1A：ADB 与G2S：S0S1 ADE S01 EAB D0 B1文法的等价：若L（G1）=L（G2），则称文法G1和G2是等价的。,34,语法分析树,语法分析树：句型推导的直观方法文法：，推导（i*i+i),E i|E+E|E*E|(E),E,E,）,（,E,E,E,E,*,i,i,E,E,）,（,*,E,E,E,E,+,i,i,i,i,35,语法分析树,给定文法G，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列4个条件：1、每个结点都有一个V中的符号作标记2、根的标记是开始符号S3、若一结点n至少有一个子孙，并且n有标记A，则AVN4、如果结点n的直接子孙，从左到右的次序是结点n1,n2,nk，其标记分别为A1,A2,Ak，那么AA1A2,Ak一定是P中的一个产生式,36,二义性,文法的二义性：一个文法存在某个句子对应两个不同的语法树，或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。上例中，句型（i*i+i）的两个不同的最左推导：推导1：E（E）（E+E）（E*E+E）（i*E+E）（i*i+E）（i*i+i）推导2：E（E）（E*E）（i*E）（i*E+E）（i*i+E）（i*i+i）消除二义性：修改文法，规定优先顺序和结合律 ET|E+T TF|T*F F(E)|i,37,上下文无关文法,对文法的限制不含PP形式的产生式每个非终结符P都必须有用必须存在含P的句型（可到达）且P不存在永不终结的回路（可终止）,38,形式语言概述,形式语言：从语法这一侧面来看语言。分类：通过对产生式施加不同的限制，Chomsky将文法分为四种类型0型文法（短语结构文法）：对任一产生式，都有(VNVT)+，(VNVT)*。识别系统是图灵机。1型文法（上下文有关文法）：对任一产生式，都有|；仅仅 S除外，但S不能出现在任何产生式右部。识别系统为线性有界自动机。,39,形式语言概述,2型文法（上下文无关文法）：对任一产生式，都有VN。识别系统为下推自动机。3型文法（正规文法）：任一产生式的形式都为AB或A，其中AVN，BVN，VT*。识别系统为有限自动机。右线性文法：任一产生式的形式都为AaB或Aa左线性文法（正规文法）：任一产生式的形式都为ABa或Aa,40,文法类型,例1:文法GS：SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabD,41,文法类型,例2:文法GS：SABABS|0BSA|1,42,文法类型,例3：文法GS：S0A|1B|0A0A|1B|0SB1B|1|0GI：I lT I lT lTT dTT lT d,43,小结,程序语言的定义语法：词法规则，语法规则语义语用高级语言的一般特性分类：强制式，应用式，基于规则，面向对象程序结构数据类型语句,44,小结,程序语言的语法描述上下文无关文法概念：符号串，字母表运算：连接，方幂，闭包，正则闭包形式表示：四元式（VT,VN,S,P）推导，句子，句型，语言语法分析树，文法的二义性Chomsky文法的四种类型,