# 概论

# 编译过程

1. 编译过程主要有哪几个阶段？ 词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。

   考察编译原理的基本认识。

2. 词法分析的输入是什么？输出是什么？ 输入是字符，输出是单词（token）序列

   考察词法分析的输入和输出。

3. 语法分析的输入是什么？输出是什么？ 输入是词法分析输出的 token 序列，输出一般是抽象语法树

   考察语法分析的输入和输出。

4. 语义分析的输入是什么？输出是什么？ 输入输出均为标识符。具体来说，输入是 token ($id, 标识符名表地址)，输出是新的 token ($id, 符号表地址)

5. 中间代码的一种常见形式是近似 “三地址指令” 的四元式，请问四元式形式是 。

   • (运算符，运算对象 1，运算对象 2，结果)
   • (运算对象 1，运算符，运算对象 2，结果)
   • (结果，运算符，运算对象 1，运算对象 2)
   • (运算符，运算对象 1，运算对象 2)

# 编译程序的结构、编译阶段的组合

6. 上述编译过程的 6 个阶段的任务可以分别由 6 个模块完成，分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序和目标代码生成程序。此外，一个完整的编译程序还必须包括 表格管理程序和出错处理程序。

   考察对编译程序的全面认识。

7. 编译阶段的前端有哪些阶段？

   • 词法分析
   • 语法分析
   • 语义分析
   • 中间代码生成

   考察编译阶段的前端。
   某些代码优化工作也可在前端做，还包括与前端每个阶段相关的出错处理工作和符号表管理工作。

8. 编译阶段的后端主要有哪些工作？

   • 词法分析
   • 目标代码生成阶段
   • 出错处理工作
   • 符号表管理工作

   考察编译阶段的后端。

9. 占内存空间少，但时间消耗大的扫描方式是？

   • 多遍扫描
   • 单遍扫描
   • 两者都是
   • 不知道

   单遍扫描时间消耗小，但是占内存空间大，需要一次性存储所有信息。

# 解释程序与存储组织

10. 解释程序一个个的获取、分析并执行源程序语句，一旦第一个语句分析结束，源程序便开始运行并且生成结果，它特别适合程序员以 交互方式 工作的情况。

    程序的解释是非常慢的。

11. 在编译阶段，存储区主要为 源程序 (中间形式) 和目标代码 开辟空间，要存放编译需要的各种 表格。在运行阶段，存储区主要是 目标代码 和 数据

12. 对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。
    (1) else 没有匹配的 if。 语法分析
    (2) 数组下标越界。语义分析
    (3) 使用的函数没有定义。语法分析
    (4) 在数中出现非数字字符。 词法分析

    语法分析通常解决匹配问题。如，使用的函数没有定义，说明没有声明部分与之匹配。又如第一题的 else 没有与 if 匹配。
    跟字符有关的通常是词法分析

# 文法和语言

# 形式定义

13. 文法 G 定义为四元组（V,Q,P,S）。其中，V 是 非终结符集；Q 是 终结符集；P 是 一组产生式；S 是 文法初始符。

14. 终结符通常用什么表示？小写字母 非终结符通常用什么表示？大写字母

15. ABsa 是句子？（）

    所有字符为终结符才是句子。

16. B->dAaui，则 dAaui 是句型？（）

    句型是推导得到的符号串，可由终结符和非终结符组成。

17. 文法描述的语言是该文法一切 句子 的集合。

# 文法类型

18. 如果一个文法的每个产生式左部至少含一个非终结符，则这种文法是 0 型文法

    0 型文法又称为短语文法。

19. 如果一个文法的每个产生式左部只有一个非终结符，则这种文法是 2 型文法

    2 型文法又称为上下文无关文法，是当前语言使用最多的文法。

20. 如果一个文法的每个产生式的形式都是 A->aB 或 A->a，则这种文法是 正规文法

    正规文法即为 3 型文法。

21. 如果一种文法的每个产生式右部的符号个数不少于左部符号的个数，则这种文法是 1 型文法

    1 型文法又称为上下文有关文法。

# 语法树

22. 给定一个文法，其语法树唯一。（）

    对于一个文法，语法树不一定唯一。

23. 语法树结构中，根节点一定是文法开始符。（）

