《编译原理(龙书)习题(5678)章ppt课件》由会员分享，可在线阅读，更多相关《编译原理(龙书)习题(5678)章ppt课件（37页珍藏版）》请在金锄头文库上搜索。
1、 第5章语法制导的翻译 5 2 3假设我们有一个产生式 A B C D这四个非终结符号都有两个属性 s是一个综合属性 而i是一个继承属性 对于下面的每组规则 指出 i 这些规则是否满足S属性定义的要求 ii 这些规则是否满足L属性定义的要求 iii 是否存在和这些规则一致的求值过程 1 A s B i C s不满足S属性定义 满足L属性定义2 A s B i C s和D i A i B s不满足S属性定义 满足L属性定义3 A s B s D s满足S属性定义 满足L属性定义4 A s D i B i A s C s C i B s和D i B i C i不满足S属性定义 不满足L属性定义 5
2、 2 4这个文法生成了含 小数点 的二进制 设计一个L属性的SDD来计算S val 即输入串的十进制数值 比如 串101 11应该被翻译为十进制数5 635 提示 使用一个继承属性L side来指明一个二进制位在小数点的哪一边 为了求小数部分的值 引入L的综合属性b记录2的L的位数次幂值 2lengthofL S L1 L2S val L1 val L2 val L2 b S LS val L val L L1BL val L1 val 2 B val L b L1 b 2 L BL val B val L b 2 B 0B val 0 B 1B val 1 5 3 1下面是涉及运算符 和整数
3、或浮点运算分量的表达式的文法 区分浮点数的方法是看它有无小数点 1 给出一个SDD来确定每个项T和表达式E的类型 2 扩展 1 中得到的SDD 使得它可以把表达式转换成为后缀表达式 使用一个单目运算符intToFloat把一个整数转换为相等的浮点数 设code为综合属性 代表各非终结符的代码属性type为综合属性 代表各非终结符的类型属性inttoreal把整型值转换为相等的实型值vtochar将数值转换为字符串 5 3 3给出一个SDD对x 3 x x x 这样的表达式求微分 表达式中涉及运算符 和 变量x和常量 假设不进行任何简化 也就是说 比如3 x将被翻译为3 1 0 x exp为原表
4、达式的字符串 s为求导后的字符串 为串联接符 5 4 3下面的SDT计算了一个由0和1组成的串的值 它把输入的符号串当作按照正二进制数来解释 改写这个SDT 使得基础文法不再是左递归的 但仍然可以计算出整个输入串的相同的B val的值 非终结符D的综合属性b表示二进制数的位数 val表示对应的十进制数的数值 消除左递归后如下 第6章中间代码生成 6 1 1为下面的表达式构造DAG x y x y x y x y x y 6 2 1将算术表达式a b c 翻译成1 抽象语法树2 四元式序列3 三元式序列4 间接三元式序列 1 抽象语法树 2 四元式序列 3 三元式序列 4 间接三元式序列 6 4
5、 1向图6 19的翻译方案中加入对应于下列产生式的规则 1 2 6 4 2使用图6 20中的增量式翻译方案重复练习6 4 1 在增量方式中 gen不仅要构造出一个新的三地址指令 还要将它添加到至今为止已生成的指令序列之后 6 4 3使用使用图6 22所示的翻译方案来翻译下列赋值语句 2 x a i j b i j 假设w1为数组a的第一维的宽度 w2为数组b的第一维的宽度 整数的宽度为w t1 i w1 t6 j w t2 j w t7 t5 t6 t3 t1 t2 t8 b t7 t4 a t3 t9 t4 t8 t5 i w2 x t9 6 6 1在图6 30的语法制导定义中添加处理下列控
6、制流构造的规则 1 一个repeat语句 repeatSwhileB2 一个for循环语句 for S1 B S2 S3 S repeatS1whileBbegin newlabel S1 next newlabel B true beginB false S nextS code label begin S1 code label S1 next B code S for S1 B S2 S3S1 next newlabel B true newlabel begin newlabel B fale S nextS2 next S1 nextS3 next beginS code S1 co
7、de label S1 next B code label begin S2 code gen goto S1 next label B true S3 code gen goto begin 6 7 7使用图6 37中的翻译方案翻译下列表达式 给出每个子表达式的truelist和falselist 你可以假设第一条被生成的指令的地址是100 1 a b c d e f 100 ifa bgoto102101 goto 102 ifc dgoto 103 goto104104 ife fgoto 105 goto 第7章运行时环境 7 2 3图7 9中是递归计算Fiabonacci数列的C语言
8、代码 假设f的活动记录按顺序包含下列元素 返回值 参数n 局部变量s 局部变量t 通常在活动记录中还会有其他元素 下面的问题假设初始调用是f 5 intf intn intt s if n 2 return1 s f n 1 t f n 2 returns t 图7 9 活动树 第1个f 1 调用即将返回 第5个f 1 调用即将返回 7 2 5在一个通过引用传递参数的语言中 有一个函数f x y 完成下面的计算 x x 1 y y 2 returnx y 如果将a赋值为3 然后调用f a a 那么返回值是什么 函数返回值为 12此时a的值为 6 第8章代码生成 8 2 1假设所有的变量都存放在
9、内存中 为下面的三地址语句生成代码 1 x 1LDR1 1STx R13 x a 1LDR1 aADDR1 R1 1STx R1 8 2 2假设a和b是元素为4字节值的数组 为下面的三地址语句序列生成代码 2 三个语句序列x a i y b i z x y LDR1 iMULR1 R1 4LDR2 a R1 STx R2LDR3 iMULR3 R3 4LDR4 b R3 STy R4LDR5 xLDR6 yMULR5 R5 R6STz R5 8 2 4假设x y和z存放在内存位置中 为下面的语句序列生成代码 ifx ygotoL1z 0gotoL2L1 z 1 LDR1 xLDR2 ySUBR
10、1 R1 R2BLTZR1 L1LDR3 0STz R3JMPL2L1 LDR4 1STz R4 8 2 6确定下列指令序列的代价 1 LDR0 y2LDR1 z2ADDR0 R0 R11STx R02总代价 73 LDR0 c2LDR1 i2MULR1 R2 82STa R1 R02总代价 8 8 3 3假设使用栈式分配 且假设a和b都是元素大小为4字节的数组 为下面的三地址语句生成代码 2 三个语句序列x a i y b i z x y LDR1 iMULR1 R1 4ADDR1 R1 SPLDR2 a R1 STx SP R2LDR3 iMULR3 R3 4ADDR3 R3 SPLDR4
11、 b R3 STy SP R4LDR5 x SP LDR6 y SP MULR5 R5 R6STz SP R5 8 5 1为下面的基本块构造DAG d b ce a bb b ca e d 1 只有a在基本块的出口处活跃 d b ce a ba e d 2 a b c在基本块的出口处活跃 e a bb b ca e b 8 5 8假设一个基本块由下面的C语言赋值语句生成 x a b c d e f y a c e 1 给出这个基本块的三地址语句 每个语句只做一次加法 t1 a bt2 t1 ct3 t2 dt4 t3 et5 t4 fx t5t6 a ct7 t6 ey t7 2 假设x和y都
12、在基本块的出口处活跃 利用加法的结合律和交换律来修改这个基本块 使得指令个数最少 把原始的赋值语句进行调整 x a c e b d fy a c e对应的三地址语句序列 t1 a ct2 t1 et3 t2 bt4 t3 dt5 t4 fx t5t6 a ct7 t6 ey t7 DAG 优化后的三地址语句序列 t1 a cy t1 et3 y bt4 t3 dx t4 f 优化后的目标代码序列 LDR1 aLDR2 cADDR1 R1 R2LDR2 eADDR1 R1 R2STy R1LDR2 bADDR1 R1 R2LDR2 dADDR1 R1 R2LDR2 fADDR1 R1 R2STx R1 8 6 1为下面的每个C语言赋值语句生成三地址代码1 x a b c t1 b ct2 a t1x t23 x a i 1t1 a i t2 t1 1x t2 LDR1 bLDR2 cMULR1 R1 R2LDR3 aADDR1 R1 R3STx R1 LDR1 iMULR1 R1 4LDR2 a R1 ADDR2 R2 1STx R2 假设数组元素宽度为4
