生成抽象语法树的语法制导定义 ·a+a*(b-c)+(b-c)*d的抽象语法树 PRODUCTION SEMANTIC RULES 1) E→E1+T E.node new Node('+',E1.node,T.node) 2) E→E1-T E.node new Node('-,E.node,T.node) 3) E→T E.node=T.node 4) T→（E) T.node=E.node 5) T→id T.node =new Leaf(id,id.entry) 6) T→num T.node new Leaf(num,num.val) 6
生成抽象语法树的语法制导定义 • a + a * (b – c) + (b – c) * d的抽象语法树 6 南大编译许畅
表达式的有向无环图 语法树中，公共子表达式每出现一次，就有一颗 对应的子树 表达式的有向无环图(Directed Acyclic Graph, DAG)能够指出表达式中的公共子表达式，更简 洁地表示表达式 b 图6-3 表达式a+a*(b-c)+ (b-c)*d的DAG 7
表达式的有向无环图 • 语法树中，公共子表达式每出现一次，就有一颗 对应的子树 • 表达式的有向无环图 (Directed Acyclic Graph, DAG) 能够指出表达式中的公共子表达式，更简 洁地表示表达式 7 南大编译许畅
DAG构造 可以用和构造抽象语法树一样的SDD来构造 不同的处理 在函数Lemf和Node每次被调用时，构造新节点前先检查 是否已存在同样的节点，如果已经存在，则返回这个 已有的节点 1) PI Leaf (id,entry-a) 。构造过程示例 2) P2 Leaf(id,entry-a)=p 3) P3 Leaf(id,entry-b) 4)pa Leaf(id,entry-c) 5)）5=Node'-',ps,p4) 6)p6=Node('*',p1,pP5) 7)p= Node('+',p1,p6) 8)ps Leaf (id,entry-b)=p3 9) po Leaf(id,entry-c)=pa 10) P1o Node('-',P3,PA)=ps 11) pu=Leaf(id,entry-d) 12) p12=Node('*',p5,p11) 13) p13=Node'+',p7,p12) 图6-3表达式a+a*(b-c)+ (b-c)*d的DAG 图6-5 图6-3所示的DAG的构造过程 8
DAG构造 • 可以用和构造抽象语法树一样的SDD来构造 • 不同的处理 – 在函数Leaf和Node每次被调用时，构造新节点前先检查 是否已存在同样的节点，如果已经存在，则返回这个 已有的节点 • 构造过程示例 8 南大编译许畅
三地址代码(1) 每条指令右侧最多有一个运算符 一般情况可以写成x=y0p2 0 允许的运算分量 名字：源程序中的名字作为三地址代码的地址 常量：源程序中出现或生成的常量 编译器生成的临时变量 9
三地址代码 (1) • 每条指令右侧最多有一个运算符 – 一般情况可以写成x = y op z • 允许的运算分量 – 名字：源程序中的名字作为三地址代码的地址 – 常量：源程序中出现或生成的常量 – 编译器生成的临时变量 9 南大编译许畅
三地址代码(2) 指令集合(1) 运算/赋值指令： x=yopz 人/ x=opy 复制指令： x=y 无条件转移指令： goto L 条件转移指令： if x goto L if False x goto L 条件转移指令： if x relop y goto L 10
三地址代码 (2) • 指令集合 (1) – 运算/赋值指令： x = y op z x = op y – 复制指令： x = y – 无条件转移指令： goto L – 条件转移指令： if x goto L if False x goto L – 条件转移指令： if x relop y goto L 10 南大编译许畅