6.6 节的练习

6.6.1

在图 6-36 的语法制导定义中添加处理下列控制流构造的规则：

一个 repeat 语句：repeat S while B
！一个 for 循环语句：for (S1; B; S2) S3

解答

Production                  Syntax Rule

S -> repeat S1 while B      S1.next = newlabel()
                            B.true = newlabel()
                            B.false = S.next
                            S.code = label(B.true) || S1.code
                                || label(S1.next) || B.code

S -> for (S1; B; S2) S3     S1.next = newlabel()
                            B.true = newlabel()
                            B.false = S.next
                            S2.next = S1.next
                            S3.next = newlabel()
                            S.code = S1.code
                                || lable(S1.next) || B.code
                                || lable(B.true) || S3.code
                                || label(S3.next) || S2.code
                                || gen('goto', S1.next)

6.6.2

现代计算机试图在同一个时刻执行多条指令，其中包括各种分支指令。因此，当计算机投机性地预先执行某个分支，但实际控制流却进入另一个分支时，付出的代价是很大的。因此我们希望尽可能地减少分支数量。请注意，在图 6-35c 中 while 循环语句的实现中，每个迭代有两个分支：一个是从条件 B 进入到循环体中，另一个分支跳转回 B 的代码。基于尽量减少分支的考虑，我们通常更倾向于将 while(B) S 当作 if(B) {repeat S until !(B)} 来实现。给出这种翻译方法的代码布局，并修改图 6-36 中 while 循环语句的规则。

解答

Production               Syntax Rule

S -> if(B) {             B.true = newlabel()    
        repeat S1        B.false = S.next            
        until !(B)       S1.next = newlabel()
     }                   S.code = B.code
                             || label(B.true) || S1.code
                             || label(S1.next) || B.code

6.6.3！

假设 C 中存在一个异或运算。按照图 6-37 的风格写出这个运算符的代码生成规则。

解答

B1 ^ B2 等价于 !B1 && B2 || B1 && !B2 (运算符优先级 ! > && > ||)

Production      Syntax Rule

B -> B1 ^ B2    B1.true = newlabel()
                B1.false = newlabel()

                B2.true = B.true
                B2.false = B1.true

                b3 = newboolean()
                b3.code = B1.code
                b3.true = newlabel()
                b3.false = B.false

                b4 = newboolean()
                b4.code = B2.code
                b4.true = B.false
                b4.false = B.true

                S.code = B1.code
                    || label(B1.false) || B2.code
                    || label(B1.true) || b3.code
                    || label(b3.true) || b4.code

6.6.4

使用 6.6.5 节中介绍的避免 goto 语句的翻译方案，翻译下列表达式：

if (a==b && c==d || e==f) x == 1
if (a==b || c==d || e==f) x == 1
if (a==b || c==d && e==f) x == 1

解答

if (a==b && c==d || e==f) x == 1

     ifFalse a==b goto L3 
     if c==d goto L2
 L3: ifFalse e==f goto L1
 L2: x == 1
 L1:

if (a==b || c==d || e==f) x == 1

     if a==b goto L2
     if c==d goto L2
     ifFalse e==f goto L1
 L2: x==1
 L1:

if (a==b || c==d && e==f) x == 1

     if a==b goto L2
     ifFalse c==d goto L1
     ifFalse e==f goto L1
 L2: x==1
 L1:

6.6.5

基于图 6-36 和图 6-37 中给出的语法制导定义，给出一个翻译方案。

6.6.6

使用类似于图 6-39 和图 6-40 中的规则，修改图 6-36 和图 6-37 的语义规则，使之允许控制流穿越。

解答

仅补充完毕书中未解答部分

Production              Syntax Rule

S -> if(B) S1 else S2   B.true = fall
                        B.false = newlabel()
                        S1.next = S.next
                        S2.next = S.next
                        S.code = B.code 
                            || S1.code
                            || gen('goto' S1.next)
                            || label(B.false) || S2.code

S -> while(B) S1        begin = newlabel()
                        B.true = fall
                        B.false = S.next
                        S1.next = begin
                        S.code = label(begin) || B.code
                            || S1.code
                            || gen('goto' begin)

S -> S1 S2              S1.next = fall
                        S2.next = S.next
                        S.code = S1.code || S2.code

B -> B1 && B2           B1.true = fall
                        B1.false = if B.false == fall
                                   then newlabel()
                                   else B.false
                        B2.true = B.true
                        B2.false = B.false
                        B.code = if B.false == fall
                                 then B1.code || B2.code || label(B1.false)
                                 else B1.code || B2.code

6.6.7！

练习 6.6.6 中的语义规则产生了一些不必要的标号。修改图 6-36 中语句的规则，使之只创建必要的标号。你可以使用特殊符号 deferred 来表示还没有创建的一个标号。你的语义规则必须能生成类似于例 6.21 的代码。

6.6.8！！

6.6.5 节中讨论了如何使用穿越代码来尽可能减少生成的中间代码中跳转指令的数据。然而，它并没有充分考虑将一个条件替换为它的补的方法，例如将 if a < b goto L1; goto L2 替换成 ifFalse a >= b goto L2; goto L1。给出语法制导定义，它在需要时可以利用这种替换方法。