视频加载失败

课程

返回 编译原理 归档
8232 字
约 24 分钟

编译原理试题

编译原理exercises/review·更新于 2026-09-15

编译原理试题

一、单项选择题

1. 将编译程序分成若干个”遍”是为了（ ）。

  • A. 提高程序的执行效率
  • B. 使程序的结构更加清晰
  • C. 利用有限的机器内存并提高机器的执行效率
  • D. 利用有限的机器内存但降低了机器的执行效率

答案：B

2. 不可能是目标代码的是（ ）。

  • A. 汇编指令代码
  • B. 可重定位指令代码
  • C. 绝对指令代码
  • D. 中间代码

答案：D

3. 词法分析器的输入是（ ）。

  • A. 单词符号串
  • B. 源程序
  • C. 语法单位
  • D. 目标程序

答案：B

4. 中间代码生成时所遵循的是（ ）。

  • A. 语法规则
  • B. 词法规则
  • C. 语义规则
  • D. 等价变换规则

答案：C

5. 编译程序是对（ ）。

  • A. 汇编程序的翻译
  • B. 高级语言程序的解释执行
  • C. 机器语言的执行
  • D. 高级语言的翻译

答案：D

6. 词法分析应遵循（ ）。

  • A. 语义规则
  • B. 语法规则
  • C. 构词规则
  • D. 等价变换规则

答案：C

7. 词法分析器的输出结果是（ ）。

  • A. 单词的种别编码
  • B. 单词在符号表中的位置
  • C. 单词的种别编码和属性值
  • D. 单词属性值

答案：C

8. 正规式 M1M_1 和 M2M_2 等价是指（ ）。

  • A. M1M_1 和 M2M_2 的状态数相等
  • B. M1M_1 和 M2M_2 的有向弧条数相等
  • C. M1M_1 和 M2M_2 所识别的语言集相等
  • D. M1M_1 和 M2M_2 状态数和有向弧条数相等

答案：C

9. 词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此（ ）。

  • A. 词法分析器应作为独立的一遍
  • B. 词法分析器作为子程序较好
  • C. 词法分析器分解为多个过程，由语法分析器选择使用
  • D. 词法分析器并不作为一个独立的阶段

答案：B

10. 如果 L(M1)=L(M2)L(M_1) = L(M_2)，则 M1M_1 与 M2M_2（ ）。

  • A. 等价
  • B. 都是二义的
  • C. 都是无二义的
  • D. 它们的状态数相等

答案：A

11. 文法 GG：S→xSx∣yS \to xSx \mid y 所识别的语言是（ ）。

  • A. xyxxyx
  • B. (xyx)∗(xyx)^*
  • C. xnyxn (n≥0)x^n yx^n\ (n \geq 0)
  • D. x∗yx∗x^* yx^*

答案：C

12. 文法 GG 描述的语言 L(G)L(G) 是指（ ）。

  • A. 从 SS 推出的所有符号串的集合
  • B. 从 SS 推出的终结符号串的集合
  • C. 从 SS 推出的含非终结符的符号串的集合
  • D. 以上说法都不对

答案：B

13. 有限状态自动机能识别（ ）。

  • A. 上下文无关文法
  • B. 上下文有关文法
  • C. 正规文法
  • D. 短语文法

答案：C

14. 如果文法 GG 是无二义的，则它的任何句子（ ）。

  • A. 最左推导和最右推导对应的语法树必定相同
  • B. 最左推导和最右推导对应的语法树可能不同
  • C. 最左推导和最右推导必定相同
  • D. 可能存在两个不同的最左推导，但它们对应的语法树相同

答案：A

15. 由文法的开始符经 0 步或多步推导产生的文法符号序列是（ ）。

  • A. 短语
  • B. 句柄
  • C. 句型
  • D. 句子

答案：C

16. 文法 GG：

E→E+T∣T,T→T∗P∣P,P→(E)∣iE \to E + T \mid T,\quad T \to T * P \mid P,\quad P \to (E) \mid i

