抽象语法树回顾 产生式」 语义规则 E→E1+TE,n0le= new node(“+,E1,nOdl,T,node) E>E-TEnode= new Node("-',E,, node, Tnode) E→T E node= tnode T→T1*FT.node= new nodel(“*2,T1,nOdl,F,noe) T→F Tnode= f node F→(E) F,node= enode F→id Fnode= new leaf (id, identry) F→num F node= new leaf (num, num. val) 例:a+a*(b-c)+(b-c)*
抽象语法树回顾 例：a + a * (b – c) + (b – c) * d 产 生 式 语 义 规 则 E → E1 +T E.node = new Node(‘+’, E1 .node, T.node) E → E1 −T E.node = new Node(‘−’, E1 .node, T.node) E → T E.node = T.node T → T1 F T.node = new Node( ‘’, T1 .node, F.node) T → F T.node = F.node F → (E) F.node = E.node F → id F.node = new Leaf (id, id.entry) F → num F.node = new Leaf (num, num.val)
有向无环图( Directed Acyclic Graph, DAG) 语法树中,公共子表达式每出现一次,就有一个对应的 子树 表达式的有向无环图能够指出表达式中的公共子表达式, 更简洁地表示表达式 例:a+a*(b-c)+(b-C)*d
有向无环图（Directed Acyclic Graph, DAG） • 语法树中，公共子表达式每出现一次，就有一个对应的 子树 • 表达式的有向无环图能够指出表达式中的公共子表达式， 更简洁地表示表达式 例：a + a * (b – c) + (b – c) * d
构造赋值语句语法树/DAG的语法制 导定义 ·修改构造结点的函数Node和Leaf可生成DAG:构 造新节点前先检查是否已存在同样的节点,如果 已经存在,则返回这个已有的节点 生式 语义规则 E,,+T Enode= new Node(+, Er, node, Tnode) E→E1-TE. node= new node(“-,E1,node, T node) E→T|Emle=rmhe T→T* FTnode= new node(“*,T1,node,F,nodl) T→F Tnode= fnode F→(E) Fnode= enode F→)id Fnode= new Leaf (id, id entry) F→num Fnode= new Leaf (num, num.val)
构造赋值语句语法树/DAG的语法制 导定义 • 修改构造结点的函数Node和Leaf可生成DAG：构 造新节点前先检查是否已存在同样的节点，如果 已经存在，则返回这个已有的节点 产 生 式 语 义 规 则 E → E1 +T E.node = new Node(‘+’, E1 .node, T.node) E → E1 −T E.node = new Node(‘−’, E1 .node, T.node) E → T E.node = T.node T → T1 F T.node = new Node( ‘’, T1 .node,F.node) T → F T.node = F.node F → (E) F.node = E.node F → id F.node = new Leaf (id, id.entry) F → num F.node = new Leaf (num, num.val)
a+a*(b-c)+(b-c)*d的DAG的构造 「产生式 语义规则 E→E1+TE. node= new node(“+,E1,nole, Tnode) E,E1-T Enode= new Node(-, Er- node, T node Enode= tnode →T1* F Tnode= new node(*’,T,node, F node) T→F Tnode= fnode F→(E) Anode= enode F→id Fnode= new Leaf(id, id entry) F→Ⅲum| Fnode= new Leaf(mum, num.val) a
a + a * (b – c) + (b – c) * d的DAG的构造 + + * * – d b c a 产 生 式 语 义 规 则 E → E1 +T E.node = new Node(‘+’, E1 .node, T.node) E → E1 −T E.node = new Node(‘−’, E1 .node, T.node) E → T E.node = T.node T → T1 F T.node = new Node( ‘’, T1 .node, F.node) T → F T.node = F.node F → (E) F.node = E.node F → id F.node = new Leaf (id, id.entry) F → num F.node = new Leaf (num, num.val)
三地址代码 般形式:x=yopz 条指令右侧最多有一个运算符 三地址代码拆分了多运算符表达式和控制流语句的嵌 套结构,所以适用于目标代码的生成 例表达式x+y*z翻译成的三地址语句序列是 ,=y*Z
三地址代码 • 一般形式：x = y op z • 一条指令右侧最多有一个运算符 • 三地址代码拆分了多运算符表达式和控制流语句的嵌 套结构，所以适用于目标代码的生成 • 例 表达式x + y z翻译成的三地址语句序列是 t1 = y z t2 = x + t1