1、第四章 程序语言的设计,第一节 语言的定义语言语法语义 语法:用以构造程序及其成分的一组规则 的集合 语义:用以规定语法正确的程序或其成分的含义的一组规则的集合,一.语法1.几个术语字母表:语言允许使用字符的集合,其元素称为字符符号:由字符组成的有限串（字符串）字汇表:由符号组成的集合，其元素称为字词法规则:规定什么样的字符串可以构成语言的有效符号语法规则:确定一个符号序列是否为一个句子,并提供句子的结构（什么样的符号序列是合法的）,2. 生成的观点 一个简单英语句子的描述I/Students study/run. 文法:语言的一个完整的语法描述,记为(N,T,P,S)I|Studentsst
2、udy|run语言:所有句子的集合,”标识符”和”表达式”的定义(递归定义)(注意递归的结束条件) 标识符A|B|X|Y|Z|a|b|x|y|z0|1|2|3|4|5|6|7|8|9,表达式()+|-|*|/,3.识别的观点 用语法图来定义给定的语言 语法图的构造 N1|2|n对应一个语法图终结符x非终结符NN1|2|n,12m |,识别原则:若一个终结符序列是合法的，那么,必须从语法图的入口边通过语法图而到达出口边，而且在通过的过程中,恰恰能识别该终结符序列。.终结符框.非终结符框.分支、回溯 参见图4-6、图4-7、图4-8、图4-9 语言:语法图能识别的所有终结符序列的集合。,标识符,表
3、达式,运算符,表达式,(,),表达式,表达式,字母,字母,数字,标识符,字母,字母,数字,表达式,表达式,(,),表达式,+,表达式,-,*,/,+,-,*,/,运算符,图4-6,图4-7,图4-8,图4-9,4.语法描述的基本用途 表达语言设计者的意图和设计目标; 指导语言的使用者如何写一个正确的程序； 指导语言的实现者如何编写一个语法检查程序来识别所有合法的程序。,二.语义 例：大象吃花生Elephants eat peanuts.1.何谓语义?定义语言合法句子的含义，即句子的作用和意义。 例：if(ab)max=a;else max=b;2. GAM的结构指令指针+代码存储器C +数据存
4、储器D举例:若懂汉语,可以将任何外语以汉语解释；亦即理解了汉语则理解了外语.,ip,代码存储器（C）,数据存储器（D）,第二节 文 法一. 文法的定义文法是描述语言的语法结构的形式规则,必须准确,易于理解,且描述能力强,1. 文法的形式定义G=(VT,VN,S,P) 例 G0=(VT,VN,S,P):EE+T|TTT*F|FF(E)|i 显然 VT =+,*,(,),iVN =E,T,FS=EP为上述产生式的集合,说明: 的读法,其中 V*VNV*, V*，VVT VN 1 2. n约定：用英文大写字母表示非终结符；小写字母表示终结符；希腊小写字母表示串,缩写为 1| 2| n,2. 文法的分
5、类0型文法:产生式形如1型文法:=（S例外）或产生式形如A， V + (上下文有关文法)2型文法:产生式形如A(上下文无关文法)3型文法:产生式形如A或AB(正则文法,右线性文法) VT,*,3. 简化的上下文无关文法 不含形如AA的有害规则 不含多余规则即AVN, 必有S A,*,二. 文法产生的语言 1. 推导与归约直接推导: 即由产生式右边替换产生式左边推导:1 n、1 n归约:推导的逆过程,*,+,举例: 已知G(E) EE+EE*E(E)ii+i*i的推导过程 E E+E E+E*E E+E*i E+i*i i+i*i E E+E i+E i+E*E i+i*E i+i*i E E*
6、E E*i E+E*i E+i*i i+i*i,2. 句型和句子 设文法G=(VT,VN,S,P), 若S , V*, 则称为文法G的一个句型。 若上述 VT，则称是一个句子，即只含终结符的句型是一个句子。,*,*,3. 文法产生的语言文法G=(VT,VN,S,P)的句子的全体, 称为由文法G产生的语言, 记为L(G), 即L(G)=S VT ,+,*,G2(I):ILLSSTSTTLDLab. . .zD012 . . .9,G3(S):SaSaPPbPbQQcQc L(G3)=aibjcki,j,k1,G4(S):SaSPQabQQPPQbPbbbQbccQcc L(G4)= aibici
7、i 1,Sai-1S(PQ)i-1 (i-1次使用第一个产生式)aibQ(PQ)i-1 (使用第二个产生式)aib(PQ)i-1Q (i-1次使用第三个产生式)aib2(QP)i-2Q2 (使用第四个产生式)aib3(QP)i-3Q3 (i-2次使用第三个产生式)aibiQiaibicQi-1 (使用第五个产生式) aibici (i-1次使用第六个产生式),*,*,*,*,*,*,*,*,*,文法的重要特性:用有限规则描述无穷语言 文法的等价:两个文法G和G,如果有L(G)=L(G),则称G和G等价,4语法树（推导树）以图的方式表示推导过程推导树是一棵有序的标记树 每个结点的标记是文法G的非
8、终结符或终结符； 标记为A的内部结点从左到右有子结点X1，X2，, Xn,则AX1Xn是一个产生式; 如果有结点标记为，则它必是叶结点，且它是该父结点的唯一子结点。,推导树的构造例（i+i*i）,E,（,E,）,E,E,+,E,E,i,i,i,*,推导树的边缘：一棵推导树所有叶结点的从左到右的连接。 文法的二义性：一个句子有两棵不同的推导树。,设计的依据：设计目标 面向的问题和面向的机器 设计内容：表达式、语句、程序单元、程序,第三节 语言的设计,一. 表达式的设计表达式包括：逻辑表达式、关系表达式、算术表达式 1. 逻辑表达式 truefalse,第三节 语言的设计,、 、 的优先顺序由低到
9、高 布尔表达式的值为true（真）和false（假）,第三节 语言的设计,2. 关系表达式 = 关系运算符之间没有优先顺序、没有重载,第三节 语言的设计,3. 算术表达式 （） 算术运算符之间有优先顺序、允许重载 算术运算符服从左结合 上述描述具有二义性,第三节 语言的设计,没有二义性的描述： +- */ （） ,第三节 语言的设计,二.语句的设计 1.说明语句 const = type = var ： ， integerrealcharboolean ,第三节 语言的设计,2.执行语句 （1）赋值语句 := （2）控制语句 顺序、选择、重复 语句结束符 （3）复合语句 begin end ；
10、,第三节 语言的设计,3.程序单元的设计 ()； procedurefunctionclass ； 形参可以是变量、数组、过程等，必须说明类型及与实参的绑定方式,第三节 语言的设计,begin ； end ； ；,第三节 语言的设计,begin ； end ； ； ； ； ； ； ；,第三节 语言的设计,4.程序的设计 ,第三节 语言的设计,5.语言设计实例 问题：设计一个极小的语言，求n！ if n=0 then F:=1 else F:=n*F(n-1) 机器：PC机,第三节 语言的设计, begin ； end ； integer ,第三节 语言的设计, abcdefghijklmno
11、pq rstuvwxyz 0123456789 integer function （）； ,第三节 语言的设计,begin ； end ； read() write(),第三节 语言的设计,:= - * ,第三节 语言的设计,ifthenelse =,第三节 语言的设计,求n!的程序： begininteger k;integer function F(n);begininteger n;if n=0 then F:=1else F:=n*F(n-1)end;read(m);k:=F(m);write(k) end,第三节 语言的设计,6.一些设计准则 （1）可写性：语言通过提供一些构造来方便地表达设计方法以帮助完成程序设计。语言提供的这些构造，使得程序员可以把注意力集中在理解问题和求解问题上。可写性表现在简单性、可表达性、正交性和准确性等方面。 （2）可读性：抽象、注解；影响可修改性和可维护性 （3）可靠性：软件系统正常工作的能力。数据抽象、信息隐蔽、异常处理机制有利于提高可靠性。,第三节 语言的设计,第四章习题,4-1 4-4为思考题 4-5 4-11是必做题,
