第一章 高级语言与编译程序概述

典型例题: 单项选择题

1.1.1．将编译程序分成若干个“遍”是为了___。 a.提高程序的执行效率 b.使程序的结构更加清晰

c.利用有限的机器内存并提高机器的执行效率 d.利用有限的机器内存但降低了机器的执行效率 1.1.2．构造编译程序应掌握____。（陕西省2000年自考题） a.源程序 b.目标语言 c.编译方法 d.以上三项都是 1.1.3．变量应当＿。

a.持有左值 b.持有右值

c.既持有左值又持有右值 d.既不持有左值也不持有右值 1.1.4．编译程序绝大多数时间花在____上。（陕西省1998年自考题） a.出错处理 b.词法分析 c.目标代码生成 d.管理表格

1.1.5．____不可能是目标代码。 ( 陕西省1997年自考题) a.汇编指令代码 b.可重定位指令代码 c.绝对指令代码 d.中间代码

1.1.6．数组A[1?20,1?10]的首地址偏移量为0，按列存储，每个元素占一个字节，存储器 按字节编址，则A[i,ｊ］的偏移地址为____。 a.(i-1)X10+（j-1） b.(i-1)X20+(j-1) c. (i-1)＋(j-1)X10 d.(i-1)+(j-1)X20 1.1.7.使用____可以定义一个程序的意义。 a.语义规则 b.词法规则 c.产生规则 d.左结合规则

1.1.8．表达式X:=5中，变量x____。 a.只有左值 b.只有右值

c.既有左值又有右值 d.没有左值也没有右值 1.1.9．词法分析器的输入是__。 a.单词符号 b.源程序 c.语法单位 d.目标程序

1.1.10．中间代码生成时所遵循的是＿。 a.语法规则 b.词法规则 c.语义规则 d.等价变换规则 1.1.11．编译程序是对__。

a.汇编程序的翻译 b.高级语言程序的解释执行 c.机器语言的执行 d.高级语言的翻译

1.1.12．词法分析应遵循＿。 （陕西省2000年自考题） a.语义规则 b.语法规则

c.构词规则 d.等价变换规则

多项选择题：

1.2.1 编译程序各阶段的工作都涉及到___。 （陕西省1999年自考题） a.语法分析 b.表格管理 c.出错处理 d.语义分析 e.词法分析

1.2.2下列各项中，____与数组元素的地址有关。 （陕西省1999年自考题） a.数组第一个元素的存储地址 b.数组的存储方式 c.数组的维数 d.内存的编址方式 e.编译程序

1.2.3 编译程序工作时,通常有__阶段。 （陕西省1998年自考题） a.词法分析 b.语法分析 c.中间代码生成 d.语义检查 e.目标代码生成

1.2.4 过程调用的参数传递方式有__。 a传名 b.传值 c.传参数 d.传地址 e.传结果

1.2.5 编译过程中所遵循的规则有____。 a.等价变换规则b.短语规则c.构词规则 d. 语义规则 e.语法规则

填空题：

1.3.1 解释程序和编译程序的区别在于＿。

1.3.2 编译过程通常可分为5个阶段，分别是＿、语法分析、＿、代码优化和目 标代码生成。（陕西省1999年自考题）

1.3.3 编译程序工作过程中，第一阶段输入是＿，最后阶段的输出为一程序。

（陕西省1997年自考题） 1.3.4 静态数组元素地址的计算公式由两部分确定，一部分是＿，它在＿时确定； 另一部分是＿，它在＿时确定。

1.3.5 把语法范畴翻译成中间代码所依据的是语言的＿。（陕西省2000年自考题） 1.3.6 目标代码可以是＿指令代码或＿指令代码或绝对机器指令代码。

（陕西省2000年自考题） 1.3.7 编译程序是指能将____程序翻译成____程序的程序。

1.3.8 数组元素的地址由___和___组成，其中＿中的a和c在翻译数组说明语句时填入到数组的＿中。

1.3.9 过程调用时，参数传递的方式有______、______、_____。

1.3.10 词法分析所遵循的是语言的______，而中间代码生成所遵循的是语言的_____。 （陕西省1997年自考题） 1.3.11 数组元素的地址计算与数组的_____数及____方式有关，也与数组的类型及机器对存 储器的编址方式有关。 （陕西省2000年自考题）

判断题：

1.4.1．赋值号左边的变量只持有左值，不持有右值。 （ ） 1.4.2．二维数组a[3?15,5?20]按行存放，并且每个元素占用一个存储单元，则数组元素a[i ,j]的地址为base-85+i X 16+j (base是数组a存放的起始地址）。 （ ）

1.4.3．变量的名字用标识符来表示，同时名字代表一定的存储单元，有属性、值、作用域等特性。 （陕西省1997年自考题） （ ） 1.4.4．指示器变量的右值只持有右值，没有左值。（陕西省2000年自考题） （ ） 1.4.5．般而言，中间代码是一种独立于具体硬件的记号系统。 （ ）

综合题

1.5.1 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？

1.5.2 何谓“标识符”，何谓“名字”，两者的区别是什么？

1.5.3 简述在过程调用中，形参和实参间常见的各种信息传递方式（即形实结合方式）的含义。

1.5.4 画出编译程序的总体结构图，简述各部分的主要功能。

1.5.5 对于下面的程序： PROCEDURE P(x,y,z)； BEGIN｛P｝ y：=y+l； Z：=Z+X END；｛P｝ BEGIN { main} A：=2； B：=3；

P（A+B,A,A）； Print A

END．{ main}

若参数传递的办法分别为（1)传名，(2）传地址，(3）传结果，(4)传值；试问，程序 执行时所输出的A值分别是什么？

1.5.6 对于下面的程序：

PROGRAM main； a:integer；

PROCEDURE test(x：:integer)； temp:integer； BEGIN {test}

x：=a+l； Temp：=a+2

x：=temp END；{ test} BEGIN a:=2； test(a)； print(a)

END．

分别给出参数传递为传地址、传结果、传值和传名时a的输出结果。

1.5.7 三维数组a[2:5,-2:2,5:7]首址为100,每个数组元素占4个存储单元，求数组元素a[3,1,6] 的地址。

1.5.8 什么叫自展？什么叫交叉编译？

1.5.9 试分析编译程序是否分遍应考虑的因素及多遍扫描编译程序的优缺点。

1.5.10 请画出编译程序的总框。如果你是一个编译程序的总设计师，应当考虑哪些问题？

（国防科大2000年研究生试题）

1.5.11 对于下面说明语句所定义的数组A array A[-2:3,-5:5]

假定数组按行存放，存储器按字节编址，每四个字节为一机器字，令A的首地址为1000，问A[i+3,j+2]的首地址是什么？（写出步骤）（同济大学1998年研究生试题）

1.5.12 数组var a：array[1..5,-3..6] of integer；按列存放，其首址100,每个整数占4个字节，内存按字节编址，则数组元素a[4,3]的地址是什么？ （上海交大1997年研究生试题）

1.5.13 对于下面的程序段

?

procedure P(x,y,z) begin

y：=y*2；;

z：=x+z； end； begin

a：=5； b：=2； p(a*b,a,a)； print(a) end．

若参数传递的方法分别为（1)传值、(2)传地址、(3)传名，试问程序执行所输出的结 果分别是什么？

1.5.14 有一段程序为： PROGRAM sample; x：integer；

PROCEDURE sun(m：integer)； BEGIN｛sun｝ M：=11； x：=m+ END；｛sun｝ BEGIN

X：=100； sun（x）； write（x） END；

请用（1）传地址；（2）传值；（3）传结果；(4)传名的参数传递方式，给出程序的运行 结果。

1.5.15有一程序如下：

PROGRAM ex； a：integer；

PROCEDURE PP(x：integer)； BEGIN｛PP｝ a：=5；x：=a+1 END；｛PP｝ BEGIN a：=2； PP（a）； write（a） END ． 用（1)传地址；(2)传值；（3)传结果；(4)传名等4种参数传递方式，；试写出程序的 运行结果。

5

※<习题二>

第二章 词法分析

典型例题: 单项选择题

1.1.1．词法分析所依据的是____。 a.语义规则 b.构词规则 c.语法规则 d.等价变换规则

1.1.2．词法分析器的输出结果是____。

a.单词的种别编码 b.单词在符号表中的位置 c.单词的种别编码和自身值 d.单词自身值 1.1.3．正规式MI和M2等价是指____。

a. MI和M2的状态数相等 b.Ml和M2的有向弧条数相等。

C.M1和M2所识别的语言集相等 d. Ml和M2状态数和有向弧条数相等 1.1.4．状态转换图（见图2.5），接收的字集为：

图2.5

a.以0开头的二进制数组成的集合 b.以0结尾的二进制数组成的集合 c.含奇数个0的二进制数组成的集合 d.含偶数个0的二进制数组成的集合

1.1.5．词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此___。 a.词法分析器应作为独立的一遍 b.词法分析器作为子程序较好

c.词法分析器分解为多个过程，由语法分析器选择使用 d.词法分析器并不作为一个独立的阶段 1.1.6．词法分析器的输入是—。 a.单词符号串 b.源程序 c.语法单位 d.目标程序 1.1.7.如果L(M)=L(M'），则M与M'__。（陕西省1999年自考题） a. 等价 b．M与M'都是二义的 c. M与M'都是无二义的 d. 他们的状态数相等

1.1.8．图2.56所示的状态转换图接受的字集所对应的正规式为＿。（陕西省1997年自考题）

a. a*b*(aa|bb)a*b* b. (a|b)*(aa|bb)(a|b)

c. (a*|b*)(aa|bb)(a*|b*) d. (a*|b*)aa(a*|b*)|(a*|b*)bb(a*|b*)

图2.56 状态转换图

多项选择题：

1.2.1在词法分析中，能识别出＿。 （陕西省1998年自考题） a.基本字 b.四元式 c.运算符 d.逆波兰式 e..常数

1.2.2令∑={a,b}，则∑上所有以b开头，后跟若干个ab的字的全体对应的正规式为＿。 a．b(ab)* b.b(ab) c.(ba)* b d.(ba)+b e. b(alb)*

1.2.3设∑={0,1}，则∑上字的全体可用正规式_____表示。 a.(1|0)* b.(1*|0*)* c.(1|0)+ d.(1*0*)* e.(10)*

填空题：

1.3.1 确定有限自动机DFA是_______的一个特例。

1.3.2 若二个正规式所表示的______相同，则认为二者是等价的。（陕西省1997年自考题） 1.3.3 一个字集是正规的，当且仅当它可由______所______（陕西省1997年自考题）

判断题：

1.4.1．一个有限状态自动机中，有且仅有一个唯一的终态。 （ ） 1.4.2．设r和s分别是正规式，则有L(r|s)=L(r)|L(s) （ ）

1.4.3．自动机M和M'的状态数不同，则二者必不等价。 （ ） 1.4.4．确定的自动机以及不确定的自动机都能正确地识别正规集。 （ ） 1.4.5．对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。 （ ） 1.4.6 对任意一个右线性文法G,都存在一个DFA M,满足L(G}=L(M) 。 （ ） 1.4.7 对任何正则表达式e,都存在一个NFA M,满足L(G)=L(e) 。 （ ） 1.4.8 对任何正则表达式e,都存在一个DFA M,满足L(G)=L(e)。 （ ） 1.4.9 两个正规集相等的必要条件是他们对应的正规式等价。（） 1.4.10 词法分析作为单独的一遍来处理较好。（）

1.4.11 一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（）

综合题

1.5.1 什么是扫描器？扫描器的功能是什么？

1.5.2 给出字母表∑上的正规式及其所描述的正规集的递归定义。

1.5.3 正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言能力上是否相互等价？

1.5.4 已知Pascal语言的实数表示规则如下： （1)实数十进制表示