则句型 P+T+iP + T + i 的句柄为（ ）。

  • A. P+TP + T
  • B. PP
  • C. P+T+iP + T + i
  • D. ii

答案：B

17. 文法 GG：S→b∣∧∣(T)S \to b \mid \wedge \mid (T)，T→T∨S∣ST \to T \vee S \mid S，则 FIRSTVT(T)=\text{FIRSTVT}(T) = （ ）。

  • A. {b,∧,(}\{b, \wedge, (\}
  • B. {b,∧,)}\{b, \wedge, )\}
  • C. {b,∧,(,∨}\{b, \wedge, (, \vee\}
  • D. {b,∧,),∨}\{b, \wedge, ), \vee\}

答案：C

18. 产生正规语言的文法为（ ）。

  • A. 0 型
  • B. 1 型
  • C. 2 型
  • D. 3 型

答案：D

19. 任何算符优先文法（ ）优先函数。

  • A. 有一个
  • B. 没有
  • C. 有若干个
  • D. 可能有若干个

答案：D

20. 采用自上而下分析，必须（ ）。

  • A. 消除左递归
  • B. 消除右递归
  • C. 消除回溯
  • D. 提取公共左因子

答案：A

21. 在规范归约中，用（ ）来刻画可归约串。

  • A. 直接短语
  • B. 句柄
  • C. 最左素短语
  • D. 素短语

答案：B

22. 有文法 GG：E→E∗T∣TE \to E * T \mid T，T→T+i∣iT \to T + i \mid i，句子 1+2∗8+61 + 2 * 8 + 6 按该文法 GG 归约，其值为（ ）。

  • A. 23
  • B. 42
  • C. 30
  • D. 17

答案：B

23. 如果文法是无二义的，那么规范归约是指（ ）。

  • A. 最左推导的逆过程
  • B. 最右推导的逆过程
  • C. 规范推导
  • D. 最左归约的逆过程

答案：B

24. 文法 GG：S→S+T∣TS \to S + T \mid T，T→T∗P∣PT \to T * P \mid P，P→(S)∣iP \to (S) \mid i，句型 P+T+iP + T + i 的短语有（ ）。

  • A. i,P+Ti, P + T
  • B. P,P+T,i,P+T+iP, P + T, i, P + T + i
  • C. P+T+iP + T + i
  • D. P,P+T,iP, P + T, i

答案：B

25. 四元式之间的联系是通过（ ）实现的。

  • A. 指示器
  • B. 临时变量
  • C. 符号表
  • D. 程序变量

答案：B

26. 后缀式 ab+cd+/ab + cd + / 可用表达式（ ）来表示。

  • A. a+b/c+da + b / c + d
  • B. (a+b)/(c+d)(a + b) / (c + d)
  • C. a+b/(c+d)a + b / (c + d)
  • D. a+b+c/da + b + c / d

答案：B

27. 使用间接三元式表示法的主要目的（ ）。

  • A. 便于优化处理
  • B. 便于表的修改
  • C. 节省存储空间
  • D. 生成中间代码更容易

答案：A

28. 表达式 (¬A∨B)∧(C∨D)(\neg A \vee B) \wedge (C \vee D) 的逆波兰表示为（ ）。

  • A. ¬AB∨∧CD∨\neg AB \vee \wedge CD \vee
  • B. A¬B∨CD∨∧A \neg B \vee CD \vee \wedge
  • C. AB∨¬CD∨∧AB \vee \neg CD \vee \wedge
  • D. A¬B∨∧CD∨A \neg B \vee \wedge CD \vee

答案：B

二、判断题

1. 一个确定有限状态自动机中，有且仅有一个唯一的终态。（ ╳ ）

2. 设 RR 和 SS 分别是字母表 Σ\Sigma 上的正规式，则有 L(R∣S)=L(R)∪L(S)L(R \mid S) = L(R) \cup L(S)。（ √ ）

3. 自动机 M1M_1 和 M2M_2 的状态数不同，则二者必不等价。（ ╳ ）

4. 确定有限自动机以及非确定有限自动机都能正确地识别正规集。（ √ ）