24. 语法树结构中，叶结点一定是终结符。（）

    叶结点可以是终结符也可以是空串。

25. 最右推导是规范推导。（）

    最右推导得到的句型称为右句型。最左推导得到的句型称为左句型。

26. 每个句子都有最左推导和最右推导，但是每个句型不一定有最左推导和最右推导。（）

27. 当某个文法中存在某个句子有两个不同的最左（最右）推导，则这个文法是二义的。（）

# 语法分析初步

28. 文法的短语是文法初始符经过多步推导得到的所有子串。（）

29. 短语中经过一步推导得到的子串称为直接短语。（）

    直接短语又称为简单短语。

30. 该文法的句柄是该文法最后一步推导得到的直接短语。（）

31. 句柄只适用于左句型。（）

    句柄只适用于右句型，因此通常用最右推导求句柄。

32. 自顶向下语法分析方法的关键是什么？ 寻找候选式

33. 自底向上语法分析方法的关键是什么？ 寻找句柄

34. 规范推导的逆过程是规范规约。（）

    错！规范推导的逆过程是规范归约。“归”。

35. 闭包比正闭包多了空串。（）

# 词法分析

# 词法分析与语法分析的接口方式

36. 词法分析与语法分析的协同工作关系决定了两者之间存在接口方式的规定，最容易想到的方式是词法分析工作是独立的一遍，把字符流的源程序变为 单词序列（token），输出到一个中间文件，以供语法分析使用。

    考察词法分析的输出。词法分析的输出是单词序列（token）
    词法分析的接口方式还有两种，一种是词法分析程序作为语法分析程序的子程序，当语法分析程序需要一个单词时，就调用词法分析程序。还有一种是协同程序方式，词法分析程序与语法分析程序以生产者消费者的方式同步进行。

37. 你能想到的词法分析任务有哪些？如下

    （1）组织源程序的输入。（2）删除注释，无用空格。（3）查填标识符名表。（4）检查词法错误。（5）记录遇到的换行符个数，以便提供词法报错信息。（6）识别单词，转换成机内表示形式，即 token 的二元式表示。

# 标识符名表

38. token 的机内表示方式采用二元式表示：（单词种别，单词自身值），如常数 5 的二元式是（2,'5'），其中，2 这个编码代表种类是常数，'5' 代表值。（）

39. 所有 token 的二元式形成的表格称为标识符名表。（）

40. token 中，关键字、界限符、运算符的单词类别编码足以表示其完整信息，因此对于这些 token，它们二元组的单词属性值常为空。（）

41. 标识符的 token 的二元式表示为：（标识符的类别编码，指向该标识符所在符号表中位置的指针）（）

42. 标识符名表就是符号表。（）

    标识符名表常用于词法分析，而符号表常用于语义分析。

# 正规文法和正规式

43. 正规式又称为正则表达式，也可以认为是字符串的形式规则，这种规则能表示的所有字符串的集合称为正规集。（）

44. 空串不是正规式。（）

45. 一个字符也能是正规式。（）

46. 如果 a,b 是正规式，那么 (a)、a|b、a・b、a * 也是正规式（* 表示闭包）。（）

47. (a|b)* 等价于 (a|b)(a|b)...(a|b)。(a*|b*) 等价于 (a|b)*。（）

48. 如果 d 表示 0-9 中的数字，那么 dd * 可以表示空串。（）

    dd * 表示至少一个数字。

49. 若两个正规式 a 和 b 所表示的 正规集 相同，则说 a 和 b 等价。

# 有穷自动机

50. 一个确定的有穷自动机 DFA 可以用五元组 M 表示：M=(K,$\sum$,$f$,S,Z)。K 是 状态集。$\sum$ 是 输入符号表。$f$ 是 转换函数。S 是 初始状态。Z 是 终态集。

    考察 DFA 的五要素。

51. DFA 只能有一个初始状态，但是可以有多个终态。（）

52. DFA 可以表示成一个状态图。其中，初态状态冠以 =>，终态用双圈表示。（）

    考察 DFA 状态图。

53. DFA 状态图的弧上允许有空串。（）

    DFA 不允许空串转换。