(a)实型数的小数点前后必须出现数字： (b）必须出现小数点。

（2）实数科学表示（指数形式） (a)字母e表示以十为底的指数；

(b）字母e前必须出现实数或者整数；

（c）字母e后必须出现整数，这个整数表示实型数的指数部分。 试画出该实数对应的状态转换图。

1.5.5 设M= <{x,y}，{a,b) ,f,x, {y})为一非确定的有限自动机，其中f定义如下：

f(x,a)=｛x,y｝ f｛a,b｝=｛Y)

f(Y,a)=φ f｛y,b｝＝｛x,y｝ 试构造相应的确定有限自动机M`。

＋

1.5.6 (1）对给定正规式b*(d|ad) (b|ab)，构造其NFA M； （陕西省1997年自考题） （2) 对给定正规式(a|b)*a (a|b)，构造其DFA M。 （中科院计算所1997年研究生试题）

1.5.7 构造一个DFA,它接收∑=｛a,b｝上的所有满足下述条件的字符串，即该字符串中的每个a都有至少一个b直接跟在其右边。

1.5.8 有穷状态自动机M接受字母表∑＝{0，1｝上所有满足下述条件的串：串中至少包含两个连

续的0或两个连续的1。

（1)请给出与M等价的正规（则）式。 （2）将M最小化。

（3）构造与M等价的正规文法。

1.5.9 构造正规表达式((a|b)*|bb)*的ＤＦＡ（要求写出步骤）。

1.5.10 设有L(G)={a2n+1b2ma2p+1|n≥0,p≥0,m≥1} （1)给出描述该语言的正规表达式。

(2)构造识别该语言的确定的有穷自动机（可直接用状态图形式给出）。

1.5.11 请写出在∑＝(a,b)上，不是a开头的，但以aa结尾的字符串集合的正规表达式，并构造与之等价状态最少的DFA。

＋

1.5.12 有语言L={w|w∈(0,1），并且w中至少有两个1，又在任何两个1之间有偶数个0，试构造接受该语言的确定有限状态自动机（DFA）。

1.5.13 已知正规式(1)((a|b)*|aa)*b和正规式(2)(a|b)*b。 (1)试用有限自动机的等价性证明正规式(1)和(2)是等价的。 (2）给出相应的正规文法。

1.5.14 某操作系统下合法的文件名为device:name.extension,其中第一部分（device:）和第三部分（.extension)可缺省，若device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。

1.5.15 Pascal语言无符号数的正规定义如下： Num→digit+(.digit+)?(E(+|-)?digit+)?

其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。

1.5.16 在C语言中无符号整数可用十进制（非0打头）、八进制（0打头）和十六进(0X打头）表示，试写出其相应的文法和识别无符号数的DFA(假定位数不限)。

1.5.17 下列程序段若以B表示循环体，A表示初始化，I表示增量，T表示测试。 I:=1；

while I<=n do begin

sun:=sun+a[I];

I:=I+l End

请用正规表达式表示这个程序段可能的执行序列。

1.5.18 在操作系统的进程管理中，进程的状态转换如图2.50所示。假设现有两个进程Pi和CPU每次只能运行一个进程。当P1、P2都处于就绪状态时为初态，当P1、P2都处于睡眠状态时为终态。请用一个有限自动机来描述这个进程管理系统。

图2.50 进程状态转换图

1.5.19 有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中

投放≥3分的硬币，便可得到一块糖（注意：只给一块并且不找钱）。 (1)写出售货机售糖的正规表达式。 (2)构造识别上述正规式的最简DFA。

1.5.20 证明：一不含无用状态的有限自动机M的接收集L(M)是无限集，当且仅当M相应的状态转换图中含有回路。

1.5.21 假定A和B都是正规集，请用正规集与有限自动机的等价性说明A∪B也是正规的。

1.5.22 下面的正规式等价吗？为什么？ (1)(a|b)* (2) (a*|b*)* (3)((ε|a)b*)*

1.5.23 （电子科大1996年研究生试题） 构造识别下列单词符号的状态转换图：

begin end标识符正整数＋－***，．∷＝

1.5.24 （清华大学1998年研究生试题） 请将图2.57所示的有穷自动机M1最小化。

图2.57 有穷自动机M1

1.5.25 （清华大学1998年研究生试题） 将有穷自动机M2确定化

M2=({U,V,W,X}，10,1｝,f,{U}，{W}） 其中：f(U,0）＝φ f(U,1）＝｛V,X} f(V,0)={V} f(V,l）＝tvlwl f(W,0)={X｝ f(W,1)＝{W} f(X,0)={X} f(X,1）＝{X}

1.5.26 （清华大学1998年研究生试题） 将图2.58所示的DFA最小化。

图2.58 DFA

1.5.27 （中科院计算所1997年研究生试题） 为正规式(a|b) *a(a|b)构造一个确定的有限自动机。

1.5.28 （南开大学1998年研究生试题） 写出正规式(alb) *(aa|bb)(a|b)*的DFA。

1.5.29 （复旦大学1999年研究生试题）

将图2.59所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。

图2.59 NFA

其中，X为初态，Y为终态。

1.5.30 （上海交大1997年研究生试题）

请构造与正规式R=(a*|b*)b(ba)*等价且状态最少的DFA。

1.5.31 （国防科大1999年研究生试题）

构造一个确定的有限自动机DFA,它接受∑＝{0,1}上的所有不带前导0的二进制区数。

1.5.32 （国防科大2000年研究生试题）

已知DFA M如图2.60所示。

图2.60 DFA M

请给出M所识别的字的全体L(M)。

1.5.33 （华中理工2001年研究生试题）

构造一个确定的有穷自动机DFA M,它识别∑={a,b}上所有满足如下条件的字符串：字 符串由a, b组成，且其中b的个数为3k (k≥0)。

1.5.34 （华中理工2001年研究生试题）

正规式(ab）*a与正规式a(ba) * 是否等价？请说明理由。

1.5.35 DFA与NFA有何区别

5

※<习题三>

第三章 语法分析

典型例题: 单项选择题

3.1.1. 文法G: S-xSxly所识别的语言是_____（陕西省1997年自考题） a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx* 3.1.2. 文法G描述的语言L(G)是指_____。

a. L(G)=｛α|S=>α，α ∈VT*｝b. L(G)={ α|SA=>α,α ∈VT*｝

c．L(G)={ α|S=>α，α∈(VT∪VN)*｝d. L(G)=｛α|S=>α,α∈(VT∪VN)*｝ 3.1.3. 有限状态自动机能识别＿。

a.上下文无关文法 b.上下文有关文法 c.正规文法 d.短语文法

3.1.4. 设G为算符优先文法，G的任意终结符对a, b有以下关系成立____。 a.若f(a)>g(b)，则a>b b.若f(a)

3.1.5．茹果文法G是无二义的，则它的任何句子α_＿。（西电1999年研究生试题） a.最左推导和最右推导对应的语法树必定相同 b.最左推导和最右推导对应的语法树可能不同 c.最左推导和最右推导必定相同

d.可能存在两个不同的最左推导，但它们对应的语法树相同

3.1. 6.由文法的开始符经。步或多步推导产生的文法符号序列是____。

（陕西省2000年自考题）

a．短语 b.句柄 c.句型 d.句子

3.1.7．文法G：E-E+TIT T-T*P|P P-(E)|I

则句型P+T+i的句柄和最左素短语分别为__＿。 a. P+T和i b. P和P+T c. i和P+T+i d. P和P 3.1.8．设文法为：S--SA|A A→a|b

则对句子aba，下面____是规范推导．

a. S=>SA=>SAA=>AAA=>aAA=>abA=>aba b. S=>SA=>SAA=>AAA=>AAa=>Aba=>aba c. S=>SA=>SAA=>SAa=>Sba=>Aba=>aba d. S=>SA=>Sa=>Sba=>Aba=>aba 3.1.9.文法G: S→b|∧|(T) T-T,SIS

则FIRSTVT(T)=____。 a.｛b，∧，（｝ b.｛b，∧，）｝ c.｛b,∧，（，,｝ d.{b, ∧，），，｝

3.1.10．产生正规语言的文法为____＿。 a. 0型 b. 1型 c. 2型 d. 3型

3.1.11．任何算符优先文法—优先函数。

a.有一个 b.没有 c.有若干个 d.可能有若干个 3.1.12.采用自上而下分析，必须____＿。 a.消除左递归 b.消除右递归 c.消除回溯． d.提取公共左因子

3.1.13．设a, b, c是文法的终结符，且满足优先关系a=b和b=c，则_____＿。 a.必有a=ｂ b．必有c=a

c.必有b=a d. a~c都不一定成立 3.1.14.在规范归约中，用___＿来刻画可归约串。（陕西省1999年自考题） a.直接短语 b.句柄 c.最左素短语 d.素短语 3.1.15.有文法Ｇ：E→E*T|T T→T+i|i

句子1+2*8+6按该文法G归约，其值为___＿。 a.23 b.42 c.30 d.17 3.1.16.规范归约是指________。（陕西省９８年自考题） a.最左推导的逆过程 b.最右推导的逆过程 c.规范推导 d.最左归约的逆过程 3.1.17.一文法G:S→S+T|T．（陕西省1998年自考题） T→T*P|P P→(S)|i

则句型P+T+i的短语有___＿。

a. i,P+T b. P,P+T,i,P+T+i c. P+T+i d. P, P+T,i

多项选择题：

3.2.1.下面哪些说法是错误的___＿。（陕西省1998年自考题）

a. 有向图是一个状态转换图 b.状态转换图是一个有向图

c． 状态转换图可以用DFA表示 d. DFA可以用状态转换图表示 e.有向图是一个DFA

3.2.2.对无二义性文法来说，一棵语法树往往代表了___＿。 a.多种推导过程 b.多种最左推导过程 c.一种最左推导过程 d.仅一种推导过程 e.一种最右推导过程

3.2.3．如果文法G存在一个句子，满足下列条件___之一时，则称该文法是二义文法。

a.该句子的最左推导与最右推导相同 b、该句子有两个不同的最左推导 c.该句子有两个不同的最右推导 d,该句子有两棵不同的语法树 e.该句子的语法树只有一个

3.2.4.语法分析时通过___＿操作使用符号栈。（陕西省2000年自考题） a. 移进 b. 归约 c. 比较 d. 接受 e. 出错处理

3.2.5.算符优先文法与算符优先函数的关系描述中，下列__＿正确。（陕西省1997年自考题）

a、一个算符优先文法可能不存在算符优先函数与之对应 b. 一个算符优先文法可能存在多对算符优先函数与之对应 c.一个算符优先文法一定存在多对算符优先函数与之对应 d.一个算符优先文法一定存在算符优先函数与之对应

e.一个算符优先文法一定存在有限对算符优先函数与之对应

3.2.6.有一文法G: S--AB （陕西省1998年自考题）

A--aAb|ε B一cBd|ε 它不产生下面__＿集合。

a. {anbmcndm|n,m≥0} b. {anb\｝ c. {anbmcmdn|n,m≥0} d. {anbncmdm|n,m≥0} e. {anbncndn|n≥0}

3.2.7．文法的无二义性是指_________。

a.文法中不存在句子有两个不同的最左推导 b.文法中不存在句子有两个不同的最右推导 c.文法中不存在句子有不同的推导

d.文法中不存在句子有两裸不同的语法树 e.文法中不存在句子有不同的最左和最右推导 3.2.8. 文法G：S→aAcB|Bd A→AaB|c B→bScA|b

则句型aAcbBdcc的短语是_______。

a. Bd b. c c. bBdcc d. aAcbBdcc e. cbBd 3.2.9.在自下而上的语法分析中，应从_________开始分析。 a.句型 b.句子 c.以单词为单位的程序 d.文法的开始符 e.句柄

3.2.10.对正规文法描述的语言，以下_____＿有能力描述它。 a. 0型文法 b. 1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法

填空题：

3.3.1．规范归约中的可归约串是指______;算符优先分析中的可归约串是指______＿。

3.3.2.文法中的终结符和非终结符的交集是______。词法分析器交给语法分析器的文法符号一定是______，它一定只出现在产生式的_____＿部。

3.3.3.在自上而下的语法分析中，应先消除文法的_______递归，再消除文法的_____递归。

3.3.4.规范归约是指在移进过程中，当发现栈顶呈现_____时，就用相应产生式的_____符号进行替换。

3.3.5．当文法非终结符的所有_____两两___＿时，该文法对应的句子分析不含回溯。

3.3.6.最左推导是指每次都对句型中的____＿非终结符进行扩展。（陕西省1998年自考题）

3.3.7.在语法分析中，最常见的两种方法一定是_____分析法，另一是______分析法。 （陕西省1998年自考题）

3.3.8.______语法分析的关键问题是精确定义可归约串的概念。（陕西省2000年自考题）

3.3.9. Chomsky定义的4种形式语言文法为：

①______文法，又称______文法；②_____文法，又称_____文法； ③______文法，又称______文法；④______文法，又称_____＿文法。 （中国科技大学1999年研究生试题） 3.3.10. LL(K)文法中，第一个L表示_____＿，第二个L表示_____＿，K表示_____，通常情况下K_____。（西安电子科大2000年研究生试题）

3.3.11．采用_______＿语法分析时，必须消除文法的左递归。 3.3.12．_____树代表推导过程，______＿树代表归约过程。

3.3.13.自下而上分析法采用____＿、归约、错误处理、_____＿等四种操作。

（陕西省1999年自考题） 3.3.14．设αβδ是文法G的一个句型，A是非终结符，则β是句型αβδ相对于A的短语，若______＿；β是句型αβδ相对于A的直接短语，若_____＿；β是句型αβδ的句柄，若_______。（西安电子科大2000年研究生题）

3.3.15．Chomsky把文法分为______＿种类型，编译器构造中采用______和_____＿文法，它们分别产生_____和_____语言，并分别用______和______自动机识别所产生的语

言。 （西安电子科大2000年研究生试题）

判断题：

3.4.1语法分析之所以采用上下文无关文法是因为它的描述能力最强。 （ ）

3.4.2 欲构造行之有效的自上而下分析器，则必须消除左递归。 （ ） 3.4.3文法( 有图片 )描述的语言是（a|bc）* ( ) 3.4.4 在自下而上的语法分析中，语法树与分析树一定相同。（ ） 3.4.5 二义文法不是上下文无关文法。（陕西省1999年自考题）（ ） 3.4.6 每一个算符优先文法，必定能找到一组优先函数与之对应。（陕西省2000年自考题） （ ）

3.4.7 语法分析时必须先消除文法中的左递归。 （ ） 3.4.8 规范归约和规范推导是互逆的两个过程。 （ ） 3.4.9 一个文法所有句型的集合形成该文法所能接受的语言。 （ ）

3.4.10 LL(1)文法一定不含左递归和二义性。 （ ）

综合题

3.5.1 简答题 1．句柄 2.素短语 3．语法树 4.归约 5.推导

3.5.2给出上下文无关文法的定义。

3.5.3 Chomsky将文法分成四类。指明这四类文法与自动机的对应关系。指出右线性文法、左线性文法、正规文法之间的主要区别。

3.5.4 文法G是LL(1)文法的充分必要条件是什么？

3.5.5 文法G[S］：

S→aSPQ|abQ QP→PQ bP→bb bQ→be cQ→cc

（1)它是Chomsky哪一型文法？ （2）它生成的语言是什么？

3.5.6 指出下述文法的所有类型，并给出所描述的语言。 （1）S→Be （2）A→ε|aB（3）TS→abcA B→eC|Af B→Ab|a S→Aabc A→Ae|e A→ε C→Cf Aa→Sa

D→fDA cA→cS

3.5.7 按指定类型，给出语言的文法。 （1）L=｛aidj>i≥l}的上下文无关文法。

(2)字母表∑={a,b｝上的同时只有奇数个a和奇数个b的所有串的集合的正规文法。 (3）由相同个数a和b组成句子的无二义文法。

3.5.8 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。 S→SandS|S or S|not S|p|q|(S)

3.5.9 有文法G：S→aAcB|Bd A→AaB|c B→bScA|b

（1)试求句型aAaBcbbdcc和aAcbBdcc的句柄； (2)写出句子acabcbbdcc的最左推导过程。

3.5.10 对文法G：E→E+T|T T→T*P|P P→i

（1)构造该文法的优先关系表（不考虑语句括号＃），并指出此文法是否为算符优先文法；

(2）构造文法G的优先函数

3.5.11 在上一题中，如果将文法改为E→E+E|E*E|i,在不改动文法的情况下是否同样能构造出优先关系表？此外，针对例3.14中的文法与本例中的文法，对算符优先分析快于规范归约进行说明。

3.5.12 对于文法G[S]：

S→(L)|aS|a L→L,S|S （1)画出句型（s，（a））的语法树。

(2)写出上述句型的所有短语、直接短语、句柄和素短语。

3.5.13 构造算符文法G[H]的算符优先关系（含＃）。 G[H]：H→H;M|M M→d|aHb

3.5.14 设有文法G[S]为： S→a|b|(A) A→SdA|S

（1) 完成下列算符优先关系表，见表3.6.并判断G[S]是否为算符优先文法。

(2）给出句型（SdSdS)的短语、简单短语、句柄、素短语和最左素短语。 （3)给出输入串(adb)#的分析过程。

3.5.15 下面映射if语句的文法G[S]是算符优先文法吗？若是，则构造其优先关系矩阵。若不是，请按照多数程序设计语言（如Pascal)的习惯，给出一个相应的算符优先文法。

G[S]：S→iBtS|iBtSeS|a B→b

3.5.16 文法G[]不是LL(l)的，请说明理由，并给出其等价的LL(1)文法。 G[]:

→ →i:|ε

→i=e

3.5.17 已知文法G[A]为： A→aAB1|a B→Bb|d

（I）试给出与G[A]等价的LL(I）文法G’[A]。 （2)构造G’[A］的预测分析表。 （3）给出输入串aadl#分析过程。

3.5.18 将G[V]改造为LL（1）文法。 G[V]: V→N|N[E] E→V|V+E N→i

3.5.19 有文法G[S]: S-BA A--BS|d B～aA|bS|c

(I）证明文法G是LL(I）文法。 （2）构造LL（1）分析表。

(3）写出句子adccd的分析过程。

3.5.20 考虑文法G[T]：

T→T*F|F F→F↑P|P P→(T)|i

（1)证明T*P↑(T*F)是该文法的一个句型，并指出其直接短语和句柄。 (2)构造文法G的优先关系表（要求写出步骤）。

3.5.21 给出算符优先文法的分析算法。

3.5.22 文法G的产生式集为：S→S+S|S*S|i|（s），对于输入串i+i*i；

（1)给出一个推导； (2）画出一棵语法树；

（3)文法G是否是二义性的，请证明你的结论。

3.5.23 已给文法G[E]：

E→EOE|(E)|i 0→+|*

试将其改造为可进行不带回溯的自顶向下分析的文法，并给出其相应的LL(1)分析表。

3.5.24 考虑文法G(S)：

S→(T)|a+S|a T→T,S|S

消除文法的左递归及提取公共左因子，然后，对每个非终结符，写出不带回溯的递归子程序。

3.5.25 有映射程序设计语言if-the-else语句的文法G[S]: S→iEtSeS|EtS|a

E→b 其中，else遵从最近匹配原则。

（1)试改造文法，并为之构造LL（1）分析表。 (2）利用构造的分析表分析句子ibtibtaea,要求给出分析过程中每一步的分析栈和输入串的变化以及输出信息。

3.5.26 下述文法描述了C语言整数变量的声明语句： D→TL T→int|long|short L→id|L,id

（1)改造上述文法，使其接受相同的输入序列，但文法是右递归的。 (2)分别用上述文法和改造文法，为输入序列int a,b,c构造分析树。

3.5.27 设有文法G[W]：

W→AO

A→AO|W1|0

请改写文法，消除规则左递归和文法左递归。

3.5.28 文法G[P]及相应翻译方案为：

P→bQb {print:”1”｝ Q→cR {print:”2”｝ Q→a {print:”3”｝ R→Qad (print:”4”｝

（1)该文法是不是算符优先文法，请构造算符优先关系表证实之。 (2)输入串为bcccaadadadb时，该翻译方案的输出是什么。

3.5.29 设有文法G[S]： S→SAS|b A→bSb|b

试构造一个与其等价的算符文法。

3.5.30 在算符优先分析法中，为什么要在找到最左素短语的尾时，才返回来确定其对应的头，能否按扫描顺序先找到头后找到对应的尾，为什么？

3.5.31 试证明在算符文法中，任何句型都不包含两个相邻的非终结符。

3.5.32假定文法包含产生式A→α，α∈V*（V是文法的词汇表，由终结符和非终结符组成的集合），证明：如果FIRST（α）∩FOLLOW（A）≠φ，则该文法不是LL（1)文法。

3.5.33 给出文法G1：

S→aSb|P A→bPc|bQc B→Qa|a

（1)它是Chomsky哪一型文法？ （2）它生成的语言是什么？

（3)它是不是算符优先文法？请构造算符优先关系表证实之。

(4)请证实所有①左递归文法②有公共左因子的文法均不是LL（1)文法。 (5)文法G1消除左递归、提取公共左因子后是不是LL (1）文法？请证实。

3.5.34 简答题

（1)什么是文法的二义性？二义性问题的不可判定指的是什么？ (2)在规范句型中，句柄以右的符号有什么特征？为什么？

3.5.35 写正规文法G,它产生的语言是L(G)={ anibncp|m,n,p≥0}

3.5.36 语言L是所有由偶数个0和偶数个1组成的句子的集合，给出定义L的正规文法。

3.5.37 已知文法G[S］：S→ABS|AB

AB→BA A→0 B→1

该文法是几型的？该文法所产生的语言是什么？（用自然语言描述）写出与该文法等价的CFG文法。

3.5.8 写一个上下文无关文法G，使得L(G)={anbmcmdn|n≥0,m≥1｝。

3.5.39 写一个文法G，使其语言为L(G)={ anbm|n≥m≥1｝。

3.5.40 生成语言1={albmclanbn|1>=O,m>=1，n>=2｝的文法是什么？它是Chomsky那一型文法？

3.5.41文法G[P]：P→aPQR|abR

RQ→QR bQ→bb bR→be cR→cc

它是Chomsky哪一型文法？请证aaabbbccc是G[P]的一个句子。

3.5.42文法G[S］：S→aSPQ|abQ

QP→PQ bP→bb bQ→be cQ→cc

（1)它是Chomsky哪一型文法？ （2）它生成的语言是什么？

3.5.43 给定文法G[S]：S→(S)S|ε，给出句子（（）（））（）（）的规范推导，并指出每步推导所得句型的句柄，画出该句子的语法推导树，指出所有的短语和直接短语。

3.5.44 设文法G[S]：S→(A)|a

A→A+S|S

（1）构造各非终结符的FIRSTVT和LASTVT集合。 （2）构造优先关系表。

3.5.45已知文法G[S]：S→dAB

A→aA|a B→Bb|ε

（1)试问G[S]是否为正规文法，为什么？ (2）G[S]所产生的语言是什么？

（3) G[S]能否改写为等价的正规文法?

3.5.46 选择题

有文法G[S]：S→aA|a|bC，A→aS|bB，B→aC|bA|b，C→aB|bS，则____＿为L(G) 中句子。

a. aloob5oabloo b. alooob5ooaba

c. a500b60aab2a d. a l00 b4oab10 aa

3.5.47 对文法G[S‘］：S‘→#S#

S→fstS S→i=E E→E+T|T T→P↑T|P P→(E)|i

（1）求各非终结符的FIRSTVT和LASTVT集合。 (2）构造该文法的优先关系表。（请将终结符以＝＋、↑、（、i, f, t,）、＃的顺序构造优先关系表）

3.5.48 有文法R::=i|(T)，T::=T，R|R，完成表3.21所示的算符优先关系表（填写第一、第二行）。

3.5.49 文法G[M]是否LL(1)的，说明理由。 G[M]：M→TB T→Ba|ε B→Db|eT|ε D→d|ε

3.5.50 将文法G[E]改写为等价的LL(I)文法，并给出相应的预测分析表。 G[E]：E→[T T→F]|TE F→i|Fi 3.5.51 已知文法G[S]: S→S*aP|aP|*aP P→+aP|+a

（1）将文法G[S]改写为LL(1）文法G‘［S］。 (2)写出文法G' [S]的预测分析表。

5

※<习题四>

第四章

典型例题: 单项选择题

语法分析器的自动构造

4.1.1.若a为终结符，则A→a·aβ为____＿项目。 a.归约 b.移进 c.接受 d.待约

4.1.2.两个LR(1)项目集如果除去______后是相同的，则称这两个LR(1)项目同心。 a.项目 b.活前缀 c.搜索符 d.前缀 4.1.3．同心集合并不会产生—冲突。

a.二义 b.移进／移进 c.移进／归约 d.归约／归约 4.1.4．左结合意味着____＿。

a.打断联系实行移进 b.打断联系实行归约 c.建立联系实行移进 d.建立联系实行归约 4.1. 5.若项目集Ik含有A→a·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A) 时，才采取“A→a·”动作的一定是_____。

a. LALR文法 b. LR(0)文法 c. LR(1)文法 d. SLR(1)文法 4.1.6．就文法的描述能力来说，有____＿。 a. SLR(1）cLR(0) b. LR(1）cLR(0) c. SLR(1）cLR(1） d.无二义文法cLR(1）

4.1. 7.在LR(0)的ACTION子表中，如果某一行中存在标记为\”的栏，则___＿。 a.该行必定填满ri b.该行未填满ri

c.其他行也有ri d. goto子表中也有ri

4.1.8.一个____指明了在分析过程中的某时刻所能看到产生式多大一部分。 a.活前缀 b.前缀 c.项目 d.项目集 4.1.9.若B为非终结符，则A→a·Bβ为____项目。 a.接受 b.归约 c.移进 d.待约 4.1.10．同心集合并有可能产生新的＿冲突。

a.归约 b.移进／移进 c.移进／归约 d.归约／归约 4.1.11．右结合意味着＿。

a.打断联系实行归约 b.建立联系实行归约 c.建立联系实行移进 d.打断联系实行移进 4.1.12.若项目集Ik含有A→a·，则在状态K时，无论面临什么输入符号都采取“A→α 归约”的动作一定是＿。

a. LR(1）文法 b. LALR(1)文法 c. LR(0)文法 d. SLR(1）文法 4.1.13．就文法的描述能力来说，有＿。

a.无二义文法cSLR(1） b. LR(0) cLR(1) c.无二义文法cLR(0) d. LR(1) cLR(0)

多项选择题：

4.2.1．一个LR分析器包括____。

a.一个总控程序 b.一个项目集。 c.一个活前缀 d.一张分析表 e.一个分析栈

4.2.2 ．LR分析器核心部分是一张分析表，该表包括_____等子表。 a. LL(1）分析 b.优先关系 c. GOTO d. LR e. ACTION

4.2.3．每一项ACTION[S,a]所规定的动作包括______。

a.移进 b.比较 c.接受 d.归约 e.报错

4.2.4.对LR分析表的构造，有可能存在_____动作冲突。

a.移进 b.归约 c.移进／归约 d.移进／移进e .归约／归约 4.2.5．就文法的描述能力来说，有____。

a. SLR(1）c LR(1） b. LR(0) c SLR(1）c. LR(0) c LR(1） d. LR(1）c无二义文法 e. SLR(1）c无二义文法 4.2.6．对LR分析器来说，存在＿___等分析表的构造方法。

a. LALR b. LR(0) c. SLR(1) d. SLR(0) e. LR(1) 4.2.7.自上而下的语法分析方法有＿__。

a.算符优先分析法 b. LL(1)分析法 c. SLR(1)分析法 d. LR(0)分析法 e. LALR(1)分析法

填空题：

4.3.1．对于一个文法，如果能够构造___，使得它的____均是唯一确定的，则称该文法 为LR文法。

4.3.2.字的前缀是指该字的＿___。

4.3.3．活前缀是指_____的一个前缀，这种前缀不含____＿之后的任何符号。

4.3.4.在LR分析过程中，只要＿的已扫描部分保持可归约成一个____，则扫描过的 部分正确。

4.3.5.将识别＿___的NFA确定化，使其成为以＿____为状态的DFA,这个DFA就是建 立的基础。

4.3.6. A→a·称为_____项目；对文法开始符S'，称S'→a·为＿__项目；若a为

终结符，则称A→a·aβ为__＿项目；若B为非终结符，则称A→a·Bβ为_____项目。 4.3.7. LR(0)分析法的名字中“L”表示，“R”表示，\”表示______。 4.3.8．一个LR分析器包括两部分：________和_______.

4.3.9.两个LR(1)项目集如果除去＿_____后是相同的，则称这两个LR(1)项目集_____。 4.3.10.构成识别一个文法___＿的DFA的项目集全体，称为这个文法的LR(0) _____.

4..3.11.一个活前缀γ的＿___，就是从识别文法活前缀DFA的初态出发，经读出γ后所到达的那个

4.3.12．左结合意味着打断联系实行___＿，右结合意味着打断联系实行____＿。 4.3.13.同心集合并不会产生—冲突，但可能产生___＿冲突。

判断题：

4.4.1. LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 （）

4.4.2.构造LR分析器的任务就是产生LR分析表。 （） 4.4.3 .LR文法肯定是无二义的，一个无二义文法决不会是LR文法。 （） 4.4.4.在任何时候，分析栈的活前缀X1X2...Xm的有效项目集就是栈顶状态Sm所在的那个 项目集。 （） 4.4.5．同心集的合并有可能产生新的“移进”／“归约”冲突。 （） 4.4.6.由于LR(0)分析表构造简单，所以它的描述能力强、适用面宽；LR(1)分析表因构造复杂而描述能力弱、适用面窄。 （） 4.4.7．所有LR分析器的总控程序都是一样的，只是分析表各有不同。 （） 4.4.8. LR分析技术无法适用二义文法。 （） 4.4.9.项目A→β1·β2对活前缀αβ1是有效的，其条件是存在规范推导S'*=>aAW=> a β

1β2ω。 （）

4.4.10. SLR(1)文法的特点是：当符号栈中的符号串为βα，而面临的输入符号为α则存在 把α归约为A的规范句型的前缀β Aα时，方可把a归约为A。 （ ）

综合题

4.5.1请指出图4.2中的LR分析表（a）、（b）、（c）分属LR（0）、SLR和LR（1）中的那一 种，并说明理由。

4.5.2文法G的产生式如下：

S→BB B～aB|b

请分别构造该文法的（1) LR (0）分析表；(2）SLR分析表；(3）规范LR分析表（即 LR（1）分析表）；（4）LALR分析表。

4.5.3什么是规范句型的活前缀？引进它的意义何在？

4.5.4对于文法G[S］：S→AS|b A→SA|a (1)列出所有LR (0)项目。

(2)根据列出的项目构造识别文法活前缀的NFA并确定化为DFAo （3)证明DFA的所有状态全体构成文法LR（0)规范族。

4.5.5 LR分析器与优先关系分析器在识别句柄时的主要异同是什么？

4.5.6 LR（0）、SLR(1), LR（1)及LALR有何共同特征？它们的本质区别是什么？试论述之。 4.5.7 为二义文法G构造一个LR分析表（详细说明构造方法）。其中终结符“，”满足右结

合性，终结符“；”满足左结合性，且“，”的优先级高于“；”的优先级。 文法G[T]：T→TAT|bTe｝a A→，|；

4.5.8 二义文法G[S],符的优先性和结合性说明如下： （a）else与最近的if结合 (b）“；”优先性大于if (c）“；”优先性大于else (d)“；”服从左结合

请使用LR分析法的基本思想，凭借上述条件，为G[S]构造LR分析表，要求写出详细 的构造过程。

G[S]:S→if S else S S→if S S→S;S S→a

4.5.9 已知文法G[S]为 S→aAd|;Bd|aB↑|;A↑

A→a

B→a

（1)试判断G[S]是否为LALR(1)文法。

(2)当一个文法是LR(1)而不是LALR(1)时，那么LR(1)项目集的同心集合并后会出现哪几种冲突，请说明理由。

4.5.10 文法G[T]及其LR分析表（见表4.9)如下，给出串bibi的分析过程。 （1）T→EbH （2）E→d （3）E→ε （4）H→i （5）H→Hbi （6）H→ε

4.5.11 给出文法G[S]及图4.9所示的LR(1)项目集规范族中的0、1, 2, 3, 4. G[S]: S→S;B|B B→BaA|A A→b(S)

4.5.12 证明AdBd是文法G[S]的活前缀，说明活前缀在LR分析中的作用。给出串dbdb#的LR

分析过程。

G[S］： （1）S→AdB (4) B→b （2）A→a （5）B--Bdb （3）A→ε （6）B→ε

4.5.13 一个非LR（1）的文法如下：

L→MLb|a M→ε

请给出所有有移进一归约冲突的LR(1)项目集，以说明该文法确实不是LR(1)的。

4.5.14 文法G(S)的产生式集为：

S→(EtSeS)|(EtS)|i =E E→+EF|F F→*Fi|i

构造文法G的SLR(1)分析表。要求先画出相应的DFA。

4.5.15 下述文法是哪类LR文法？并构造相应分析表。

4.5.16 给定文法G［A]：A→(A)|a

（1)证明：LR(1)项目[A→(A·），］］对活前缀“((a”是有效的；

(2)画出LR(1)项目识别所有活前缀的DFA; （3）构造LR(1）分析表；

(4)合并同心集，构造LALR(1)分析表。

4.5.17 已知布尔表达式的方法G[B]如下：

度为G[B]构造LR分析表。

4.5.18 8086/8088汇编语言对操作数域的检查可以用LR分析表实现。设m代表存储器，r代表寄存器，i代表立即数；并且为了简单起见，省去了关于m,r,和i的产生式，暂且认为m、r、i为终结符，则操作数域P的文法G如：试构造能够正确识别操作数域的LR分析表。

4.5.19 为语言｛amb0|n>m≥0｝写3个文法，它们分别是二义文法、LR(1）文法以及非LR（1)且非二义的文法。不必证明所写文法的正确性，但每个文法的产生式不能超过4个。

4.5.20 由文法二义引起的LR(1)分析动作冲突，可以依据消除二义的规则而得到LR(1)分析表，根据此表可以正确识别输入串是否为相应语言的句子。对于非二义非LR(1)文法引起的LR(1)分析动作的冲突，是否也可以依据什么规则来消除LR(1)分析动作的冲突而得到LR(1)分析表，并且根据此表识别相应语言的句子？若可以，是否可以给出这样的规则？

4.5.21 有文法G＝（｛S｝，｛a｝，｛S→SaS,S→ε，S），该文法是_____。 A. LL(l)文法。 B.二义性文法 C.算符优先文法 D. SLR(1)文法

4.5.22 试证明任何一个SLR(1）文法一定是一个LALR(1)文法。

4.5.23 文法G[P]：P→aPb|Q Q→bQc|bSc S→Sa|a

（1)请构造它的SLR分析表，以说明它是不是SLR文法。 (2)在消除左递归、提取公共因子后可得等价文法G[P’］，它是不是LL(1)文法。

4.5.24 给出文法G2: S→SaS|SbS|cSd|eS|f （1)请证实这是一个二义文法；

（2)给出什么样的约束条件，可构造无冲突的LR分析表？请证实你的论点。

4.5.25 有简单语言的文法G(VT,VN,P,δ，其中，VT＝｛黑体小写字母串，标点符号，赋值号，运算符｝

VN＝{P,D,L,S,E,T,B｝ δ: P→begin D;S end D→id:L

L→integer|boolean S→id:=Elif B then S E→E+TIT T→id B→id|true|false

（1)试写出该文法的一个句子；

(2)该文法属于以下哪几种文法，不属于哪几种文法，请说明理由。 a)上下文无关文法 b) LL(1)文法 c) SLR(1)文法

4.5.26 试分析LR(0)、SLR(1), LR(1)和LALR(1)分析表的优缺点。

4.5.27 比较LL(K)和LR(K)的异同点。

4.5.28 文法G[A］的LR分析表，见表4.21，请给出串ab的分析过程。G[A］的拓广文法为G[A`］。

