9．程序中的表达式语句在语义翻译时不需要回填技术。 (√) 10．对中间代码的优化依赖于具体的计算机。 (× ) 三、填空题(每空1分，共10分)

1．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。

2．语法分析基于__上下文无关___文法进行，即识别的是该类文法的句子。语法分析的有效工具是__语法树___。

3．分析句型时，应用算符优先分析技术时，每步被直接归约的是__最左素短语___，而应用LR分析技术时，每步被直接归约的是___句柄__。

4．语义分析阶段所生成的与源程序等价的中间表示形式可以有__逆波兰___、___四无式表示__与___三元式表示__等。

一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）

1．一个 LL(l)文法一定是无二义的。 (× ) 7．LR 法是自顶向下语法分析方法。 (× ) 2．正规文法产生的语言都可以用上下文无关文法来描述。 (× )

3．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 (√) 4．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 (× ) 5．逆波兰法表示的表达式亦称前缀式 。 (√ )

6．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 (√ ) 8．数组元素的地址计算与数组的存储方式有关。(× ) 9．算符优先关系表不一定存在对应的优先函数。 (×)

10．对于数据空间的存贮分配， FORTRAN 采用动态贮存分配策略。 (×) 三、填空题(每空1分，共10分)

5

1．语法分析是依据语言的__语法___规则进行的，中间代码产生是依据语言的__语义___规进行的。 2．语法分析器的输入是__单词符号串___，其输出是__语法单位___。 3．一个名字的属性包括__类型___和__作用域___。 4．产生式是用于定义___语法成分__的一种书写规则。

5．逆波兰式 ab+c+ d*e- 所表达的表达式为__(a+b+c)*d-e___ 。

6．语法分析最常用的两类方法是__自上而下___和__自下而上___分析法。

二、填空题（每空2分，共22分）

1．已知文法G[S]：S→(A)|a ，A→AcS|S|b ；该文法的开始符号是 S，非终结符号集合为

{S,A}，终结符号集合为{a,b,c,(,)}。

2．描述源程序中的单词结构有3种方法：有穷自动机，正规式和正规文法。 3．自上而下的语法分析方法有LL(1)和递归下降方法。

4．设有文法G[S]：S→Sa|a ，构造它的拓广文法，引入一个产生式：Sˊ→S ；则I。=Closure（{[Sˊ→·S，＃]}）= {[Sˊ→·S，＃], [S→·Sa，＃/a], [S→·a，＃/a]}。 5．在LR（0）项目集规范族中，若有项目：A?A?bB，其中b?VT，称该项目为移进项目。 6.LL(1)语法分析方法中应解决的主要问题是消除回溯；LR语法分析方法中应解决的主要问

题是项目冲突。

三、判断题（判断下列各题的正错，若正确，在括号中写“正”；否则写“错”。每题2分，共

16分）

1．一个文法有二义性，则由它描述的语言一定具有二义性。（错 ）

2．若一个语言有无穷多个句子，则定义该语言的文法一定是递归的。（正 ） 3．若有正规式a*b，则与之等价的文法应该是G[A]：A→aA|b 。（ 正 ） 4．设有文法G[A]：A→aB ，B→bB|b，则该文法是LL(1)文法。（错 ） 5．由文法法G的开始符号S推导出来的符号串，称为文法G的句子。（ 错 ） 6．最左素短语是句型最左边的短语。（错 ）

7．LR语法分析法是一种规范规约的分析方法。（正 ）

6

8．存在能够被确定的有穷自动机DFA识别，却不能用正规式表示的语言。（ 错 ）

1. 文法G的一个句子对应于多个推导，则G是二义性的。（× ）

2. 动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（√ ） 3. 算符优先文法采用“移进－规约”技术，其规约过程是规范的。（ × ） 4. 删除归纳变量是在强度削弱以后进行。（ √ ）

5. 在目标代码生成阶段，符号表用于目标代码生成。（ × ）

1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两

种：静态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。 2. 规范规约是最（3）规约。

3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。

6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i，j]的地址计算公式为（9）。

7．局部优化是局限于一个（10）范围内的一种优化。 答案：：

一． 填空题（每空2分，共20分）

(1) 栈式动态存储分配 (2) 堆式动态存储分配 (3) 左 (4) 语法分析 (5) 目标代码生成 (6) 表格管理 (7) xyz*ab+/+ (8) 继承属性

7

(9) a+(i-1)*20+j-1 (10)

基本块

一、 填空题（每空2分，共20分）

1目标程序 （target code） 语法分析（syntax analyzer） 代码优化器（code optimizer） 代码产生器（code generator） 符号表管理（symbol table manager）

2 继承属性（inherited attribute） 3 局部优化（local optimization） 4 四元式（quatriple） 5 E + * ( ) id

二、填空题（本大题共5小题，每小题2分，共10分）

1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。 2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。

3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。

4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。

5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。

三、名词解释题(共5小题，每小题4分，共20分)

1．词法分析

词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位， 并转换成统一的内部表示(token)，送给语法分析程序。 2．LL(1)文法

若文法的任何两个产生式A ? ? | ?都满足下面两个条件： （1）FIRST(? ) ? FIRST(? ) = ?；

（2）若? ?* ? ，那么FIRST(? ) ? FOLLOW( A ) = ?。

我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左 向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步 动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一 些明显的性质，它不是二义的，也不含左递归。 3．语法树

句子的树结构表示法称为语法树(语法分析树或语法推导树)。 给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的

8