高级语言及其语法描述21.ppt

第2章 高级语言及其语法描述,2.1 编译程序需要重点考虑的程序语言特性 2.2 符号和符号串 2.3 上下文无关文法 2.4 语法树和二义性 2.5 形式语言介绍,2.1 编译程序需要重点考虑的程序语言特性,1. 标识符与名字,标识符：字母打头的字母数字串。 名字：用标识符表示的，带有类型、值域的 程序语言对象。,高级语言之间的差异也是在这里体现的。,例： aa 标识符 real aa 名字，实型变量， 值域、运算确定。,2. 名字的定义,影响 - 目标程序的执行效率的高低。 能否静态分配存储空间； 能否作静态语义检查,例： int aa aa=12.3；,类型错误（静态语义检查）,全程变量：主程序中定义。 局部变量：过程/函数/分程序/对象 中定义。,影响：,3.变量的作用域,存储空间能否复用。 变量重名时的实现方法。 如：采用最小作用域原则。,4.语义,同一语句，在不同的语言中的含义可能不同。,例：数组 A13,14，访问: A2,3 Pascal：按行分配,FORTRAN：按列分配,a23地址=a11地址+7,访问: a23地址=a11地址+6,5.支持的数据类型，类型中允许的运算,基本数据类型: 整型，实型，布尔，字符，字符串 复杂数据类型： 数组，记录，结构，指针，集合,类 ,6.支持的语句,分支、循环、过程、函数,7. 存储空间分配方式,静态存储分配 动态存储分配,函数：允许递归调用时，每一次调用 需要一片数据区 动态数组 动态创建对象 用户可动态申请/释放数据空间,2.2 符号和符号串,字母表: 元素的非空、有穷集合。 符号：字母表中的元素。,例1: V=a,b,c 字母表 V 符号 a ，b , c 例2：单词符号集=if,then,begin,标识符,+,-, 字母表 单词符号集 符号 if,then,begin,标识符,+,-,3.符号串：符号组成的任何有穷序列。不包括任何符号的符号串称为空串（空字），记为。 注：符号串中符号的顺序是重要的。,例1: V=a,b,c 符号串：a,b,c,ab,ba,cc,aab 其中：abba 例2:单词符号集=if,then,begin,，标识符，+,-, 程序：由上述符号构成的一个符号串 但：任一符号串不一定是合法的程序。 编译研究：什么样的符号串是合法的程序。,4. 串的长度: 设是字母表V中的符号串， 的长度=中符号的个数。记为：| 5. 串的联结： 设、是字母表V中的符号串，联结是指： 将放在之后形成的符号串，记为：,例: V=a,b,c， 且有：=ab , =bca 则： = abbca ， = bcaab |=2, |=5 特别： , |= 0,6. 符号串集合： 由符号串构成的集合，记为： A= x | xA 7. 符号串集合的乘积: 若A,B是V上的符号串集合，A,B的乘积定义 为： AB= | A ,B ,例: 若： A=ab,ba, B=ca,acb 则： AB=abca, abacb, baca, baacb = = A = A = A,8.符号串的方幂： 对任意符号串， 0 = 1 = 2 = n =n-1 (n0),例: =ab 则：0 =， 1 =ab ， 2 = abab ， 3 = ababab,例: V=a,b,c V0 = 长度=0 的符号串的集合 V1 =a,b,c 长度=1 的符号串的集合 V2 =aa,ab,ac,ba,bb,bc,ca,cb,cc长度=2 的符号串的集合 V3 =aaa,aab,aac,aba,abb,abc长度=3 的符号串的集合 V100 长度=100 的符号串的集合 Vn 长度=n 的符号串的集合,9. 集合V的方幂：对任意集合V， V0 = ， V1 = V ， V2 = V V ， V3 = V V V Vn = V Vn-1 (n0),10. 集合的闭包： 设V为集合， V+ = V1 V2 V3 Vn 正闭包 V* = V0 V1 V2 V3 Vn 闭包 两种闭包之间的关系： V* = V0 V+ V+ = V V* = V* V 两个集合的乘积,2.3 上下文无关文法,1.产生式（产生规则，简称规则）： 一个有序对（A，），通常写作： A= 或 A A：符号，称为产生式左部； ：符号串，称为：产生式右部， 或：产生式的候选式,产生式的书写方式称为：BNF范式 若有产生式： A1 A2 An 写成：A1|2| |n,候选式,2. 文法GS： 产生式的非空有穷集合，S是一个符号，它至少要在一条产生式中作为左部出现，称为识别符号或开始符号，出现在产生式左部和右部中的所有符号形成字母表 V。,例: GE E E + T | T T T * F | F F i | (E) V = E , + , T, *, F, i, ( , ) ,产生式,识别符号或开始符号,3. 非终结符号： 给定文法G，把作为产生式左部出现的那些符号称为非终结符号，或语法实体，所有非终结符号汇集成：非终结符号集，记为：VN 。,例: GE E E + T | T T T * F | F F i | (E) - V = E , + , T, *, F, i, ( , ) VN = E, T, F ,左 部,4. 终结符号： 给定文法G，产生式中不属于VN 的那些符号称为终结符号，所有终结符号汇集成：终结符号集，记为：VT 。 由定义知：V = VN VT ，VN VT =,例: GE: E E + T | T T T * F | F F i | (E) V = E , + , T, *, F, i, ( , ) VN = E, T, F ， VT = + , *, i, ( , ) ,5. 上下文无关文法的形式定义： 上下文无关文法是一个四元组 GS = (VN , VT , P , S ) 其中：VN 非终结符号集合 VT 终结符号集合 P 产生式集合 S 文法的识别符号（开始符号）,6. 直接推导、直接归约： 令G为文法，、为符号串，若：A是一个产生式，称：A直接推导出，或直接归约为A。 记为：A=,例: GE: E E + E | EE | E * E | (E) | i 推导: E = E + E ( = , = ) E + E = E * E + E ( = , = + E ) i * E + E = i * i + E ( = i* , = + E ) E * E + i = E * i + i ( = E* , = + i ),7. 推导、归约：若存在一个直接推导序列 1 =2 =3 = =n 称：1 可以出推导n ,或n可归约为1 记为： 1 n （推导步骤0步，读作：+号推导出）, = ,或 ,即：,例: GE: E E + E | EE | E * E | (E) | i 从 E + E 到 i * i + i 的几种可能推导： E + E =E * E + E =i * E + E =i * i + E =i * i + i E + E =E + i =E * E + i =E * i + i =i * i + i E + E =E * E + E =E * E + i =E * i + i =i * i + i E + E =E * E + E =E * i + E =E * i + i =i * i + i,8. 最左推导、最右推导：推导中若每一步直接推导， 替换的都是符号串的最左非终结符，称为最左推导； 替换的都是符号串的最右非终结符，称为最右推导。,说明：,例: GE: E E + E | E E | E * E | (E) | i E =E + E =E * E + E =i * E + E =i * i + E =i * i + i,只要符号串中有产生式的左部符号，就能从该符号串 推导出新的符号串，即：推导过程未结束(非终结)， 所以左部符号称为非终结符号 Non-terminal symbol 符号串中没有产生式的左部符号了，那么推导过程就 必须终结。所以不在产生式的左部出现的符号称为 终结符号 Terminal symbol 故：非终结符集 VN 终结符集 VT,9. 句型、句子： 令GS为一文法，如果符号串是由文法的开始 符号推导出来的，即：S ，则称是句型。 若 S ，且 VT* ， 则称是句子。 （即：仅由终结符号构成的句型称为句子）,例: GE: E E + E | EE | E * E |(E)| i E = E + E = E * E + E = i * E + E = i * i + E = i * i + i 句型：E，E + E，E * E + E，i * E + E，i * i + E，i * i + i 句子：i * i + i,例: G1E: E E + E | E E | E * E | (E) | i L(G1E) = 带有+、-、*、扩号等运算的 算术表达式 ,说明： 句型集 （VNVT)* ， 即：句型集是符号串集的子集 L(GS) VT* ， 即：语言是终结符号串集的子集 句子是由文法决定的。 不同的文法可以产生相同的语言， 即：G1SG2S ，但 L(G1S)=L(G2S) 则称文法 G1S、G2S 等价。,G1EG2E，但 L(G1E) = L(G2E) 称：文法 G1E、G2E 等价。 即：不同的文法，可以产生相同的语言。,例: G1E: E E + E | E E | E * E | (E) | i L(G1E)=带有+、-、*、扩号等运算的算术表达式 G2E: E E + T | E T | T T T * F | F F (E) | i L(G2E)= 带有+、-、*、扩号等运算的算术表达式 ,例: GS: S bA A aA|a 句子： S = bA= ba S = bA = baA = baa S = bA = baA = baaA = baaa S = bA = baA =baaA = = baaaA = baaa L(GS) = ban | n1 ,例: GS: S PQ P aPb| ab Q Qc| 句子： S = PQ = abQ = ab S = PQ = aPbQ = aaPbbQ =+= aabb S = PQ=+= aabbQc =+= aabbcc L(GS) = anbncm | n1, m0 ,2.4 语法树和二义性,1.语法树: 用图表示一个句型的推导过程。通常表示成一棵倒立的树。树根表示文法开始符号；,S,A,a1 a2 a3 an,若有直接推导: A=a1a2an， 则从结点A出发，划出n个分支， 指向n个结点：a1 ,a2 ， an,语法树末端结点：再没有分支从中向下射出的结点。 从左向右遍历语法树末端结点，形成该树表示的句型。,例: GE: E E + T | T T T * F | F F i |(E) i*i+i 推导过程： E = E + T = T + T = T * F + T = F * F + T = i * F + T = i * i + T = i * i + F = i * i + i 末端结点：i、*、i、+、i 语法树对应的句型：i*i+i,2.子树：由语法树的某个结点（子树根），连 同从它向下射出的部分组成的。 子树的末端结点形成一个短语(相对于子树根).,子树: i1 (F2) ，i1 (T3) , i2 (F1) ， i1 * i2 (T2) ，i1 * i2 (E2) ， i3 (F3) ，i3 (T1) , i1 * i2 + i3 (E1),总结：,例: GE: E E + T | T T T * F | F F i |(E) 句型：T + F * F 推导1：E = E + T = T + T = T + T * F = T + F * F 推导2：E = E + T = E + T * F = E + F * F = T + F * F 推导3：E = E + T = E + T * F = T + T * F = T + F * F,对于每个语法树，至少存在一个推导； 对于每个推导，都有一个对应的语法树； 若不同的推导产生相同的语法树，称这些推导是等价的；,3.二义性： 句子的二义性：若文法G中，某一个句子有两棵不同的语法树，称该句子是二义的。,例: GE: E E + E | E E | E * E | (E) | i 句子： i + i * i 如：2 + 3 * 4,语 法 树 1,( 2 + 3)* 4 = 20,2 +( 3 * 4)= 14,语 法 树 2,句子二义性的等价定义 若文法G中，某一个句子存在两个不同的最左推导，称该句子是二义的。 若文法G中，某一个句子存在两个不同的最右推导，称该句子是二义的。,例: GE: E E + E | E E | E * E | (E) | i 句子： i + i,最左推导：E=E+E=i+E=i+i 最右推导：E=E+E=E+i=i+i,误解：有两个不同的推导，就是二义的句子,文法的二义性：如果一个文法包含有一个二义性的句子，称该文法是