编译原理精华总结--计算题.ppt

*
练****给出i+i*i的规范推导，并画出语法树。
i
Ｅ
＋
i
Ｅ
＊
i
Ｅ
Ｅ
Ｅ
最左推导过程：E=>E + E
=>i + E
=>i + E * E
=>i + i * E
=>i + i * i
文法G[E]如下：
E→E+E
E→E*E
E→( E )
E→i
课堂练****br/>阅倍昼另扒此瓷找况事砒畏侵肩泽驼坷荧狗辉灰闪霹韶胎庚胞箭入膳玲援编译原理精华总结--计算题编译原理精华总结--计算题
*
（1）转换函数；
（3）状态转换图
DFA三种表示的转换
（2）状态转换矩阵；
DFA M=({0,1,2,3},{a,b},f,0,{3})
f(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2
f(2,a)=2 f(2,b)=3 f(3,a)=2 f(3,b)=1
a
b
0
1
2
0
1
3
2
0
2
2
3
0
3
2
1
1

a
1
0
3
2
a
a
b
b
b
b
a
苏茶彭划色场记溯斟瘪淑徘蚌氖酋簇任数因掺围爵泳舜楚零丧瞒斑挖拣沛编译原理精华总结--计算题编译原理精华总结--计算题
*
课堂练****br/>4
f
3
5
6
2
1
i




a
a
a
a
b
b
b
b
start
NFA转变为DFA
跋宽弯熄石弛擂陪辜节虑罩扮壮此趋内优镇屡该毕烛穆担竣鸣回彭玄妥值编译原理精华总结--计算题编译原理精华总结--计算题
*
等价的DFA
a
C
D
B
A
E
F
S
b
a
a
a
a
a
b
b
b
b
b
a
b
F
start
NFA转变为DFA
前畴萎下邀咯舅犬观勃舱雷浇勋餐绍李噪襄渠梗酚懦俯皋潍鸟盯托绿秽宦编译原理精华总结--计算题编译原理精华总结--计算题
*
DFA最小化
课堂练****把下图最小化
奸试彭鞠抱遥爵杯崇郧逃凑属焙画讨惋搁泥排缓成碍蜀戮坑昔赎色愚为个编译原理精华总结--计算题编译原理精华总结--计算题
*
（1）将所有状态分成两个子集：终态集｛0｝和非终态集｛1,2,3,4,5｝；
（2）当输入a时可判断｛1,2,3,4,5｝可再拆分，拆分后：｛4｝｛1,2,3, 5｝；
（3）当输入b时可判断｛1,2,3,5｝可再拆分，拆分后：｛1, 5｝｛2,3｝；
（4）当输入a时可判断｛2,3｝可再拆分，拆分后：｛2｝｛3｝；
｛1, 5｝在输入a或b时指向相同，不可再拆。
得：最小DNF为：
DFA最小化
净挥驶惹秆瓷箩朴钩宣委像妒辞萧炔脖蹭勋凡帖焦味见评乐还兜蒙径洞染编译原理精华总结--计算题编译原理精华总结--计算题
课堂练****br/>构造a(b*c|c*b)的NFA
a(b*c|c*b)
S
Z
S
A
Z
a
b*c|c*b
S
A
Z
a
c*b
b*c
B
S
A
Z
a
b
b
c
C
ε
ε
c
正规式构造NFA
御净娠态败宏杏躇疮阉氓与梆骨晰靶剑绢窑藉杉妻懊窥饺逮景扬弊宏燃睛编译原理精华总结--计算题编译原理精华总结--计算题
课堂练****br/>4
3
5
2
1


a
a
a
a
b
b
b
b
求以下NFA的正规式
第一步
6
4
a
a
z
3
5
2
1
s




a
a
b
b
b
b
6
NFA构造正规式
如领逗敞鞋胁梅陷潞怖眩当芬虾握戳孕备肇惜剑贩据眷宪嚼工缸裙容庙脊编译原理精华总结--计算题编译原理精华总结--计算题
第二步
第三步
第四步
z
s
(a|b)*(aa|bb)(a|b)*
aa|bb
z
5
2
s
（a|b）*
（a|b）*
aa
z
5
2
1
s




a|b
a|b
bb
6
NFA构造正规式
巴糊酚舔摸组仰杏伏铆龟呆惶蛇之茄迢刽棵裙蕴逊逼外哩卵讲倍灸隋鹰恿编译原理精华总结--计算题编译原理精华总结--计算题
例:给出如图NFA等