一:(15分)判断下列命题的真假,并简述理由:

1.文法G的一个句子对应于多个推导,则G是二义的.

2.LL(1)分析必须对原有文法提取左因子和消除左递归.

3.算符优先分析法采用"移近-归约"技术,其归约过程是规范的.

4.文法S→aA;A→Ab;A→b是LR(0)文法(S为文法的开始符号).

5.一个BASIC解释程序和编译程序的不同在于,解释程序由语法制导翻译成目标代码

并立即执行之,而编译程序需产生中间代码及优化.

二:(15分)设计一个最小状态有穷自动机,识别由下列子串组成的任意字符串.GO,GOTO,TOO,ON例如:GOTOONGOTOOGOON是合法字符串.

三:(15分)构造一个LL(1)文法G,识别语言L:L={ω|ω为{0,1}上不包括两个相邻的1的非空串}并证明你的结论.

四:(20分)设有一台单累加器计算机,并汇编语言含有通常的汇编指令LOAD,STORE,ADD和MUL.

1.写一个递归下降分析程序,将如下文法所定义的赋值语句翻译成汇编语言:

A→i:=E

E→E+E|E*E|(E)|i

2.利用加,乘法满足交换率这一性质,改进你的分析程序,以期产生比较高效的目标

代码.

五:(15分)C为大家熟知的程序语言.

1.C的参数传递采用传值的方式,而且允许函数定义和调用时的参数个数不一致(如printf).请指出其函数调用语句:

f(arg1,arg2,...,argn)

翻译成的中间代码序列,并简述其含义.

2.C语言中的变量具有不同的作用范围,试述C应采用的存储分配策略.

六:(20分)设有一个子程序的四元式序列为:

(1) I:=1

(2) if I>20 GOTO (16)

(3) T1:=2*J

(4) T2:=20*I

(5) T3:=T1+T2

(6) T4:=addr(A)-22

(7) T5:=2*I

(8) T6:=T5*20

(9) T7:=2*J

(10) T8:=T6+T7

(11) T9:=addr(A)-22

(12) T10:=T9[T8]

(13) T4[T3]:=T10+J

(14) I:=I+1

(15) goto (2)

(16) ret

1.分划基本块.

2.对代码施行各种可能的优化,并写出优化过程中采用了何种优化策略