《编译原理和技术》部分课后试题解答

虑文法 GS,其产生式如下 : S(L)|a LL ， S|S (1) 试指出此文法的终结符号、非终结符号。 终结符号为： (,),a, 非终结符号为： S,L 开始符号为： S (2)给出下列各句子的分析树： (a,a) (a,(a,a) (a,(a,a),(a,a) (3)构造下列各句子的一个最左推导： (a,a) S (L) (L,S) (S,S) (a,S) (a,a) (a,(a,a) S (L) (L,S) (S,S) (a,S) (a,(L) (a,(L,S) (a,(S,S) (a,(a,S) (a,(a,a) (a,(a,a),(a,a) S (L) (L,S) (S,S) (a,S) (a,(L) (a,(L,S) (a,(S,S) (a,(L),S) (a,(L,S),S) (a,(S,S),S) (a,(a,S),S) (a,(a,a),S) (a,(a,a),(L) (a,(a,a),(L,S) (a,(a,a),(S,S) (a,(a,a),(a,S) (a,(a,a),(a,a) (4)构造下列各句子的一个最右推导： (a,a) S (L) (L,S) (L,a) (S,a) (a,a) (a,(a ， a) S (L) (L,S) (L,(L) (L,(L,S) (L,(L,a) (L,(S,a) (L,(a,a) (S,(a,a) (a,(a,a) (a ， (a， a)， (a， a) S (L) (L,S) (L,(L) (L,(L,S) (L,(L,(L) (L,(L,(L,S) (L,(L,(L,a) (L,(L,(S,a) (L,(L,(a,a) (L,(S,(a,a) (L,(L),(a,a) (L,(L,S),(a,a) (L,(L,a),(a,a) (L,(S,a),(a,a) (L,(a,a),(a,a) (S,(a,a),(a,a) (a,(a,a),(a,a) (5)这个文法生成的语言是什么？ L(GS) = ( 1, 2,., n)或 a 其中 i(1in) ，即 L(GS)是一个以 a 为原子的纯表，但不包括空表。 虑文法 GS S (1)试说明此文法是二义性的。可以从对于句子 S 以此文法是二义性的。 (2)对于句子 S 3)对于句子 (一 ) (二 ) (4)此文法所产生的语言是什么？ 此文法产生的语言是：所有 b 的个数相等的由 a 和 知文法 GS的产生式如下： S (L)|a L L,S|S 属于 L(GS)的句子是 A ， (a,a)是 L(GS)的句子，这个句子的最左推导是 B ，最右推导是 C ，分析树是 D ，句柄是 E 。 A： a a,a (L) (L,a) B,C： S (L) (L,S) (L,a) (S,a) (a,a) S (L) (L,S) (S,S) (S,a) (a,a) S (L) (L,S) (S,S) (a,S) (a,a) D： E： (a,a) a,a (a) a 解答： A： B： C： D： E： 有限状态自动机可用五元组（ Q， ， 描述 ,设有一有限状态自动机 M 的定义如下： 0,1， Q=q0,q1, 的定义为： （ 0） = （ ） = （ 1） = （ ） = 是一个 A 有限状态自动机，它所对应的状态转换图为 B ,它所能接受的语言可以用正则表达式表示为 C 。其含义为 D 。 A: 歧义的 非歧义的 确定的 非确定的 B: C： (0|1) * 00(0|1) * (0|1) *00 0(0|1) *0 D： 由 0 和 1 所组成的符号串的集合； 以 0 为头符号和尾符号、由 0 和 1 所组成的符号串的集合； 以两个 0结束的，由 0 和 1所组成的符号串的集合； 以两个 0开始的，由 0 和 1所组成的符号串的集合。 答案 A: B: C: D: (1)有穷自动机接受的语言是正则语言。（） (2)若 上的正规式，则 r1|） (3)设 M 是一个 且 L(M) x,y,z，则 M 的状态数至少为 4个。 (4)令 a,b，则 上所有以 b 为首的字构成的正规集的正规式为 b*(a|b)*。 (5)对任何一个 ，都存在一个 ，使得 L(M)=L(M)。（） (6)对一个右线性文法 G，必存在一个左线性文法 G，使得L(G)=L(G)，反之亦然。（） 答案 (1) T (2) T (3) F (4) F (5)T 述下列各正规表达式所表示的语言。 (1) 0(0|1)*0 (2) (|0)1 *)* (3) (0|1)*0(0|1)(0|1) (4) 0*10*10*10* (5) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)* 答案 (1) 以 0 开头并且以 0 结尾的，由 0 和 1 组成的所有符号串(2) | 0,1*即由 0 和 1 组成的所有符号串。 (3) 由 0 和 1 组成的符号串，且从右边开始数第 3 位为 0。 (4) 含 3 个 1 的由 0 和 1 组成的所有符号串。 | 0,1+，且 中含有 3 个 1 (5) | 0,1*, 中含 0 和 1 的数目为偶数。 知文法 GS，其产生式如下： S(L)|a LL,S|S 文法 GS的算符优先关系由下表给出。建立与下表相应的算符优先函数并用算符优先分析法分析句子 (a,(a,a)。 文法 GS的算符优先关系表： 解： 对每个终结符或建立符号 f 与 g，把 f(和 g)分成一组。 根据 GS的算符优先关系表，画出如下的有向图 : 优先函数如下： 用算符优先分析法分析句子 (a,(a,a) 1) 存在有左递归规则的文法是 )的。 (2) 任何算符优先文法的句型中不会有两个相邻的非终结符号。 (3) 算符优先文法中任何两个相邻的终结符号之间至少满足三种 关系( ， ， )之一。 (4) 任何 )文法都是无二义性的。 (5) 每一个 )文法也都是 )文法。 (6) 存在一种算法 ，能判定任何上下文无关文法是否是 )的。 (7) 任何一个 )文法都是一个 )文法，反之亦然。 (8) )括号中的 1 是指，在选用产生式 A 进行分析，看当前读入符号是否在 ) 中。 答案： (1) (2) (3) (4) (5) (6) (7) (8) 编译程序中，语法分析分为自顶向下分析和自底向上分析两类。 _L(1)分析法属于自顶向下分析； _R 分析法属 于自底向上分析。自顶向下分 析试图为输入符号串构造一个 _底向上分析试图为输入符号串构造一个 _用自顶向下分析方法时，要求文法中不含有 _ A、 B： 深度分析法 宽度优先分析法 算符优先分析法 预测递归分析法 C、 D： 语法树 有向无环图 最左推导 最右推导 E： 右递归 左递归 直接右递归 直接左递归 A： B： C： D： E： 底向上语法分析采用 _用的是自 底向上语法分析有算符优先分析法和 析法。 _算符优先分析是寻找右句型的 _析法中分析能力最强的是 _析能力最弱的是 _ A： 递归 回溯 枚举 移进规约 B、 C： 短语 素短语 最左素短语 句柄 D、 E： ) ) ) ) A： B： C： D： E： 产生的二进制数的值（例如，对于输入 S L B0|1 （ 1）试用各有关综合属性决定 （ 2）试用一个语法制导定义来决定 这个定义中仅有 B 的综合属性，设为 c，它给出由 B 生成的位对于最后的数值的贡献。例如，在 的第一位和最后一位对于值 贡献分别为 解答： (1)用综合属性决定 语法制导定 义： 产生式 语义规则 S - L S - L - B 2 L - + B - 0 0; B - 1 1; 注： (2)分析：设 B 的综合属性，是 求出 须求出 B 产生位的权，设 另外，设 继承因子， 综合因子，语法制导定义如下： 产生式 语义规则 S - L 1; 2; 1; S - ; ; 1; ; 2 L - B L - B - 0 0; B - 1 种称为 ( A ),另一种称为( B )。 ( A )值的计算依赖于分析树中它的 ( C )的属性值； ( B )的值的计算依赖于 分析树中它的 ( D )的属性值。 A,B: 综合属性 继承属性 C,D: 父结点 子结点 兄弟结点 父结点与子结点 父结点与兄弟结点 解答 : A B C D ) 语法制导定义中某文法符号的一个属性，既可以是综合属性，又可以是继承属性。 (2) 只使用综合属性的语法制导定义称为 (3) 把 构造翻译程序的过程中前进了一大步。 (4)一个特定的翻译模式既适于自顶向下分析 ，又适于自底向上分析。 (5) 用于自顶向下分析的翻译模式，其基础文法中不能含有左递归。 (6) 在基础文法中增加标记非终结符不会导致新的语法分析冲突。 解答 :(1) (2) (3) (4) (5) (6) (1) 对于允许递归调用的程序语言，程序运行时的存储分配策略不能采用静态的存储分配策略。（ ） (2) 若一个程序语言的任何变量的存储空间大小和相互位置都能在编译时确定，则可采用静态分配策略。（ ） (3) 在不含嵌套过程的词法作用域中，若一个过程中有对名字 函数）外被说明。（ ） (4) 在允许嵌套的词法作用域的语言中，过程不能作为参数，原因时不能建立其运行环境的存取链。（ ） (5) 在堆式存储分配中，一个堆中存活的活动记录不一定是邻接的。（ ） (6) 如果源程序正文中过程 p 直接嵌入在过程 q 中，那么， p 的一个活动记录中的存取链接指向 q 的最近的活动记录。（ ） 解答： (1)(2)(3)(4)( (5)( (6)( 行时的存储分配策略分 ( A )和 ( B )两类。 ( B )又分 ( C )和 ( D )。一个语言中不同种类的变量根据定义域和生存期的不同往往采用不同的存储分配策略， C 语言中的静态变量往往采用 ( A )，而自动 (变量往往采用 ( C )。使用申请的内存单元采用 ( D )。 A,B,C,D: 栈式分配 最佳分配 堆式分配 静态分配 随机分配 动态分配 解答： A: B: C: D: 译算术表达式一（ a b） *（ c d）（ a b c）为 (1)四元式， (2)三元式 (3)间接三元式 解答： (1)四元式序列为： (1) + a b 2) + c d 3) * t1 t2 4) 5) + a b 6) + t5 c 7) + t4 t6 2)三元式序列为： (1) + a b (2) + c d (3) * (1) (2) (4) 3) (5) + a b (6) + (5) c (7) + (4) (6) (3)间接三元式表示： (1) (11) (11) + a b (2) (12) (12) + c d (3) (13) (13) * (11) (12) (4) (14) (14) 13) (5) (11) (15) + (11) c (6) (15) (16) + (14)