单选题 (4分)

令文法G[E]为：E->E+T | T

T->T*F | F

F-> (E) | i

句型 F*i+T 的最左素短语是（）

A.F

B.i

C.T

D.F*i

B

短语：

F*i+T、F*i、F、i

素短语：

i

最左素短语：

i

单选题 (4分)

若在C语言程序中出现“aa 11 bb=123;”，且不出现在引号和注释里，在编译时会

A.语法分析时报错

B.语义分析时报错

C.生成中间代码时报错

D.语法分析时报错

D

单选题 (4分)

活动记录中静态链的作用是（）

A.用以实现对非局部名字的访问

B.用来指向静态数据区

C.表明过程的嵌套层次

D.建立本过程和主调过程间的联系

A

嵌套过程语言的程序，内层过程引用非局部量可通过（B ）跟踪外层过程最新活动记录的位置

A 老SP B 静态链C Previous链 D 全局display

静态链的作用是（A）

A.存放过程的直接外层过程最新活动记录的地址，用以访问局部数据

B.存放主调过程最新活动记录的地址，用以建立主被调的联系

C.存放代码的返回地址，用以返回主调程序

D.存放静态数据区的地址，用以访问静态数据

表达式(A + B) * (- C - D) 的逆波兰式是：

A.ABCD+*--

B.AB+CD--*

C.AB+C-D-*

D.AB+-CD-*

C

如果某种程序设计语言设计的程序，其所需数据空间的总量在编译时是完全确定了的，则最好采用以下哪种存储分配策略

A.堆式分配策略

B.栈式分配策略

C.静态分配策略

D.以上都有

C

下面哪种不是自底向上的语法分析文法（）。

A.LR(1)

B.SLR(1)

C.LL(K)

D.算符优先法

C

若一个文法是递归的，则它产生的句子个数是（）

A.无穷个

B.可能有限个，可能无穷个

C.有限个

A

以下关于DFA描述错误的是（）

A.初态唯一

B.终态唯一

C.转态转换函数是单值映射

D.不含标记有空串的转换弧

B

下面关于编译方式与解释方式描述有误的是（）

A.编译方式是先翻译后执行

B.解释方式是边翻译边执行

C.在解释方式下，程序运行时解释器掌握控制权

D.解释方式优于编译方式

D

令文法G[E]为：E->E+T| T

T->T*F| F

F->(E) | i

E+F*(T+i)文法G的一个规范句型，指出这个规范句型的句柄是（）

A.i

B.T

C.T+i

D.F

D

LR分析器的核心部分是一张分析表，这张表包括（）

A.预测分析表、转态转换表

B.优先关系矩阵、动作表

C.动作表、状态转换表

D.内情向量表、符号表

C

局部优化是在什么范围内进行的优化？

A.过程体

B.函数体

C.基本块

D.循环体

C

如果文法无二义性，则与规范归约互为逆过程的是（）

A.最右归约

B.最左归约

C.规范推到

D.最左推导

C

在C语言中，不同过程中的变量名可以相同，这些相同的变量名在符号表中存入同一符号表入口。

错

递归文法的语言是无穷集，程序设计语言的文法通常是递归的

对

中间代码优化的目的是生成更有效的目标代码，为了追求高效的目标代码，优化应不计代价。

错

“遍”是对源程序或源程序的中间结果从头到尾扫描一次，并做有关加工处理，生成新的中间结果或目标程序。一个编译程序所分遍数越多越好。

错

只能用机器语言编写编译程序

错

过程的活动指该过程的一次执行，在任一时刻，一个过程只可能有一个活动活跃着。（）

错

如果文法中的某个句型，存在不同的推导序列，则该文法就是二义性文法

错

反例：存在非二义性文法，其某些句型有多个推导序列，但所有句子只有一个推导树。

S → A b | B c
A → a
B → a

句型 S 的推导序列：

序列 1：S ⇒ A b

序列 2：S ⇒ B c

句型 S 有两个不同的推导序列。

句子分析：

句子 a b 的唯一推导：S ⇒ A b ⇒ a b

句子 a c 的唯一推导：S ⇒ B c ⇒ a c

所有句子（如 a b、a c）都只有唯一语法树，因此文法 非二义性。

