一、选择题
1. 编译的各阶段工作都涉及（ A ）。
A．符号表管理 B．词法分析 C．语法分析 D．语义分析
2. 一个上下文无关文法消除了左递归，提取了左公共因子后是该文法满足LL（1）文
法的( B )。
A．充分条件 B．必要条件 C．充要条件 D．没有关系 3. 一个LR（1）文法合并同心集后若不是LALR（1）文法（ B ）。
A．则只可能存在移进/归约冲突 B．则只可能存在归约/归约冲突 C．则可能同时存在移进/规约冲突和归约/归约冲突 D．则没有冲突存在 4. 设有文法G[S]：S?S1|S0|Sa|Sc|a|b|c，下列符号串中哪个不是该文法的句子？
（ D ）。
A. bc10 B. a0c01 C. aaa D. ab0 5. 下列哪一项不是活动记录的组成部分（ C ）。
A.返回值 B.控制链 C.代码段 D.访问链 6. 词法分析器加工的对象是（ A ）。
A． 源程序 B.中间代码 C. 目标代码 D. 记号流 7. 正规式是（ D ）型文法。
A．0 B．1 C．2 D．3 8. 文法 S→aaS|abc 定义的语言是（ C ）。
A．{a2kbc|k>0} B．{akbc|k>0} C．{a2k-1bc|k>0} D．{akakbc|k>0}
9. 若B为非终结符，则 A→?·B? 为（ D ）。
A． 移进项目 B．归约项目 C．接受项目 D．待约项目 10. （ B ）和代码优化部分不是每个编译程序都必需的。
A．语法分析 B．中间代码生成 C．词法分析 D．目标代码生成
二、填空题
1. 语法分析最常用的两类方法是__自上而下_____和____自下而上____分析法。 2. 文法符号的属性有两种，一种称为__继承属性___，另一种称为__综合属性___。 3. 三种常用的存储分配办法是 静态存储 分配、 栈式存储 分配和 堆式存
储 分配。
4. 像Pascal这样的语言，允许过程嵌套，并使用静态作用域，运行时访问非局部名字
的时候，可以利用 访问链 来确定该非局部名字被绑定到的活动记录。 5. 指令SUB *R0, *12(R1)的代价为 2 ，*R0所代表的地址为 contents(R0) 。
三、画出能被3整除的二进制串的DFA。
四、已知文法G[S]: S?SaA|bB
A?aB|c B?Bb|d
(1)（5分）消除G[S]中的左递归为等价的文法G’[S]。
(2)（10分）构造消除左递归后的G’[S]的FIRST集和FOLLOW集，并判断G’[S]是否是LL(1)文法。
(1) S?bBS’
S’?aAS’ |? A?aB|c B? dB’
B’?bB’|? (2) FIRST(S)={d}
FIRST(S’)={a, ?} FIRST(A)={a,c} FIRST(B)={d}
FIRST(B’)={b, ?}
FOLLOW(S)={$} FOLLOW (S’)={$} FOLLOW (A)={a，$} FOLLOW (B)={a，$} FOLLOW (B’)={a，$}
是LL(1)文法。
五、（10分）设有字母表{a, b}上的正规式R=(ab|a)。 （1）构造R的NFA。 （2）构造R的DFA。
*
