2020/4/6
2
CH.3.练习题7(P64.)
7. (1) 1(0|1)*101 构造DFA。 解1: 正规式对应的NFA:
1
X 1 1ε 3 ε 2 1 4 0 5 1 Y
0
2020/4/6
3
(1) 正规式 1(0|1)*101 DFA:
0
3,2
0
1
x
1,3,2
1
1
3,4,2
1
0
0 1
3,5,2
0
01
0
1
0
1
2
2020/4/6
10
CH.3.练习题14(P64.)
(1) 正规式: (10|0)*
(2) NFA:
0
X ε 1εY
1
0
2
DFA: 0
0
1 1
2020/4/6
0
1
0
2
构造一个DFA，它接受 S＝ {0,1}上所有满足如下条件 的字符串：每个1都有0直 接跟在右边。
DFA:(最简)
(2) 1(1010*|1 (010)*1)*0
1
4
05
0*
1
6
X 1 1ε 2 ε 3 0 Y
1
7 (010)* 8
1
4 0 5 1 6ε
0
9
1
ε
X 1 1ε 2 ε 3 0 Y
1
7
ε
10 ε
010
1
8
2020/4/6
8
4 0 5 1 6ε 9 0
1
ε
X 1 1ε 2 ε 3 0 Y
1
7
ε
10 ε
证明: 因为存在句子 iiiei， 它对应两棵不同的语法树,如 右图: 所以该文法是二义文法。
说明：按定义只要能给出一 个反例即可，iiiei不是唯一 的反例。
2020/4/6
S iS
i S eS ii
S
i S eS i Si
i
16
程序设计语言
Chapter 5.自下而上 语法分析
CH.5.练习题1(P133.)
证明2: ∵可构造出E+T*F的语法树，如右
图所示， ∴E+T*F是G1的一个句型。
语法树
证明3: (也可用归约来证明) E
（概念熟悉后，短语、直接短语和句柄可直接列出
1.令文法G1为：E→E+T|T T→T*F|F F→(E)|i
证明E+T*F是它的一个句型,指出这个句型的所有短 语、直接短语和句柄。
证明1: ∵存在从开始符号E出发到E+T*F
的推导： E E+T E+T*F
语法树
∴E+T*F是G1的一个句型。
E
短语: E+T*F是句型相对于非终结符E的短
2020/4/6
1
6
7. 构造下列正规式相应的NFA。(P64.)
(2) 1(1010*|1 (010)*1)*0
1010*
X 1 1ε 2 ε 3 0 Y
1 (010)*1
4 051 6
1
0*
X 1 1ε 2 ε 3 0 Y
1
7 (010)* 8 1
2020/4/6
7
7. 构造下列正规式相应的NFA。(P64.)
最右推导
E T T*F T*(E) T*(E+T) T*(E+F) T*(E+i) T*(T+i) T*(F+i) T*(i+i) F*(i+i) i*(i+i)
14
CH.2.练习题8(P36.)
8. 令文法为
(2) 给出 i+i+i、i+i*i和i-i-i的语法树。
E → T|E+T|E-T
1
0
3,Y,4,2
(1) 正规式 1(0|1)*101 DFA:
0
2 04
0
0 11
10 1 0
13 15
1
CH.3.练习题7(P64.)
7. 构造下列正规式相应的DFA。 (1) 1(0|1)*101 解2: 正规式对应的NFA:
01
1
1 12
0
031 4
0
0 11
DFA: 03
1
0 10
2 14
8. 令文法为
(1) 给出 i+i*i、i*(i+i)的最左推导
E → T|E+T|E-T 和最右推导。
T → F|T*F|T/F
F → (E)|i
解：此处仅以 i*(iF*F i*F i*(E) i*(E+T) i*(T+T) i*(F+T) i*(i+T) i*(i+F ) i*(i+i)
(2) 给出句子0127、34和568的最左和最右推导。 注意：1)步骤，和 + 的区别；2) 不能写为→ 解：0127的最左推导：NNDNDDNDDDDDDD 0DDD01DD012D0127 0127的最右推导：NNDN7ND7N27ND27 N127D1270127
13
CH.2.练习题8(P36.)
语; T*F是句型相对于非终结符T的短语。 E + T
直接短语: T*F是句型相对于规则T→T*F的 直接短语
T*F
句柄: T*F
2020/4/6
18
CH.5.练习题1(P133.)
1.令文法G1为：E→E+T|T T→T*F|F F→(E)|i
证明E+T*F是它的一个句型,指出这个句型的所有短 语、直接短语和句柄。
010
1
8
7. (2) 1(1010*|1 (010)*1)*0的NFA。
4 0 5 1 6ε 9 0
1
ε
X 1 1ε 2 ε 3 0 Y
1
7 ε 10
ε 0
1
8
0 12 1 11
CH.3.练习题14(P64.)
(1) 正规式: (10|0)*
(2) NFA:
0
X ε 1εY
1
0
2
确定化:
DFA:
程序设计语言
Chapter 3.词法分析
CH.3.练习题8(P64.)
8. 给出下面的正规表达式。
(1) 以01结尾的二进制数串; 正规式 (0|1)*01
(2) 能被5整除的十进制整数; 允许任意0开头： (0|1|2|3|4|5|6|7|8|9)*(0|5) 不允许0开头（0本身除外）：
(0|5)|(1|2|3|…|9)(0|1|2|3|…|9)*(0|5)
0 1
0 0
1
11
程序设计语言
Chapter 2.高级语言及 其语法描述
CH.2.练习题6(P36.)
6.令文法G6为: N → D|ND D → 0|1|2|3|4|5|6|7|8|9
(1) G6的语言L(G6)是什么? 注意：集合的写法不正确 解：L(G6)={0,1,2,3,4,5,6,7,8,9}+ ={09数字构成的所有数字串，可以0开头}
T → F|T*F|T/F F → (E)|i
注意：树枝和符号均不可随意增减！
i-i-i 的语法树 E
E -T
E-T F
T
Fi
F
i
i
i+i+i 的语法树 E
E+T
E +T F
T
Fi
F
i
i
i+i*i 的语法树
E E +T T T* F FF i ii
15
CH.2.练习题9(P36.)
9. 证明下面的文法是二义的： S → iSeS|iS|i