编译原理与技术 中间代码生成.ppt
《编译原理与技术 中间代码生成.ppt》由会员分享,可在线阅读,更多相关《编译原理与技术 中间代码生成.ppt(62页珍藏版)》请在三一文库上搜索。
1、2019/9/22,编译原理与技术讲义,1,编译原理与技术,中间代码生成,2019/9/22,编译原理与技术讲义,2,中间代码生成,中间代码形式 控制流语句翻译,2019/9/22,编译原理与技术讲义,3,中间代码生成,中间代码的种类 后缀式(逆波兰式) e.g.1 a + b * -c a b c * + e.g.2 1)a := b* -c + b * -c,其后缀式为 a b c * b c * + assign 2)if ab then c := c + 1 a b c c 1 + assign IF 语法树 vs. 分析树 e.g.3 1)a := b* -c + b * -c,其语
2、法树为,2019/9/22,编译原理与技术讲义,4, e.g.3 1)a := b* -c + b * -c 语法树 vs. 分析树,中间代码的种类,assign,a,+,*,b,c,*,b,c,assign,E,E,E,+,E,*,E,b,E,E,a,赋值语句,c,E,*,E,b,E,c,2019/9/22,编译原理与技术讲义,5, e.g.3 2)a := b* -c + b * -c 语法树 vs. DAG,中间代码的种类,assign,a,+,*,b,c,*,b,c,assign,a,+,*,b,c,2019/9/22,编译原理与技术讲义,6,中间代码的种类,e.g.4 构造表达式的语
3、法树(DAG) 产生式 语义规则 EE1 + E2 E.nptr := mknode(+,E1.nptr, E2.nptr) EE1 - E2 E.nptr := mknode(-,E1.nptr, E2.nptr) EE1 * E2 E.nptr := mknode(*,E1.nptr, E2.nptr) EE1 / E2 E.nptr := mknode(/,E1.nptr, E2.nptr) E( E1 ) E.nptr := E1.nptr E - E1 E.nptr := mknode(,E1.nptr, ) Enumber E.nptr := mkleaf(NUM,number.l
4、ex_val) Eid E.nptr := mkleaf(ID,id.entry),2019/9/22,编译原理与技术讲义,7,中间代码的种类,e.g.4 构造表达式的语法树(DAG) E.nptr E的语法树(根结点指针) mknode(op, left, right)建立一个表达式语法树结点,它的运算符为op,左、右运算对象是left和right所指的语法树。 mkleaf(NUM,number.lex_val) mkleaf(ID,id.entry) 建立表达式语法树的叶子结点。,2019/9/22,编译原理与技术讲义,8,e.g.4 构造表达式a+b*-4的语法树(DAG),中间代码的
5、种类,2019/9/22,编译原理与技术讲义,9,中间代码的种类,三地址代码 一般形式:x := y op z 或 x := op y e.g.5 a := b* -c + b * -c的三地址代码 1)t1 := - c 1) t1 := - c 2)t2 := b * t1 2) t2 := b * t1 3)t3 := - c 3) t3 := t2 + t2 4)t4 := b * t3 4) a := t3 5)t5 := t2 + t4 6)a := t5,2019/9/22,编译原理与技术讲义,10,中间代码的种类,常用的三地址代码 x := y op z 二元运算 x := o
6、p y 单目运算 x := y 值拷贝 goto L 无条件转移到代码标号L处 if x RELOP y goto L 条件转移代码:若x和y满足RELOP关系,则转移至代码标号L处 param X 参数X CALL proc,N 调用过程proc,参数个数为N,2019/9/22,编译原理与技术讲义,11,中间代码的种类,常用的三地址代码(续) return y 过程返回,返回值为y x := y i x i := y 变址语句 x := &y *x := y x := *y 指针操作语句 三地址代码实现形式 四元式: ( op, arg1, arg2, result ) 三元式: ( op
7、, arg1, arg2 ) 间接三元式(三元式的指针表),2019/9/22,编译原理与技术讲义,12,中间代码的种类,e.g.6 a := b* -c + b * -c 的四元式和三元式 四元式 vs. 三元式 1)( , c, , t1) ( , c, ) 2)( * , b, t1, t2) ( * , b, ) 3)( , c, , t3) ( , c, ) 4)( * , b, t3, t4) ( * , b, ) 5)( + , t2, t4, t5 ) ( + , , ) 6)(:=, t5, a) (:=, a, ),2019/9/22,编译原理与技术讲义,13,中间代码的种
8、类,e.g.7 a := b * c + d / f 的间接三元式 间接三元式 / 调整次序 三元式 ( * , b , c ) ( / , d , f ) ( + , , ) ( := , a , ),2019/9/22,编译原理与技术讲义,14,中间代码的种类,2019/9/22,编译原理与技术讲义,15,说明语句的翻译,一般不产生代码;仅将有关变量的属性填入符号表(如类型、存储偏移位置offset) e.g. 8 一个说明语句的翻译方案 文法G1如下: PD DD ; D Did : T Tint | real | array number of T1 | T1,2019/9/22,编译
9、原理与技术讲义,16,e.g. 8 一个说明语句的翻译方案(续), 有关符号的属性 T.type 变量所具有的类型,如 整型 INT 实型 REAL 数组类型 array(元素个数,元素类型) 指针类型 pointer(所指对象类型) T.width 该类型数据所占的字节数 offset 变量的存储偏移地址,2019/9/22,编译原理与技术讲义,17,e.g. 8 一个说明语句的翻译方案(续),2019/9/22,编译原理与技术讲义,18,e.g. 8 一个说明语句的翻译方案(续),(1)PM D (2)DD1 ; D2 (3)Did : T / 填入变量的相关属性 enter( id.na
10、me, T.type, offset) / 计算下一可用偏移位置 offset = offset + T.width (4)M offset := 0 / 偏移初始为0,2019/9/22,编译原理与技术讲义,19,e.g. 8 一个说明语句的翻译方案(续),(5)Tint T.type := INT; T.width := 4 (6)Treal T.type := REAL; T.width := 4 (7)Tarray number of T1 T.type := array( number.val, T1.type); T.width := number.val * T1.width (
11、8)Tpointer( T1 ) T.type := pointer( T1.type) ; T.width := 4 ,2019/9/22,编译原理与技术讲义,20,e.g. 9 一个嵌套说明语句的翻译方案,文法G2如下: PD DD1 ; D2 Did : T D proc id ; D1 ; S Tint | real | array number of T1 | T1 Sa,2019/9/22,编译原理与技术讲义,21,e.g. 9 一个嵌套说明语句的翻译方案,产生式 D proc id ; D1 ; S 引入过程id的声明;D1为其局部说明语句,可以声明变量或嵌套定义其它过程; 约定
12、每个过程有自己独立的符号表且嵌套定义的过程符号表头有指针指向外围(父)过程的符号表;而父过程符号表中有该嵌套子过程的条目(涉及子过程名和子过程符号表的指针等属性)。,2019/9/22,编译原理与技术讲义,22,相关定义: /* 在父过程符号表中建立子过程名的条目*/ enter-proc(parent-table, sub-proc-name, sub-table) /* 将所声明变量的类型、偏移填入当前符号表*/ enter(current-table, name, type, current-offset) /* 建立新的符号表,其表头指针指向父过程符号表*/ mktable(paren
13、t-table) addwidth(table,offset )/记录变量占用的总空间 符号表栈tblptr和偏移栈offset(栈顶值分别表示当前分析的过程的符号表及可用变量偏移位置),2019/9/22,编译原理与技术讲义,23,e.g. 9 一个嵌套说明语句的翻译方案,PM D addwidth( top(tblptr), top(offset) ), pop( tblptr ) ; pop( offset ) /* 保留变量分配空间大小并清空符号表和偏移栈 */ M t := mktable(null); push(t,tblptr); push(0,offset) /* 建立主程序(
14、最外围)的符号表 偏移从0开始 */ DD1 ; D2,2019/9/22,编译原理与技术讲义,24,D proc id ; N D1 ; S t := top( tblptr ); addwidth( t, top( offset ) ); pop( tblptr ); pop( offset ); enter-proc( top( tblptr ), id.name, t ) /* 保留当前(子)过程声明变量的总空间;弹出符号表和偏移栈顶(露出父过程的符号表和偏移);在父过程符号表中填写子过程名有关条目 */ N t := mktable( top( tblptr ) ); push( t
15、, tblptr ) ; push( 0, offset ) /* 建立子过程的符号表和偏移从0开始 */,2019/9/22,编译原理与技术讲义,25,Did : T enter( top( tblptr ), id.name, T.type, top( offset ) ); top( offset ) := top( offset ) + T.width; /* 将变量name的有关属性填入当前符号表 */ /* 以下产生式的翻译方案略 */ Tint | real | array number of T1 | T1 Sa,2019/9/22,编译原理与技术讲义,26,i : int;
16、j : int ; PROC P1 ; k : int; f : real ; PROC P2; l : int ; a1 ; a2; PROC P3; temp : int ; max : int ; a3;,e.g.10 过程嵌套声明,P0,P1,P3,P2,过程声明层次图,2019/9/22,编译原理与技术讲义,27,初始:M,e.g.10 过程嵌套声明(续),符号栈,偏移栈,P0,0,top,null,总偏移:,P0,2019/9/22,编译原理与技术讲义,28,i : int ; j : int ;,e.g.10 过程嵌套声明(续),符号栈,偏移栈,P0,8,top,null,总偏移
17、:,P0,i,INT,0,j,INT,4,2019/9/22,编译原理与技术讲义,29,PROC P1 ; (N),e.g.10 过程嵌套声明(续),符号栈,偏移栈,P0,8,top,null,总偏移:,P0,i,INT,0,j,INT,4,P1,0,总偏移:,P1,2019/9/22,编译原理与技术讲义,30,k : int ; f : real ;,e.g.10 过程嵌套声明(续),符号栈,偏移栈,P0,8,top,null,总偏移:,P0,i,INT,0,j,INT,4,P1,8,总偏移:,P1,k,INT,0,f,real,4,2019/9/22,编译原理与技术讲义,31,PROC P
18、2 ; (N),e.g.10 过程嵌套声明(续),符号栈,偏移栈,P0,8,top,null,总偏移:,P0,i,INT,0,j,INT,4,P1,8,总偏移:,P1,k,INT,0,f,real,4,P2,0,总偏移:,P2,2019/9/22,编译原理与技术讲义,32,l : int ;,e.g.10 过程嵌套声明(续),符号栈,偏移栈,P0,8,top,null,总偏移:,P0,i,INT,0,j,INT,4,P1,8,总偏移:,P1,k,INT,0,f,real,4,P2,4,总偏移:,P2,l,INT,0,2019/9/22,编译原理与技术讲义,33,a1 ;,e.g.10 过程嵌套
19、声明(续),符号栈,偏移栈,P0,8,top,null,总偏移:,P0,i,INT,0,j,INT,4,P1,8,总偏移:,P1,k,INT,0,f,real,4,总偏移:4,P2,l,INT,0,P2,proc,2019/9/22,编译原理与技术讲义,34,a2 ;,e.g.10 过程嵌套声明(续),符号栈,偏移栈,P0,8,top,null,总偏移:,P0,i,INT,0,j,INT,4,总偏移:8,P1,k,INT,0,f,real,4,总偏移:4,P2,l,INT,0,P2,proc,P1,proc,2019/9/22,编译原理与技术讲义,35,PROC P3 ; (N),e.g.10
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理与技术 中间代码生成 编译 原理 技术 中间 代码 生成
链接地址:https://www.31doc.com/p-3734709.html