编译原理课后习题(修订版?/p>
第二?/p>
高级语言及其语法描述
3
、何谓“标识符?/p>
,何谓“名字?/p>
,两者的区别是什么?
解:标识符是高级语言中定义的字符串,一般是以英文字母(包括大小写字
母)或下划线开头的,由数字、字母和下划线组成的一定长度的字符串,它只?/p>
一个标志,
没有其他含义?/p>
名字是用标识符表示的?/p>
但名字不仅仅是一个字符串?/p>
它还具有属性和值?/p>
4
?/p>
?/p>
+?/p>
*
和↑代表加?/p>
乘和乘幂?/p>
按如下的非标准优先级和结合性质的约定,
计算
1
?/p>
1*2
?/p>
*1
?/p>
2
的值:
?/p>
1
?/p>
、优先顺序(从高至低)为+?/p>
*
和↑,同级优先采用左结合?/p>
?/p>
2
?/p>
、优先顺序为↑、+?/p>
*
,同级优先采用右结合?/p>
解:
?/p>
1
?/p>
?/p>
1
?/p>
1*2
?/p>
*1
?/p>
2 = 2*2
?/p>
*1
?/p>
2 = 4
?/p>
*1
?/p>
2 = 4
↑↑
2 =
?/p>
2
?/p>
?/p>
1
?/p>
1*2
?/p>
*1
?/p>
2 =
6
、令文法
G
6
?/p>
N
?/p>
D
?/p>
ND
?/p>
D
?/p>
0
?/p>
1
?/p>
2
?/p>
3
?/p>
4
?/p>
5
?/p>
6
?/p>
7
?/p>
8
?/p>
9
?/p>
1
?/p>
?/p>
G
6
的语言
L(G
6
)
是什么?
?/p>
2
?/p>
、给出句?/p>
0127
?/p>
34
?/p>
568
的最左推导和最右推导?/p>
分析:根据产生式
N
?/p>
D
?/p>
ND
可以看出?/p>
N
最终可推导?/p>
1
个或多个(可
以是无穷多个?/p>
D
,根据产生式
D
?/p>
0
?/p>
1
?/p>
2
?/p>
3
?/p>
4
?/p>
5
?/p>
6
?/p>
7
?/p>
8
?/p>
9
可以看出?/p>
每个
D
可以推导?/p>
0
?/p>
9
中的某一个数字。因此,
N
最终推导出的是?/p>
0
?/p>
9
?/p>
10
个数字组成的字符串?/p>
解:
?/p>
1
?/p>
?/p>
L(G
6
)
是由
0
?/p>
9
?/p>
10
个数字组成的
字符?/p>
?/p>
?/p>
2
?/p>
、句?/p>
0127
?/p>
34
?/p>
568
的最左推导:
N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127
N=>ND=>DD=>3D=>34
N=>ND=>NDD=>DDD=>5DD=>56D=>568
句子
0127
?/p>
34
?/p>
568
的最右推导:
N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127
N=>ND=>N4=>D4=>34
N=>ND=>N8=>ND8=>N68=>D68=>568
7
、写一个文法,使其语言是奇数集,且每个奇数不以
0
开头?/p>
分析:本题要构造一个文法,由它产生的句子是奇数,且不以
0
开头。也?/p>
是说它的每个句子都以
1
?/p>
3
?/p>
5
?/p>
7
?/p>
9
中某数结尾。如果数字只有一位,则满?/p>
要求;如果有多位,则要求第一位不能是
0
;而中间有多少位,每位是什么数?/p>
则没有要求?/p>
因此我们可以把这个文法分
3
部分完成?/p>
分别?/p>
3
个非终结符来?/p>
生句子的第一位、中间部分和最后一位。引入几个非终结符,其中,一个用作产