5. 对任意一个右线性正规文法 GG，都存在一个 NFA MM，满足 L(G)=L(M)L(G) = L(M)。（ √ ）

6. 对任意一个右线性正规文法 GG，都存在一个 DFA MM，满足 L(G)=L(M)L(G) = L(M)。（ √ ）

7. 对任何正规式 ee，都存在一个 NFA MM，满足 L(M)=L(e)L(M) = L(e)。（ √ ）

8. 对任何正规式 ee，都存在一个 DFA MM，满足 L(M)=L(e)L(M) = L(e)。（ √ ）

9. 从一个句型到另一个句型的推导过程是唯一的。（ ╳ ）

10. 词法分析作为单独的一遍来处理较好。（ ╳ ）

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

12. 二义文法不是上下文无关文法。（ ╳ ）

13. 自上而下分析法是一种”移进—归约”法。（ ╳ ）

14. 文法是描述语言的语法结构的形式规则。（ √ ）

15. 产生式是定义语法范畴的一种书写规则。（ √ ）

16. 要构造行之有效的自上而下的分析器，则必须消除左递归。（ ╳ ）

17. 如果文法 GG 是无二义的，那么规范归约和规范推导是互逆的两个过程。（ √ ）

18. 自下而上的分析法是一种”移进—归约”法。（ √ ）

19. 如果文法 GG 是二义的，那么规范归约和规范推导是互逆的两个过程。（ ╳ ）

三、填空题

1. 解释程序和编译程序的区别在于（是否生成目标代码）。

2. 编译过程通常可分为 5 个阶段，分别是（词法分析）、（语法分析）、语义分析与中间代码产生、代码优化和目标代码生成。

3. 编译程序工作过程中，第一阶段输入是（源程序），最后阶段的输出为（目标代码）程序。

4. 把语法范畴翻译成中间代码所依据的是（语义规则）。

5. 目标代码可以是（汇编）指令代码或（可重定位）指令代码或绝对机器指令代码。

6. 词法分析的任务是：输入源程序，对构成源程序的（字符串）进行扫描和分解。

7. 源程序中的错误通常分为（语法错误）和（语义错误）两大类。

8. （编译程序）是将源程序翻译成目标程序的程序。

9. 一个上下文无关文法 GG 包括四个部分：（终结符号）、（非终结符号）、（开始符号）和一组（产生式）。

10. 若从一个符号序列经过若干步推导得到另一个符号序列，则称这个序列是一个（推导）。

11. 设文法 GG 的开始符号为 SS，如果 S⇒∗αS \Rightarrow^* \alpha，则称 α\alpha 是 L(G)L(G) 的一个（句型）。

12. 文法 GG 所产生的句子的全体是文法 GG 所定义的（语言）。

13. 若一个文法存在某个句子对应的两棵不同的语法树，则称这个文法是（二义文法）。

14. 程序语言的单词符号一般可分为五种：（关键字）、（标识符）、常数、（运算符）和界符。

15. （确定有限自动机 DFA）是非确定有限自动机 NFA 的一个特例。

16. 对于正规文法 GG 和有限自动机 MM，若 L(G)=L(M)L(G) = L(M)，则称 GG 和 MM 是（等价）的。

17. 若两个正规式所表示的正规集相等，则认为二者是（等价）的。

18. 按照语法分析树的建立方法，语法分析可分为两类：（自上而下分析）和（自下而上分析）。

19. 规范归约中的可归约串是指（句柄）。

20. 算符优先分析中的可归约串是指（最左素短语）。

21. （自下而上）语法分析的关键问题是精确定义可归约串的概念。

四、简答题

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

一个上下文无关文法 GG 是一个四元式 (VT,VN,S,P)(V_T, V_N, S, P)，其中：

  • VTV_T 是一个非空有限集，它的每个元素称为终结符号；
  • VNV_N 是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=∅V_T \cap V_N = \emptyset；
  • SS 是一个非终结符号，称为开始符号；
  • PP 是一个产生式集合（有限），每个产生式的形式是 P→αP \to \alpha，其中 P∈VNP \in V_N，α∈(VT∪VN)∗\alpha \in (V_T \cup V_N)^*。

