第二章
1
3.何谓“标志符”,何谓“名字”,两者的区别是什么?
2
答:标志符是一个没有意义的字符序列,而名字却有明确的意义和属性。3
4.令+、*和↑代表加、乘和乘幂,按如下的非标准优先级和结合性质的约4
定,计算1+1*2↑2*1↑2的值。
5
(1)优先顺序(从高到低)为+、*和↑,同级优先采用左结合。
6
(2)优先顺序为↑、+、*,同级优先采用右结合。
7
答:(1)1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256
8
(2)1+1*2↑2*1↑2=1+1*2↑2*1=1+1*4*1=2*4*1=2*4=8
9
6.令文法G
6为
10
N-〉D|ND
11
D-〉0|1|2|3|4|5|6|7|8|9 12
(1)G
6的语言L(G
6
)是什么?
13
(2)给出句子0127、34、568的最左推导和最右推导。
14
答:(1)由0到9的数字所组成的长度至少为1的字符串。即:L(G
6)={d n|n
15
≧1,d∈{0,1,…,9}}
16
(2)0127的最左推导:17
N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127
18
0127的最右推导:N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 19
20
(其他略)
21
7.写一个文法,使其语言是奇数集,且每个奇数不以0开头。
22
答:G(S):S->+N|-N
23
N->ABC|C
24
C->1|3|5|7|9
25
A->C|2|4|6|8
26
B->BB|0|A|ε
27
[注]:可以有其他答案。
28
[常见的错误]:N->2N+1
29
原因在于没有理解形式语言的表示法,而使用了数学表达式。
8.令文法为
30
31
E->T|E+T|E-T
32
T->F|T*F|T/F
F->(E)|i
33
34
(1)给出i+i*i、i*(i+i)的最左推导和最右推导。
35
(2)给出i+i+i、i+i*i和i-i-i的语法树,并给出短语,简单短语和句柄。
36
答:(1) i*(i+i)的最左推导:
37
E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=> 38
i*(i+F)=> i*(i+i)
i*(i+i)的最右推导: 39
E=>T=>T*F=>T*(E) 40
=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=> T*(i+i)=> F*(i+i) 41
=> i*(i+i) 42
(其他略) 43
[注]:要牢记每一步都是对最左(右)的一个非终结符号进行一步推导。 44
(2) i+i+i 的语法树:
45 46
(其他略) 47
9.证明下面的文法是二义的:S->iSeS|iS|i 48
证明:反例法: 49
对于该文法的句子iiiei 有两个最右推导如下,所以该文法是二义的: 50
S=>iS=>iiSeS=>iiSei=>iiiei 51
S=>iSeS=>iSei=>iiSei=>iiiei 52
10.把下面的文法改写成无二义的:S->SS|(S)|()
53 短语:i 1, i 2, i 3, i 1
+ i 2, i 1+i 2+ i 3
答:假设规定左结合的顺序,可以改造成无二义文法如下:54
s->s(t)|(s)|()
55
t->s|ε
56
[注]:大纲不要求掌握,作为参考
57
11.给出下面语言的相应文法:
58
L
1={a n b n c i|n≧1,i≧0}
59
L
2={a i b n c n|n≧1,i≧0}
60
L
3={a n b n a m b m|m,n≧0}
61
L
4={1n0m1m 0n|m,n≧0}
62
答:(1) S->AB A->aAb|ab B->Bc|ε63
(2) S->AB B->bBc|bc A->Aa|ε
64
(3) S->AA A-> aAb|ε
65
(4) S->1S0|A A-> 0A1|ε
66
[注]:可以有其他答案。
67
68