9．若项目集Ik含有A->α · ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A->α · ”动作的一定是_____。
A. ( ) LALR文法 B．( ) LR(0)文法 C．( ) LR(1)文法 D．( ) SLR(1)文法 10．堆式动态分配申请和释放存储空间遵守_____原则。 A. ( ) 先请先放 B．( ) 先请后放 C．( ) 后请先放 D. ( ) 任意 三、填空题(每空1分，共10分)
1．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。
2．语法分析基于__上下文无关___文法进行，即识别的是该类文法的句子。语法分析的有效工具是__语法树___。
3．分析句型时，应用算符优先分析技术时，每步被直接归约的是__最左素短语___，而应用LR分析技术时，每步被直接归约的是___句柄__。
4．语义分析阶段所生成的与源程序等价的中间表示形式可以有__逆波兰___、___四无式表示__与___三元式表示__等。
5．按Chomsky分类法，文法按照___规则定义的形式__进行分类。
6．一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有___递归__定义的规则。 四、简答题（20分） 1. 文法 G[S] 为： S->Ac|aB A->ab
B->bc
写出 L(G[S]) 的全部元素。 解：S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc}
2. 构造正规式 1(0|1)*101 相应的DFA。 解：先构造NFA：
确定化：
重新命名，令AB为B、AC为C、ABY为D得：
所以，可得DFA为：
3. 文法 S->a|^|(T) T->T,S|S
对 (a,(a,a) 和 (((a,a),^,(a)),a) 的最左推导。
解： 对(a,(a,a)的最左推导为： S=>(T) =>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)) =>(a,(a,a))
对(((a,a),^,(a)),a) 的最左推导为： S=>(T) =>(T,S) =>(S,S) =>((T),S)
=>((T,S),S) =>((T,S,S),S) =>((S,S,S),S)
=>(((T),S,S),S) =>(((T,S),S,S),S) =>(((S,S),S,S),S) =>(((a,S),S,S),S) =>(((a,a),S,S),S) =>(((a,a),^,S),S) =>(((a,a),^,(T)),S) =>(((a,a),^,(S)),S) =>(((a,a),^,(a)),S) =>(((a,a),^,(a)),a)
4. 文法： S->MH|a H->LSo| ε K->dML| ε L->eHf M->K|bLM
判断 G 是否为 LL(1) 文法，如果是，构造 LL(1) 分析表。 解：各符号的FIRST集和FOLLOW集为：
预测分析表为：
由于预测分析表中无多重入口，所以可判定文法是LL(1)的。
五.计算题（10分） 已知文法 G[S] 为： S->a|^|(T) T-> T,S|S
(1) 计算 G[S] 的 FIRSTVT 和 LASTVT 。
(2) 构造 G[S] 的算符优先关系表并说明 G[S] 是否未算符优先文法。 (3) 计算 G[S] 的优先函数。
(4) 给出输入串 (a,a)# 的算符优先分析过程。
解：（1）各符号的FIRSTVT和LASTVT：
（2）算符优先关系表：
（3）对应的算符优先函数为：
（4）句子(a,a)#分析过程如下：