北航研究生课程程序语言设计原理教程第02章.ppt

第1页,第二章 程序设计语言设计概述,2.1 表示与抽象2.2 设计目标2.3 设计准则2.4 规格说明,第2页,2.1 表示与抽象,表示是人为制造的符号组合以表达我们需要表达的意思。程序是程序设计语言表示的计算float n;/n 是浮点数变量sqrt(n);/对n取平方根同一程序的高级语言表示、经翻译后的汇编码表示、机器码表示就是该程序在不同抽象层次上的表示。,第3页,2.1 表示与抽象,程序在不同抽象层次表示的关系例：x=x+1在机器码上就有两种方法。,从内存代表x的地址中取出值放在运算器中。加1，将结果放于某临时单元。将临时单元内容做类型检查（必要时转换）并放入x中。,从内存代表x的地址中取出值放在运算器中。加1，将结果放入x地址中。,第4页,2.1 表示与抽象,儿子10岁女儿8岁母亲35岁几年后儿女岁数之和大于等于母亲？,u=m-s-d,每人每年增1岁每增 一年比较一次，满足 条件即所求。,read(m,s,d);u=m-s-d;print(u),read(m,s,d);u=0;while(m+us+d+2u)u+;print(u);,m,s,d,u,指令集,客观世界问题抽象,模型世界数学模型模拟模型,程序世界以程序世界术语表示描述模型,机器世界以机器的术语实现程序,图2-1 计算机解题的四个世界,第5页,2.2 PL设计目标,定义一组能表示某种范型的特征集，每个特征有严格定义并可在机器上高效实现，程序员可灵活运用这些特征表达它所希望的任何计算。,模型有力 Model Power语义清晰 Semantic Clarity移植性好 Portability可读性好 Readability,方便 Convenience简单 Simplicity高效 Efficiency灵活性 Flexibility,第6页,2.3 设计准则,频度准则 越常用越简单 方便、可读结构一致 程序结构和计算的逻辑结构一致 可读、方便局部性 Locality 只有全局变量Basic 不鼓励全局变量Pascal,C 无全局变量函数式 Java词法内聚 Lexical Coherence 变量在使用处就近声明（Pascal声明和语句严格分开）,(lambda(x y)(let(x 3.5)(y(+a 2)(+(*x y)(+(*x y)(-x y)(-x y)3.5(+a 2)x.y.(x*y)+(x-y)3.5(a+2),第7页,续,语法一致性 GO TO(L1,L2,Ln),I I=1.n GO TO N,(L1,L2,Ln)ASSIGN Li TO N N=L1.Ln安全性Security 语言编译系统自动找出安全漏洞，不能弥补也要支持 安全性强类型，即每个计算操作运算之前类型必须确定 C 留给程序员 过程参数不检查 一般不安全,第8页,续,正交性和正规性(Orthogonality&Regularity)正交:每个语言特征都是独立的,增减不影响其它 正规:每一约定或规则无一例外 不正规：数组不能作返回值,不能赋值 函数不能做参数 不正交不正规,第9页,续,数据隐藏(Data hiddening)封装,以名字封装内部数据设计者可见使用者不可见 局部性不一定封装，如：Do l0 I=1,10,2 当I=7时 GOTO 20 10 CONTINUE20.R=I 可以,此时R=7.0,.,第10页,续,抽象表达 抽取因子、递归表达、高层模块名、常量名=常量表达式（易于维护）先抽象再修饰具体（如同自然语言）static const int maxlndex=MAX_LENGTH_1MATHLIB.TRIANG COS(X)可移植性 力图不依赖环境 预定义机制、预处理程序,第11页,形式语法：以形式结构规则的语言元素组合规则微语法 词法 Lexicon宏语法 定义特征的规则,2.4 程序设计语言规格说明语言参考手册,2.4.1 语法规格说明,第12页,T是终结符号串的有限集。N是非终结符号串的有限集。TN=，即它们是不相交的。S是起始符号串，SN。P是产生式，一般形式是:，(TN)*“”表示左端可推导出右端，如，则可写为：|如果产生式将语言的非终结符中的每一个标记都推得为终结符号，则这一组产生式集即为该语言的全部文法。,2.4.1.1 文法文法 产生符合语法的语言（句子集合）规则，如：G=(S,N,T,P)SN,TN=*,第13页,整数的产生式表示法：设0|1|2|3|4|5|6|7|8|9则 一位数是整数 两位数也是 n位数也是 n个这势必造成产生式臃肿，如果写成：|,续,第14页,续,Chomsky的四种文法产生式 左符号集右符号集 由左符号集推导出右符号集0型文法(NT)+，(NT)*递归可枚举语言 图灵机可以识别1型文法 A B,(NT)*，AN，B(NT)+上下文相关文法上下文敏感语言 线性有界自动机可识别2型文法 A(NUT)*,AN 上下文无关文法语言 非确定下推自动机可识别,第15页,续,3型文法 ABB T*,A,BN 正则文法 正则语言 有限自动机可以识别 可消除右端非终法符 P可以成为终结符表达式 例：N=S,R,Q,T=a,b,c P=SRa，SQ，RQb，Qc 则有 SRaQbacba|SQc RQbcb Qc 简单语言用 3型，汇编，词法子语言 最常用 2型 0、1型无法判定二义性,不常用,0,1,2,3,第16页,2.4.1.2 上下文无关文法,文法的递归表示法 0123|4|5|6|7|89 一位数 二位数.n 位数 n个 左递归 右递归尾递归,第17页,2.4.1.3 BNF 和EBNF,BNF：:=代替 BNF表达能力同EBNF 指示非终结 终结符直接写出(或黑体)或者有扩充：括号内容是可选的 括号内容可重复0至多次或扩充：C+Kleene加 C可重复1至多次 C*Kleene星 C可重复0至多次,第18页,续,BNF示例:=|:=+|-|:=|,:=+|-:=|:=+:=|,第19页,EBNF：左端取消,空白加-减少递归表示再加(,),.,尽量用正则表达式 终结符号加 号或黑体,续,第20页,续,program:=；.program-heading:=program().program-parameters:=.identifier-list:=，.program-block:=.block:=.variable-declaration-part:=var；.variable-declaration:=；.statement-part:=compound-statement.,第21页,compound-statement:=begin end.statement-sequence:=；.statement:=：(|).simple-statement:=|.structured-statement:=|.,续,第22页,2.4.1.4 语法图,同EBNF 取消 以短路表示 以迥环表示,非终结符,走向,复合语句,;,begin,end,语句,终结符,终结符,第23页,2.4.1.5 语法分析,语法规格说明定义了该语言程序合法的特征和语句。语言处理器则通过语法分析接受合法的程序，这就叫做程序释义（Parsing a Program）,释义过程是产生式生成句子的逆过程。,语法分析的算法可归为两类：“自顶向下”释义则从文法的起始符开始，按可能产生的表达式寻找语句相同的结构匹配。每一步都产生下一个可能的源符号串，找到再往下走。“由底向上”释义则相反，它先查找源代码的各个符号串，看它能否匹配归结为产生式左边的非终结符，如果有含混则向前多读入k个符号串，为此归约下去，一个短语一个短语，最后到达起始符号串，归约的过程就形成了释义树。,第24页,begin x：=17；writeIn(x)end,标识符,变量标识符,变量访问,无符号常量,完整变量,无符号数,无符号整数,因子,项,简单表达式,表达式,过程标识符,标识符,变量标识符,完整变量,变量访问,因子,项,简单表达式,表达式,write参数,writeln参数表,赋值语句,简单语句,语句,过程语句,简单语句,语句,语句序列,复合语句,第25页,2.4.2 语义规格说明,操作语义:每一动作的净效果指称语义:语义函数（语法特征）语义域上的值 用辅助函数表征的值 用函数的数学模型只看最后效果，不考虑操作过程execute C1;C2 env sto=execute C2 env(execute C1 env sto)execute while E do C=let execute_while env sto=if evaluate E env sto=truth_value true then execute_while env(execute C env sto)else sto in execute_while,第26页,2.4.2 语义规格说明,公理语义：从程序的前题推导出结论前题 f1,f2,.,fn结论 f0 f1:pSq公式也是定理 p,q前后置断言,S语句集 x=a and y=b 只要前提为真结论亦为真 t:=x;x:=x+y;y:=t x=a+b and y=a,第27页,续,specification LISTS sorts List NATURALS formal sort Component Operations empty_list:List cons(_，_):Component,ListList headof_:List Component tailof_:List List lengthof_:List NATURALSs variables c:Component l:List equations headof cons(c,l)=c tailof cons(c,l)=l tailof empty_list=empty_list lengthof empty_list=0 lengthof cons(c,l)=succ(length of l)end specification,代数语义：把语义模型的集合看成是一个代数结构，模型簇 对应为代数系统 用代数方法描述数据类型 A=(V,Op),第28页,2.4.3 上下文规格说明,限定程序短语的良构规则简化语法语义形式化使上下文无关文法得以使用,