开始符号 SS 至少必须在某个产生式的左部出现一次。

2. 给出正规式与正规集的递归定义。

(1) ε\varepsilon 和 ∅\emptyset 都是 Σ\Sigma 上的正规式，它们所表示的正规集分别为 {ε}\{\varepsilon\} 和 ∅\emptyset；

(2) 任何 a∈Σa \in \Sigma，aa 是 Σ\Sigma 上的一个正规式，它所表示的正规集为 {a}\{a\}；

(3) 假定 UU 和 VV 都是 Σ\Sigma 上的正规式，它们所表示的正规集分别记为 L(U)L(U) 和 L(V)L(V)，那么 (U∣V)(U \mid V)、(U⋅V)(U \cdot V) 和 (U)∗(U)^* 也都是正规式，它们所表示的正规集分别为 L(U)∪L(V)L(U) \cup L(V)、L(U)L(V)L(U)L(V)（连接积）和 (L(U))∗(L(U))^*（闭包）。

仅由有限次使用上述三步骤而得到的表达式才是 Σ\Sigma 上的正规式。仅由这些正规式所表示的字集才是 Σ\Sigma 上的正规集。

3. 设文法 GG 为：

S→aAcB∣BdS,A→BaB∣aBc∣a,B→aScA∣cAB∣bS \to aAcB \mid BdS,\quad A \to BaB \mid aBc \mid a,\quad B \to aScA \mid cAB \mid b

对于输入串 aacabccb，给出最左推导。

S⇒aAcB⇒aaBccB⇒aacABccB⇒aacaBccB⇒aacabccB⇒aacabccbS \Rightarrow aAcB \Rightarrow aaBccB \Rightarrow aacABccB \Rightarrow aacaBccB \Rightarrow aacabccB \Rightarrow aacabccb

4. 设文法 GG 为：

S→BA,A→BS∣d,B→aA∣bS∣cS \to BA,\quad A \to BS \mid d,\quad B \to aA \mid bS \mid c

对于输入串 adccd，给出最左推导。

S⇒BA⇒aAA⇒adA⇒adBS⇒adcS⇒adcBA⇒adccA⇒adccdS \Rightarrow BA \Rightarrow aAA \Rightarrow adA \Rightarrow adBS \Rightarrow adcS \Rightarrow adcBA \Rightarrow adccA \Rightarrow adccd

5. 证明：文法 GG：P→PaP∣PbP∣cP∣Pe∣fP \to PaP \mid PbP \mid cP \mid Pe \mid f 为二义文法。

⚠️ 原始图片缺失，此题需要参考原试卷中的图

对于文法 GG 定义的句子 fbfbf，可以构造两棵不同的语法树，因此该文法是二义文法。

6. 证明：文法 GG：P→S+S∣S∗S∣i∣(S)P \to S + S \mid S * S \mid i \mid (S) 为二义文法。

⚠️ 原始图片缺失，此题需要参考原试卷中的图

对于文法 GG 定义的句子 i+i∗ii + i * i，可以构造两棵不同的语法树，因此该文法是二义文法。

7. 给定正规文法 GG：

S→aS∣bA∣b,A→aSS \to aS \mid bA \mid b,\quad A \to aS

请构造与之等价的有限自动机。

8. 给定正规文法 GG：

S→aA,A→bA∣aB∣b,B→aAS \to aA,\quad A \to bA \mid aB \mid b,\quad B \to aA

请构造与之等价的有限自动机。

9. 对下面给出的 NFA 确定化。

⚠️ 原始图片缺失，此题需要参考原试卷中的图

10. 对下面给出的 NFA 确定化。

⚠️ 原始图片缺失，此题需要参考原试卷中的图

11. 对下面给出的 DFA 最小化。

⚠️ 原始图片缺失，此题需要参考原试卷中的图

12. 对下面给出的 DFA 最小化。

⚠️ 原始图片缺失，此题需要参考原试卷中的图

13. 有如下布尔表达式：

