计算机编译原理ppt课件.ppt
1,第4章 程序语言的设计,第2章和第3章分别讨论了程序设计语言的数据类型和控制结构，分别描述程序的数据结构和算法。本章介绍语言的设计方法。,2,1 语言的定义,语言 = 语法 + 语义语法：用以构造程序及其成分（语法单位）的规则的集合。语义：用以规定语法正确的语法单位的含义的规则的集合。,3,1.1 语法,1.1.1 几个术语(1) 字母表语言允许使用字符的集合，其元素称为字符(2) 符号由字符组成的有限串（字符串）(3) 字汇表由符号组成的集合，其元素称为字,4,(4) 词法规则规定什么样的字符序列可以构成语言的有效符号（单词符号）(5) 语法规则确定一个符号序列是否为一个句子，并提供句子的结构（什么样的符号序列是合法的）,5,语言的定义,语言的定义可以从生成（文法）和识别（语法图）的观点进行。,6,1.1.2 生成的观点,用文法来定义语言(1) 一个简单英语句子的描述I/Students study/run,7,(2) 文法I|Studentsstudy|run,8,(3) 语言根据文法规则生成的所有句子的集合，称为语言。,9,标识符的文法,A|Z|a|z0|9,10,表达式的文法,()+|-|*|/,11,1.1.3 识别的观点,用语法图来定义的语言(1) 语法图的构造终结符x对应一个语法图非终结符N对应一个语法图,12,N1|2|n对应一个语法图,13,12m对应一个语法图,14,|对应一个语法图,15,(2) 识别原则若一个终结符序列是合法的，那么，必须从语法图的入口边通过语法图而到达出口边，而且在通过的过程中，恰恰能识别该终结符序列。,16,(3) 语言语法图能识别的所有终结符序列的集合，称为语言。,17,标识符的语法图,18,表达式的语法图,19,语法描述方法等价,文法和语法图是语言语法的等价表示。文法从产生的观点来定义语言，更通用、更准确地给出语言的语法结构。语法图以识别的观点定义语言，更直观、更清晰地给出语言的语法结构。采用生成的方法还是采用识别的方法来定义语言，由语言的设计者确定。,20,1.1.4 语法描述的用途,(1) 表达语言设计者的意图和设计目标(2) 指导语言的使用者编写正确的程序(3) 指导语言的实现者编写语法检查程序来识别所有语法单位,21,1.2 语义,语义：定义语言合法句子的含义（即句子的作用和意义）的规则组合。文法和语法图已成为语法描述的典型工具，但语义描述至今尚无人们普遍接受的典型描述工具。许多语言仍采用自然语言描述语义。,22,本章的语言设计，采用自然语言来描述语义。（下篇的）语言实现涉及到的语义，将以操作语义学的方法来描述。即以一个抽象机的行为来描述语言的各个结构的作用和意义。,23,抽象机GAM的组成,由存储器，控制器，处理器，指令指针ip组成。存储器分为代码区和数据区。,24,抽象机GAM的模型,ip,代码存储器（C）,数据存储器（D）,25,抽象机GAM的结构,代码区（代码存储器），存放程序指令，代码存储器的内容不允许被修改。数据区（数据存储器），存放必要的信息和程序中的数据。,26,ip的内容是代码区存储单元的地址，该单元的内容是一条指令。 Ci和Di表示相应存储区第i个单元。ip:= ip+ 4 表示指针指向下一条指令，假定每条指令占4个存储单元（字节）。,27,GAM一旦启动，由专门的装入程序将一个要运行的程序装入代码存储器，并置 ip 指向该程序的第一条指令。然后依次完成下述工作：,28,(1)执行 ip 所指向的指令。 (2)修改 ip 的内容。若所执行的指令未修改ip，则ip+4，使之指向下一条指令。 (3)若ip 指向特殊的STOP指令，则终止执行，否则转回执行(1)。,29,假设 GAM 对各种程序设计语言所常用的运算符，如：，-，*，/ ，= 等，都有相应的指令与之对应。以GAM的操作行为来定义语言的语义，是基于已经“理解”GAM的语义。因此，一旦用 GAM 的操作行为来定义语言结构的作用时，就知道了语言的意义。,30,2 文法,2.1 文法的定义文法是描述语言语法结构的形式规则。通用，准确，易于理解，描述能力强,31,2.1.1 文法的形式定义,G=(VT，VN ， S ， P)VT为终结符的非空有限集；VN为非终结符的非空有限集； S是文法的开始符号， SVN ；P为产生式的非空有限集。,32,产生式是一个有序偶对(，)，记为：和是由终结符、非终结符组成的符号串，但至少应含有一个非终结符。即： V*VN V* V*,33,产生式的简化, 1 2 n简化为： 1 | 2 |n,34,文法的表示,描述文法，直接给出产生式集合即可。例如，算术表达式文法G(E)E E+T | TT T*F | FF (E) | i,35,2.1.2 文法的分类,(1)无限制文法（0型文法）产生式为，V*VNV*, V*(2)上下文有关文法（1型文法）产生式为A，AVN，、V*，V+,36,(3)上下文无关文法（2型文法）产生式为A ，AVN， V*(4)正则文法（3型文法）产生式为A或AB， VT*，BVN,37,2.2 文法产生的语言,2.2.1 推导与归约(1) 直接推导：w w 即由产生式右边替换产生式左边(2) 推导：1 *n、1 +n,38,E E+EE*E(E)i i+i*i的最左推导过程,E,E+E,i+E,i+E*E,i+i*E,i+i*i,39,最右推导（规范推导）,E E+E E+E*E E+E*i E+i*i i+i*i,40,E E*E E*i E+E*i E+i*i i+i*i,41,2.2.2 句型和句子,文法G=(VT,VN,S,P)S*若V*, 则为文法G的一个句型若VT*, 则是一个句子,42,句型与句子的关系,只含终结符的句型就是一个句子。一个句子是句型。一个句型不一定是句子。,43,2.2.3 文法产生的语言,文法G=(VT,VN,S,P)产生的所有句子的集合, 称为由文法G产生的语言, 记为L(G), 即L(G)=S +且 VT * ,44,文法实例1,文法G1：E E + T | TT T * F | FF ( E ) | i语言L(G1)表示由符号 i、+、*、(、)构成的表达式。,45,文法实例2,文法G2：SaS | aPPbP | bQQcQ | c语言L(G2)= aibjck | i，j，k1,46,文法实例3,文法G3：SaSPQabQQPPQbPbbbQbccQcc,47,S ai-1S(PQ)i-1 ai-1abQ(PQ)i-1 aibPi-1Qi aibiQi aibicQi-1 aibici语言L(G3)= aibici | i 1,48,说明,1) 文法的重要特性用有限规则描述无穷的语言。2) 文法的等价对两个文法G和G，如果L(G) = L(G)，则称文法G和文法G等价。,49,2.2.4 推导树（语法树）,(1) 推导树是一棵有序的标记树每个结点的标记是文法G的非终结符或终结符；标记为A的内部结点从左到右有子结点X1，X2，, Xn，则AX1Xn是一个产生式；,50,对于文法EE+EE*E(E)i句子i+i*i的推导树为：,51,E,（,E,）,E,E,*,E,E,+,i,i,i,E,（,E,）,E,E,+,E,E,i,i,i,*,52,(2) 推导树的边缘推导树所有叶结点从左到右的连接。(3) 文法的二义性一个句子有两棵不同的推导树。,53,4.3 语言的设计,设计的依据：面向的问题和面向的机器设计内容(语法)： 表达式、语句、程序单元、程序描述方式：语法文法、语义自然语言,54,4.3.1 表达式的设计,逻辑表达式关系表达式算术表达式,55,(1) 逻辑表达式, | | | | | ,56, true|false 、 、 的优先顺序由低到高,57,(2) 关系表达式, | = | = | 关系运算符没有优先顺序、没有重载,58,(3) 算术表达式, | | ()| ,59,算术运算符有优先顺序、允许重载算术运算符服从左结合（上述描述具有二义性）,60,没有二义性的描述, + | - | * | / | () | | ,61, ,62,4.3.2 语句的设计,说明语句执行语句,63,(1) 说明语句, | | ,64, const = type = var ： | ，,65, int | real | char | boolean | ,66,(2) 执行语句, | | | := | | 针对面向的问题选择一个方案,67, begin end | ； read() | write(),68,4.3.3 程序单元的设计, ()； procedure | function | | ；,69,形参可以没有；如果有，可以是变量、数组、过程等，必须说明类型及与实参的绑定方式。,70, begin ; end | ;,71, | ;,72, begin ； end ； ； ； ,73, | ； | ；,74, | ； | ；,75,4.3.4 程序的设计, ,76,4.3.5 一些设计准则,(1) 可写性语言提供一些机制来方便地表达设计方法以帮助完成程序设计，使得程序员可以把注意力集中在理解问题和求解问题上。,77,(2) 可读性抽象、注解；影响可修改性和可维护性。(3) 可靠性软件系统正常工作的能力。数据抽象、信息隐蔽、异常处理机制有利于提高可靠性。,
