edure =10 end (o) cedur d. hegin(。） call a: end () begin（s) callr: end (s) begin (p) call s: end (p): begin (main) call p: end (main). 3.写出题2中当程序编译到r的过程体时的名字表table的内容 table表 name kind level adr size 4.指出题2中各指针当前最新值及每个指针（栈顶指针T,最新活动记录基地址指 针B,动态链指针DL,静态链指针SL)的作用，与返回地址RA的用途。 5.PL/0编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该 汇编语言中下列指令各自的功能和所完成的操作 ·INT o A ·OPR oo ·CAL.oA 6.给出对PL/0语言作如下功能扩充时的语法图和BNF的语法描述 (1)扩充一维整型数组。 (2)扩充条件语句的功能使其为 if(条件then(语句)[else(语句)] (3)扩充reapeat语句为： ·27
reapeat(语句)unitl(条件) (4)扩充其他数据类型或语句，如： 记录型数据，for循环语句带参数的过程等。 7,对题6的(1)扩充给出 (1)符号表数据结构改动后的格式 (2)数组上下界的越界处理。 (3)数组元素地址计算方法。 (4)增加的目标指令形式及功能 8.给出对题6的(2)，(3)扩充时， (1)所生成的目标代码结构示意图。 (2)编译时此段目标代码生成的实现方法 28
第3章文法和语言 一个程序设计语言是一个记号系统，如同自然语言一样，它的完整的定义应包括语法 和语义两个方面，所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程 序目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法 的描述工具。语法只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系，比 如对于一个PASCAI,程序来说，一个上下文无关文法可以定义A=B+C是合乎语法 的，而A:=B十就不是。但是，如果B是实型的，而C是布尔型的，或者B,C中任何一个 变量没有事先说明，则A:=B十C仍不是正确的程序，也就是说程序结构上的这种特点 类型区配，变量作用域等是无法用上下文无关手段检查的，这些工作属于语义分析工 作。我们常常把程序设计语言的语义分为两类：静态语义和动态语义。静态语义是一系列 限定规则，并确定哪些合乎语法的程序是合适的：动态语义也称作运行语义或执行语义， 表明程序要做些什么，要计算什么」 明语法的 ,个工具是文法，这是形式语言理论的基本概念之一，本章将介绍文法和 语言的概念，重点讨论上下文无关文法及其句型分析中的有关问题。 阐明语义要比阑明语法困难得多，尽管形式语义学的研究已取得重大进展，但是仍没 有哪一种公认的形式系统可借助于来自动构造出正确的编译系统，本书不对形式语义学 进行介绍。 3.1文法的直观概念 在给出文法和语言的形式定义之前，我们先直观地认识一下文法的概念。 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句 子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出 它的有穷表示的问题 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则 来说明（或者定义）句子的组成结构，比如：“我是大学生”。是汉语的一个句子。汉语句子 可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用第2章所介绍的 EBNP来表示这种句子的构成规则： 〈句子)：=〈主语)（谓语） (主语)：=（代词）川（名词 (代词)：=我你他 〈名词：=王明|大学生工人英语 《谓语)：=〈动词)（直接宾语）》 (动词》：=是学习 ·29
〈直接宾语)：=〈代词)川（名词） “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是 句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种 元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。这样的语言描述称为文法 一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子，我们开始 去找：=左端的带有〈句子)的规则并把它表示成：=右端的符号串，这个动作表示成： (句子)→（主语）（谓语），然后在得到的串〈主语)（谓语）中，选取〈主语》或〈谓语)，再用相 应的规则：=右端代替之。比如，选取了《主语)，并采用规则（主语：=（代词），那么得 到：〈主语)（谓语）→（代词）（谓语），重复做下去，我们得到句子：“我是大学生”的全部动作 过程是： (句子)→（主语（谓语》 →（代词》（谓语 →我（谓语） →我（动词》（直接宾语】 →我是（直接宾语》 →我是（名词》 一我是大学生 符号→的含义是，使用一条规则，代替→左边的某个符号，产生→右端的符号串 显然，按照上述办法，不仅生成“我是大学生"这样的句子，还可以生成“王明是大学 生”，“王明学习英语”，“我学习英语”，’他学习英语”，“你是工人”，“你学习王明”等几十个 句子，事实上，使用文法作为工具，不仅为了严格地定义句子的结构，也是为了用适当条数 的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。 3.2符号和符号串 正如英语是由句子组成的集合，而句子又是由单词和标点符号组成的序列那样，程序 设计语言PASCAL或C,是由一切PASCAL或C程序所组成的集合，而程序是由类似 F,BEGN,END的符号，字母和数字这样-些基本符号所组成，从字面上看，每个程序都 是一个“基本符号”串，设有一基本符号集，那么PASCAL或C语言可看成是在这个基本 符号集上定义的，按一定规则构成的一切基本符号串组成的集合，为了给出语言的形式定 义，我们首先讨论符号和符号串的有关概念。 字母表字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此字母 表也称为符号集。不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字，数字 及标点符号等.PASCAL语言的字母表是由字母，数字，若干专用符号及BEGIN,.IF之类 的保留字组成。 符号串由字母表中的符号组成的任何有穷序列称为符号串，例如001】10是字母 表工={0,1}上的符号串，又如字母表A={a,b,c}上的一些符号串有：a,b,c,ab,aaca。在 符号串中，符号的顺序是很重要的，例如符号串ab就不同于ba,abca和aabc也不同。可 ·30
以使用字母表示符号串，如x=STR表示“x是由符号S、T和R,并按此顺序组成的符号 ” 如果某符号串x中有m个符号，则称其长度为m,表示为x=m,如001110的长度 是6。 允许空符号串，即不包含任何符号的符号串，用e表示，其长度为0，即|e=0。 下面介绍有关符号串的一些运算。 符号串的头尾，固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的 尾，如果×是非空的，那么y是周有尾；同样如果y非空，那么x是固有头设z=abc,那么 z的头是e,a,ab,abc,除abc外，其它都是固有头z的尾是e,c,bc,abc,z的固有尾是e,c, bc。 当我们对符号z=y的头感兴趣而对其余部分不感兴趣时，我们可以采用省略写法： =x.如果只是为了强调x在符号串z中的某处出现，则可表示为：2=x.符号t是 符号串z的第一个符号，则表示为zt.。 符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后 得到的符号串，例如设x=ST,y=abu,则它们的连接xy=STabu,看出x-2,y=3, xy=5。由于e的含义，显然有x=x=X 符号串的方幕：设×是符号串，把x自身连接n次得到符号串2，即z=xxxx,称为 符号串x的方幂，写作zx",也即把符号串×相继地重复写n次。x”=,x'=x,x2=xx,x =xxx分别对应于n=0,1.2和3.例如，设x=AB,则x°=e,x=AB,x2=ABAB,x- ABABAB。对于n>0,有x=xX-=X1X 符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表 上的符号串集合，两个符号串集合A和B的乘积定义如下：AB={xyx∈A且y∈B},即 AB是满足x属于Ay属于B的所有符号串xy所组成的集合。例如，若A=(ab},B= {c,d),则集合AB=(ac,ad,bc,bd》。因为对任意符号串x有ex-xe-x,所以有{e}A A(e)=A. 指定字母表Σ之后，可用Σ*表示Σ上的所有有穷长的串的集合。例如，如Σ={0,1} 则Σ ={e,0,1,00,01,10,11,000,001.010,.,也可表示为字母表的方幂形式： S*=E°LUΣUE.UΣ” Σ·称为集合三的闭包。而Σ=UΣ.称为Σ的正闭包。显然有 Σ‘=UΣ Σ+=Σ*=Σ*Σ Σ具有可数的无穷数量的元素。使用一般集合论的表示符号：若x是Σ·中的元素。 则表示为x∈三*，否则x年Σ*。对于所有的三，有e∈Σ”。 3.3文法和语言的形式定义 这里使用3.2所引用的术语，将3.1中描述汉语句子的规则加以形式化，然后给出文 314