《编译原理》模拟试题三
一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×)
2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(× )
3．递归下降分析法是自顶向上分析方法。(√ ) 4．产生式是用于定义词法成分 的一种书写规则。 (×) 5．LR 法是自顶向下语法分析方法。 (√ )
6．在 SLR （ 1 ）分析法的名称中，S的含义是简单的。(√) 7．综合属性是用于 “ 自上而下 ” 传递信息。(× )
8．符号表中的信息栏中登记了每个名字的 属性和特征等有关信息 ，如类型、种属、所占单元大小、地址等等。 (×)
9．程序语言的语言处理程序是一种应用软件。 (×) 10．解释程序适用于 COBOL 和 FORTRAN 语言。 (×)
二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)
1． 文法 G 产生的_____的全体是该文法描述的语言。
A．( ) 句型 B．( ) 终结符集 C．( ) 非终结符集 D．( ) 句子 2． 若文法 G 定义的语言是无限集，则文法必然是 _____。 A．( ) 递归的 B．( ) 前后文无关的 C．( ) 二义性的 D．( ) 无二义性的
3． 四种形式语言文法中，1型文法又称为 _____文法。 A．( ) 短语结构文法 B．( ) 前后文无关文法 C．( ) 前后文有关文法 D．( ) 正规文法 4． 一个文法所描述的语言是_____。
A．( ) 唯一的 B．( ) 不唯一的 C．( ) 可能唯一，好可能不唯一 D．( ) 都不对 5． _____和代码优化部分不是每个编译程序都必需的。 A．( ) 语法分析 B．( ) 中间代码生成 C．( ) 词法分析 D．( ) 目标代码生成 6．_____是两类程序语言处理程序。
A．( ) 高级语言程序和低级语言程序 B．( ) 解释程序和编译程序 C．( ) 编译程序和操作系统 D．( ) 系统程序和应用程序 7． 数组的内情向量中肯定不含有数组的_____的信息。
A. ( ) 维数 B．( ) 类型 C．( ) 维上下界 D．( ) 各维的界差 8. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式
9． 文法分为四种类型，即0型、1型、2型、3型。其中2型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．文法 G 所描述的语言是_____的集合。
A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 三、填空题(每空1分，共10分)
1．一个句型中的最左简单短语称为该句型的___句柄__。
2．对于文法的每个产生式都配备了一组属性的计算规则，称为 __语义规则___ 。 3．一个典型的编译程序中，不仅包括__词法分析___、__语法分析___、__中间代码生成___、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。
4． 从功能上说，程序语言的语句大体可分为__执行性___语句和__说明性___语句两大类。 5． 扫描器的任务是从__源程序___中识别出一个个___单词符号__。 6． 产生式是用于定义__语法范畴___的一种书写规则。 四、简答题（20分）
1. 写一个文法，使其语言是奇数集，且每个奇数不以0开头。 解：文法G(N)： N→AB|B A→AC|D B→1|3|5|7|9 D→B|2|4|6|8 C→0|D 2. 设文法G(S)： S→(L)|a S|a L→L，S|S (1) 消除左递归和回溯；
(2) 计算每个非终结符的FIRST和FOLLOW。
解：(1) S→(L)|aS' S'→S|ε L→SL' L'→SL'|ε (2)
FIRST)S)＝{(，a} FOLLOW(S)＝{#，，，)} FIRST(S')＝{，a,ε} FOLLOW(S')＝{#，，，)} FIRST(L)＝{(，a} FOLLOW(L)＝{ )} FIRST(L')＝{，，ε} FOLLOW(L'〕＝{ )}
3. 已知文法G(E)
E→T|E＋T
T→F|T *F
F→(E)|i
(1)给出句型(T *F＋i)的最右推导；
(2)给出句型(T *F＋i)的短语、素短语。
解：(1) 最右推导： E->T->F->(E)->(E＋T)->(E＋F)->(E＋i) ->(T＋i)->(T*F＋i)
(2) 短语：(T*F＋i)，T*F＋i，T*F，i 素短语：T*F,i
4. While a＞0 ∨ b＜0 do Begin
X：＝X＋1； if a＞0 then a：＝a－1 else b：＝b＋1 End；
翻译成四元式序列。 解：
(1) (j＞，a，0，5) (2) (j，－，－，3) (3) (j＜，b，0，5) (4) (j，－，－，15) (5) (＋，×，1，T1)
(6) (：＝，T1，－，×) (7) (j≥，a，0，9) (8) (j，－，－，12) (9) (－，a，1，T2) (10) (：＝，T2，－，a) (11) (j，－，－，1) (12) (＋，b，1， T3) (13) (：＝，T3，－，b) (14) (j，－，－，1) (15)
五.计算题（10分）
已知 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并最小化。
解：根据题意有NFA图:下
表
由
子
集
法
将
NFA
转
换
为
DFA
：