2-高级语言及其语法描述

资源描述

《2-高级语言及其语法描述》由会员分享，可在线阅读，更多相关《2-高级语言及其语法描述（44页珍藏版）》请在金锄头文库上搜索。

1、第2章高级语言及其语法描述 2.1 编译程序需要重点考虑的程序语言特性2.2 符号和符号串2.3 上下文无关文法2.4 语法树和二义性2.5 形式语言介绍2.1 编译程序需要重点考虑的程序语言特性1. 标识符与名字标识符：字母打头的字母数字串。名字：用标识符表示的，带有类型、值域的程序语言对象。高级语言之间的差异也是在这里体现的。例： aa 标识符real aa 名字，实型变量，值域、运算确定。2. 名字的定义影响 - 目标程序的执行效率的高低。能否静态分配存储空间；能否作静态语义检查类型名字定义方式典型语言显式定义名字的类型必须定义C, Pascal隐式定义名字的类型可以定义或者不

2、定义,未定义的名字的类型按照缺省定义处理。FORTRAN(I-N规则)不定义名字的类型不必定义。根据运行时名字的取值动态确定。早期的BASIC,VFP例： int aaaa=12.3；类型错误（静态语义检查）全程变量：主程序中定义。局部变量：过程/函数/分程序/对象中定义。影响：3.变量的作用域存储空间能否复用。变量重名时的实现方法。如：采用最小作用域原则。4.语义同一语句，在不同的语言中的含义可能不同。例：数组 A1.3,1.4，访问: A2,3Pascal：按行分配a11 a12 a13 a141a21 a22 a23 a242a31 a32 a33 a343a11a12a13

3、a14a21a22a23a24a31a32a33a34 1234FORTRAN：按列分配a23地址=a11地址+7访问: a23地址=a11地址+65.支持的数据类型，类型中允许的运算基本数据类型: 整型，实型，布尔，字符，字符串复杂数据类型：数组，记录，结构，指针，集合,类 6.支持的语句分支、循环、过程、函数7. 存储空间分配方式静态存储分配动态存储分配函数：允许递归调用时，每一次调用需要一片数据区动态数组动态创建对象用户可动态申请/释放数据空间2.2 符号和符号串1.字母表: 元素的非空、有穷集合。2.符号：字母表中的元素。例1: V=a,b,c 字母表 V 符号 a ，

4、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. 串的联结：

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 = A8.符号串的方幂：对任意符号串，0 = 1 = 2 = n =n-1 (n0) 例: =ab 则：0 =，

6、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

7、正闭包 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。

9、 = VN VT ，VN VT =例: GE: E E + T | TT T * F | FF 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 *

10、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步，读作：+号推导出） = 或，表示推导步骤0步，（读作：*号推导出）即：例: GE: E E + E | EE | E * E | (E) | i 从 E + E 到 i *

11、i + i 的几种可能推导：E + E =E * E + E =i * E + E =i * i + E =i * i + iE + E =E + i =E * E + i =E * i + i =i * i + iE + E =E * E + E =E * E + i =E * i + i =i * i + iE + E =E * E + E =E * i + E =E * i + i =i * i + i8. 最左推导、最右推导：推导中若每一步直接推导，替换的都是符号串的最左非终结符，称为最左推导；替换的都是符号串的最右非终结符，称为最右推导。说明：例: GE: E E + E | E E

12、 | 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 终结符集 VT9. 句型、句子：令GS为一文法，如果符号串是由文法的开始符号推导出来的，即：S ，则称是句型。若 S ，且 VT* ，则

13、称是句子。（即：仅由终结符号构成的句型称为句子）例: 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 + i10. 语言：令GS为一文法，G 所产生的句子的全体是一个语言。记为：L(G), L(GS) =| S ，且VT* 例: 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 | TT T *

展开阅读全文

2-高级语言及其语法描述

最新文档