《计算机编译原理幻灯片4》由会员分享，可在线阅读，更多相关《计算机编译原理幻灯片4（77页珍藏版）》请在金锄头文库上搜索。
1、1,第4章 程序语言的设计,第2章和第3章分别讨论了程序设计语言的数据类型和控制结构，分别描述程序的数据结构和算法。 本章介绍语言的设计方法。,2,1 语言的定义,语言 = 语法 + 语义 语法：用以构造程序及其成分（语法单位）的规则的集合。 语义：用以规定语法正确的语法单位的含义的规则的集合。,3,1.1 语法,1.1.1 几个术语 (1) 字母表 语言允许使用字符的集合，其元素称为字符 (2) 符号 由字符组成的有限串（字符串） (3) 字汇表 由符号组成的集合，其元素称为字,4,(4) 词法规则 规定什么样的字符序列可以构成语言的有效符号（单词符号） (5) 语法规则 确定一个符号序列是
2、否为一个句子，并提供句子的结构（什么样的符号序列是合法的）,5,语言的定义,语言的定义可以从生成（文法）和识别（语法图）的观点进行。,6,1.1.2 生成的观点,用文法来定义语言 (1) 一个简单英语句子的描述 I/Students study/run,7,(2) 文法 I|Students study|run,8,(3) 语言 根据文法规则生成的所有句子的集合，称为语言。,9,标识符的文法, A|Z|a|z 0|9,10,表达式的文法, () +|-|*|/,11,1.1.3 识别的观点,用语法图来定义的语言 (1) 语法图的构造 终结符x对应一个语法图 非终结符N对应一个语法图,12,N1
3、|2|n对应一个语法图,13,12m对应一个语法图,14,|对应一个语法图,15,(2) 识别原则 若一个终结符序列是合法的，那么，必须从语法图的入口边通过语法图而到达出口边，而且在通过的过程中，恰恰能识别该终结符序列。,16,(3) 语言 语法图能识别的所有终结符序列的集合，称为语言。,17,标识符的语法图,18,表达式的语法图,19,语法描述方法等价,文法和语法图是语言语法的等价表示。 文法从产生的观点来定义语言，更通用、更准确地给出语言的语法结构。 语法图以识别的观点定义语言，更直观、更清晰地给出语言的语法结构。 采用生成的方法还是采用识别的方法来定义语言，由语言的设计者确定。,20,1
4、.1.4 语法描述的用途,(1) 表达语言设计者的意图和设计目标 (2) 指导语言的使用者编写正确的程序 (3) 指导语言的实现者编写语法检查程序来识别所有语法单位,21,1.2 语义,语义：定义语言合法句子的含义（即句子的作用和意义）的规则组合。 文法和语法图已成为语法描述的典型工具，但语义描述至今尚无人们普遍接受的典型描述工具。 许多语言仍采用自然语言描述语义。,22,本章的语言设计，采用自然语言来描述语义。 （下篇的）语言实现涉及到的语义，将以操作语义学的方法来描述。即以一个抽象机的行为来描述语言的各个结构的作用和意义。,23,抽象机GAM的组成,由存储器，控制器，处理器，指令指针ip组
5、成。 存储器分为代码区和数据区。,24,抽象机GAM的模型,ip,代码存储器（C）,数据存储器（D）,25,抽象机GAM的结构,代码区（代码存储器），存放程序指令，代码存储器的内容不允许被修改。 数据区（数据存储器），存放必要的信息和程序中的数据。,26,ip的内容是代码区存储单元的地址，该单元的内容是一条指令。 Ci和Di表示相应存储区第i个单元。 ip:= ip+ 4 表示指针指向下一条指令，假定每条指令占4个存储单元（字节）。,27,GAM一旦启动，由专门的装入程序将一个要运行的程序装入代码存储器，并置 ip 指向该程序的第一条指令。 然后依次完成下述工作：,28,(1)执行 ip 所指
6、向的指令。 (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)
7、 VT为终结符的非空有限集； VN为非终结符的非空有限集； S是文法的开始符号， SVN ； P为产生式的非空有限集。,32,产生式是一个有序偶对(，)，记为： 和是由终结符、非终结符组成的符号串，但至少应含有一个非终结符。即： V*VN V* V*,33,产生式的简化, 1 2 n 简化为： 1 | 2 |n,34,文法的表示,描述文法，直接给出产生式集合即可。 例如，算术表达式文法G(E) E E+T | T T T*F | F F (E) | i,35,2.1.2 文法的分类,(1)无限制文法（0型文法） 产生式为，V*VNV*, V* (2)上下文有关文法（1型文法） 产生式为A，AV
8、N，、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=(
9、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 | T T T * F | F F ( E ) | i 语言L(G1)表示由符号 i、+、*、(、)构成的表达式。,45,文法实例2,文法G2： SaS | aP PbP | bQ QcQ | c 语言
10、L(G2)= aibjck | i，j，k1,46,文法实例3,文法G3： SaSPQabQ QPPQ bPbb bQbc cQcc,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的内部结点从左
11、到右有子结点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) 逻辑表达式,
12、 | | | | | ,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,
13、(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) 可靠性 软件系统正常工作的能力。数据抽象、信息隐蔽、异常处理机制有利于提高可靠性。,
