计算机编译原理课件4.ppt

1、1第4章 程序语言的设计第2章和第3章分别讨论了程序设计语言的数据类数据类型型和控制结构控制结构，分别描述程序的数据结构数据结构和算算法法。本章介绍语言的设计设计方法。21 语言的定义语言语言=语法语法+语义语义语法语法：用以构造程序及其成分（语法单位）的规则的集合。语义语义：用以规定语法正确的语法单位的含义的规则的集合。31.1 语法1.1.1 几个术语(1)字母表语言允许使用字符字符的集合，其元素称为字符(2)符号由字符组成的有限串（字符串字符串）(3)字汇表由符号符号组成的集合，其元素称为字字4(4)词法规则规定什么样的字符字符序列可以构成语言的有效符号符号（单词符号单词符号）(5)语法

2、规则确定一个符号序列符号序列是否为一个句子句子，并提供句子的结构结构（什么样的符号序列是合法的）5语言的定义语言的定义可以从生成生成（文法）和识别识别（语法图）的观点进行。61.1.2 生成的观点用文法文法来定义语言(1)一个简单英语句子的描述I/Students study/run7(2)文法I|Studentsstudy|run8(3)语言根据文法规则生成的所有句子句子的集合集合，称为语言语言。9标识符的文法A|Z|a|z0|910表达式的文法()+|-|*|/111.1.3 识别的观点用语法图语法图来定义的语言(1)语法图的构造终结符x对应一个语法图非终结符N对应一个语法图xN12N1|

3、2|n对应一个语法图2n11312m对应一个语法图12m14|对应一个语法图15(2)识别原则若一个终结符序列是合法的，那么，必须从语法图的入口边通过语法图而到达出口边，而且在通过的过程中，恰恰能识别识别该终结符序列终结符序列。16(3)语言语法图能识别的所有终结符序列终结符序列的集合集合，称为语语言言。17标识符的语法图字母字母数字18表达式的语法图标识符表达式运算符()表达式表达式19语法描述方法等价文法和语法图是语言语法的等价等价表示。文法从产生的观点产生的观点来定义语言，更通用、更准确地给出语言的语法结构。语法图以识别的观点识别的观点定义语言，更直观、更清晰地给出语言的语法结构。采用生

4、成的方法还是采用识别的方法来定义语言，由语言的设计者设计者确定。201.1.4 语法描述的用途(1)表达语言设计者设计者的意图和设计目标(2)指导语言的使用者使用者编写正确的程序(3)指导语言的实现者实现者编写语法检查程序来识别所有语法单位211.2 语义语义：定义语言合法句子的含义含义（即句子的作用和意义）的规则组合。文法和语法图已成为语法描述的典型工具，但语义描述至今尚无人们普遍接受的典型描述工具。许多语言仍采用自然语言自然语言描述语义。22本章的语言设计，采用自然语言来描述语义。（下篇的）语言实现涉及到的语义，将以操作语义操作语义学学的方法来描述。即以一个抽象机抽象机的行为行为来描述语言

5、的各个结构的作用和意义。23抽象机GAM的组成由存储器，控制器，处理器，指令指针ip组成。存储器分为代码区代码区和数据区数据区。24抽象机GAM的模型ip代码存储器（C）数据存储器（D）25抽象机GAM的结构代码区（代码存储器），存放程序指令，代码存储器的内容不允许被修改。数据区（数据存储器），存放必要的信息和程序中的数据。26ip的内容是代码区存储单元的地址，该单元的内容是一条指令。Ci和Di表示相应存储区第i个单元。ip:=ip+4 表示指针指向下一条指令，假定每条指令占4个存储单元（字节）。27GAM一旦启动，由专门的装入程序将一个要运行的程序装入代码存储器，并置 ip 指向该程序的第一

6、条指令。然后依次完成下述工作：28(1)执行 ip 所指向的指令。(2)修改 ip 的内容。若所执行的指令未修改ip，则ip+4，使之指向下一条指令。(3)若ip 指向特殊的STOP指令，则终止执行，否则转回执行(1)。29假设 GAM 对各种程序设计语言所常用的运算符，如：，-，*，/，=等，都有相应的指令与之对应。以GAM的操作行为的操作行为来定义语言的语义，是基于已经“理解”GAM的语义。因此，一旦用 GAM 的操作行为来定义语言结构的作用时，就知道了语言的意义语言的意义。302 文法2.1 文法的定义文法是描述描述语言语法语法结构的形式规则形式规则。通用，准确，易于理解，描述能力强31

