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）对应的算符优先函数为：