5.4 节的练习

5.4.1

我们在 5.4.2 节中提到可能根据语法分析栈中的 LR 状态来推导出这个状态表示了什么文法符号。我们如何推导这个信息？

解答

见算法 4.44

5.4.2

改写下面的 SDT:

A -> A {a} B | A B {b} | 0
B -> B {c} A | B A {d} | 1

使得基础文法变成非左递归的。

5.4.3 ！

下面的 SDT 计算了一个由 0 和 1 组成的串的值。它把输入的符号串当做正二进制数来解释。

B -> B_1 0 {B.val = 2 * B_1.val}
   | B_1 1 {B.val = 2 * B_1.val + 1}
   | 1 {B.val = 1}

改写这个 SDT，使得基础文法不再是左递归的，但仍然可以计算出整个输入串的相同的 B.val 的值。

解答

提取左公因子

B -> B_1 digit {B.val = 2 * B_1.val + digit.val}
   | 1 {B.val = 1}
digit -> 0 {digit.val = 0} 
       | 1 {digit.val = 1}

在形如 A = A a | b 的左递归产生式中， a 为 digit {B.val = 2 * B_1.val + digit.val}， b 为 1

消除左递归后得

B -> 1 {A.i = 1} A
A -> digit {A_1.i = 2 * A.i + digit.val} A_1 {A.val = A_1.val}
   | ε {A.val = A.i}
digit -> 0 {digit.val = 0} 
       | 1 {digit.val = 1}

5.4.4 ！

为下面的产生式写出一个和例 5.19 类似的 L 属性 SDD。这里的每个产生式表示一个常见的 C 语言那样的控制流结构。你可能需要生成一个三地址语句来跳转到某个标号 L，此时你可以生成语句 goto L。

S -> if ( C ) S_1 else S_2
S -> do S_1 while ( C )
S -> '{' L '}'; L -> L S | ε

请注意，列表中的任何语句都可能包含一条从它的内部跳转到下一个语句的跳转指令，因此简单地为各个语句按顺序生成代码是不够的。

解答

S -> if ( C ) S_1 else S_2

 L_1 = new()
 C.false = L_1  
 S_1.next = S.next
 S.code = C.code || S_1.code || label || L_1 || S_2.code

S -> do S_1 while ( C )

L_1 = new()
C.true = L_1
S.code = label || L_1 || S_1.code || C.code

5.4.5

按照例 5.19 的方法，把在练习 5.4.4 中得到的各个 SDD 转换成一个 SDT。

解答

S -> if ( C ) S_1 else S_2

 S -> if (     {new L_1; C.false = L_1}   
      C )      {S_1.next = S.next}
      S_1 else
      S_2      {S.code = C.code || S_1.code || label || L_1 || S_2.code}

S -> do S_1 while ( C )

S -> do           {new L_1} 
     S_1 while (  {C.true = L_1}
     C )          {S.code = label || L_1 || S_1.code || C.code}

5.4.6

修改图 5.25 中的 SDD，使它包含一个综合属性 B.le，即一个方框的长度。两个方框并列后得到的方框的长度是这两个方框的长度和。然后把你的新规则加入到图 5.26 中 SDT 的合适位置上。

5.4.7

修改图 5.25 中的 SDD，使它包含上标，用方框之间的运算符 sup 表示。如果方框 B_2 是方框 B_1 的一个上标，那么将 B_2 的基线放在 B_1 的基线上方，两条基线的距离是 0.6 乘以 B_1 的大小。把新的产生式和规则加入到图 5.26 的 SDT 中去。

5.4.6 和 5.4.7 的解答

1) S -> B               B.ps = 10
                        B.wd = 

2) S -> B_1 B_2         B_1.ps = B.ps
                        B_2.ps = B.ps
                        B.wd = B_1.wd + B_2.wd
                        B.ht = max(B_1.ht, B_2.ht)
                        B.dp = max(B_1.dp, B_2.dp)

3) B -> B_1 sub B_2     B_1.ps = B.ps
                        B_2.ps = 0.7 * B.ps
                        B.wd = B_1.wd + B_2.wd
                        B.ht = max(B_1.ht, B_2.ht - 0.25 * B.ps)
                        B.dp = max(B_1.dp, B_2.dp + 0.25 * B.ps)

4) B -> B_1 sup B_2     B_1.ps = B.ps
                        B_2.ps = 0.6 * B.ps
                        B.wd = B_1.wd + B_2.wd
                        B.ht = max(B_1.ht, B_2.ht + 0.6 * B.ps)
                        B.dp = max(B_1.dp, B_2.dp - 0.6 * B.ps)    

5) B -> ( B_1 )         B_1.ps = B.ps
                        B.wd = B_1.wd
                        B.ht = B_1.ht
                        B.dp = B_1.dp

6) B -> text            B.wd = getWd(B.ps, text.lexval)
                        B.ht = getHt(B.ps, text.lexval)
                        B.dp = getDp(B.ps, text.lexval)