54. DFA 还可以表示成一个状态表，行表示状态，列表示输入符号，矩阵元素表示相应状态经过输入符号转换的新状态。（）

    考察 DFA 状态转换表

55. 一个符号串，能被自动机识别，在于从初始状态到终止状态存在一条道路。（）

56. DFA 的状态图中，从一个状态结点出发的弧的数量是无限制的。（）

    DFA 的每个状态结点，只能伸出 n 条弧，这个 n 是输入符号表的长度，即状态转换表中有效列的个数。

57. 一个不确定的有穷自动机 NFA 能被一个五元组表示：M=(K,$\sum$,$f$,S,Z)，其中 K 是状态集、$\sum$ 是输入符号表、$f$ 是转换函数、S 是 非空状态集、Z 是终态集。

    NFA 的初态可以不止一个。

58. NFA 的状态图的弧上允许有空串。（）

59. NFA 的状态图中，每个状态结点伸出的弧的数量没有限制。（）

# 自顶向下语法分析

# 自顶向下思想

60. LL (1) 分析方法有递归下降分析方法和表驱动的 LL (1) 分析方法。（）

61. 自顶向下分析方法的四个动作是 推导 -> 匹配 -> 成功 -> 报错

62. 自顶向下分析方法分为确定的自顶向下分析方法和不确定的自顶向下分析方法。（）

63. 递归下降方法和 LL (k) 分析方法都属于不确定的自顶向下分析方法。（）

    都属于确定的自顶向下分析方法。

64. 确定的自顶向下分析方法要尽可能地消除 回溯

65. 确定的自顶向下分析方法的 “确定” 含义在于，对于一个非终结符，通过给定的一个输入字符，推导得到的符号串是唯一的。（）

    换言之，一个非终结符，通过给定的输入符号，选择的候选式是唯一的，而不确定的自顶向下分析方法选择的候选式是不唯一的。

# LL（1）分析方法

66. FIRST 集允许有空串。（）

67. 尾符（$、#）可含于 FOLLOW 集中，而空串不能。（）

68. 文法初始符的 FOLLOW 集一定不包含尾符。（）

    FOLLOW 集由于文法初始符一定包含尾符，故 FOLLOW 集可以包含尾符。同时，FOLLOW 集还不允许包含空串。

69. 给定上下文无关文法的产生式 A->aBc，若 B 导空，则 A 导空。（）

    导空条件是右部的所有文法符号均导空，不能只导空一个。换言之，只要出现一个终结符，这个产生式左部对应的非终结符一定不导空。

70. 给定上下文无关文法的产生式 A->a，如果 a 不导空，则该产生式的 SELECT 集为 FIRST (a)。（）

71. 给定上下文无关文法的产生式 A->a，如果 a 导空，则该产生式的 SELECT 集为 FIRST (a)$\cup$FOLLOW(A)。（）

    (FIRST(a) - $\epsilon$) $\cup$ FOLLOW(A)

72. 一个上下文无关文法是 LL (1) 文法的充分必要条件是，对每个非终结符 A 的所有不同产生式，以两个为例，A->a, A->b，满足 SELECT (A->a) $\cap$ SELECT (A->b) 等于空集。

73. LL (1) 的第一个 L 含义是使用最左推导，第二个 L 的含义是自左向右扫描输入串。（）

    1 表明只需向右看一个符号便可决定如何推导。

74. 如果 A 和 B 均为非终结符，则 FIRST (AB) = FIRST (A)。（）

    FIRST (AB) = FIRST (A) 和 FIRST (B) 的并集。

75. 如果产生式 X->aB，则 FIRST (X)={a}。（）

76. 如果产生式 X->$\epsilon$，则 FIRST (X)={$\epsilon$}。（）

77. 如果产生式 X->Ab，A 不可导空，则 FIRST (X)=FIRST (A)。（）

78. 如果产生式 X->ABCD，A,B,C 均导空，D 不可导空，则 FIRST (X)=FIRST (A) $\cup$ FIRST(B) $\cup$ FIRST(C) $\cup$ FIRST(D)。（）

    正确的公式应该是：FIRST (X)=(FIRST (A)-$\epsilon$) $\cup$ (FIRST(B)-$\epsilon$) $\cup$ (FIRST(C)-$\epsilon$) $\cup$ FIRST(D)。

