填空（30分）
1、将编译过程的各阶段划分为前端或后端和将编译程序分遍的主要参考因素都是（）和（）的特征。
2、（）是一种语法分析程序的自动构造工具，用它可以直接构造各种语言的语法分析器；而（）是一种词法分析程序的自动构造工具，用它可以直接构造各种语言的词法分析器。
3、假设 G[S] 是一个文法, 如有 $S \Rightarrow x$ , 则称 x 是该文法 G 的 ( )；文法 G 产生的 ( ) 的全体称为该文法所描述的语言。
4、所谓2型文法就是指（）文法，若用 $G = (V_{N}, V_{T}, P, S)$ 表示它，则它要求G中的所有规则 $\alpha \rightarrow \beta$ 都满足： $\alpha$ 是（），而 $\beta$ 属于 $(V_{N} U V_{T})^{*}$ 。
5、文法中形如 U→U 的规则称为（）规则；由不可达的非终结符或不可终止的非终结符作为左部的规则称为（）规则。在实用文法中一般不允许含有这两类规则。
6、在用五元组表示的确定的有穷自动机 DFAM=（K，V，F，S，Z）中，元素 V 表示字母表；元素 S 表示唯一的初态，它是状态集 K 的一个元素；元素 F 表示（）；元素 Z 表示终态集，它是状态集 K 的一个（）。
7、语法分析方法分为自上而下与自下而上两类，自上而下的分析方法方要有递归子程序分析法和（）；而自下而上的分析方法主要有（）和 LR 分析方法。
8、LR(0)项目集规范族中的项目可分为四类，它们是移进项目、（）、归约项目和接受项目。其中，接受项目是（）的一种特例。
9、将非LL(1)文法转换为等价的LL(1)文法所采用的两种方法是（）和（）。但这两种方法并不能保证所有的非LL(1)文法都能转换为等价的LL(1)文法。
10、通常局部优化是指基本块内的优化，所谓基本块是指程序中一顺序执行的语句序列，其中只有一个（）语句和一个（）语句。
11、算符优先分析时，在句型 $N_{1}a_{1}N_{2}\cdots a_{i-1}N_{i}a_{i}N_{i+1}a_{i+1}\cdots a_{j}N_{j+1}a_{j+1}N_{j+2}\cdots$ 中，寻找的最左素短语 $N_{i}a_{i}N_{i+1}a_{i+1}\cdots a_{j}N_{j+1}$ 中的终结符应满足下优先关系：（）、（）、（）。
12、在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。符号表的功能可以归结为三个主要方面，即（）、作为上下文语义合法性检查的依据和作为（）的依据。
13、根据优先关系矩阵计算优先函数可用迭代法或优先关系图法，但先关系图方法计算出来的优先函数不一定有效，当（）时，所得的优先函数无效，这时也说明该优先关系矩阵不存在优先函数。
14、当一个过程调用其他过程时，调用过程和被调用过程之间的通信经由非局部变量或者经由参数传递，常用的参数传递方式有（）、（）等。
15、现代很多编译程序都采用（）翻译方法，它是指在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义子程序或语义动作进行翻译的办法。这种方法使用（）为工具来说明程序设计语言的语义。
二、结合你所熟悉的一门高级语言的编译系统，简述典型编译程序在各个工作阶段的任务。(共7分)
三、给定正规式 $R = (01|10)(01|10)^*$ ，要求：（10分）
1、构造对应的正规文法 G，使得 L(G)=L(R)。（4 分）
2、构造对应的NFA M状态图，使得 $\mathrm{L(M) = L(R)}$ 。 (3分)
3、将所得NFA M确定化为DFA。（3分）
四、现有文法G[E]：（共10分）
1、证明：E-F\*(i)是文法的一个句型。(3分)
2、构造句型 E-F\*(i) 的语法推导树。(2 分)
3、指出该句型所有短语、直接短语和句柄。(5 分)
五、任意给定一个文法 G[S]: (10 分)
1、给出判断 G[S] 是否为 LL(1) 文法的步骤。(4 分)
2、如果 G[S] 是 LL(1) 文法，怎样构造它的预测分析表？(3 分)
3、怎样根据预测分析表对给定的某个输入串进行预测分析？(3 分)
六、现有文法G[E]：(共15分)
$\mathrm{E}\rightarrow \mathrm{E};\mathrm{D}|\mathrm{D}$
$\mathrm{D}\rightarrow \mathrm{D(T)}|\mathrm{H}$
$\mathrm{H}\rightarrow \mathrm{a}\mid (\mathrm{E})$
$\mathrm{T}\rightarrow \mathrm{T}*\mathrm{E}|\mathrm{E}$
1、计算 G[E] 的 FIRSTVT 和 LASTVT；(4 分)
2、构造 G[E] 的算符优先关系表, 并说明 G[E] 是否为算符优先文法; (5 分)
3、给出输入串(a\*a)# 的算符优先分析过程，并据此说明算符优先分析方法的优点和缺点。(6 分)
七、现有文法 G[S’]：（共 18 分）
0) S' → S
1) S → L = R
2) S → R
3) L → \* R
4) L → i
5) R → L
1、构造 G[S'] 的 LR(0) 项目集规范族 DFA，并据此判断 G[S'] 是否为 LR(0) 文法或 SLR(1) 文法。(6 分)
2、构造 G[S’] 的 LR(1) 项目集规范族 DFA，并据此判断 G[S’] 是否为 LR(1) 文法或 LALR(1) 文法。(6 分)
3、给出相应的LALR(1)分析表。(3分)
4、简述 LR 分析算法。(3 分)