4.5.29 文法G[S]及其LR分析表（见表4.22）如下，请给出对串baba#的分析过程。

4.5.30 为下面的二义文法G构造一个LR分析表（详细说明构造方法），其中“*”的优先级高于“＋”，且，\、“＋”都服从左结合。 文法G：E→E+E|E*E|a

4.5.31根据程序设计语言的一般要求，为定义条件语句的二义文法G[S]构造SLR(1)分析表，要求写出步骤和必要说明。

G[S］：S→iSeS|iS|a

4.5.32 对下列文法：

1）S'→S 2）S→bRST 3）S→bR 4）R→dSa 5）R→e 6）T→fRa 7）T→f

（1）求各非终结符的FIRST和FOLLOW集合。 （2）构造该文法的SLR(1)分析表。（请将终结符和非终结符以abdef#SRT顺序构造分 析表）

4.5.33 下述文法是SLR文法吗？若是，给出分析表；否则，说明理由。 （1）S→bASB|bA （2）A→dSa|e （3）B→cAa|c

4.5.34 己知某语言L={ambn|n>m≥0}。试写出产生该语言的两种文法G1和G2,其中G1是 LR(1)文法，G2是非LR(1)和非二义性文法。

4.5.35 构造一个LR(1）文法G,它产生语言L（G）={w}w|(a|b)*，w中a和b的个数相等｝。

4.5. 36 试证明任何的SLR(l)文法都是LR(1)文法。

4.5.37 给定拓广文法G (S为G的开始符号），G的产生式（附带编号）如下： 0）S→E 1）E→E+T 2）E→T 3）T→i 4）T→(E)

(1)构造文法G的LR(1)项目集规范族和GO函数。 （2）构造G的LR(1）分析表。

5

※<习题五>

第五章 中间代码生成

5．1 单项选择题

1．中间代码生成时所依据的是—。

a．语法规则 b．词法规则 c．语义规则 d．等价变换规则 2．四元式之间的联系是通过___实现的。

a．指示器 b．临时变量 c．符号表 d．程序变量 3．后缀式ab+cd+/可用表达式___来表示。（陕西省1999年自考题） a． a+b/c+d b． (a+b)/(c+d) c． a+b/(c+d) d． a+b+c/d 4．间接三元式表示法的优点为＿。（陕西省1998年自考题）

a．采用间接码表，便于优化处理 b．节省存储空间，不便于表的修改 c．便于优化处理，节省存储空间 d．节省存储空间，不便于优化处理 5．表达式(A∨B)∧(C∨D)的逆波兰表示为＿。（陕西省1998年自考题） a．┐AB∨∧CD∨ b． A┐B∨CD∨∧

c． AB∨┐CD∨∧ d． A┐B∨∧CD∨ 6．中间代码的树型表示 所对应的表达式为___。（陕西省1998年自考题） a． A+B+C+D b． A+(B+C)+D c．（A+B)+C+D d． (A+B)+(C+D) 7．四元式表示法的优点为＿。（陕西省1997年自考题）

a．不便于优化处理，但便于表的更动b．不便于优化处理，但节省存储空间 c．便于优化处理，也便于表的更动d．便于表的更动，也节省存储空间 8．终结符具有＿属性。

a．传递 b．继承 c．抽象 d．综合

9．有文法G及其语法制导翻译如下所示（语义规则中的*和＋分别是常规意义下的算术运算符）：

E→E'∧T｛E．val：=E'．val*T．val} E→T｛E．val：=T．val}

T→T'#n｛T．val：=T'．val+n．val｝ T→n {T．val：=n．val;} 则分析句子1∧2∧3#4其值为＿。 （西安电子科大2000年研究生试题）

a． 10 b． 34 c． 14 d． 54

10．表达式（a+b)*c的后缀式表示为＿。