a < b and (c < d or e < f)

假定整个表达式的真假出口分别为 Ltrue 和 Lfalse，请翻译成三地址语句。

if a < b goto L1
goto Lfalse
L1: if c < d goto Ltrue
goto L2
L2: if e < f goto Ltrue
goto Lfalse

14. 有如下语句：

if a < b then if c < d then p := a + 1 else p := b + 1 else p := c + 1

请翻译成三地址语句。

if a < b goto L1
goto L2
L1: if c < d goto L3
goto L4
L3: T1 := a + 1
p := T1
goto L5
L4: T2 := b + 1
p := T2
L5: goto Lnext
L2: T3 := c + 1
p := T3
Lnext: …

五、语法分析

1. 设有文法 GG：

S→a∣b∣(A),A→SdA∣SS \to a \mid b \mid (A),\quad A \to SdA \mid S

(1) 完成下列算符优先关系表，并判断是否为算符优先文法（请说明理由）。

aabb(())dd#\#
aa⋅>\cdot>⋅>\cdot>⋅>\cdot>
bb⋅>\cdot>⋅>\cdot>⋅>\cdot>
((⋅<\cdot<⋅<\cdot<⋅<\cdot<==⋅<\cdot<
))⋅>\cdot>⋅>\cdot>⋅>\cdot>
dd⋅<\cdot<⋅<\cdot<⋅<\cdot<⋅>\cdot>⋅<\cdot<⋅>\cdot>
#\#⋅<\cdot<⋅<\cdot<⋅<\cdot<==

由于该文法的任何产生式的右部都不含两个相继的非终结符，故属于算符文法。从上表可以看出，任何两个终结符之间至多满足 ==、⋅<\cdot<、⋅>\cdot> 三种关系之一，故 GG 为算符优先文法。

(2) 给出句型 (SdSdS)(SdSdS) 对应的语法树，指出该句型的短语、句柄。

  • 短语：(SdSdS)(SdSdS)，SdSdSSdSdS，SdSSdS，SS
  • 句柄：SS

2. 设有文法 GG：

S→S∗F∣F,F→F↑P∣P,P→(S)∣iS \to S * F \mid F,\quad F \to F \uparrow P \mid P,\quad P \to (S) \mid i

(1) 完成下列算符优先关系表，并判断是否为算符优先文法（请说明理由）。

∗*↑\uparrow(())ii#\#
∗*⋅>\cdot>⋅<\cdot<⋅<\cdot<⋅>\cdot>⋅<\cdot<⋅>\cdot>
↑\uparrow⋅>\cdot>⋅>\cdot>⋅<\cdot<⋅>\cdot>⋅<\cdot<⋅>\cdot>
((⋅<\cdot<⋅<\cdot<⋅<\cdot<==⋅<\cdot<
))⋅>\cdot>⋅>\cdot>⋅>\cdot>⋅>\cdot>
ii⋅>\cdot>⋅>\cdot>⋅>\cdot>⋅>\cdot>
#\#⋅<\cdot<⋅<\cdot<⋅<\cdot<⋅<\cdot<==

由于该文法的任何产生式的右部都不含两个相继的非终结符，故属于算符文法。从上表可以看出，任何两个终结符之间至多满足 ==、⋅<\cdot<、⋅>\cdot> 三种关系之一，故 GG 为算符优先文法。

(2) 给出句型 S∗P↑(S)S * P \uparrow (S) 对应的语法树，指出该句型的短语、句柄。

  • 短语：S∗P↑(S)S * P \uparrow (S)，P↑(S)P \uparrow (S)，PP，(S)(S)
  • 句柄：PP
返回 编译原理 学科归档返回主页
Profile Image of the Author
Sonder
好想要技术
这是公告标题
这只是一个公告
分类
标签
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.7
文章许可
CC BY-NC-SA 4.0
© 2026Sonder. All Rights Reserved.RSSSitemap
Powered byAstroFireflyAdapted byAstro Course Hub
文章目录
1
编译原理试题
一、单项选择题
二、判断题
三、填空题
四、简答题
五、语法分析