句型和句子

句子：仅含终结符的句型

二义性文法的正确定义

一个文法是二义性的，当且仅当存在 至少一个句子（即终结符串），该句子对应：

两个或更多不同的 最左推导（或等价地，两个或更多不同的 最右推导），或

两个或更多不同的 语法树。

关键点：二义性必须针对 句子（终结符串） 定义，而不是针对一般的句型（可能包含非终结符）。

现有文法G[S]： S—>a |b | (T)

T —>S T’

T’->*ST’|ɛ

则FOLLOW(S)为：( )

A.{#}

B.{#,)}

C.{#,*,)}

D.{*,)}

C

FIRST(S)={a,b,(}

FIRST(T)=FIRST(S)={a,b,(}

FIRST(T')={*, $\varepsilon$ }

FOLLOW(S)={#} $\cup$ FIRST(T')- $\varepsilon$ $\cup$ FOLLOW(T)={#,*,)}

FOLLOW(T)={)}

FOLLOW(T')=FOLLOW(T)={)}

非终结符 FOLLOW 集关键步骤说明
S {#,∗,)}
1. 开始符号加入 # [1]
2. T→ST′加入 * [3] FIRST(T')- $\varepsilon$

3. T→ST′,T′⇒∗ε 时加入 FOLLOW(T)={)} [4]

T {)} S→(T) 直接加入 ) [2]
T′ {)}
T→ST′ 末尾加入 FOLLOW(T)={)} [4]

当T’推导出 ε 时，产生式T→ST’等价于T→S（即T’“隐身”）。此时，S在T中的位置相当于直接处于T的末尾，因此S后面的符号（即FOLLOW(T)）会直接成为T’后面的符号。
换句话说，T’作为可空后缀，其后面的符号本质上就是T后面的符号，因此FOLLOW(T')与FOLLOW(T)相同。

空符号串在语法分析中对后继符号集的传递作用

非终结符	FOLLOW 集	关键步骤说明
S	{#,∗,)}	1. 开始符号加入 # [1] 2. T→ST′加入 * [3] FIRST(T')- $\varepsilon$ 3. T→ST′,T′⇒∗ε 时加入 FOLLOW(T)={)} [4]
T	{)}	S→(T) 直接加入 ) [2]
T′	{)}	T→ST′ 末尾加入 FOLLOW(T)={)} [4] 当`T’`推导出 ε 时，产生式`T→ST’`等价于`T→S`（即`T’`“隐身”）。此时，`S`在`T`中的位置相当于直接处于`T`的末尾，因此`S`后面的符号（即`FOLLOW(T)`）会直接成为`T’`后面的符号。换句话说，`T’`作为可空后缀，其后面的符号本质上就是`T`后面的符号，因此`FOLLOW(T')`与`FOLLOW(T)`相同。空符号串在语法分析中对后继符号集的传递作用

间接三元式表示法的特点为（）。

A.采用间接码表，便于优化处理

B.节省存储空间，不便于表的修改

C.便于优化处理，浪费存储空间

D.节省存储空间，不便于优化处理

A

四元式（Quadruples）

结构：包含四个字段 (运算符, 运算对象1, 运算对象2, 结果)。
特点：
每个四元式独立存储运算信息，便于代码优化（如删除无用代码、重新安排计算顺序）。
需要显式存储临时变量（结果字段），可能导致存储空间浪费。

对应选项：
C. 便于优化处理，浪费存储空间。

三元式（Triples）

结构：通过运算对象的位置（编号）引用操作数，不单独存储临时变量，而是通过 “对三元式的引用” 表示中间结果。
特点：
无需显式存储临时变量，节省存储空间。
若需调整计算顺序（如优化时），可能需要大量修改三元式编号的引用，不便于优化。

对应选项：
D. 节省存储空间，不便于优化处理

间接三元式（Indirect Triples）

结构：在三元式基础上增加一个 “执行顺序表”（间接码表），通过该表记录三元式的执行顺序，而非直接修改三元式本身。
特点：
优化时只需调整间接码表，无需修改三元式，便于优化处理。
需额外维护间接码表，增加了实现复杂度。

对应选项：
A. 采用间接码表，便于优化处理。