北方工业大学编译原理习题集

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