(单词翻译:单击)
一:文法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
成转移四元式序列(即四元式中仅包含(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
└
七:已知如下流图,试给出回边与循环.
↓
┌─→①←┐
│ / / /
│↓ ↓/
/② ③
/ / /↑
/↓↓/
┌→④──┐
││ ↓
││┌→⑤
│↓/ │
└─⑥←─┘
