软件开发过程与项目管理综述

Part2高级语言及其语法描述授课：胡静内容提要程序语言的定义程序语言的语法定义程序语言的语义定义高级语言的一般特性高级语言的程序结构数据类型和操作语句与控制结构程序语言的文法关于文法的定义文法的类型上下文无关文法及其语法树有关文法实用中的一些说明程序语言的定义程序语言的语法定义任何语言程序都可以看成是一定字符集（称为字母表）上的一字符串（有限序列）。所谓一个语言的语法是指这样一组规则，用它可以形成和产生一个合式的程序。这些规则一部分称为词法规则则，另一部分称为语法规则（或产生规则）词法规则：词法规则规定了字母表中哪样的字符串是一个单词符号，是单词符号的形成规则语法规则：语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法规则是语法单位的形成规则程序语言的定义程序语言的语义定义所谓一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义。我们将要介绍的是目前大多数编译程序普遍采用的一种方法，即基于属性文法的语法制导翻译方法，虽然还不是形式系统，但是比较接近形式化的。高级语言的一般特征高级语言的程序结构程序子程序或分程序语句表达式数据引用算符函数调用数据类型和操作数据类型的要素：用于区别这种类型的数据对象的属性；这种类型的数据对象可以具有的值；可以作用于这种类型的数据对象的操作；数据类型分类：初等数据类型：数值数据、逻辑数据、字符数据、指针类型数据结构：数组、记录、字符串、表格、栈、队列和抽象数据类型（Ada通过程序包package提供，其余通过类class提供）语句与控制结构表达式：一个表达式是由运算量（操作数，即数据引用或函数调用）和算符组成的。语句：不同程序语言含有不同形式和功能的各种语句执行语句：描述程序的动作，分为赋值语句、控制语句、输入/输出语句；说明性语句：定义各种不同数据类型的变量或运算从形式上分，语句可以分为简单句、复合句和分程序等。程序语言的文法——相关定义字母表：字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此，字母表也称为符号集，记做∑字符串：由符号表中的符号组成的任何有穷序列称为符号串，不包含任何符号的序列称为空串，记为ε，Φ表示不含任何元素的空集。∑*符号串的长度：如果某符号串x中有m个符号，则称其长度为m，表示为|x|=m，即|ε|=0。符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。符号串的方幂：设x是符号串，把x自身连接n次得到的符号串z称为符号串x的方幂，写成z=xn。程序语言的文法——相关定义（续）符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。用∑*表示∑上的所有有穷长的串的集合，空串也包含在内。∑*的子集U和V的（连接）积定义为：UV={αβ|α∈U&β∈V}，一般而言，UV≠VUV的n次（连接）积记为Vn，规定V0={ε}V*称为V的闭包，V+=VV*，是V的正则闭包更多的概念和一些约定A,B,C,…用来表示非终结符a,b,c,…表示终结符…,X,Y,Z可以用来表示终结符或者非终结符…,w,x,y,z表示终结符号串α,β,γ,δ,…表示由终结符或非终结符构成的符号串在产生式A→α中，A是产生式的左边(lefthandside,LHS)α是产生式的右边(righthandside,RHS)A→α1|…|αn表示产生式A→α1,…,A→αn文法的直观概念EBNF(扩充的巴科斯－瑙尔范式)表示的句子的构成规则〈句子〉：：=〈主语〉〈谓语〉〈主语〉：：=〈代词〉|〈名词〉〈代词〉：：=我|你|他〈名词〉：：=王明|大学生|工人|英语〈谓语〉：：=〈动词〉〈直接宾语〉〈动词〉：：=是|学习〈直接宾语〉：：=〈代词〉|〈名词〉“我是大学生”的推导过程〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生关于文法的定义定义3.1文法G定义为四元组（VN,VT,P,S）。其中VN为非终结符号（或语法实体，或变量）集；VT为终结符号集；P为产生式（也称规则）的集合；VN,VT和P是非空有穷集。S称做识别符号或开始符号，它是一个非终结符，至少要在一条规则中作为左部出现。VN和VT不含公共元素，即VN∩VT=Φ。通常V表示VN∪VT，V称为文法G的字母表或字汇表。例3.1文法G=（VN，VT，P，S）VN={S},VT={0,1}P={S→0S1,S→01}S为开始符号关于文法的定义（续）定义3.2如α→β是文法G=(VN,VT,P,S)的规则(或说是P中第一个产生式)，γ和δ是V*中的任意符号，若有符号串v，w满足：v=γαδ，w=γβδ，则说v（应用规则α→β）直接产生w，或说w是v的直接推导。例：G：S→0S1，S→01S0S100S11000S11100001111关于文法的定义（续）定义3.3如果存在直接推导的序列：v=w0=w1=w2…=wn=w，(n0)，则称v推导出（产生）w（推导长度为n）。记做v=+w。定义3.4若有v=+w，或v=w，则记做v=*w。关于文法的定义（续）定义3.5设G[S]是一文法，如果符号串x是从识别符号推导出来的，即有S=*x，则称x是文法G[S]的句型。若x只由终结符号组成，则称x为G[S]的句子。定义3.6文法G所产生的语言定义为集合{x|S=*x，其中S为文法的开始符号，且x∈VT*}。可用L(G)表示该集合。例：G：S→0S1，S→01S0S100S11000S11100001111L(G)={0n1n|n≥1}关于文法的定义（续）定义3.7若L(G1)=L(G2)，则称文法G1和G2是等价的。例1：如文法G1[A]：A→0R与G2[S]：S→0S1等价A→01S→01R→A1例2：G1[E]:E→i与G2[E]：E→T|E+T等价E→E+ET→F|T*FE→E*EF→（E）|iE→(E)文法的类型Chomsky将文法分为四种类型：0型文法：对任一产生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*1型文法：对任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外2型文法：对任一产生式α→β，都有α∈VN，β∈(VN∪VT)*3型文法：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN，B∈VN，a∈VT。上述叫做右线性文法，另有左线性文法，二者等价。文法的类型举例1型（上下文有关）文法文法G[S]：S→CDAb→bAC→aCABa→aBC→bCBBb→bBAD→aDC→εBD→bDD→εAa→bDL(G)={ww|w∈{a,b}*}文法的类型举例2型（上下文无关）文法文法G[S]：S→aB|bAA→a|aS|bAAB→b|bS|aBB文法G[S]：S→0A|1B|0A→0A|1B|0SB→1B|1|0文法的类型举例定义标识符的3型（正规）文法文法G[I]：I→lTI→lT→lTT→dTT→lT→d文法和语言0型文法0型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法（上下文有关文法）产生式的形式为α1Aα2→α1βα2，即只有A出现在α1和α2的上下文中时，才允许β取代A。其识别系统是线性界限自动机。2型文法（上下文无关文法）产生式的形式为A→β，β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正则文法）产生的语言是有穷自动机（FA）所接受的集合上下文无关文法上下文无关文法有足够的能力描述现今程序设计语言的语法结构算术表达式语句赋值语句条件语句读语句……文法G=({E},{+,*,I,(,)},P,E}条件语句→if条件then语句P:E→i|if条件then语句else语句E→E+EE→E*EE→(E)上下文无关文法的语法树用于描述上下文无关文法的句型推导的直观方法例:G[S]:S→aASA→SbAA→SSS→aA→baSaASSbAba句型aabbaa的语法树（推导树）叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。aa上下文无关文法的语法树推导过程中施用产生式的顺序例:G[S]:S→aASA→SbAA→SSS→aA→baSaASSbAaabaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa文法的二义性最左（最右）推导：在推导的任何一步αβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型文法的二义性例：G[E]:E→iE→E+EE→E*EE→(E)EE+EE*EiiiEE*EiE+Eii句型i*i+i的两个不同的最左推导：推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i文法的二义性若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。部分二义文法可以改造为无二义文法G[E]:E→iG[E]：E→T|E+TE→E+ET→F|T*FE→E*EF→（E）|iE→(E)规定优先顺序（T）和结合律（左递归）Thanksforyourtime!Questions&Answers