试题编号 :553
试题名称 :编译原理
一 :已知文法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<d do
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 │
└─────┘
