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：
下面将该DFA最小化：
(1) 首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}
(2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于 F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。 有P21={C,F},P22={B}。
(3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分， 有P11={A,E},P12={D}。
(4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。
(5) 综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA 如下：
《编译原理》模拟试题四
一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）
1．一个 LL(l)文法一定是无二义的。 (× )
2．正规文法产生的语言都可以用上下文无关文法来描述。 (× )
3．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 (√)
4．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 (× )
5．逆波兰法表示的表达式亦称前缀式 。 (√ )
6．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 (√ )
7．LR 法是自顶向下语法分析方法。 (× )
8．数组元素的地址计算与数组的存储方式有关。(× )
9．算符优先关系表不一定存在对应的优先函数。 (×)
10．对于数据空间的存贮分配， FORTRAN 采用动态贮存分配策略。 (×)
二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共 40分)
1．词法分析器用于识别_____。