3、树 用树形数据结构来表示一个表达式或语句 )树 ①简单变量或常数的树就是该变量或常数本身 ②如果表示e1和e2的树为T1和T2, 则e1+e2,e1*e2-e1的树为 米 2 2 16
16 3、树 用树形数据结构来表示一个表达式或语句. (1)树 ①简单变量或常数的树就是该变量或常数本身. ②如果表示e1和e2的树为T1和T2 , 则e1+e2 , e1*e2 , －e1的树为: + * － T1 T2 T1 T2 T1
例:A*B+C*D 树 三元式 op ARGI ARG2 A B (2)*C ab C D (3)+(1)(2)
17 例:A*B+C*D 树: + 三元式 op ARG1 ARG2 * * (1) * A B (2) * C D A B C D (3) + (1) (2)
(2)语法制导生成树形表示 EVAL:指示器指向树的一个结点 NODE(op, LEFT, RIGHT 建立一棵新树,根为op, LEFT RIGHT分别为左右 分支;从NODE回送的值是一个指示器指向这棵新树 的根 UNARY(op, CHILD) 生成只有一个分支CHID的子树 LEAF(i):建立一个以为标志的结点并回送此结点的地址
18 (2)语法制导生成树形表示 E·VAL:指示器,指向树的一个结点. NODE(op, LEFT , RIGHT): 建立一棵新树, 根为op , LEFT, RIGHT分别为左右 分支；从NODE回送的值是一个指示器,指向这棵新树 的根. UNARY(op, CHILD): 生成只有一个分支CHILD的子树. LEAF(i):建立一个以i为标志的结点并回送此结点的地址