东南大学历年编译原理试卷2
- 格式：doc
- 大小：35.00 KB
- 文档页数：6
东南大学历年编译原理试卷2 [%repeat_0
match="/data/option"%] [%=@title%]
[%=@count%]票
[[%=@percent%]％][%_repeat_0%]
试题编号:553
试题名称:编译原理
一:由文法G1构造LR(1)部分分析表:
1.列出4个项目集I0,I1,I2,I3;(如下图)
2.填写LR(1)分析表的状态0,1,2的action和goto表的内容.(如下图) G1: (0) S→T
(1) T→T(T)
(2) T→ε
┌──────┐┌──┐┌──┐┌──┐
│I0:S→．T,# │ T │I1: │ ( │I2: │ T │I3: │
││ -→││-→ ││-→ ││
└──────┘└──┘└──┘└──┘
┌──┬────────┬───┐
││action │ goto │
│状态├──┬──┬──┼───┤
││ (│ ) │ #│T │
├──┼──┼──┼──┼───┤
│ 0│││││
├──┼──┼──┼──┼───┤
│ 1│││││
├──┼──┼──┼──┼───┤
│ 2│││││
├──┼──┴──┴──┼───┤
││││
│... │ ... │ ...│
││││
└──┴────────┴───┘
二:已知文法G2,请用类pascal语言写出它的递归下降分析程序.
G2: A→[B
B→X]|BA
X→Xa|Xb|a|b
三:已知文法G3,要求:
1.写出各非终极符的首终极符集合和尾终极符集合;
2.填写opt表:
│+ │* │@ │ ↑ │i │# │
──┼──┼──┼──┼──┼──┼──┤
+ │││││││
──┼──┼──┼──┼──┼──┼──┤
* │││││││
──┼──┼──┼──┼──┼──┼──┤
@ │││││││
──┼──┼──┼──┼──┼──┼──┤
↑ │││││││
──┼──┼──┼──┼──┼──┼──┤
i │││││││
──┼──┼──┼──┼──┼──┼──┤
# │││││││
──┼──┼──┼──┼──┼──┼──┤
│││││││
G3: E→E+T|T|@T
T→T*F|F
F→p↑F|P
p→i
四:请写出产生下列语言的文法.
1. L1={a^ib^j|i>j>=1}
2. L2={ω1|ω1↔{0,1}*&ω1中包含0,1个数相等的任意串}
3. L3={ω2|ω2↔{a,b}*&ω2中a之后必定跟b}
4. L4={ω3+ω3|ω3↔{0,1}*}
五:简要回答问题.
1.对编译程序而言,模块,遍,子程序这三个概念的主要区别?
2.静态存储分配与动态存储分配的主要区别?
3.何谓自适应线性表?
六:翻译如下布尔表达式成四元式序列,结果留待填的真假链的四元式序号.
试题编号:553
试题名称:编译原理
一:按算法构造文法G1:
S→#M#
M→(L|a
L→M,a)
的算符优先矩阵.(即填写下列矩阵)
│ a │, │( │ ) │# │
──┼──┼──┼──┼──┼──┼
a ││││││
──┼──┼──┼──┼──┼──┼
, ││││││
──┼──┼──┼──┼──┼──┼
( ││││││
──┼──┼──┼──┼──┼──┼
) ││││││
──┼──┼──┼──┼──┼──┼
# ││││││
──┼──┼──┼──┼──┼──┼
二:将下列cfg文法修改成正规文法.
S→AB
A→M|N|P
B→aB|a
M→bM|b
N→cN|c
P→αP|ε
三:已知文法G2:
(1) S'→S
(2) S→AAA
(3) S→1A
(4) S→0
1.列出LR(0)项目集族;
2.构造SLR分析表;
3.试给处语句01100#的LR分析过程.
四:
1.构造由下列三型文法G3所对应的FA.
2.将构造的FA确定化和最小化.
3.写出该DFA所识别的语言.
G3: S→aA|bS|dC
A→dE
C→aD|bC|b
D→bE|b
E→aD|bE|b
五:设有源语句A[I+1,J+2]:=A[B[K+2],5]
1.列出计算两个数组的下标地址(按行存放)
A[I+1,J+2]的地址D1=?
B[K+2]的地址D2=?
2.按语法制导翻译该语句成四元式序列.(设数组首地址分别为a,b;数组按行存放,每个元
素占一字编址.数组说明:A:array[1..10,-5..5],B:array[-5..5])
六:求文法G4:
A→BCc|gDB
B→bcDE|ε
C→Dab|ca
D→dD|ε
E→gAf|c
的各非终结符的随符集.
七:
1.简述由基本块寻找循环结点的算法.
2.对于如下一段程序,若参数传递分别采用:
(a)传名 (b)传结果 (c)传地址
试问程序执行结果,Y值是什么?
proc Q(B,C)
begin
B:=B+2;
B:=B*C
end;
begin
Y:=2;
Q(Y,2*Y);
print(Y)
end;
3.文法G5:
E→P↑E|P
P→P*Q|Q
Q→Q+R|R
R→(E)|a
a→整常数
试给出下列表达式计值结果(语法制导).
3+2*5↑2*2+3
2+(2↑2↑3)*2+3
试题编号:553
试题名称:编译原理
一:
1.试写一正规文法,使其定义的语言是不以0打头的偶整数集合.其中数字可以用简名表示
,比如α1→0|2|4|6|8,并把α1看作是终结符.
2.试写一上下文无关文法,它能产生下列语言:
L={ω|ω↔{a,b}*,且ω中a的个数是b的两倍,例如aab等}
二:请写出由下列文法所确定的语言.
1. G1: S→10S01
S→aA
A→bA
A→a
2. G2: S→aSS
S→a
三:已知NFA的状态转换图如下,试对它确定化并化简,并写出该FA接受的语言.
∩b a
→S──────→A
d││c
↓ a b ↓
b＜C──→D──→E＞b
│b│←──│
b│↓ a │b
└─→T ←──┘
四:已知文法G4:
S'→S
S→AS
S→b
A→SA
A→a
1.试求closure({(S'→．S,#)})和GO(closure({(S'→．S,#)}),S)
2.文法是LR(1)吗?为什么?
五:试将下面语句按语法制导翻译成四元式序列.
while (a<c) and (b<d) do
if a=1 then c:=c+1
else while a<=d do a:=a+2;
六:
1.试对如下四元式序列划分成基本块,并化出程序流图;
2.写出源语句.
(1) I:=1
(2) if I>M goto (19)
(3) J:=1
(4) if J>N goto (17)
(5) T1:=I*N
(6) T2:=T1+J
(7) T3:=addr(A)-C
(8) T4:=I*2
(9) T5:=J+2
(10) T6:=T4*N
(11) T7:=T6+T5
(12) T8:=addr(A)-C
(13) T9:=T8[T7]
(14) T3[T2]:=T9
(15) J:=J+1
(16) goto (4)
(17) I:=I+1
(18) goto (2)
(19) ...
七:
1.求文法G7的各非终结符的终结首符集First和随符集Follow.
2.判定该文法是LL(1)吗?
G7: A→BCc|gDB
B→bCDE|ε
C→DaB|ca
D→dD|ε
E→gAf|c。
