试题编号 :553
试题名称 :编译原理
一 :文法G1:
E→ET+|T
T→TF*|F
F→FP↑|P
P→E|i
1.试证明符号串TET+*i↑是G1的一个句型(要求画出语法树).
2.写出该句型的所有短语,简单短句和句柄.
二 :
1.给出下图FA的正规式.
a b
──→ ──→ ②
→○ ① a↑↓ε
←── ←── ③
ε b
2.已知正规文法G2:
S→aS|A
A→bB
B→aB|ε
试构造一确定有限自动机 DFA(要求化简),使得它接受的语言正是该文法产生的语言,要求画出状态图.
三 :
1.试写出一个上下文无关文法G3,它能产生配对的圆括号串(例如,(),(()),()(())等,甚至包含0对括号).
2.使用文法G3给出输入串(())()#的自上而下分析过程.
四 :已知文法G4:
S→aAb|Sc|ε
A→aAb|ε
1.给出G4文法的LR(0)项目集规范族;
2.构造SLR分析表;
3.G4文法所定义的语言;
4.已知有如下文法及相应的LR分析表,试给出语句01001#的LR分析过程(填写下表).
S→AAA
A→1A
A→0
LR分析表:
───┬──┬──┬──┰──┬──
状态 │ 1 │ 0 │ # ┃ S │ A
───┼──┼──┼──╂──┼──
0 │ S3 │ S4 │ ┃ 1 │ 2
───┼──┼──┼──╂──┼──
1 │ │ │acc ┃ │
───┼──┼──┼──╂──┼──
2 │ S3 │ S4 │ ┃ │ 5
───┼──┼──┼──╂──┼──
3 │ S3 │ S4 │ ┃ │ 6
───┼──┼──┼──╂──┼──
4 │ r3 │ r3 │ r3 ┃ │
───┼──┼──┼──╂──┼──
5 │ S3 │ S4 │ ┃ │ 7
───┼──┼──┼──╂──┼──
6 │ r2 │ r2 │ r2 ┃ │
───┼──┼──┼──╂──┼──
7 │ │ │ r1 ┃ │
───┴──┴──┴──┸──┴──
分析过程 :
──────┬──────┬──────
状态栈 │ 符号栈 │ 输入串
──────┼──────┼──────
│ │
│ │
│ │
│ │
│ │
│ │
│ │
──────┴──────┴──────
五 :
1.翻译下面语句成四元式中间代码序列和后缀式(逆波兰式);
while x+y>a do
if a<10 then a:=a+1 else x:=x-1;
2.翻译布尔表达式
(a>b) or (c=d) and not (e<f)
成转移四元式序列 (即四元式中仅包含(zθ,-,-,-)和(j,-,-,-)两类语句,其中θ为关系运算符.)
六 :
1.有如下Fortran说明语句,试借助符号表登记等价环链EQ和相对数OFFSET,即填写下表的EQ栏和OFFSET栏.设每个整型量占1子编址.
integer a,b,c(10,10),d(10)
equivalence (a,d(8),c(5,5))
equivalence (b,c(5,8))
符号表
┌───┬──────┬───┬───┐
│ name │ ... │ EQ │OFFSET│
├───┼──────┼───┼───┤
1│ a │ ... │ │ │
├───┼──────┼───┼───┤
2│ b │ ... │ │ │
├───┼──────┼───┼───┤
3│ c │ ... │ │ │
├───┼──────┼───┼───┤
4│ d │ ... │ │ │
└───┴──────┴───┴───┘
2.有如下pascal语言的程序轮廓,当运行该程序且第一次递归调用Q过程(即在过程Q中又调用了Q)时,数据区建立情况.假定各数据区首址用SP(i)(i=0,1,……)表示,试给出P,Q数据区的display表.
┌ main
│┌ P
││┌ Q
│││ Call Q
││└
││ Call Q
│└
│┌ R
││ Call P
│└
│┌ S
││ Call R
│└
│ Call S
└
七 :已知如下流图,试给出回边与循环.
↓
┌─→①←┐
│ / / /
│ ↓ ↓ /
/ ② ③
/ / /↑
/↓↓/
┌→④──┐
│ │ ↓
│ │┌→⑤
│ ↓ / │
└─⑥←─┘