7、2.1.1 文法的形式定义G=(VT，VN，S，P)VT为终结符的非空有限集；VN为非终结符的非空有限集；S是文法的开始符号，SVN；P为产生式的非空有限集。32产生式是一个有序偶对(，)，记为：和是由终结符、非终结符组成的符号串符号串，但至少应含有一个非终结符非终结符。即：V*VN V*V*33产生式的简化 1 2 n简化为：1|2|n34文法的表示描述文法，直接给出产生式集合产生式集合即可。例如，算术表达式文法G(E)E E+T|TT T*F|FF (E)|i352.1.2 文法的分类(1)无限制文法（0型文法）产生式为，V*VNV*,V*(2)上下文有关文法（1型文法）产生式为A，AVN

8、，、V*，V+36(3)上下文无关文法（2型文法）产生式为A，AVN，V*(4)正则文法（3型文法）产生式为A或AB，VT*，BVN372.2 文法产生的语言2.2.1 推导与归约(1)直接推导：w w 即由产生式右边右边替换产生式左边左边(2)推导：1*n、1+n 38E E+EE*E(E)i i+i*i的最左推导最左推导过程E EE E+E+Ei i+E Ei+i+E E*E Ei+ii+i*E Ei+ii+i*i i39最右推导（规范推导）E E+E E+E*E E+E*i E+i*i i+i*i40E E*E E*i E+E*i E+i*i i+i*i412.2.2 句型和句子文法G=

9、(VT,VN,S,P)S*若V*,则为文法G的一个句型句型若VT*,则是一个句子句子42句型与句子的关系只含终结符的句型就是一个句子。一个句子是句型。一个句型不一定是句子。432.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，k146文法实例3文法G3：SaSPQabQQP

10、PQbPbbbQbccQcc47S ai-1S(PQ)i-1 ai-1abQ(PQ)i-1 aibPi-1Qi aibiQi aibicQi-1 aibici语言L(G3)=aibici|i 148说明1)文法的重要特性用有限有限规则描述无穷无穷的语言。2)文法的等价对两个文法G和G，如果L(G)=L(G)，则称文法G和文法G等价等价。492.2.4 推导树（语法树）(1)推导树是一棵有序的标记树每个结点结点的标记是文法G的非终结符或终结符；标记为A的内部结点从左到右有子结点子结点X1，X2，,Xn，则AX1Xn是一个产生式；50对于文法EE+EE*E(E)i句子i+i*i的推导树为：51E（

11、E）EE*EE+iiiE（E）EE+EEiii*52(2)推导树的边缘推导树所有叶叶结点从左到右从左到右的连接。(3)文法的二义性一个句子有两棵不同的推导树。534.3 语言的设计设计的依据：面向的问题和面向的机器设计内容(语法)：表达式、语句、程序单元、程序描述方式：语法文法、语义自然语言544.3.1 表达式的设计逻辑表达式关系表达式算术表达式55(1)逻辑表达式|56 true|false 、的优先顺序由低到高57(2)关系表达式|=|=|关系运算符没有优先顺序、没有重载58(3)算术表达式|()|59算术运算符有优先顺序、允许重载算术运算符服从左结合（上述描述具有二义性）60没有二义性

12、的描述 +|-|*|/|()|61 624.3.2 语句的设计说明语句执行语句63(1)说明语句|64 const =type =var：|，65 int|real|char|boolean|66(2)执行语句|:=|针对面向的问题选择一个方案 67 begin end|；read()|write()684.3.3 程序单元的设计 ()；procedure|function|；69形参可以没有；如果有，可以是变量、数组、过程等，必须说明类型及与实参的绑定方式。70 begin;end|;71|;72 begin；end ；73|；|；74|；|；754.3.4 程序的设计 764.3.5 一些设计准则(1)可写性语言提供一些机制来方便地表达设计方法以帮助完成程序设计，使得程序员可以把注意力集中在理解问题和求解问题上。77(2)可读性抽象、注解；影响可修改性和可维护性。(3)可靠性软件系统正常工作的能力。数据抽象、信息隐蔽、异常处理机制有利于提高可靠性。