高级语言及其语法描述21

《高级语言及其语法描述21》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、号：字母表中的元素。例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…其中：ab≠ba例2:单词符号集={if,then,begin,…，标识符，+,-,…}程序：由上述符号构成的一个符号串但：任一符号串不一定

5、是合法的程序。编译研究：什么样的符号串是合法的程序。4.串的长度:设α是字母表V中的符号串，α的长度=α中符号的个数。记为：

6、α

7、5.串的联结：设α、β是字母表V中的符号串，α联结β是指：将β放在α之后形成的符号串，记为：αβ例:V={a,b,c}，且有：α=ab,β=bca则：αβ=abbca，βα=bcaab

8、α

9、=2,

10、αβ

11、=5特别：αβ≠βα,

12、ε

13、=06.符号串集合：由符号串构成的集合，记为：A={x

14、x∈A}7.符号串集合的乘积:若A,B是V上的符号串集合，A,B的乘积定义为：AB={αβ

15、α∈A,β∈B}例:若：A={ab,ba

16、},B={ca,acb}则：AB={abca,abacb,baca,baacb}∵εα=αε=α∴{ε}A=A{ε}=A8.符号串的方幂：对任意符号串α，α0=εα1=αα2=αα…αn=ααn-1(n>0)例:α=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

17、长度=100的符号串的集合Vn长度=n的符号串的集合9.集合V的方幂：对任意集合V，V0={ε}，V1=V，V2=VV，V3=VVV…Vn=VVn-1(n>0)10.集合的闭包：设V为集合，V+=V1∪V2∪V3…∪Vn∪…正闭包V*=V0∪V1∪V2∪V3…∪Vn∪…闭包两种闭包之间的关系：V*=V0∪V+V+=VV*=V*V——两个集合的乘积§2.3上下文无关文法1.产生式（产生规则，简称规则）：一个有序对（A，α），通常写作：A∷=α或A→αA：符号，称为产生式左部；α：符号串，称为：产生式右部，或：产生式的候选式产生式的书写方式称为：B

18、NF范式若有产生式：A→α1A→α2…A→αn写成：A→α1

19、α2

20、…

21、αn候选式元符号→：定义为

22、：或2.文法G[S]：产生式的非空有穷集合，S是一