a． ab*c+ b． abc*+ c． ab+e* d． abc+*

11．后缀式＿对应的表达式是a-(-b)*c（＠代表后缀式中的求负运算符）。 a． a-b@c*、b． ab＠．c． ab@c-* d, ab@c*- 12．使用___可以把Z=(X+0．418）＊YNV翻译成四元式序列。（陕西省1999年自考题） a．语义规则 b．等价变换规则 c．语法规则 d．词法规则 13．采用右结合规则时，a+b*c+d可解释为＿（假设*的优先级高于＋）。

（陕西省2000年自考题）

a． (a+(b*c))+d b． a+((b*c)+d) c． a+d+(b*c) d． (b*c)+a+d 14．更动一张＿表很困难。（陕西省2000年自考题）

a．三元式 b．间接三元式 c．四元式 d．三元式和四元式

15．有一语法制导翻译如下所示： （西安电子科大1999年研究生试题） S→bAb {print\ A→(B {print\ A→a {print\ B→Aa) {print\

若输入序列为b(((aa)a)a)b,且采用自下而上的分析方法，则输出序列为＿。 a. 32224441 b. 34242421 c. 12424243 d. 34442212 5.2 多项选择题

1．中间代码主要有___。

a.四元式 b.二元式 c.三元式 d.后缀式 e.间接三元式

2.下面中间代码形式中，能正确表示算术表达式a+b+c的有＿。（陕西省1997年自考题）

3.在下面的＿语法制导翻译中，采用拉链一回填技术。

a.赋值语句 b.布尔表达式的短路计算 c. goto语句 d.条件语句 e.循环语句

4.下列___中间代码形式有益于优化处理。（陕西省1997年自考题） a.三元式 b.四元式 c.间接三元式 d.逆波兰表示法 e.树形表示法

5.在编译程序中安排中间代码生成的目的是＿。

a.便于进行存储空间的组织 b.利于目标代码的优化 c.利于编译程序的移植 d.利于目标代码的移植 e.利于提高目标代码的质量

6.下面的中间代码形式中，＿能正确表示算术表达式a+b*c。（西省2000年自考题）

7.三地址代码语句具体实现通常有＿表示方法。

a.逆波兰表示 b.三元式 c.间接三元式 d.树形表示 e.四元式 5.3 填空题

1.中间代码有______等形式，生成中间代码主要是为了使______。

2.语法制导翻译既可以用来产生＿代码，也可用来产生＿指令，甚至可用来对 输入串进行。（陕西省1999年自考题）

3.当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须待____时才能 确定，因而要进行____。（陕西省1998年自考落）

4.文法符号的属性有两种，一种称为____，另一种称为_____。

5．后缀式abc-/所代表的表达式是＿，表达式(a-b)*c可用后缀式＿表示。 （陕西省2000年自考题）

6.用一张______辅以_____的办法来表示中间代码，这种表示法称为间接三元式。

7.在语法分析中，根据每个产生式对应的语义子程序进行____的办法叫做____。

（陕西省1998年自考题） 8.对＋、*采用左结合习惯，对乘幂↑个采用右结合习惯，则E1+E2+E3可解释成＿， 而E1↑E2↑E3可解释成＿。（陕西省1997年自考题）

9.在语法树中，一个结点的综合属性的值由其＿的属性值确定，而继承属性则由该 结点的＿的某些属性确定。

10.对某个压缩了的上下文无关文法，当把每个文法符号联系于，且让该文法的规 则附加以＿时，称该文法为属性文法。

11.语法制导的翻译程序能够同时进行_____和______。 5.4 判断题

1.一个语义子程序描述了一个文法所对应的翻译工作。（） 2.逆波兰表示法表示表达式时无须使用括号。 （）

3.树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。（） 4.三地址语句类似于汇编语言代码，可以看成中间代码的一种抽象形式。（） 5.非终结符可以有综合属性，但不能有继承属性。（） 6.程序中的表达式语句在语义翻译时不需要回填技术。（） 7.在编译阶段只对可执行语句进行翻译。（）

8.无论是三元式表示还是间接三元式表示的中间代码，其三元式在三元式表中的位置一

旦确定就很难改变。（陕西省1998年自考题）（）

9.对中间代码的产生而言，目前还没有一种公认的形式系统。（） 10.三元式出现的先后顺序和表达式各部分的计值顺序并不一致。（）

11.自上而下分析的一个优点是：在一个产生式的中间就可以调用语义子程序。（） 12.终结符只有继承属性，它们由词法分析器提供。（） 13.翻译算术表达式语句时需要用到回填技术。（）

14.程序中不允许标号先引用后定义。（） 5.5 综合题

5.5 .1 （哈工大2000年研究生试题） 叙述下列概念：

（1）语法制导翻译 (2)翻译文法 (3)语义子程序

5.5.2 （武汉大学1999年研究生试题）

何谓“语法制导翻译(SDTS)”？试给出用SDTS生成中间代码的要点，并用一简例予以说明。

5.5.3 给出下列表达式的逆波兰表示(后缀式)： ①a*(－b+c)

②(A∨)∧(C∨┐D∧E)

③if (x+y)*Z=5 then x：=(a+b)↑c else y：=a↑b↑ c 5.5.4 写出算术表达式：A+B*(C－D)+E/(C－D)↑N的

①四元式序列；②三元式序列；③间接三元式序列；④树形表示 5.5.5 （清华大学1999年研究生试题）

令S.val为文法G[S]生成的二进制数的值，例如对输入串101．101则S.val=5.625。按照语法制导翻译方法的思想，给出计算S.val的相应的语义规则。 G[S]：S-L.L|L L→LB|B B→0|1

5.5.6 （清华大学2000年研究生试题）

现有文法G1、G2如下，欲将G1定义的expression转换成如、G2的E所描述的形式。给出其语法制导翻译的语义描述。（提示：可采用类似yacc源程序的形式，所涉及的语义函数须用自然语言给予说明，不用抄写产生式，用产生式编号表示）。 G1：(1)→：begin end. （2）→var （3）→,id： （4）→id： （5）→int （6）→bool （7）→

（8）→； （9）→ and （10）→* （11）→id （12）→num （13）→true （14）→false 要求：（1) 中的id必须在中先声明。

(2)and和*分别是常规的布尔和算术运算符，要求其运算对象的相应类型匹配， G2：E→EE*|EE and|id|num|true|false 5.5.7 下面的文法生成变量的类型说明： D→id L L→,id L|:T T→integer|real

试构造一个翻译方案，仅使用综合属性，把每个标识符的类型填入符号表中（对所用到 的过程，仅说明功能即可，不必具体写出）。

5.5.8 已知文法G及每个产生式相应的语义子程序如下：

（1）E→i {E·TC: =NXQ; E·FC:=NXQ+1：GEN (jnz, ENTRY(i), ,0);

GEN (j,＿,＿,0)}/*NXQ指针总是指向下一个将要形成的四元式的地址（编号）； GEN过程把四元式（OP, ARG1，ARG2，RESULT）填入四元式表中*/

(2)E→i(1)ropi(2) {E·TC: =NXQ; E·FC:=NXQ+1：GEN(jrop, ENTRY(i(1)),ENTRY(i(2)),0);

GEN (j,＿,＿,0)}/*jrop是根据关系符rop而定义的一条件转移指令*/ (3）E→(E(1)) {E·TC:=E(1)·TC；E·FC:＝E(1)·FC} (4)E→┐E(1) {E·TC:=E(1)·FC；E·FC:＝E(1)·TC}

（5）EA→E(1)∧{BACKPATCH(E(1)·TC，NXQ)；EA·FC:=E(1)·FC}

/*BACKPATCH过程将NXQ的当前值填入E(1)·TC所指四元式的第四区段*/ （6）E→EAE(2) {E·TC:=E(2)·TC；E·FC: =MERG（EA·FC，E(2)·FC)}

/*MERG函数将EA·FC和E(2)·FC两条链合并，并以EA·FC作为链首*/ （7）E0→E(1)∨{BACKPATCH(E(1)·FC，NXQ)；E0·TC:=E(1)·TC} （8）E→E0E(2) {E·FC:=E(2)·FC；E·TC:=MERG(E0·TC, E(2)·TC} 5.5.9 赋值语句的文法及语义动作描述如下： (1)A→:=E {GEN(:=,E·PLACE,＿ ,ENTRY(i))}

(2)E→E(1)+E(2) {E·PLACE:=NEWTEMP：GEN(＋，E(1))·PLACE,E(2)·PLACE,E·PLACE)} (3)E→E(1)*E(2) {E·PLACE:=NEWTEMP：GEN(*，E(1)·PLACE,E(2)·PLACE,E·PLACE)} (4)E→-E(1) {E·PLACE:=NEWTEMP：GEN(＠，E(1)·PLACE,＿,E·PLACE)} (5)E→(E(1) {E·PLACE:= E(1)·PLACE} (6)E→i {E·PLACE:=ENTRY(i)}

写出赋值语句X:=-B*(C+D)+A的自下而上的语法制导翻译过程。 5.6.0 (1)写出Pascal语言的repeat语句； repeat

S1；S2；…；Sn until. E；

的文法及对应的语义子程序(注：E为条件表达式)； (2)按构造好的文法分析并翻译语句： repeat x：=x+l until x>5； 5.6.1 写出翻译过程调用语句的语义子程序。要求生成的四元式序列在转子指令之前的参

数四元式par按反序出现（与实在参数的顺序相反），问这种情况下在翻译过程调用语句时是否需要语义变量（队列）QUEUE呢？

5.6.2 （国防科大2001年研究生试题） 设某语言的while语句的语法形式为： S→while E do S(l) 其语义解释如图5.8所示。

(1)写出适合语法制导翻译的产生式。

(2)写出每个产生式对应的语义动作。

5.6.3 (国防科大1999年研究生试题)

条件式if E(l) then E(2) else E(3)的语义解释为：若布尔式E(l)为真，则条件表达式值取E(2)的值；否则条件表达式值取E(3)的值。

(1)写出if E(l) then E(2) else E(3)的适合语法制导翻译的产生式及相应语义子程序。 (2)按(1)中的语义子程序把

a:=if x>0 then x+1 else x+2; 翻译为四元式序列。

5.6.4 (哈工大2000年研究生试题) 设for语句的形式为：

for V=El step E2 until E3 do S

请设计其目标结构，并给出相应的语义分析过程。 5.6.5 某程序设计语言中有如下形式的选择语句 switch (E)

{case cl：sl；

case c2：s2； case ci：si； case cn：Sn； default： Sn+l } 其中n≥1。此选择语句的语义是：先计算整型表达式E的值，然后将表达式的值依次和case 后的常数Ci比较，当与某常数ci相等时就执行语句Si, 并结束该选择语句； 若与诸常数均不相等, 则执行语句Sn+1。

为了便于翻译, 上述选择语句可用下列产生式来定义： A→switch(E) B→A{case c D→B：S|F：S F→D；case c S→D；default：S}

使用自上而下的语法制导翻译方法,给出翻译此选择语句的翻译子程序(语义子程序)。 在翻译子程序中可以使用下列指示器、过程和函数，

·指示器NXQ：指向下一个将要形成但尚未生成的四元式的地址； ·过程GEN(OP,ARG1,ARG2,RESULT),该过程把四元式 (OP,ARG1,ARG2,RESULT) 填进四元式表中，且将NXQ增加1；

·过程BACKPATCH(P,t)：把P所链接的每个四元式的第四区段都填为t； ·函数MERG(P1, P2)：把P1和P2为链首的两条链合并,回送合并后的链首；

·函数ENTRY(i)：回送标识符i在符号表中的位置。 5.6.6 含有数组元素的赋值语句翻译规则如下：

①A→V：=E {IF V·OFFSET=null THEN GEN(：=,E·PLACE,_,V·PLACE) /*V为简单变量*/

ELSE GEN([]＝,E·PLACE,_V·PLACE[V·OFFSET]) /*V为数组变量*/}

②E→E(1)+E(2) {T：=NEWTEMP；GEN(+，E(1)·PLACE，E(2)·PLACE,T)；E·PLACE：=T)

③E→(E(1)) {E·PLACE：＝E(1)·PLACE)

④E→V {IF V·OFFSET=null THEN E·PLACE：=V·PLACE

/*V为简单变量*/ ELSE BEGIN T：=NEWTEMP； GEN(＝[],V·PLACE[V OFFSET],_,T)； E·PLACE：=T END /*V为数组变量*/}

⑤V→elist] {T：=NEWTEMP；GEN(-,elist·ARRAY,C,T)；

/*elist·ARRAY为数组的首地址a, C为常数：d2d3? dn+d3 ?dn+?+dn+1*/

V·PLACE：=T； V·OFFSET：=elist·PLACE} ⑥V→i {V·PLACE：=ENTRY(i)：V·OFFSET：=null}

/*V·OFFSET为null表示V为简单变量*/ ⑦elist→elist(1),E {T：=NEWTEMP；k：=elist(1).DIM+1；/*下标记数，初值elist(l).DIM=1*/ dK：=LIMIT(elist(l).ARRAY,K)；/*给出数组第K维的长度*/ GEN (*,elist(l).PLACE,dK,T)； GEN(+,E·PLACE,T,T)； elist·ARRAY：=elist(l).ARRAY； elist·PLACE：=T； elist·DIM：=K} ⑧elist→i[E {elist·PLACE：=E·PLACE；elist·DIM：=1；elist·ARRAY：=ENTRY(i) /*ENTRY(i)为数组i的入口地址(即首地址a)*/}

己知A是一个10X20的数组且按行存放,求： (1)赋值语句X：=A[I,J]的四元式序列； (2)赋值语句A[I+2, J+1]： =M+N的四元式序列。

5.6.7 改写例题5.12文法G描述布尔表达式的语义子程序,使得i(1)rop i(2)不按通常方式翻译为下面的相继两个四元式：

(jrop, i(1), i(2), 0) (j_,_,0) 而是翻译成如下的一个四元式： (jnrop, i(1), i(2), 0)

使得当iMrop i(2)为假时发生转移，而为真时并不发生转移(即顺序执行下一个四元式),从而 产生效率较高的四元式代码。

5.6.8 (上海交大2000年研究生试题) 给出文法G[S]：S→-SaA|A A→AbB|B B→cSd|e

（1)请证实AacAbcBaAdbed是文法G[S]的一个句型。 (2)请写出该句型的所有短语、素短语以及句柄。

(3)为文法G[S]每个产生式写出相应的翻译子程序，使句型AacAbcBaAdbed经该翻译 方案后，输出131042521430。

(4)文法G[S]是不是SLR文法？请构造分析表证实之。

5.6.9 (上海交大2000年研究生试题) 语句While AD then x:=F[i,j] else x:=x+l经翻译后的三地址语句或四元式是 什么？（设三地址语句或四元式自100开始存放，数组F的内情向量自300开始存放，数组首地址500,每个数组元素占四字节。）

5.7.0 (上海交大1997年研究生试题) 文法G及相应的翻译方案如下 S→bts{printf:\

S→a {print: \ T→R {print: \ R→R/S {print: \ R→S {print: \ (1）文法G属于Chomsky哪一型文法？

(2)符号串bR/bTc/bSc/ac是不是该文法的一个句型，请证实。 （3)若是句型，写出该句型的所有短语、素短语以及句柄。 (4)文法G是不是算符优先文法，请予证实。

（5)文法G经消除左递归后得到的等价文法G’是不是LL(1)文法，请予证实。 (6)文法G是不是SLR(1)文法，请予以证实。

(7)对于题2的输入符号串，该翻译方案的输出是什么？

5.7.1 下面是用筛选法求素数的程序段，试将其翻译为四元式序列。 for i：=2 to N do B [i]：=true； i：=1；

while i≤N do begin

i：=i+l； if B[i]then begin

j：=2；

while i*j≤N do begin

B[i*j]：=false j：=j+1

end end end； 5.7.2 使用中间语言有什么好处？

5.7.3 将下面的语句翻译成四元式序列： while A

5.7.4 （陕西省1999年自考）

已知源程序如下：

prod:=0; i=1；

WHILE i≤20 do begin

prod:=prod+a[i]*b[i]； i=i+l end；

试按语法制导翻译法将上述源程序翻译成四元式序列（设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节）。 5.7.5 (中科元计算所1999年研究生试题) 己知表达式为A+B*(C-D）**N（**为幂乘） （1)给出该表达式的逆波兰式表示（后缀式）。 (2）给出上述表达式的四元式和三元式序列。 5.7.6 (中科元计算所1999年研究生试题) 文法G的产生式如下：

S→(L)|α L→L，S|S

（1)试写出一个语法制导定义，它输出配对括号个数。

(2）写一个翻译方案，打印每个a的嵌套深度。如((a), a),打印2,1。

5.7.7 (中科元计算所2000年研究生试题) 程序的文法如下：

p→D

D→D；D|id:T|proc id；D；S

（1)写一个语法制导定义，打印该程序一共声明了多少个id? (2）写一个翻译方案，打印该程序每个变量id的嵌套深度。

5.7.8 (南开大学1998年研究生试题) 写出语句

X:=(a+b)*c Y=d↑（a+b) 的间接三元式。

5.7.9 (国防科大1999年研究生试题) 把语句if a>b then while x>0 do x:=x-2 else y:=y+1； 翻译为四元式序列。

5.8.0 (国防科大1999年研究生试题) 把下面的语句

while (A>B) do

if (C

5.8.1举例说明什么是语法制导的翻译。

5.8.2 对下面的程序段，产生相应的四元式，并给出填符号表、返填、拉链等过程的执行情况。

GOTO L1； S1；

GOTO L1； S2；

COTO L1； L1： S3；

GOTO Ll； L2： S4；

GOTO L2； S5；

文法G[P]↑及相应翻译方案为

p→bQb {print：”1”} Q→cR {print：“2”} Q→a {print： \ R→Qad {print： \

(1)该文法是不是算符优先文法，请构造算符优先关系表证实之。 (2)输入串为bcccaadadadb时，该翻译方案的输出是什么？

5

※<习题六>

第六章 程序运行时存储空间组织

单项选择题：

6.1.1．过程的DISPLAY表中记录了______＿。 a.过程的连接数据 b.过程的嵌套层次 c.过程的返回地址 d.过程的入口地址 6.1.2．过程Pi调用P2时，连接数据不包含______。

a.嵌套层次显示表 b.老SP c.返回地址 d.全局DISPLAY地址 6.1.3．程序所需的数据空间在程序运行前就可确定，称为_____＿管理技术。

（陕西省1997年自考题） a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 6.1.4.堆式动态分配申请和释放存储空间遵守_______＿原则。 a.先请先放 b.先请后放 c.后请先放 d.任意 6.1.5．静态分配允许程序出现_______。

a.递归过程 b.可变体积的数据项目 c.静态变量 d.待定性质的名字 6.1.6.活动记录中的连接数据不包含____。

a.老SP b.返回地址 c.全局DISPLAY地址 d.形式单元

6.1.7. Fortran语言采用静态分配策略时，任一活动的活动记录中不包括____＿。

（西安电子科大2000年研究生试题） a.控制链 b.机器状态 c.返回地址 d.访问链 6.1.8．在编译方法中，动态存储分配的含义是_______。

a.在运行阶段对源程序中的数组、变量、参数等进行分配 b.在编译阶段对源程序中的数组、变量、参数等进行分配

c.在编译阶段对源程序中的数组、变量、参数等进行分配，在运行时这些数组、变 量、参数的地址可根据需要改变 d.以上都不正确

6.1.9.在编译时有传名功能的高级程序语言是______。 a. Fortran b. Basic c. Pascal d. ALGOL

6.1.10.栈式动态分配与管理在过程返回时应做的工作有____＿。 a.保护SP b.恢复SP c.保护TOP d.恢复TOP

多项选择题：

6.2.1. 如果活动记录中没有DISPLAY表，则说明_____＿。（陕西省1998年自考题） a.程序中不允许有递归定义的过程 b.程序中不允许有嵌套定义的过程

c.程序中既不允许有嵌套定义的过程，也不允许有递归定义的过程 d．程序中允许有递归定义的过程，也允许有嵌套定义的过程 e.程序中不允许有嵌套定义的过程，但可以有递归定义的过程 6.2.2. 动态存储分配可采用的分配方案有____＿。 a.队式存储分配 b.栈式存储分配 c.链式存储分配 d.堆式存储分配 e.线性存储分配

6.2.3．下面___＿需要在运行阶段分配存储空间。 a.数组 b.指针变量 c.动态数组· d.静态变量 e.动态变量

6.2.4栈式动态分配允许____＿。

a.递归过程 b.分程序结构 c.动态变量 d.动态数组 e.静态数组

6.2.5．栈式动态分配与管理因调用而进入过程之后，要做的工作是_____。 a.定义新的活动记录的SP b.保护返回地址。 c．传递参数值 d.建立DISPLAY表 e.定义新的活动记录的 TOP 6.2.6．过程B1调用B2时，连接数据包括____＿。 a. DISPLAY表 b.老SP值 c.返回地址 d.全局DISPLAY地址 e.参数表

6.2.7.运行阶段的存储组织与管理是为了____＿。

a.提高编译程序的运行速度 b.提高目标程序的运行速度 c.优化运行空间的管理 d.节省内存空间 e.为运行阶段的存储分配做准备

6.2.8．静态分配不允许程序出现______。

a.逆归过程 b.静态数组 c.可变体积的数据项目 d.待定性质的名字 e.静态变量 6.2.9.活动记录包括______。

a.局部变量b.连接数据c.形式单元

d.局部数组的内情变量 e.临时工作单元

6.2.10．栈式动态分配与管理在过程P调用过程Q时，应做的工作为_____＿。 a.保护过程P的SP b.将过程Ｐ的DISPLAY表地址传给Q的活动记录 c.传递参数值 d.传递参数个数 e.保护返回地址 填空题：

6.3.1．DISPLAY表用来记录__________________，它的体积在_______时确定。 6.3.2.堆式动态分配策略允许用户动态的_________＿和________＿存储空间。

（陕西省1999年自考题） 6.3.3.如果一个程序语言不允许_________，不许含__________或_________，就能 在编译时确定程序的每个数据项目存储空间的位置。

6.3.4．使用栈式存储分配意味着，运行时每当进入一个过程就有一个相应的_________＿累

筑于栈顶。

6.3.5.指示器_______＿总是指向现行过程活动记录的起点，而指示器—则始终指向栈顶单 元。

6.3.6. FORTRAN语言采用了____＿存储空间分配方案，其程序所需的存储空间在____＿时 确定。

6.3.7.一个函数的活动记录体积在____＿时确定，数组内情向量表的体积在_____＿时确定， DISPLAY表的内容在_________＿阶段完成。

6.3.8.目标程序运行的动态分配策略中，含有_______＿和_________＿分配策略。

（陕西省1997年自考题） 6.3.9.在Pascal中，由于允许用户动态地申请与释放内存空间，所以必须采用_____＿存储 分配技术。

6.3.10.如果两个临时变量名________＿不相交，则它们可分配在同一单元中。

6.3.11.在进入一个分程序时，它的TOP单元的内容是由其__________的TOP单元所赋予 的。 判断题：

6.4.1．静态数组的存储空间可以在编译时确定。 （ ）

6.4.2.一个过程DISPLAY表的内容是它的调用者DISPLAY表的内容加上本过程的SP地址。

（ ）

6.4.3．动态数组的存储空间在编译时就可完全确定。 （ ）

（陕西省1997年自考题） 6.4.4.若过程prock第K次被调用，则prock的DISPLAY表中就有k+1个元素。（）

（西安电子科大1999年研究生试题） 6.4.5.分程序的正常出口不需要执行任何指令。 （）

6.4.6.换名参数的任何实现方法都是低效的，所以大多数程序语言都不采用“换名”方法。

（ ）

综合题：

6.5.1．何谓嵌套过程语言运行时的DISPLAY表？它的作用是什么？

6.5.2. 对允许递归调用的语言，编译时有什么特殊的工作要做？作为一种存储方法，层次单

元法是否可以支持程序的递归调用？为什么？

6.5.3. 有一程序如下：

program ex; a: integer;

procedure PP(x: integer); begin:

X:=S; x:=a+l end; begin

a:= 2; PP(a); write(a) end;

试用图表示ex调用PP (a)前后活动记录的过程。

6.5.4．一个Pascal程序中的嵌套过程定义情况见下面的程序。若程序运行时的存储空间采

用栈式动态分配的方案。请给出调用序列为sort--quicksort--partition-exchange时，exchange激活后的运行栈布局，指出exchange过程活动记录的DISPLAY表的内容。

6.5.5.在下面Pascal程序中，已经第二次（递归地）进入了f,请给出f第3次进入后的运行栈及DISPLAY的示意图。

PROGRAM test(input, output)： VAR K: integer;

FUNCTION f(n: integer): integer; BEGIN

IF n<=0 THEN f:=1 ELSE f:=n*f(n-1）： END; BEGIN K:=f(10;) write(K)

END.

6.5.6. 在栈式动态存储分配方案中。

(1)嵌套层次显示表DISPLAY的作用是什么？

(2)若不使用DISPLAY表而只使用一个单元access link,能否达到同样的目的？各自 的优缺点是什么？

(3)以下面的Pascal程序片断为例，对过程调用序列S→Q→P→E的情况，给出运行栈 的布局、E过程活动记录的DISPLAY表以及access link的内容。

6.5.7. 类Pascal结构（嵌套过程）的程序如下，该语言的编译器采用栈式动态存储分配策略

管理目标程序数据空间。

（1)若过程调用序列为：①Demo→A②Demo→A→B③Demo→A→B→B ④Demo→A→B→B→A

请分别给出这4个时刻运行栈的布局和使用的DISPLAY表。 （2）若该语言允许动态数组，编译程序应如何处置？如过程B有动态局部数组R[m:n], 请给出B第1次激活时，相应的数据空间的情况。

6.5.8．下面程序的结果是120。但是如果把第5行的abs(1)改成1的话，则程序结果为1。

试分析为什么会有这种不同的结果。

int fact(） ｛

static int i=5； if(i=0)｛return（1）：｝ else｛i=i-1：return((i+abs(1））*fact（））；｝ )

main()｛

printf(\ ｝

6.5.9. 对分程序结构的存储管理，请设计另一种存储分配方案，它只用一个全局的DISPLAY,

且无论什么时候，这个DISPLAY都包含所有可引用的活动记录地址（自行决定是仅对过程分配数据区还是对分程序也分配数据区)o在这种情况下，调用过程时必须注意保护老的DISPLAY,然后建立新的DISPLAY,并在返回时恢复老的DISPLAY.

6.5.10. 过程调用时参数传递的一种方式是“传名”，即将形式参数都替换成相应的实在参数（仅仅是文字替换）。其实现方法是：在进入被调用过程时不对实在参数预先进行计值，而是让过程体中每当使用到相应的形参时才对替换的实参进行计值。

例如，假定在过程P中的某个分程序B内通过语句Q (E)调用了过程Q,此处实参E 是一个表达式，与它对应的形参假定是Z。这样，当过程Q中的某一分程序B1对Z的引用 则意味着对实参E进行一次计值；而E是属于P的表达式，因此，它的工作必须在P的环境中进行；如计算E所生成的临时变量应放入B的TOP所指栈顶之上，但这无疑会破坏当前运行栈在P之上已形成的Q数据区。试就此问题给出一种解决方案。 6.5.11. 有一程序如下所示： procedure main is

i: integer; j：integer;

function m(j：integer) return integer is

function modO return integer is begin return0; end mod0; function mod l return integer is begif return 1：end modl： function mod2 return integer is begin return2；end mod2; begin

if(j>=i) then m(j-i) else case j mod 3 is

while 0=）return mod0; while 1＝＞return mod l； while 2=＞return mod2;

end case; end if; endm begin

i:=40; j:=m(57); write(j); end main;

（1）画出程序执行时的活动树，并给出程序运行的结果。

(2)设main的嵌套深度为1，给出各子程序嵌套深度，并以树的形式给出main中各子程序的嵌套关系（若A嵌套B，则A是B的父亲）。

(3)程序运行过程中，栈中活动记录的最大值是多少？

(4)试画出栈中活动记录达到最大值时各活动记录中的控制链和访问链（指向正确的活

动记录）。

6.5.12. (1)写出实现一般递归过程的活动记录结构以及过程调用、过程进入与过程返回的指

令．

(2)对以return（表达式）形式（这个表达式本身是一个递归调用）返回函数值的特殊

函数过程，给出不增加时间开销但能节省存储空间的实现方法。假定语言中过程参数只有传值和传地址两种形式。为便于理解，举下例说明这种特殊的函数调用：

FUNCTION gcd(P,q: integer): integer; BEGIN

if P MOD q=0 then return q else return gcd (q, P MOD q) END;

6.5.13. 请说明，当过程P1调用过程P２而进入P２后，P２应如何建立起自已的DISPLAY? 6.5.14. 有一程序如下：

program main(）；

VAR A,B;C：integer; procedure PP(A,B,C); begin

C:=C+10; B:=A*B+C; end; begin

A：＝100; B:=20 C:=A+B*10; call PP(A+B,A,C); print A end.

试画出过程PP调用前后的活动记录。

6.5.15. 某程序的结构如图6.22所示，其中A, B, C为过程名。 (1)请分别画出过程C调用A前后的栈顶活动记录； (2)画出C和B的DISPLAY.

6.5.16. （1)写出实现一般递归过程的活动记录结构以及过程调用、过程进入与过程返回的

指令。

(2）对以return（表达式）形式（这个表达式本身是一个递归调用）返回函数值的特殊

函数过程，给出不增加时间开销但能节省存储空间的实现方法。假定语言中过程参数只有传值和传地址两种形式。为便于理解，举下例说明这种特殊的函数调用：

FUNCTION gcd (P, q: integer): integer; BEGIN

if P MOD q=O then return q else return gcd (q, P MOD q) END;

6.5.17. 某语言允许过程嵌套定义和递归调用（如Pascal语言），若在栈式动态存储分配中采

用嵌套层次显示表DISPLAY解决对非局部变量的引用问题，试给出下列程序执行到语句“b:=10;”时运行栈及DISPLAY表的示意图。

var x,y; procedure p;

var a; procedure q; var b; begin{q} b:=10; end(q)： procedure s; var c,d; procedure r; var e,f; begin{r} call q; end {r}； begin { s} call r; end(s)； begin {p} call s;

end(p)； begin {main} call p;

end{main｝．

6.5.18. 类似Pascal或类似Module-2的一段程序如下，其变量作用域遵循分程序结构规则，

若采用找式方案进行运行时存储管理，请给出执行到RETURNa-b语句时，列出运行栈中各过程（函数）活动记录的动态链和DISPLAY表。

6.5.20. 一个C语言程序如下： func(il,i2,i3) long il,i2,i3； ｛

long jl,j2,j3：

printf(\ printf(\ ｝ main {

long il,i2,i3;

func(i1,i2,i3); ｝

该程序在SUN工作站上的运行结果如下：

Adresses of il,i2,i3=35777773634,35777773640,35777773644 Adresses of j 1 j2j3=35777773524,35777773520,35777773514一 从上面的结果可以看出，func函数的3个形式参数的地址依次升高，而3个局部变量的地址依次降低，试说明为什么会有这个区别。

6.5.21. 在Pascal这类嵌套的分程序结构语言中，如何解决变量的定义域问题？请给出一个

合理的变量表构造方法（简述原理）。

5

※<习题七>

第七章 代码优化与目标代码生成

典型例题: 单项选择题

7.1.1.优化可生成＿的目标代码。（陕西省2000年自考题）

a.运行时间较短 b.占用存储空间较小

c.运行时间短但占用内存空间大 d.运行时间短且占用存储空间小 7.1.2．下列—优化方法不是针对循环优化进行的。

a.强度削弱 b.删除归纳变量 c.删除多余运算 d.代码外提 7.1.3.基本块内的优化为＿。 （陕西省1998年自考题）

a.代码外提，删除归纳变量 b.删除多余运算，删除无用赋值 c.强度削弱，代码外提 d.循环展开，循环合并 7.1.4.关于必经结点的二元关系，下列叙述中不正确的是__。

a.满足自反性 b.满足传递性 c.满足反对称性 d.满足对称性 7.1.5.对一个基本块来说，＿是正确的。（陕西省2000年自考题）

a.只有一个入口语句和一个出口语句 b.有一个入口语句和多个出口语句 c.有多个入口语句和一个出口语句 d.有多个入口语句和多个出口语句 7.1.6.在程序流图中，我们称具有下述性质＿的结点序列为一个循环。

a.它们是非连通的且只有一个入自结点 b.它们是强连通的但有多个入口结点 c.它们是非连通的但有多个入口结点 d.它们是强连通的且只有一个入口结点 7.1.7.＿不可能是目标代码。（陕西省1997年自考题）

a.汇编指令代码 b.可重定位指令代码 c.绝对指令代码 d.中间代码 7.1.8．＿属于局部优化。

a.代码外提 b.删除多余运算。c.强度削弱 d.删除归纳变量 7.1.9.下面＿不能作为一个基本块的入口。

a.程序的第一个语句 b.条件语句转移到的语句 c.无条件语句之后的下一条语句 d.无条件语句转移到的语句 7.1.10．下列—优化方法是针对循环优化进行的。

a.复写传播 b.删除归纳变量 c.删除无用赋值 d.合并已知量

7.1.11.属于基本块的优化为＿。（陕西省1997年自考题）

a.删除无用赋值 b.删除归纳变量 c.强度削弱 d.代码外提 7.1.12.经过编译所得到的目标程序是—。 a.二元式序列 b.四元式序列

c.间接三元式 d.机器语言程序或汇编语言程序 7.1.13.一个控制流程图就是具有＿的有向图。

a.唯一入口结点 b.唯一出口结点 c.唯一首结点 d.唯一尾结点

多项选择题：

7.2.1．根据优化所涉及的范围，可将优化分为＿。 a.局部优化 b.过程优化。 C.全局优化 d.循环优化 e.四元式优化

7.2.2.下列优化中，属于循环优化的有＿。（陕西省1997年自考题） a.强度削弱 b.合并己知量 c.删除无用赋值 d.删除归纳变量 e.代码外提

7.2.3.如果a→b是程序流图中的一条边，则由这条回边构成的循环由＿结点组成。 （陕西省1999年自考题）

a. a b. b c.有通路到达b的结点

d.有通路到达a且该通路上不经过b的结点 e.有通路到达b且该通路上不经过a的结点

7.2.4. a, b, c是程序流图中的三个结点，＿是正确的。（陕西省1998年自考题） a. a DOM b, b DOM c则a DOM c b. a DOM a c. a DOM b则b DOM a d. a DOM b, b DOM a则a=b e. a DOM b. a DOM c则b=c 7.2.5.采用无环有向图(DAG),可以实现的优化有＿。（陕西省2000年自考题） a.合并已知量 b.删除公共子表达式 c.强度削弱 d.删除无用赋值 e.删除归纳变量

7.2.6．如果A离开循环L后仍然活跃，则对不变运算S：A:=B op C来说，必须满足下面的几个条件方可将不变运算S提到循环外。 a. A在L中已经定值

b. A在L中其他地方未再定值

c. S所在结点是L的所有出口结点的必经结点 d．S所在结点不是L的所有出口结点的必经结点 e. L中所有A的引用点只有S中A的定值才能到达 7.2.7.编译程序的输出结果可以是＿。

a.目标代码 b.汇编语言代码 c.中间代码 d.优化后的中间代码 e.可重定位代码

7.2.8．通过DAG图可实现—优化。

a.合并已知量 b.变换循环控制条件 c.删除多余运算 d.复写传播 e.删除无用赋值 7.2.9．局部优化包括＿。

a.删除归纳变量 b.删除多余运算。 c.合并已知量