一:已知文法G1:

S→aB|ε

B→bC|bD

C→cB|c

D→d

1.试构造一个最小DFA,画出状态转换图.

2.由该DFA给出它所识别的语言(用正规式表示).

二:已知正规式α=ab*c*d,

1.试构造一个DFAM,其接受的语言为此α(画出图);

2.由该DFAM写出对应的正规文法(古线性).

三:文法G3:

S→A[B]

A→[B]|Aa

B→a

1.求出各非终结符N的Firstvt(N)和Lastvt(N),构造包括语句括号'#'在内的算符优先表;

2.给出语句#[a][a]#的算符优先分析过程,即填写如下格式的表:

　步骤　│栈内│输入串│动作

────┼────┼────┼─────

0　│#│[a][a]#│

...　│　　　　│　　　　│

四:已知文法G4:

T→T*F|F

F→(T)|i

1.试给出语句(i*i)#的自上而下分析过程(填下表);

2.画出对应的语法树,指出每一步归纳的句柄.

　步骤　│栈内│输入│动作

────┼────┼────┼─────

0　│#T│(i*i)#│

...　│　　　　│　　　　│

五:已知文法G5:

0. E'→E

1. E→E+T

2. E→T

3. T→i

列出LR(0)项目集规范族,求出各非终结符N的Follow集合,构造SLR分析表.

六:翻译如下语句成四元式序列(由语法制导生成).

while a>b and a

if a=5 then b:=b+1 else

repeat

a:=a+1

until a>=d;

七:按语法制导翻译下段程序成四元式序列(不要优化),设数组A: array[1..10,1..10] of

int;每个下标变量占1字编址,数组按行存放,Z为函数名.

begin

A[i,j]:=A[i,j]+2;

B:=Z(A[i,j])*5

end

八:将如下一段四元式序列进行块内优化和循环优化(强度减弱及删除基本归纳变量),写出优化后的四元式序列.(要求先划分基本块)

(1) i:=1

(2) if i>100 goto (10)

(3) T1:=20*i

(4) M:=J+T1

(5) T2:=20*i

(6) N:=K+T2

(7) O:=M+N

(8) i:=i+1

(9) goto (2)

(10) ...

九:已知如下一段程序,试给出运行时整个数据区结构.假定num初值为2,每个数据区的活动记录包含内容如下图所示,数据区从k单元开始编址.

┌─────┐program factoral;

│函数返回值│var num,fact:int;

├─────┤function f(n:int):int

│变量单元│if n>0 then f:=n*f(n-1)

├─────┤else f:=1;

│display表│begin

├─────┤read(num);

│形参单元│fact:=f(num)

├─────┤end

│返回地址│

├─────┤

│　基SP　│

└─────┘