79. 如果产生式 X->ABCD，A,B,C,D 均导空，则 FIRST (X)=FIRST (A) $\cup$ FIRST(B) $\cup$ FIRST(C) $\cup$ FIRST(D)。（）

    正确的公式应该是：FIRST (X)=FIRST (A) $\cup$ FIRST(B) $\cup$ FIRST(C) $\cup$ FIRST(D) $\cup \{\epsilon\}$。

80. 如果有上下文无关文法的产生式 A->aBC，C 是非终结符 B 后面的文法符号串，则 FOLLOW (B) 一定包含 FIRST (C)。（）

81. 在第 80 题的基础上，如果 C 导空（如 C 实际上是多个非终结符 DEF，D,E,F 均导空），则 FOLLOW (B) 还包含 FOLLOW (A)。（）

82. 求文法的所有非终结符的 FOLLOW 时，当每个非终结符的 FOLLOW 集不再增大时停止。（）

83. 一个 LL (1) 文法一定不存在左递归和左公因子。（）

84. 递归下降分析方法也需要每个非终结符的所有产生式满足 SELECT 集的交集为空。（）

85. 使用表驱动的 LL (1) 分析方法对输入符号串进行一栈一流分析时，当且仅当栈顶为 [尾符 ($ 或 #)]，而且输入流指针指向 [尾符 ($ 或 #)]，两者匹配才表示该输入字符串符合文法。

86. 表驱动的 LL (1) 分析方法在对输入符号串进行一栈一流分析时，栈中的非终结符选择候选式进行推导展开时，输入流不变。（）

    对，输入流顶部字符被抵消，当且仅当栈顶元素与输入流顶部字符匹配。

87. 如果栈的顶部是非终结符 A，则要选择与当前输入符相匹配的 A 的产生式，并用该产生式的右部替换栈顶的非终结符。（）

88. 一栈一流分析的分析栈从文法初始符开始。（）

89. LL (1) 预测分析表的行只有非终结符，列只有输入符和空串。（）

    列不含空串，而且不只含输入符，还包含尾符。

90. 递归下降分析方法内存要求高，适用于小规模文法。（）

# 自底向上语法分析

# 基本思想

92. 自底向上分析方法的四个动作是什么？

    • 移入、归约、成功、报错。
    • 推导、匹配、成功、报错。
    • 移入、匹配、成功、报错。
    • 推导、归约、成功、报错。

93. 自底向上四个动作中移入是将输入符号从输入流中移入到 。

    • 状态栈。
    • 符号分析栈。
    • ACTION 表。
    • GOTO 表。

94. 符号分析栈从尾符开始。（）

# LR (0) 分析方法

95. LR (k) 中的 L 的含义是 自左向右扫描输入流；R 的含义是 构造最右推导的逆；k 的含义是 分析动作向前所看的输入流符号个数。

96. LR (k) 分析方法相较 LL (k) 分析方法和自底向上优先分析方法的优点是 分析速度快，准确，对文法限制少，能指出出错位置，相应的缺点是 对一个实用语言文法的分析器的构造工作量相当大

97. 为了防止文法初始符出现在文法产生式右部，在原文法 G [S] 中增加产生式 S'->S，S 为原文法 G 的开始符号，所得的新文法 G' 称为原文法 G 的 拓广文法。

98. 在文法 G 中每个产生式的右部适当位置添加一个圆点构成 项目。

99. 一个产生式 S->aAcBe 对应有 6 个项目：[0] S->.aAcBe,[1] S->a.AcBe, [2] S->aA.cBe,[3] S->aAc.Be,[4] S->aAcB.e,[5] S->aAcBe.。归约项目是圆点在产生式最右端的 LR (0) 项目，如 [5]。接受项目是对文法初始符的归约项目，即 [[5]]。待约项目是圆点后第一个符号为非终结符的 LR (0) 项目，如 [1] 和 [3]。移入项目是圆点后第一个符号为终结符的 LR (0) 项目，如 [0]、[2] 和 [4]。

100. 若句型$\alpha \beta$ 中，$\beta$ 是终结符串或空串，（说明$\alpha$ 是非终结符串），则$\alpha$ 是 前缀

101. 若作为前缀的$\alpha$ 不含句柄或含一个句柄且具有形式$\alpha=\alpha'\pi$（$\pi$ 是句柄），则称前缀$\alpha$ 是 活前缀。

102. 若$\alpha$ 是含句柄的活前缀，即有$\alpha=\alpha'\pi$，且$\pi$ 是句柄，则$\alpha$ 是 归约活前缀。

103. 若有项目集 IS={.abd [1], .abc [2], .bc [3], .de [4], de.c [5]}，则项目集 IS 对 a 做投影 IS (a)={a.bd[1],a.bc[2]{.gap}}。

> 以此类推，IS(b)={b\.c[3]}, IS(c)={dec\.[5]}。

104. 例如有如下文法 G [E']：

(1) E'->E

(2) E->T

(3) T->F

(4) F->id

(5) E->E+T

(6) T->T*F

(7) F->(E)

则产生式 E'->E 关于项目 I={E'->.E} 闭包 CLOSURE ([E'->.E]) 为？{.quiz .multi}
- E'->.E {.correct}
- E->.T {.correct}
- E->.E+T {.correct}
- E->E+.T
- T->F.
- T->.F {.correct}
- T->.T*F {.correct}
- F->.id {.correct}
- F->.(E) {.correct}
- F->id.

105. LR (0) 项目集规范族又称为 LRSM、LR 自动机、DFSA。

106. 如下项目集：
     A->$\alpha$.$\alpha\beta$
     B->\gama.
     存在 移入 - 归约冲突。

107. 如下项目集：
     A->$\beta$.
     B->\gama.
     存在 归约 - 归约冲突。

108. 对一个文法的 LR (0) 项目集规范族不存在 移入 - 归约冲突或 归约 - 归约冲突时，称这个文法是 LR (0) 文法。

> LR(0)文法的项目集规范族的任何状态都不允许存在移入-归约冲突和归约-归约冲突。

109. LR (0) 分析表由 ACTION 表和 GOTO 表组成。

110. LR (0) 分析表中的 ACTION 表的列标是终结符和尾符。（）

111. LR (0) 分析表中的 GOTO 表的列标是非终结符。（）

112. ACTION [k,a] 为 S_j 的含义是，在状态 k，遇到终结符 a，将终结符 a 移入符号栈，将状态 j 压入状态栈。（）

113. ACTION [k,a] 为 r_j 的含义是，在状态 k 使用第 j 个产生式（记为 S）对符号栈中的句柄进行归约，弹出符号栈中与 S 同长的符号，弹出状态栈中与 S 同长的状态，同时将 S 的左部非终结符（记为 M）压入栈顶，根据项目集规范族，查看状态栈栈顶非终结符遇到 M 能够 GOTO 到哪个状态（记为 k'），将 k' 压入状态栈栈顶。（）

114. LR (0) 分析表的行号的含义是状态，从 0 开始。（）

115. 找到包含能够归约到文法初始符的接受项目 I，在 LR (0) 分析表中，置 ACTION [I, 尾符]=acc，表示接受。（）

# SLR (1) 分析方法

116. 如果 LR (0) 项目集规范族存在归约 - 归约冲突或移入 - 归约冲突，则这个文法不是 LR (0) 文法。例如，此时出现归约 - 归约冲突的状态涉及的产生式为：A->\gama.,B->$\theta$.。对所有涉及归约 - 归约冲突状态的产生式的左部非终结符求 FOLLOW 集。如果它们的 FOLLOW 集彼此互不相交，则这个文法是 SLR (1) 文法。（）

117. 在第 116 题的基础上，对于出现移入 - 归约冲突状态涉及的产生式为：X->$\alpha$.b$\beta$,A->\gama。移入项目的展望符为 b，如果满足归约项目的左部非终结符的 FOLLOW 集与展望符交集为空，那么这个文法依然是 SLR (1) 文法。（）

118. 对于 SLR (1) 文法，在冲突状态中，如果输入符号 a 等于移入项目的展望符 b，则选择移入。如果输入符号 a 是某个非终结符的 FOLLOW 集的一个元素，那么则使用这个终结符的产生式进行归约。（）