编译原理参考题目
第一套
一、判断题
1．用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行 ”这种说法。( N)
2．若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。( N)
3．一个句型的句柄一定是文法某产生式的右部。 (Y )
4．在程序中标识符的出现仅为使用性的。 ( N)
5．仅考虑一个基本块，不能确定一个赋值是否真是无用的。 (Y )
6．削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。 (Y )
7．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 (N )
8．算符优先关系表不一定存在对应的优先函数。 ( N)
9．数组元素的地址计算与数组的存储方式有关。 (N )
10．编译程序与具体的机器有关,与具体的语言无关。 (N )
参考答案：
1、×    2、×    3、√    4、×    5、√
6、√    7、×    8、×    9、×    10、×
二、选择题
1． 通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_____。
A．模拟执行器         B．解释器
C．表格处理和出错处理 D．符号执行器
2． 文法 G[N]= （ {b} ， {N ， B} ， N ， {N→b│bB ， B→bN} ），该文法所描述的语言是
  A． L(G[N])={bi│i≥0}  B． L(G[N])={b2i│i≥0}
  C． L(G[N])={b2i+1│i≥0}  D． L(G[N])={b2i+1│i≥1}
3． 一个句型中的最左_____称为该句型的句柄。
  A．短语 B．简单短语  C．素短语 D．终结符号
4． 设 G 是一个给定的文法， S 是文法的开始符号，如果 S->x( 其中 x∈V*), 则称 x 是文法 G 的一个_____。
  A．候选式  B．句型  C．单词 D．产生式
5． 文法 G[E] ：
E→T∣E ＋ T
T→F∣T ﹡ F
F→a∣ （ E ）
该文法句型 E ＋ F ﹡ (E ＋ T) 的简单短语是下列符号串中的_____。
① （ E ＋ T ）  ② E ＋ T   ③ F   ④ F ﹡ (E ＋ T)
  A．① 和 ③  B．② 和 ③  C．③ 和 ④  　D．③
6． 若一个文法是递归的，则它所产生的语言的句子_____。
A．( ) 是无穷多个  B．( ) 是有穷多个   
C．( ) 是可枚举的  D．( ) 个数是常量
7． 词法分析器用于识别_____。
  A．( ) 句子  B．( ) 句型 C．( ) 单词 D．( ) 产生式
8． 在语法分析处理中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_____。
  A. ( ) 非终极符集 B．( ) 终极符集  C．( ) 字母表 D. ( ) 状态集
9． 在自底向上的语法分析方法中，分析的关键是_____。
  A.( ) 寻句柄 B.( ) 寻句型 C.( ) 消除递归 D.( ) 选择候选式
10． 在 LR 分析法中，分析栈中存放的状态是识别规范句型_____的 DFA 状态。
  A.( )句柄   B.( ) 前缀   C.( )活前缀   D.( ) LR(0) 项目
参考答案：
1、C    2、C    3、B    4、B    5、B
6、A    7、C    8、B    9、D    10、C
三、填空题
1．设G是一个给定的文法，S是文法的开始符号，如果S->x( 其中 x∈VT*), 则称 x是文法的一个__句子___。
2．递归下降法不允许任一非终极符是直接  左  递归的。
3．自顶向下的语法分析方法的基本思想是：从文法的_开始符号__开始，根据给定的输入串
并按照文法的产生式一步一步的向下进行_直接推导_，试图推导出文法的__句子__，使之与给定的输入串_匹配_。
4．自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行_直接规约_ ，力求 归约到文法的__开始符号___。
5．常用的参数传递方式有_传地址_，传值和传名。
6．在使用高级语言编程时,首先可通过编译程序发现源程序的全部_语法__错误和语义部分错误。
参考答案：
1．句子
2．左
3．开始符号 直接推导 句子 匹配
4．直接归约 开始符号
5．传地址
6．语法
四、简答题
1. 已知文法 G[S] 为：
S→dAB
A→aA|a
B→Bb|ε
G[S] 产生的语言是什么？
参考答案：
答：G[S]产生的语言是L(G[S])={danbm│n≥1,m≥0}。
2. 简述 DFA 与 NFA 有何区别 ?
参考答案：
答：DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。 另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集， 即映象M将产生一个状态集合（可能为空集），而不是单个状态。 
5. 何谓优化？按所涉及的程序范围可分为哪几级优化？
参考答案：
(1)优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。        　
(2) 三种级别：局部优化、循环优化、全局优化。
五.计算题（10分）
  对下面的文法 G ：
　  E->TE'
  E'->+E| ε
  T->FT'
  T' ->T| ε
  F-> PF'
  F'-> *F'| ε
  P->(E)|a|b|^
  (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。
参考答案：
解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。
FIRST集合有：
FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(E')={+,ε}
FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(T')=FIRST(T)∪{ε}={(,a,b,^,ε};
FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(F')=FIRST(P)={*,ε};
FIRST(P)={(,a,b,^};
FOLLOW集合有：
FOLLOW(E)={),#};
FOLLOW(E')=FOLLOW(E)={),#};
FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};//不包含ε
FOLLOW(T')=FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};
FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};//不包含ε
FOLLOW(F')=FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};
FOLLOW(P)=FIRST(F')∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε
basic语言是解释型语言吗(2)证明这个方法是LL(1)的。
各产生式的SELECT集合有：
SELECT(E->TE')=FIRST(T)={(,a,b,^};
SELECT(E'->+E)={+};
SELECT(E'->ε)=FOLLOW(E/)={),#}
SELECT(T->FT')=FIRST(F)={(,a,b,^};
SELECT(T'->T)=FIRST(T)={(,a,b,^};
SELECT(T'->ε)=FOLLOW(T/)={+,),#};
SELECT(F->PF')=FIRST(P)={(,a,b,^};
SELECT(F'->*F')={*};
SELECT(F'->ε)=FOLLOW(F')={(,a,b,^,+,),#};
SELECT(P->(E))={(}
SELECT(P->a)={a}
SELECT(P->b)={b}
SELECT(P->^)={^}
可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。