一、单项选择题
1. 编译程序是一种（ A ）软件。
A. 系统 B.应用 C.MIS D.ERP
2. 下面对编译原理的有关概念描述正确的是（ D ）
A. 目标语言只能是机器语言
B. 编译程序处理的对象是源语言 C. Lex是语法分析自动生成器
D. 解释程序属于编译程序
3. （ C ）不是编译程序的组成部分。
A．词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 4. 下面对编译程序分为“遍”描述正确的是（ A ）
A. 分“遍”可以使编译程序结构清晰 B. 可以提高程序的执行效率 C. 可以提高机器的执行效率
D. 可以增加对内容容量的要求
5. 下面对编译程序分“遍”应考虑的因素描述不正确的是（C）
A．源语言的特征和约束 B.代码优化的因素 C. 编译程序的功能 D.目标代码的选择 6. 编译程序各阶段的工作都涉及到（ D ）
①表格管理 ②语法分析 ③出错处理 ④代码优化 A．①② B. ②③ C. ③④ D. ①③
7. 设有表达式a*b-c，将其中a*b识别为表达式的编译阶段是（ B ）
A.词法分析 B.语法分析 C.语义分析 D.代码生成 8. BNF是一种广采用的（ C ）的工具。
A. 描述规则 B. 描述语言
C. 描述文法 D. 描述句子
9. 无符号常数的识别和拼数工作通常在（ B ）阶段完成。
A. 词法分析
B. 语法分析 C. 语义分析
D. 代码生成
10. “运算符与运算对象类型不匹配”属于（ B ）。
A. 语法错误
B. 语义错误 C. 语用错误
D. 词法错误
11. 一遍扫描的编译程序的优点是（ D ）。
A. 算法清晰 B. 便于分工
C. 便于优化
D. 编译速度快
12. 编译程序生成的目标代码程序（ A ）是可执行的程序。
1
编译原理1 题库
A. 不一定
B. 一定 C. 一定不
D. 必须经链接装配后 13. 编译程序是对（ D ）。
A. 汇编程序的翻译
B. 高级语言的解释执行
C. 机器语言的执行 D. 高级语言的翻译
14. 测试一个编译程序时使用的测试数据是（A ）。
A. 源程序 B. 中间代码 C. 目标代码
D. 任意数据
15. 由“非终结符→符号串”形式的规则构成的文法是（ C ）。
A. 0型文法
B. 1型文法 C. 2型文法 D. 3型文法
16. 文法识别符号经过任意步推导得到的结果是（ A ）。
A. 句型
B. 句柄 C. 句子 D. 短语
17. * 关于短语和句柄，正确的描述是（ B ）。
A. 短语就是句柄 B. 直接短语才可能是句柄 C. 最左短语一定是句柄 D. 最右短语一定是句柄 18. 一个语言的文法是（ C ）。
A. 唯一的
B. 不唯一的
C. 个数有限的 D. 无数个
19. 文法G所描述的语言是（ D ）集合。
A. 文法G的字母表V中所有符号组成的符号串 B. 文法G的字母表V的闭包V*中的所有符号串 C. 由文法的开始符号推出的所有符号串
D. 由文法的开始符号推出的所有的终结符号串
20. 文法分为四种类型：0型文法、1型文法、2型文法、3型文法，其中3型文法是（B）。
A. 短语文法
B. 正规文法 C. 上下文有关文法 D. 上下文无关文法
2
编译原理1 题库
21. 一个上下文无关文法包含四个部分，一组非终结符，一组终结符，一个开始符号以及一
组（ C ）。 A. 句子 B. 句型 C. 产生式
D. 单词
22. 在编译中产生语法树是为了（ A ）。
A. 语法分析
B. 语义分析 C. 词法分析 D. 目标代码生成
23. 如果一个文法无二义性，则它的任何句子（ A ）。
A. 最左推导和最右推导对应的语法树必定相同
B. 最左推导和最右推导对应的语法树可能不同
C. 最左推导和最右推导必定相同
D. 可能存在两个不同的最左推导，但它们对应的语法树相同 24. 正则式（ D ）与(a*|b)*(c|d)等价。
A. a*(c|d)|b(c|d) B. a*(c|d)*|b(c|d)* C. a*(c|d)|b*(c|d)
D. (a|b)*c|(a|b)*d
25. 下述正规式中与(a*|b*) (c|d)等价的是（C）
A．a*(c|d)|b(c|d) B．a*(c|d)*|b(c|d)*
C．a*(c|d)|b*(c|d) D．(a|b)*c|(a|b)*d
26. 同正则式(a | b)等价的正则式是（ B ）。
A. (a | b)*
B. (a | b)(a | b)* C. (a b)*(a b)
D. (a | b) | (a | b)*
27. 同正规式a*b*等价的文法是（ C ）。
A. S→aS |bS|ε
B. S→aSb|ε C. S→aS |Sb|ε
D. S→aS|ε
28. 设正规式r=(a | b)(x | y)*，则下面错误的正规集元素是（A）
A. abx B.bxxx C.a D.bxyyxxy 29. 设有文法G(S)为：S→AB | AS A→aA | a B→b，则下面与该文法等价的正规式是（B）
A．aa*bb* B.aa*b C.(ab)* D.a(ab)*b
30. 给定语言L(G)={abb | n≥1}，则文法（ D ）可产生语言L(G)。
A. Z→aZb |aAb|b,A→aAb|b
B. A→aAb|b
C. Z→AbB, A→aA |a,B→bB|b
3
n
n
+
编译原理1 题库
D. Z→aAb, A→aAb|b
31. 由文法识别符号通过若干步推导得到的终结符号串是（ C ）。
A. 语言 B. 句型 C. 句子
D. 句柄 32. 设文法G=（{S}，{0,1}，P,S），其中P={S→SS |0S1|1S0 | ε}，该文法所描述的语言为（ B ）。
A. {01|n≥0}
B. {w| w∈ {0|1}*}且w中0和1的个数相等 C. {0m1k| m，k≥0}∪{1m0k| m，k≥0} D. {01|n≥0}∪{10|n≥0} 33. 词法分析所依据的是（ B ）。
A. 语法规则
B. 构词规则 C. 语义规则
D. 等价变换规则
34. 正规式M1和M2等价是指（ C ）。
A. M1和M2的状态数相等
B. M1和M2的有向弧条数相等
C. M1和M2的所识别的语言集相等
D. M1和M2的状态数和有向弧条数相等
35. 状态转换图（见图3-6-1）接受的字集为（ D ）。
0 X 1 Y 0 图3-6-1 A. 以 0开头的二进制数组成的集合 B. 以0结尾的二进制数组成的集合 C. 含奇数个0的二进制数组成的集合 D. 含偶数个0的二进制数组成的集合 36. 词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此（ B ）。
A. 词法分析器应作为独立的一遍
B. 词法分析器作为子程序较好
C. 词法分析器分解为多个过程，由语法分析器选择使用 D. 词法分析器并不作为一个独立的阶段 37. 设有C语句的程序段如下： while(i&&++j) { c=2.19;
j+=k; i++;
}
nn
nn
nn
则经过词法分析后可以识别的单词个数是（B） A．19 B.20 C.21 D.23
4
编译原理1 题库
38. 下列选项中，不属于预处理程序要完成的功能的是( B )
A. B. C. D.
滤掉源程序中的注释
查找源程序中的无用字符 进行宏替换
实现文件包含的嵌入和条件编译的嵌入
39. 编译过程中扫描器的任务包括（D）
① 组织源程序的输入
② 按词法规则分割单词，识别出其属性，并转换成token串输出 ③ 删除注释
④ 删除空格和无用字符 ⑤ 行计数，列计数 ⑥ 发现并定位词法错误
⑦ 建立符号表
A．②③④⑦ B. ②③④⑥⑦
C. ①②③④⑥⑦ D. ①②③④⑤⑥⑦
40. 将识别各类单词的有限自动机合并后得到的有限自动机（A）
A．可能是NFA也可能是DFA B. 一定是DFA C．一定是NFA D.是最小的DFA 41. 在词法分析阶段不能识别的是（C）
A．标识符 B.运算符 C.四元式 D.常数 42. 有穷自动机能够识别（ A ）。
A. 正则文法
B. 上下文无关文法 C. 上下文有关文法
D. 短语文法
43. 下列哪项不是DFA的构成成分（B）
A.有穷字母表 B.初始状态集合 C.终止状态集合 D.有限状态集合 44. 有限自动机M和N等价是指( D)
A. M和N的字母表相同
B. M和N的状态数和有向边数相等
C. M和N的状态数或有向边数相等 D. M和N识别的字符串集合相同
45. 下列哪项不是编译程序的组成部分（ B ）。
A. 词法分析程序 B. 设备管理程序
C. 代码生成程序 D. 语法分析程序
46. 某个语言，它能用正则表达式表达，但不能使用任何正则文法表达，则这个语言（ D ）。
A. 含有二义性
B. 是0型文法所对应的语言 C. 既含有左递归又含有右递归 D. 不存在
47. 编译程序中的语法分析程序接受以（ A ）为单位的输入，并产生有关信息供以后各
阶段使用。
5
编译原理1 题库
A. 单词
B. 表达式 C. 规则 D. 语句
48. 递归子程序法属于（ A ）语法分析方法。
A. 自顶向下 B. 自底向上
C. 自左至右 D. 自右向左
49. 语法分析方法中的LL(1)分析法属于( B )分析方法。
A． 自左至右 B． 自上而下 C． 自下而上 D． 自右至左
50. 采用确定的自顶向下分析时，必须（ C ）。
A. 消除左递归
B. 消除右递归 C. 避免回溯
D. 提取左公因子
51. 自上而下语法分析的主要分析动作是（A）
A．推导 B.移进 C.归约 D.匹配 52. LL(1)文法（ B ）二义性的。
A. 都是有 B. 都没有
C. 不一定都有 D. 极少具有
53. 一个字符属于FOLLOW(S)，这个字符的含义是（ A ）。
A. 一定会有一个句型中后随S的终结符 B. S可能推导出的第一个字符 C. S可能推导出的最后一个字符
D. 在某句型中直接跟在S后的字符
54. 在递归子程序方法中，若文法存在左递归，则会使分析过程产生（ D ）。
A. 回溯
B. 非法调用 C. 有限次调用
D. 无限循环
55. 若一个正则式描述的正则集中的元素有无穷个，则其必然包含的运算是（ D A. 连接运算“· ”
B. 或运算“ | ” C. 括号运算“(”和“)”
D. 闭包运算“*”
56. 将编译程序分成若干“遍”是为了（ B ）。
A. 提高程序的运行效率
B. 使程序的结构更加清晰
6
。 ）
编译原理1 题库
C. 利用有限的机器内存并提高机器的运行效率 D. 利用有限的机器内存但降低了机器的运行效率 57. 构造编译程序应掌握（ D ）。
A. 源语言 B. 目标语言
C. 编译方法
D. 以上三项都是
58. 编译程序绝大多数时间花在（ D ）上。
A. 出错处理 B. 词法分析
C. 目标代码生成 D. 表格管理
59. 词法分析器的输入是（ B ）。
A. 单词符号串
B. 源程序 C. 语法单位 D. 目标程序
60. 词法分析器的输出结果是（ C ）。
A. 单词的种别编码
B. 单词在符号表中的位置 C. 单词的种别编码和自身值 D. 单词自身值
61. 词法分析器用于识别（ C ）。
A. 字符串
B. 语句 C. 单词
D. 标识符
62. 语法分析器可以发现源程序中的（ D ）。
A. 语义错误
B. 语法和语义错误
C. 错误并校正 D. 语法错误
63. 下列关于解释程序的描述正确的是（ A ）。
A. 解释程序的特点是处理程序时不产生目标代码 B. 解释程序适用于COBOL和FORTRAN语言
C. 解释程序是为打开编译程序技术的僵局而开发的 D. 以上描述均不正确
64. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ B ）分析方法。
A． 自左向右 B． 自顶向下 C． 自底向上 D. 自右向左 65. 设有文法G[I]： I→I1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有（ B ）。
① ab0 ② a0c01 ③ aaa ④ bc10
可选项有：
A． ① B．②③④ C．③④ D．①②③④ 66. 下面不能用于对文法进行描述的是（ A ）
7
编译原理1 题库
A.源语言 B.EBNF C.BNF D.语法图
67. 设有文法的符号集V,非终结符集VN ，终结符集VT，下列叙述中正确的是（D）
A.V=VT B. V=VN C. V= VN∩VT D. V= VN∪VT
68. 设有文法G(S)为：S→0A A→1B B→0|0S 则L(G(S))为( B )
A. L1={(01)n0 | n≥1} B. L2={(010)n | n≥1} C. L3={0 (10) | n≥1} D. L4={(010) | n≥0}
69. 设有文法G(S)为：S→(B)a B→Bb|b|ε 下列叙述错误的是( C )
A. G是2型文法 B.L(G)={( b)a | n≥0}
n
C. L(G)= {(b)a | n≥0} D.有文法G‟为S→()a|(B)a B→bB|b ,则G‟＝G
70. 给定文法G(S)为：S→0S | 1A | 0 A→1 | 1S | 0B B→1A | 0B 下列符号串是L(G)
的元素的是( A )
A.10100010011011 B. 0101001110010010
C.1101010011110111 D.1010011101101010
71. 设有文法G(S):S→S1| S0 | Sa | Sc | a| b| c 下列符号串中不是该文法的句子的是（A） A. ab0 B.a0c01 C.aaa D.bc01
72. 设定义在字母表{a,b,c,x,y,z}上的正规式r=(a| b| c)(x | y| z)，则L(r)中元素有（A）个。
A．9 B.6 C.18 D.27
73. 文法G：S→xSx|y所识别的语言是（ C ）。
A. xyx B. (xyx)* C. xnyxn(n≥0) D. x*yx* 74. 文法G描述的语言L(G)是指（ B ）。
n
n
n
α , α∈VT*} A. L(G)={α|S+⇒
*α, α∈VT*} B. L(G)={α|S⇒
*α,α∈(VT∪VN*)} D. L(G)={α|S+ α, α∈(VT∪VN*)} C. L(G)={α|S⇒⇒75. 设文法为：S→SA|A A→a|b
则对句子aba，下面（ D ）是规范推导。
A. SSASAAAAAaAAabAaba B. SSASAAAAAAAaAbaaba C. SSASAASAaSbaAbaaba D. SSASaSAaSbaAbaaba 76. 产生正规语言的文法为（ D ）。
A. 0型 B. 1型
C. 2型
D. 3型 D. 素短语
77. * 在规范归约中，用( B )来刻画可归约串。 A. 直接短语 B. 句柄 C. 最左素短语 78. 编译程序是一种（ B ）。 A. 汇编程序 B. 翻译程序
C. 解释程序 D. 目标程序
79. 编译程序各阶段工作都涉及（ D ）。
A.
B. C. D. 词法分析 语法分析 语义分析 表格管理
80. 经编译得到的目标程序是（ A ）
A. 机器语言程序或汇编语言程序
8
编译原理1 题库
B. 四元式序列
C. 三元式序列 D. 二元式序列
81. ( B )不可能是目标代码。
A. 汇编代码
B. 中间代码
C. 绝对指令代码
D. 可重定位指令代码
82. 对于编译程序而言，输入数据是源程序，输出结果是（C ）。
A. 源程序
B. 中间代码 C. 目标程序
D. 汇编程序
83. 下面不属于LL(1)分析器的组成部分的是（D）
A. LL(1)总控程序 B. LL(1)分析表 C.分析栈 D.源程序串 84. 编译过程中，语法分析程序的任务是（ D ）
①分析单词是怎样构成的②分析单词串是如何构成语句和说明的 ③分析语句和说明是如何构成程序的④分析程序的结构 A. ①② B. ①②③ C. ①②④ D. ②③④
二、多项选择题
1. 句子x和句型y均可从无二义性文法G[S]的识别符号S推导得到，则（ AD）。
A. 一定存在S到x的最左推导
B. 一定存在S到y的两种不同的推导 C. 一定存在S到y的最左推导 D. 一定存在唯一与x对应的语法树 2. 下面哪些说法是错误的（AC）。
A.
B. C. D.
有向图是一个状态转换图 状态转换图是一个有向图 有向图是一个DFA DFA可以用状态转换图表示
3. 对无二义性文法来说，一棵语法树往往代表了（ACE）。
A. 多种推导过程 B. 多种最左推导过程 C.一种最左推导过程
D.仅一种推导过程 E.一种最右推导过程
4. 如果文法G存在一个句子，满足下列条件（BCD）之一时，则称该文法是二义文法。
A. 该句子的最左推导与最右推导相同
B. 该句子有两个不同的最左推导 C. 该句子有两棵不同的最右推导 D. 该句子有两棵不同的语法树 E. 该句子的语法树只有一个 5. 有一文法G：S→AB
A→aAb|ε B→cBd|ε
它不产生下面（AC ）集合。 A. {anbmcndm|n,m≥0} B. {anbncmdm|n,m>0}
9
编译原理1 题库
C. {abcd|n,m≥0}
nnnn
nmmn
D. {abcd|n,m≥0}
nnmm
E. {abcd|n≥0}
6. 在词法分析中，能识别出（ ACE ）。
A. 基本字 B. 四元式 D. 逆波兰式 D. 常数
C. 运算符
7. 编译程序的生成方式可以是（ABD）。
A．自编译 B.高级程序设计语言编写 C.完全自动生成 D.汇编语言编写
8. 令∑={a,b}，则∑上所有以b开头，后跟若干个ab的字的全体对应的正规式为（ABD）。
A. b(ab)*
D. (ba)+b
三、判断题
1. 解释执行与编译执行的根本区别在于解释程序对源程序没有真正进行翻译。（×） 2. “遍”是指对源程序的从头到尾扫描。（×） 3. 编译程序是将用某一种程序设计语言编写的源程序翻译成等价的另一种语言程序（目标
程序）。（×） 4. 编译程序是应用软件。（×）
5. 编译程序是系统软件。（√）
6. 编译程序的基本组成中，词法分析、语法分析和语义分析应该是有序的。（√） 7. 用高级语言书写的源程序都必须通过翻译，产生目标代码后才能运行。（√） 8. 一个语言的文法是不唯一的。（√） 9. BNF是一种广泛采用的描述文法的工具。（√） 10. 设有文法符号集V，则V＝VN∩VT。（×）
11. 设有文法符号集V，则V= VN∪VT ，同时VN∩VT=Ø。（√） 12. 一部文法G的文法符号不属于VN就属于VT。（√） 13. 有文法G1=G2，则L(G1)=L(G2)。（√）
14. 源语言是描述另一种语言的语言。（√）
15. 文法G所描述的语言就是G的终结符集VT的闭包VT*。（×）
16. 文法G所描述的语言就是G的终结符集VT的闭包VT*的一个子集，子集是满足开始符
号可以推导出的句子的集合。（√） 17. 对于文法G(S)=( VN , VT , P ,S ), V= VN∪VT ，r是文法G(S)的句型当且仅当S =>r,且r∈V* ；r是文法G(S)的句子当且仅当S =>r,且r∈VT * 。（√） 18. 文法G的一个句子对应于多个推导，则G是二义的。（×）
19. 文法G的一个句子对应于多个最左（或最右）推导，则G是二义的。（√）
20. 对给定的文法G(S)，若至少有一个句型存在两个或两个以上的不同的最左（或最右）推导，这是判定G是二义文法的充分非必要条件。（×）
21. 对给定的文法G(S)，若至少有一个句型存在两个或两个以上的不同的最左（或最右）推导，这是判定G是二义文法的充分必要条件。（√）
22. 一棵分析树反映了其叶结点从左向右连接形成的句型的任意推导情况。（×）
说明：对应于二义性文法，二义性的句子有不止一棵分析树。 23. NFA和DFA的区别之一是映射函数是否唯一。（√） 24. 一个正规式只能等价于一个确定的有限自动机。（×）
25. 描述同一个正规式的确定的有限自动机可以有多个。（√） 26. 任意有限自动机都能转化为一等价的特殊自动机，其状态图中初态无射入弧，终态无射
10
B. b(ab) E. b(a|b)
+
C.(ba)*b
编译原理1 题库
出弧。（√）
27. 对于任何正规集L，都有正规式r，满足L(r)=L。（√） 28. 设有r和s都是非ε的正规式，则有L(rs)=L(sr)。（×）
说明：正规式的连接运算不满足交换律。
29. 使用正规式运算能够描述定义在字母表上的所有符号串集合。（×） 30. 使用正规式运算能够描述定义在字母表上的正规集合。（√） 31. 正规式产生的语言都可以用上下文无关文法来描述。（√） 32. 正规式产生的语言都可以用正则文法来描述。（√）
说明：正则文法包含于上下文无关文法。
33. 对任何正规式r,都存在一个NFA M，满足L(M)=L(r)。（√）
34. 正则文法、正规式、NFA和DFA在接受语言的能力上是相互等价的。（√） 35. 自动机M1和M2状态数不同，则二者必不等价。（×）
36. 一个有限自动机至包含有限个状态，其中一个被认为是初态，最多只有一个终态。（×） 37. 一个有限自动机识别的语言是一个无限集合，则该有限自动机的状态图一定含有回路。（√）
38. 如果一个有限自动机接受空串ε，则它的状态转换图一定含有ε弧。（×）
说明：一个有限自动机的状态转换不含有ε弧，但它的初态又属于终态集，则该自动机接受空串ε。
39. 一个确定的有限自动机，可以通过多条路识别一个符号串。（×） 40. 一个确定的有限自动机，识别一个符号串的路径是唯一的。（√） 41. NFA的确定化算法具有消除ε弧的功能。（√）
42. 正则文法一定不是二义文法。（×）
说明：任何类型的文法都可以是二义文法。
43. 对每一个左线性文法G1，一定存在一个右线性文法G2，使得L(G1)=L(G2)。（√） 44. 词法分析的依据是源语言的文法规则。（×） 45. LEX是典型的词法分析程序。（×） 46. 47. 48. 49.
源程序中的单词是具有独立意义的短语。（×） 源程序中的单词是具有独立意义的最小语法单位。（√） 单词的属性字一般应该包括单词类别和单词。（×） 单词的属性字一般应该包括单词类别和单词值。（√）
50. 在C语言中有一个语句int int1;词法分析后识别出int、int、1和;四个单词。（×） 51. 在C语言中有一个语句int int1;词法分析后识别出int、int1和;3个单词。（√） 52. 一个字母或数字在C语言中不一定是单词，因为它们不一定具有独立的意义。（√） 53. 构造识别单词的有限自动机时，先要对程序语言的单词按类构造出相应的有限自动机。
（√） 54. 语法分析的任务是分析语句是如何构成程序的。（×） 55. 语法分析必须在语义分析之前完成。（√）
56. 自上而下语法分析实施的是最左推导。（√）
57. 设有文法G：S→qQ | q Q→cQd | ε ,该文法是LL(1)文法。（×）
58. LL(1)分析法中的“1”是指扫描源程序当前指针P++所指的源程序串的字符。（×） 59. LL(1)分析法中的“1”表示在分析过程中，每一步推导，最多只要向前查看一个输入字
符，即能确定当前推导所应选用的文法规则。（√） 60. 自上而下分析及自下而上分析中的“下”指的是被分析的源程序串。（√） 61. 自上而下分析及自下而上分析中的“上”指的是分析树的根结点或文法的开始符号。（√）
11
编译原理1 题库
62. LL(1)分析必须满足文法不含左公共因子和不含左递归。（√）
63. 语法分析方法中的递归下降分析法属于自上而下分析方法。（√） 64. 文法若存在左递归，则在自上而下语法分析过程中会因为假匹配造成算法的回溯。（×） 65. 文法若存在左递归，则在自上而下语法分析过程中会导致无止境的最左推导，使得分析
算法陷入死循环。（√） 66. LL(1)分析过程中使用的分析栈只能存放文法的终结符。（×）
67. LL(1)分析过程中使用的分析栈存放的是已经扫描且分析过的源程序串。（√） 68. LL(1)分析的主要依据是LL(1)分析表。（√） 69. LL(1)中的“1”通过求FIRST得到。（×）
70. 设有文法中产生式T→ε，若采用递归下降分析法，则T对应的函数是空函数。（√）
四、解答题
1. 请填写完整下图所示的编译程序的组成结构。
源程序 词法分析 语法分析 表 出错管理 格管理语义分析 中间代码生成 代码优化 2. 设有文法G[S]：S→Aa A→Bb | CD C→e 求VN、VT和该文法所描述的语言L(G)。
解：VN={S,A,C}
VT={a,B,b,D,e}
L(G)={Bba,eDa}
3. 设文法G(S)的BNF描述为：
S→S,E | E
E→E+T | T T→T*F | F F→a | (E) | a[S]
① 给出G(S)的元语言符号集、文法符号集、终结符集和非终结符集。 ② G(S)属于哪类文法？写出L(G(S))集合。
③ 判断符号串$1:a,a+a[a[S]]和$2:a*a,a+a[a]是否为文法G(S)的句子，对是L(G(S))的句
子给出相应的分析树。
12
目标代码生成 目标程序
编译原理1 题库
解：（1）元语言符号集：{→, | }
VN={S,E,T,F}
VT={,,+,*,a,(,),[,]}
V= VN∩VT ={ S,E,T,F , ,,+,*,a,(,),[,]} (2) G(S)属于2型文法。
L(G)={连续多个可用逗号连接的简单算术表达式，表达式的运算对象由“+”或“*”连接，运算对象可以为单一的“a”或带括号的表达式或a[连续多个可用逗号连接的简单算术表达式]}
(3)由于$1:a,a+a[a[S]]串中含有非终结符S，所以该符号串不是文法G(S)的句子。 $2:a*a,a+a[a]是文法G(S)的句子，其对应的语法分析树如下（略）
*+2=
4. 若有∑={0,1}，求∑-∑=？，∑？
解：∑*-∑+=ε ∑2={00，01，10，11}
5. 设有字母表A={0}，求A*。
解：A*={ε,0,00,000,0000,….}
6. 令字母表A={0,1,2}上的字符串x=01，y=2，z=001。
（1） 写出下列字符串及它们的长度：x0，xy，xyz, x4,(x3)(y2 ),(xy)2
（2） 写出集合A*和A+的7个最短的符号串。
解：（1）| x0|=|ε|=0 |xy|=|012|=3 |xyz|=|012001|=6
| x4|=|01010101|=8 | (x3)(y2 )|=|01010122|=8 | (xy)2|=|012012|=6 （2）A*={ε,0,1,2,00,01,02, …}
A+={0,1,2,00,01,02,10，…}
7. 设文法G(Z)为：
Z→U0 | V1 U→Z1 | 1 V→Z0 | 0
(1) G(Z)的语言是什么
(2) 写出文法G(Z)构造的长度为6的全部句子。 解：(1)L(G)={01,10}+
(2){010101,010110,011001,011010,101010,100101,100110,101001}
8. 设有文法G[S]：S→SS* | SS+ | a
(1) G[S]的语言L(G[S])是什么？
(2) 下列字符串哪些是该文法的句子？ $1:aa+aa*+a $2:aa+aaa*++
$3:aS+a
(3)对属于该文法的句子$i，画出其语法分析树。
解：(1) L(G[S])={运算对象为a,运算符为双目运算的+或*的逆波兰表达式} (2) $2是文法的句子 (3) $2的语法树略
13
编译原理1 题库
9. 设有文法G[A]：A→Ba B→bB | a 求该文法所描述的语言L(G)。
解：L(G)={ba,n≥0}
10. 已知文法G[E]：
E→T | E+T | E-T
T→F | T*F | T/F F→(E) | i
(1) 给出该文法的VN、VT。
(2) 画出句型E+T*F的语法分析树。
n2
解：(1)VN={E,T,F} VT={+,-,*,/,(,),i}
(2)句型E+T*F的语法树如下：
E E + T T * F 11. 有文法G：S→aAcB|Bd A→AaB|c B→bScA|b
写出句子acabcbbdcc的最左推导过程。
解: S=>aAcB=>a AaB cB=>a caB cB=> a cab cB => a cab c bScA=> a cab c b Bd cA=> a cab c b b d cA=> a cab c b b d cc
12. 文法G[T]：
T→T*F|F F→F↑P|P P→（T）|i
证明T*P↑（T*F）是该文法的一个句型。 解:方法一：推导 证明：
T=>T*F=>T* F↑P=> T* P↑P=> T* P↑（T）=> T* P↑（T*F） 由以上推导可知，T*P↑（T*F）是该文法的一个句型。 注意：推导过程必须保证是最左推导或最右推导 方法二：画语法分析树（略）
13. 设有文法G[S]：S→bTc| a T→R R→R/S | S判断bR/bTc/bSc/ac是否为该文法的句型。 解法同上题
14. 给出下图所示的DFA M描述的语言。
14
编译原理1 题库
S 1 0 1 0 0 1 0 1 1 1 Z
解：L(M)={字母表∑={0,1}上的0和1的个数都是奇数的字符串}
15. 设计一DFA，其输入字母表是{0,1}，接受以0开始以1结尾的所有序列。
解：根据题意描述序列的相应的正规式为：0(0|1)*1，则该正规式对应的NFA状态转换图如下：
0,1 S 0 A ε B ε C 1 Z
利用子集法将NFA确定化如下：
I {S} {A,B,C} { B,C} { B,C,Z} I0 {A,B,C} { B,C} { B,C} { B,C} I1 φ { B,C,Z} { B,C,Z} { B,C,Z} 由{ B,C,Z}与{Z}相交不为空可知{ B,C,Z}为终态。 将状态集重命名，得到相应的DFA状态表如下： I T0 T1 T2 T3* I0 T1 T2 T2 T2 I1 φ T3 T3 T3
16. 构造一个DFA M，它接受以000结尾的二进制串。
解：根据题意以000结尾的二进制串的正规式为：(0|1)*000 相应的NFA状态转换图如下：
0,1 S ε A ε B 0 C 0 D 0 Z
相应的DFA的初态为ε_closure(S)={ S,A,B } 利用子集法构造相应的DFA如下：
15
编译原理1 题库
I {S,A,B} {A,B,C} {A,B } { A,B,C,D} I0 {A,B,C} { A,B,C,D} { A,B,C} I1 {A,B } { A,B } {A, B } { A,B,C,D,Z} {A, B } { A,B,C,D,Z} { A,B,C,D,Z} {A, B } 由{ A,B,C,D,Z}与{Z}交集不为空可知{ A,B,C,D,Z}为DFA的终态。 重命名如下：
I 0 1 2 3 I0 1 3 1 4 I1 2 2 2 2 4* 4 2 使用分割法将DFA最小化： 划分终态、非终态{0,1,2,3} 、{4}；
检查子集{0,1,2,3}，{0,1,2}0={1,3}⊂{0,1,2,3} ，{3}0={4} ⊂{4}所以划分子集{0,1,2,3}为子集{0,1,2} 、{3}；
检查子集{0,1,2}，{0, 2}0={1}⊂{0,1,2} ，{1}0={3} ⊂{3}，所以划分子集{0,1,2}为子集{0,2} 、{1}；
检查子集{0,2}，{0, 2}0={1}⊂{1}，{0, 2}1={2}⊂{2}，所以子集{0,2}不用再划分。 用0状态代替2状态，则最小化后的DFA如下：
0 1 3 4* 0 1 3 4 4 1 0 0 0 0
17. 设M＝（{x,y}, {a,b}, f,x,{y}）为一非确定的有限自动机，其中f定义如下：
f（x,a）＝{x,y} f（y,a）＝φ
f（x,b）＝{y}
f（y,b）＝{x,y}
试构造相应的确定有限自动机M′。
解：确定有限自动机M′的初态为ε_closure(x)={x} 使用子集法确定化如下：
I x {x,y} {y} Ia {x,y} {x,y} φ Ib {y} {x,y} {x,y}
由{x,y},{y}与{y}交集不为空可知，{x,y},{y}为终态。 将M′的状态集重命名如下： I T0
Ia T1 16
Ib T2 编译原理1 题库
T1 T2 **T1 φ T1 T1
18. 为下列正规式构造NFA，并给出它们处理输入串ababbab的状态转换序列。
(1)(a|b)* (2)(a* | b*)* (3)(( ε|a)b*)*
(4)(a|b)*abb(a|b)* 解：
(1) (a|b)*对应的NFA 如下
a,b S ε 0ε Z
处理输入串ababbab的状态转换序列为：S00000000Z (2) (a* | b*)*对应的NFA 如下
a 1， 0ε 2b 处理输入串ababbab的状态转换序列为：S01102201102220110220Z
(3) (( ε|a)b*)*对应的NFA 如下
ε a 0， ε ε
ε S ε ε ε ε Z 1ε ε 2b Z
S 处理输入串ababbab的状态转换序列为：S01220122201220Z
(4) (a|b)*abb(a|b)*对应的NFA 如下
a,b S ε 0 ε 1 a 2 b 3 b4 ε a,b 5 ε Z
17
编译原理1 题库
处理输入串ababbab的状态转换序列为：S0001234555Z
19. 给定NFA M如下表所示： p q r* ε {q,r} φ φ a φ {p} φ b {q} {r} φ c {r} {p,q} φ (1)计算每个状态的ε闭包。
(2)将M确定化，并画出其状态转换图。 解：(1) ε_closure(p)={p,q,r} ε_closure(q)={q}
ε_closure(r)={r}
(2)使用子集法对其确定化为对应的DFA N如下 DFA N的初态集为ε_closure(p)={p,q,r}
{p,q,r} {q,r} {r} 重命名后DFA如下 {p,q,r} 0* {q,r} 1* Ia {p,q,r} {p,q,r} φ Ia {p,q,r} 0 {p,q,r} 0 Ib {q,r} {r} φ Ib {q,r} 1 {r} 2 Ic {p,q,r} {p,q,r} φ Ic {p,q,r} 0 {p,q,r} 0 φ φ φ {r} 2* 其中由于0、1、2状态与{r}交集不为空，所以均为终态。状态转换图略。
20. 设一NFA M=({p,q},{a,b},f,p,{q})，其中f定义如下：
f(p,a)={p,q} f(p,b)={q} f(q,a)= φ f(q,b)={p,q} 请构造相应的DFA，并给出状态转换图的表示形式。 解：答案同题18，状态转换图略。
21. 已知NFA({x,y,z},{0,1},M,{x},{z})，其中：M(x,0){z},M{y,0}{x,y},
M(z,0){x,z},M(x,1){x},M(y,1),M(z,1){y}，构造相应的DFA。
22. 给定NFA M如下图所示：
a 0 a 1 ε 2 b (1)写出NFA M的另外两种描述形式。 五元式形式：
Q={0,1,3,4,5,6} ∑={a,b} q0={0} Z={6} f={ f(0,a)={1} f(0,b)= φ f(0, ε)= φ
18
ε 3 a4 b 5 a 6
编译原理1 题库
f(0,a)={1} f(0,b)= φ f(0, ε)= φ f(1,a)= φ f(1,b)= φ f(1, ε)= {2} f(2,a)={2} f(2,b)= {2} f(2, ε)= {3} f(3,a)={4} f(3,b)= φ f(3, ε)= φ f(4,a)= φ f(4,b)= {5} f(4, ε)= φ f(5,a)={6} f(5,b)= φ f(5, ε)= φ f(6,a)= φ f(6,b)= φ f(6, ε)= φ }
状态表形式：
0 1 2 3 4 5 6* a {1} φ {2} {4} φ {6} φ b φ φ {2} φ {5} φ φ ε φ {2} {3} φ φ φ φ
(2)将M确定化且最小化为DFA，并给出其相应的状态转换图。 解：使用子集法确定化如下
{0} {1,2,3} {2,3,4} {2,3} {2,3,5} {2,3,4,6} 重命名如下：
0 1 2 3 4 5* 最小化的状态表如下 0 1 2 3 4*
Ia {1,2,3} {2,3,4} {2,3,4} {2,3,4} {2,3,4,6} {2,3,4} Ia 1 2 2 2 5 2 a 1 2 2 4 2 19
Ib {2,3} {2,3,5} {2,3} {2,3} {2,3,5} Ib 3 4 3 3 4 b 1 3 1 3 编译原理1 题库
(3)用DFA识别字符串aabaababaaaab为哪几个单词。 识别单词：aaba，ababa；不可识别aaab
最长匹配识别单词aabaababa；不可识别串aaab 23. 对下图和表所示的NFA分别确定化和最小化。
(1)NFA如下图所示
a1 ε 2 b
(2)NFA如下表所示 0 1 2 3 4* 解：
(1)DFA的初态集为ε_closure(1)={1,2,3,4} 使用子集法确定化如下
{1,2,3,4} {2,3,4} {2,3,4,5} Ia {2,3,4} {2,3,4} {2,3,4} Ib {2,3,4,5} {2,3,4,5} {2,3,4,5} a {1,3} {4} φ {1,3} {4} b {2,3} φ {3,4} {4} {4} ε a3 ε 4 b 5
其中{2,3,4,5}∩{5}不为空，所以{2,3,4,5}为终态。 重命名后如下所示 {1,2,3,4} 0 {2,3,4} 1 {2,3,4,5} 2* 最小化的DFA如下： 0 1* Ia {2,3,4} 1 {2,3,4} 1 {2,3,4} 1 a 0 0 Ib {2,3,4,5} 2 {2,3,4,5} 2 {2,3,4} 2 b 1 1
(2) DFA的初态集为ε_closure(0)={0} 使用子集法确定化如下
{0} {1,3} Ia {1,3} {1,3,4} 20
Ib {2,3} {4} 编译原理1 题库
{2,3} {1,3,4} {4} {1,3} {1,3,4} {4} {3,4} {4} {4} {3,4} {1,3,4} {4} 其中{1,3,4}、{4}、{3,4}∩{4}不为空，所以均为终态。 重命名后如下所示
0 1 2 3* 4* 5* 最小化的DFA如下： 0 1 2 3*
24. 构造正规式1(0|1)*101相应的DFA。
解：正规式对应的NFA如下图所示：
0，1 1 1 0 1 Ia 1 3 1 3 4 3 a 1 3 1 3 Ib 2 4 5 4 4 4 b 2 3 3 3 X A B C Y
使用子集法将NFA确定化如下：
{X} T0 {A} T1 {AB} T2 {AC} T3 {ABY} T4 0 {A} {AC} {A} {AC} 1 {A} {AB} {AB} {ABY} {AB} 确定化后的DFA如下图所示： 21
编译原理1 题库
0 1 1 1 0 1 1 T0 T1 T2 T3 T4 0 25. 有如下C语言程序段:
int m;
m=33;
printf(“m=%d\\n”,m);
指出程序段中合法的单词有哪些。 解：int 、m、；、m、=、33、；、printf、（、“m=%d\\n”、，、m、）、；
26. 设计识别单词“-”，“--”，“-=”、“->”的最简的DFA。
27. 已知文法G[E]：
E→T | E+T | E-T
T→F | T*F | T/F F→(E) | i
消除文法中的左递归。 解： 消除左递归后文法如下：
E->T E‟
E‟->+T E‟ |-T E‟ |ε T->FT‟
T‟->*FT‟|/FT‟|ε F→(E) | i
28. 文法G(A)如下
A→BaC | CbB B→Ac | c C→Bb | b
请消除其左递归。
解：令文法G(A)的非终结符排序为A，B，C
0
对于A，不存在直接左递归，将A带入B，代换后的B的规则为： B→BaCc | CbBc | c
B存在直接左递归，消除B的直接左递归 B→CbBcB‟ | c B‟ B‟ →aCcB‟ | ε
将B代入C，代换后C的规则变为： C→CbBcB‟b | cB‟b | b
22
编译原理1 题库
C存在直接左递归，消除C的直接左递归 C→cB‟bC‟ | bC‟ C‟ →bBcB‟b C‟ | ε
所以消除G(A)的左递归后的文法为： A→BaC | CbB B→CbBcB‟ | c B‟ B‟ →aCcB‟ | ε C→cB‟bC‟ | bC‟ C‟ →bBcB‟b C‟ | ε
29. 将下面的左递归文法G(S)改为非左递归的。
S→SaP | Sf | P
P→QbP | Q Q→cSd | e
30. 将文法G[V]改造成为LL(1)的。
G[V]：V→N|N[E] E→V|V+E N→i 解：改造文法如下
V→NA
A→ε |[E] E→VB B→ε |+E
N→i
验证改造后的文法是否为LL(1)： SELECT(A→ε )={ ε} SELECT(A→[E])={[} SELECT(B→+E)={+} SELECT(B→ε)={ ε}
由于文法中相同非终结符的不同产生式的选择集合交集为空，所以改造后的文法是LL(1)文法。
31. 文法G[A]如下：
G(A)：A→aAB | a B→ Bb | d
(1) 判断该文法是否为LL(1)文法。
(2) 若不是请改写为等价的LL(1)文法G′[A]。
解：（1）文法不是LL(1)文法。因为文法中含有左递归，含有左公共因子。 （2）改写后的文法为：
A->aA’ A’->AB|ε B->dB’
B’->bB’ |ε
验证：对A’有FIRST（AB）={a}∩FIRST（A’）={#}= Ø
23
编译原理1 题库
对B’有FIRST（b B’）={b}∩FIRST（B’）={#}= Ø 所以改写后的文法是LL(1)文法。
32. 设有文法G[S]：S→Aa| b A→Ac | Sd | e
(1)． 该文法是否含有直接左递归。
(2)． 该文法是否含有间接左递归。 (3)． 若有请给出消除递归后的文法。 解：
(1)含有直接左递归A→Ac
(2)含有间接左递归S=>Aa=>Sda (3)消除左递归如下： 将非终结符排序S，A S→Aa| b 保持不变
将S代入A→Ac | Sd | e得：
A→Ac | Aad | bd | e
消除上式左递归得：A→cB | adB B→bdB | eB| ε 所以消除左递归后的文法如下： S→Aa| b A→cB | adB B→bdB | eB | ε
33. 已知文法G[S]如下： S→AB|bC A→b | ε
B→aD | ε
C→AD | b
D→aS | ε 求FIRST（aD），FOLLOW（A）和SELECT（B→ ε）。 解：FIRST（aD）={a}
FOLLOW（A）=(FIRST(B)-{ ε})∪FOLLOW（S）∪(FIRST(D)-{ ε})∪FOLLOW（C）
={a}∪{#}∪ FOLLOW（D）{a}∪FOLLOW（S） ={a,#} ∪ FOLLOW（B） ={a,#} ∪ FOLLOW（S）
={a,#}
SELECT（B→ ε）=(FIRST(ε)-{ ε})∪FOLLOW（B）= FOLLOW（S）={#}
34. 文法G(E)如下，求FIRST(T ’)和FOLLOW(F)。
E→TE’ E’→+ TE’ | ε T→FT ’ T ’→ *FT ’ | ε F→(E) | a 解：FIRST(T ’)={*，ε}
24
编译原理1 题库
FOLLOW(F)=(FIRST(T ’)-{ ε})∪FOLLOW(T) ∪FOLLOW(T’) FIRST(T ’)-{ ε}={*}
FOLLOW(T)= (FIRST(E ’)-{ ε})∪FOLLOW(E) ∪FOLLOW(E’)={+, )，#} 所以FOLLOW(F)= {*，+, )，#}
35. 判断文法G(A)：A→aAa | ε是否为LL(1)文法。
解：SELECT(A→aAa)={a}
SELECT(A→ε)=FOLLOW(A)={a,#}
由于SELECT(A→aAa)∩SELECT(A→ε) ={a} 所以该文法不是LL(1)文法。
36. 判断文法G[S]是否为LL（1）文法。
S →AB | PQx
A→xy B→bc P →dP | ε Q→aQ | ε
解：SELECT(S→AB)= FIRST(A) = {x}
SELECT(S→PQx)= (FIRST(P)-{ ε})∪(FIRST(Q)-{ ε})∪FIRST(x)={d,a,x} 由于SELECT(S→AB)∩SELECT(S→PQx) ={x} 所以该文法不是LL(1)文法。
37. 判断文法G(A)：A→aABe |Ba B→dB | ε是否为LL(1)文法。
解：SELECT(A→aABe)={a}
SELECT(A→Ba)=(FIRST(B)-{ ε})∪{a}={a,d}
由于SELECT(A→aABe)∩SELECT(A→Ba) ={a} 所以该文法不是LL(1)文法。
38. 设有文法G[A]: A->AaB | bB B->Dc D->Ad
(1)计算文法中每个非终结符的FISRT和FOLLOW集合。
(2)判断该文法是否为LL(1)文法？若不是请改写为LL(1)文法。 (3)构造LL(1)分析表。
解：
（1）FISRT(A)={b} FISRT(B)={b} FISRT(D)={b}
FOLLOW(A)={a,d,#} FOLLOW(B)={ a,d,#} FOLLOW(D)={c} (2)由于文法存在左递归A->AaB，所以该文法不是LL(1)文法。 改写文法：
将D代入B得B-> Adc
将B代入A得A->Aa Adc | b Adc 消除左递归得：A-> b AdcA‟
A‟->a Adc A‟ | ε 由于SELECT(A‟->a Adc A‟)∩SELECT(A‟->ε) ={a}∩{d,#}= φ 所以改写后的文法是LL(1)文法。
25
编译原理1 题库
（3） 改写后的文法的LL(1)分析表如下 A A‟ A‟->a Adc A‟ a b A-> b AdcA‟ c A‟->ε d A‟->ε #
39. 设有下列文法：
PROGRAM→begin d; S end S→d;S | sT T→;sT | ε （1） 构造该文法LL(1)分析表； （2） 给出句子begin d;s;s end的分析过程（写出含有符号栈、输入串和规则的分析过程）。 解：（1）SELECT(PROGRAM→begin d; S end)= FISRT(begin d; S end)=｛begin｝
SELECT(S→d;S)= FISRT(d;S)=｛d｝ SELECT(S→sT)= FISRT(sT)=｛s｝ SELECT(T→;sT)= FISRT(;sT)=｛;｝ SELECT(T→ε)= FOLLOW(T)=｛end｝ 根据上述结果构造文法LL(1)分析表如下： begin PROGRAM PROGRAM→begin d; S end S T 步骤 1 2 3 4 5 6 7 8 9 10 11 12
26
d S→d;S s S→sT ; end 分析栈 # PROGRAM # end S; d begin # end S; d # end S; # end S # end T s # end T # end T s; # end T s # end T # end # 剩余输入串 begin d;s;s end# begin d;s;s end# d;s;s end# ;s;s end# s;s end# s;s end# ;s end # ;s end # s end # end # end # # T→;sT T→ε (3) 句子begin d;s;s end的分析过程如下： 推导用产生式或匹配 PROGRAM→begin d; S end „begin‟匹配 „d‟匹配 „;‟匹配 S→sT „s‟匹配 T→;sT „;‟匹配 „s‟匹配 T→ε „end‟匹配 分析成功 编译原理1 题库
40. 设有文法G[S]:S->Pab | bP P->ε | b
根据文法G[S]填写如下LL(1)分析表的内容。 P
41. 设有文法G[S]:
S->AB|bb |bAC A->ε|b B-> |aC C->aS|c
则FOLLOW(A)={ a,c,# }。 对给出的文法G[S]填写如下LL(1)分析表的内容。 A
42. 已知文法G[S]:
S→aBc|bAB A→aAb|b B→b|ε
（1） 构造其LL（1）分析表；
（2） 判断符号串baabbb是否为该文法的句子（写出含有符号栈、输入串和规则的分析过
程）。 解：
(1) SELECT(S→aBc)={a} SELECT(S→bAB)={b} SELECT(A→aAb)={a}
SELECT(A→b)={b} SELECT(B→b)={b}
SELECT(B→ε)={c,#}
由于文法中相同非终结符的不同产生式的选择集合交集为空，所以该文法是LL(1)文法。根据每条产生式的选择集合构造LL(1)分析表如下：
S A B a S→aBc A→aAb b S→bAB A→b B→b c B→ε # B→ε 推导用产生式或匹配 S→bAB „b‟匹配 A→aAb „a‟匹配 27
a P->ε P->b b P->ε # a A->ε A->b b A->ε c A->ε # (2) 符号串baabbb的分析过程如下： 步分析栈 剩余输入串 骤 1 2 3 4 #S # BAb # BA #BbAa baabbb# baabbb # aabbb# aabbb# 编译原理1 题库
5 6 7 8 9 10 11 12
#BbA # BbbAa # BbbA # Bbbb # Bbb # Bb #B # abbb # abbb # bbb # bbb # bb # b# # # A→aAb „a‟匹配 A→b „b‟匹配 „b‟匹配 „b‟匹配 B→ε 分析成功 43. 构造下面文法的LL（1）分析表。
D→ TL T→ int | real L→ id R
R→ , id R | ε
解：SELECT(D→ TL)={int,real}
SELECT(T→ int )={int} SELECT(T→ real)={real} SELECT(L→ id R)={id}
SELECT(R→ , id R)={,} SELECT(R→ε)={#}
由于文法中相同非终结符的不同产生式的选择集合交集为空，所以该文法是LL(1)文法。根据每条产生式的选择集合构造LL(1)分析表如下：
D T L R
44. 文法G[A]如下：
G(A)：A→aABe | a B→ Bb | d
(1)． 该文法是否为LL(1)文法。
(2)． 若不是请改写为等价的LL(1)文法G′[A]。 (3)． 构造G′[A]的LL(1)分析表。 (4)． 给出符号串aade#的分析过程。 解：
(1)由于关于A的产生是含有左公共因子，关于B的产生是含有左递归，所以该文法不
28
int D→ TL T→ int real D→ TL T→ real id L→ id R , R→ , id R # R→ε 编译原理1 题库
是LL(1)文法。 (2)改写后的文法为： A→a A‟ A‟ →ABe |ε B→ dB‟
B‟ →bB‟ |ε
验证：对A’有FIRST（ABe）={a}∩FOLLOW（A’）={d,#}= Ø
对B’有FIRST（b B’）={b}∩FIRST（B’）={e}= Ø 所以改写后的文法是LL(1)文法。
(3) 该文法的LL（1）分析表。
A A‟ B B‟ a d b B‟ →bB‟ e B‟ →ε # A‟ →ε A→a A‟ A‟ →ABe A‟ →ε B→ dB‟ (4) 符号串aade#的分析过程如下 步骤 1 2 3 4 5 6 7 8 9 10 11 分析栈 #A # A‟a # A‟ #eBA #eBA‟a # eBA‟ #eB #eB‟d # eB‟ #e # 剩余输入串 aade# aade # ade# ade # ade # de# de# de# e# e# # 推导用产生式或匹配 A→a A‟ „a‟匹配 A‟ →ABe A→a A‟ „a‟匹配 A‟ →ε B→ dB‟ „d‟匹配 B‟ →ε „e‟匹配 分析成功
45. 已知文法G[S]:
S→aH
H→aMd | d
M→Ab | ε A→aM | e
(1) 证明该文法是否为LL(1)文法。
29
编译原理1 题库
证明：SELECT（H→aMd）∩SELECT（H→d）={a}∩{d}= Ø SELECT（M→Ab ）∩SELECT（M→ ε）={a，e}∩{d,b}= Ø SELECT（A→aM ）∩SELECT（A→e）={a}∩{e}= Ø ∴该文法是LL(1)文法。
(2) 构造该文法的LL（1）分析表。 S S→aH H M A H→aMd M→Ab A→aM H→d M→ ε M→ ε M→Ab A→e a d b e #
(3) 给出输入串aaabd#的预测分析过程，并判断该输入串是否为该文法的句子。
步骤 1 2 3 4 5 6 7 8 9 10 11 分析栈 #S #Ha #H #dMa #dM #dbA #dbMa #dbM #db #d # 剩余输入串 aaabd# aaabd# aabd# aabd# abd# abd# abd# bd# bd# d# # 推导用产生式或匹配 S→aH „a‟匹配 H→aMd „a‟匹配 M→Ab A→aM „a‟匹配 M→ ε „b‟匹配 „d‟匹配 分析成功
∴输入串aaabd#是该文法的句子。
46. 编写下列文法G[E]的递归下降分析程序(伪代码即可)。 G[E]：
E→Aa | Bb
A→cA | eB B→bd
30
因篇幅问题不能全部显示，请点此查看更多更全内容