编译原理笔记（6）

1. 引入中间代码的作用

   1. 使编译程序在结构上更清晰（前端、后端）
   2. 便于进行代码优化
   3. 便于移植

2. 后缀式

   1. 后缀式不使用括号，只要知道运算符的数目，无论是从左端还是右端扫描，都可以对齐进行无歧义的分解

3. 表达式向后缀式的翻译
   

4. 有向无环图（DAG）

   1. 内部结点代表运算符
   2. 公共表达式会有多个父节点（即该表达式参与了多个运算）

5. DAG的生成方式

   1. 首先画出产生式的语法树
   2. 对语法树的重复子树进行合并

6. 三地址代码形式

   1. x := y op z

7. 四元式
   

8. 三元式

   • 相比于三元式没有了result域保存表达式的值，使用序号代表相应表达式的值
     

9. 间接三元式

   1. 使用三元式+间接码表
   2. 解决了三元式中某些表达式需要反复计算的问题，并且优化起来很方便
      

10. 翻译语句的属性文法 *

    1. S.place表示存储非终结符S值的地址
    2. S.code表示对S值计算的三地址代码序列（后缀式）

11. 赋值语句的三地址代码翻译模式 *
    

12. 数组元素地址计算

    • $ A [ i_1 , i_2 , i_3 , … , i_n ] = A + ((((i_1-low_1)*n_2+i_2-low_2)*n_3…)*n_k + i_k - low_k ) * w $

    该表达式中 $ low_1 , low_2 ,…, low_n $ 是确定的所以可以对上面的式子进行一个分解

    • $ A [ i_1 , i_2 , i_3 , … , i_n ] = offset + base - c $
    • $ base = A $
    • $ offset=(((i_1 * n_2 + i_2) * n_3 …) * n_k+ i_k) * w $
    • $ c = (((low_1 * n_2 + low_2) * n_3…) * n_k+low_k) * w $

13. 数组元素引用的翻译模式 *

    1. 将文法改写为
       $ L \rightarrow Elist ] | id $
       $ Elist \rightarrow Elist , E | id [E $

    2. 引入下列语义

       • Elist.ndim:下标个数计数器
       • Elist.place:保存数组Offset部分被计算出来的值
       • Elist.array:数组名
       • limit(array,j):给出数组第j维的长度

    3. 几个关键的产生式的语义
       $ Elist \rightarrow id [ E$

       Elist.place = E.place
       Elist.ndim = 1
       Elist.array = id.place

       $ Elist \rightarrow Elist ,E $

       t=newtemp
       m=ndim+1
       t=Elist.place*limit(Elist.array,m)
       t=t+E.place
       Elist.array=Elist.array
       Elist.place=t
       Elist.ndim=m

       $ L \rightarrow Elist ] $

       L.place=newtemp
       L.offset=newtemp
       L.place=Elist.array - C
       L.offset=w*Elist.place

14. 例题：A是一个二维数组，即n1=10，n2=20，w=4，数组的第一个元素为A[1,1]，请给出x:=A[y,z]的三代码语句序列。

    t1 = y  * 20
    t2 = t1 + z
    t3 = t2 * 4                  # offset
    t4 = A  - ( 1 * 20 + 1 ) * 4 # base-c
    t5 = t4[t2]
    x  = t5 

15. 例题：按照作为条件控制的布尔式翻译写出布尔式A or (B and not (C or D))的四元式序列。

    (1) ( jnz , A  , _ , 0 )
    (2) ( j   , _  , _ , 3 )
    (3) ( jnz , B  , _ , 5 )
    (4) ( j   , _  , _ , 0 )
    (5) ( or  , C  , D , T1)
    (6) ( not , T1 , _ , T2)
    (7) ( jnz , T2 , _ , 1 )
    (8) ( j   , _  , _ , 4 )

16. 例题：把下面的语句翻译成四元式序列：

while A < C and B < D do
    if  A = 1 then C:=C + 1 else
         while A <= D do A:= A + 2;

(1)  ( j< , A  , C , 3  )
(2)  ( j  , _  , _ , 15 )
(3)  ( j< , B  , D , 5  )
(4)  ( j  , _  , _ , 15 )
(5)  ( j= , A  , 1 , 7  )
(6)  ( j  , _  , _ , 10 )
(7)  ( +  , C  , 1 , T1 )
(8)  ( := , T1 , _   C  )
(9)  ( j  , _  , _ , 1  )
(10) ( j<=, A  , D , 12 )
(11) ( j  , _  , _ , 1  )
(12) ( +  , A  , 2 , T2 )
(13) ( := , T2 , _ , A  )
(14) ( j  , _  , _ , 10 )
(15) ( j  , _  , _ , 1  )
(16)