分类: 项目管理
2008-04-02 07:25:53
一、选择题(每个选择题2分,共20分)
1.文法G产生的 ⑴ 的全体是该文法描述的语言。
A.句型 B. 终结符集 C. 非终结符集 D.句子
2.若文法G定义的语言是无限集,则文法必然是 ⑵ :
A.递归的 B 前后文无关的 C 二义性的 D 无二义性的
3.Chomsky定义的四种形式语言文法中,0型文法又称为 ⑶ 文法;1型文法又称为 ⑷ 文法;2型语言可由 ⑸ 识别。
A.短语结构文法 B 前后文无关文法 C 前后文有关文法 D正规文法
E 图灵机 F 有限自动机 G 下推自动机
4.一个文法所描述的语言是 ⑹ ;描述一个语言的文法是 ⑺ 。
A.唯一的 B不唯一的 C 可能唯一,也可能不唯一
5.数组的内情向量中肯定不含有数组的
⑻ 的信息
A.维数 B.类型 C.维上下界 D.各维的界差
6.在下述的编译方法中,自底向上的方法有 ⑼ ,自顶向下的分析方法有 ⑽ 。
①简单优先分析 ②算符优先分析 ③递归下降分析 ④预测分析技术 ⑤LR(K)分析
⑥SLR(k)分析 ⑦ LL(k)分析 ⑧LALR(K)分析
A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦
E.①②⑤⑥⑦ F. ①②⑤⑥⑧
二、简答题(每小题5分,共20分)
1.LL(1)分析法对文法有哪些要求?
2.常见的存储分配策略有几种?它们都适合于什么性质的语言?
3.常见循环优化都有哪些项目?
4.什么是活动记录?它主要由哪些内容构成?
三、(8分)化简文法G[S]:
S→ASe | BCaD | aD | AC
A→Cb | DBS
C→bC | d
B→Ac D→aD
四、(12分)已知文法G的产生式为:S->AB A->aA|ε B->bBc|bc
(1)求文法G识别的语言L。
(2)试构造识别L的最小化的DFA。
五、(8分)已给文法G[S]: S→SaP | Sf | P P→ qbP | q
将G[S]改造成LL(1)文法,并给出LL(1)分析表。
六、(8分)给定文法 S→(A)|a A→A+S A→b
试构造相应的算符优先矩阵,并判断其是否为算符优先文法。
七、(8分)给定文法G[S]:S→Aa|dAb|Bb|dBa A→c B→c
构造文法G[S]的LR(1)分析表。
八、(8分)将下面的条件语句表示成和四元式序列:
if a>b
then x:=a+b else x:=b-a;
九、(8分)给定基本块:
A:=3*5
B:=E+F
C:=A+12
D:=E+F
A:=D+12
C:=C+1
E:=E+F
假定出基本块后,只有A、C、E是有用的,给出用DAG图完成优化后的代码序列。