编译原理 Compiler Principles 第六章中间代码生成 湖南大学信息科学与工程学院 软件工程系杨金民 2019

Transcription

1 编译原理 Compiler Principles 第六章中间代码生成 湖南大学信息科学与工程学院 软件工程系杨金民 2019

2 什么叫语法制导的翻译 (SDT) 求表达式的值 id 1 + id 2 *id * 5 文法 :E E + E E * E id E 5 E 1 + E 4 id 1 E 2 * E 3 id 2 id 3 四者的语义相同 对于计算机执行的指令流 : E 1 = id 1 E 2 = id 2 E 3 = id 3 E 4 = E 2 * E 3 E 5 = E 1 * + E 4 对于计算器的计算结果 : 19

3 翻译之一 : 源程序 中间代码 求表达式的值 id 1 + id 2 *id * 5 文法 :E E + E E * E id E 5 E 1 + E 4 id 1 E 2 * E 3 id 2 id 3 对于计算机执行的指令流 : E 1 = id 1 E 2 = id 2 E 3 = id 3 E 4 = E 2 * E 3 E 5 = E 1 + E 4 对于计算器的计算结果 : 19 源程序是语句流, 中间代码是指令流, 都是线性结构

4 中间代码形式 源程序 高级中间表示形式 低级中间表现形式 目标代码 文法 :E E + E E * E id E 5 E 1 + E 4 id 1 E 2 * E 3 + * E 1 = id 1 E 2 = id 2 E 3 = id 3 E 4 = E 2 * E 3 E 5 = E 1 * + E 4 id 2 id 3 id 1 id 1 id 1 语法分析树 抽象语法树 三地址码

5 中间代码形式 有向无环图 DAG DAG(directed acyclic graph) 表达式 a + a * (b - c) + (b - c ) * d 的 DAG: + + * a * - d b c

6 中间代码形式 有向无环图 DAG 表达式 a + a * (b - c) + (b - c ) * d + + * * - a b c d DAG

7 DAG 与抽象语法树的联系与差异 生成抽象语法树的 SDD 产生式 1)E E 1 + T 2)E T 3)T T 1 * F 4)T F 5)F (E) 6)F id 语义规则 E.node = new Node('+', E 1.node, T.node) E.node =T.node E.node = new Node('*', T 1.node, F.node) T.node = F.node F.node = E.node F.node = new Leaf(id, id.entry)

8 产生式 1)E E 1 + T 2)E T 3)T T 1 * F 4)T F 5)F (E) 6)F id DAG 与抽象语法树的联系与差异 : 生成 DAG 的 SDD 语义规则 E.node = gennode('+', E 1.node, T.node) E.node =T.node E.node = gennode('*', T 1.node, F.node) T.node = F.node F.node = E.node F.node = gen Leaf(id, id.entry) gennode((op, left_node, right_node) { node = getnode(op, left_node, right_node); if (node == null ) then return new Node(op, left_node, right_node); else return node; 差异何在?

9 6.2 中间代码 : 三地址代码 概念计算机上执行的指令流 ( 指令序列 ), 无穷的存储器 1 运算指令 : 一个运算符, 两个运算分量, 一个运算结果 ; x = y op z 运算分量 : 名字 : 用源程序中名字作为三地址代码的地址 常量 : 源程序中出现的 ; 编译器生成的临时变量 ;

10 三地址代码 (2) 运算 / 赋值指令 :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

11 三地址代码 (3) 过程调用 / 返回 : param x1 param x2 param xn call p, n // 调用子过程 p,n 为参数个数 带下标的复制指令 :x=y[i] x[i] = y 地址 / 指针赋值指令 : x=&y, x=*y, *x=y

12 三地址码例子 语句 : do i = i + 1; while (a[i]<v); L: t 1 = i + 1 i = t 1 t 2 = i * 8 t 3 = a[t 2 ] IF t 3 < v GOTO L 符号表 id name type size 0 i integer 4 1 a float(6, integer) 2 v integer 4 3 t1 integer 4 4 t2 integer 4 5 t3 integer : 组元素的大小 ( 字节数 )

13 其它中间代码表达形式 在实现时, 还有四元式 三元式 间接三元式 静态单 赋值 ; 四元式 :op, arg1, arg2, result; 三元式 : 就是 DAG;

14 对程序的中间代码的理解 (1) 表达式 a+b*c 结合律, 交换律 带来了写程序时表达的灵活性 : 写成 b*c+a; c*b+a; a+c*b 都行 t 1 =b*c t 2 =a+t 1 识别 : 结合律, 交换律 引入了通用计算机特性 : ü 计算的单元化特性 ; ü 计算指令的序列性 ; ü 计算结果的存储性

15 对程序的中间代码的理解 (2) c=0 L 0 : if (c>10) goto L 1 goto L2 L 1 : c=c-1 if(a>b) goto L 3 goto L 4 L 3 : d=x+y goto L 5 L 4 : d=x*y goto L 5 L 5 : goto L 0 L 2 : x=1 { c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; x=1 在外形上, 层次结构变成了线性结构 控制语句的多样性, 变成了单一性 :for, do,if,while,switch if + goto

16 对程序的中间代码的理解 (3) int a[2][3], c, i, j; 表达式 c+a[i][j] 的三地址码 : t 1 = i * 12 t 2 = j * 4 t 3 = t 1 + t 2 t 4 = a[ t 3 ] t 5 = c + t 4 数组在三地址码中, 概念完全不同, 变成了 相对位置概念, 与基地址的偏移量 ( 字节数 )

17 对程序的中间代码的理解 (4) 函数调用 :n = f(x+y, x*y); 的三地址码 : t 1 = x + y t 2 = x*y param t 1 param t 2 t 3 = call f, 2 n = t 3 更加接近函数调用的实现机理

18 语义分析和中间代码生成中的数据结构 1. 中间代码表 三地址中间代码表 : nextinstr row_id tag code goto src_row_id 1 L 1 : i = j + k 2 3 生成特点 : 分析中通过栈缓存来实现了顺序调转, 只增不插 操作 : gen(get(i) '=' E.addr); gen( if (' E 1.addr ' >' E 2.addr ') goto' begin); AddLabel( begin ':'); backpatch( list, nextinstr);

19 语义分析之一 : 变量先定义后使用原则 2. 符号表 每申明一个变量, 便在符号表中添加一行 在中间代码表中, 变量的真实表达为 :V Tid.Rid 变量要先申明后使用, 因此每遇到一个变量, 都要到符号表 中检查, 检查它是否已经申明 ; 就近匹配原则, 确定是指哪个变量 ; 变量申明的重复性检查 : 同一块中申明的变量不允许同名 ; int main( ) { int p = 2; MyFun( p ); if (p > 0) { float p = 4; s = substr(s 1, p);

20 符号表的数据结构 T ID row_id name type_id offset s_row_num 1 i 符号表 : 2 j k cur_pos 中间代码中的变量, 标识形式 :V TID. RID AddVariable(id, type); 全局变量 : 符号表数量计数器 :st_num;

21 类型表和类型的项表 cur_pos TypeTable row_id name type width d_row_num 1 student record float 符号表 : item row_id type_id name type offset d_row _num 1 1 age integer tall float cur_pos

22 符号表的链表 : 每个 Block, 以 { 标识, 都有自己的符号表 S { M S N M { st = new SymbolTable(); st. prior =cst; cst = st; N { cst = cst.prior; E id { E.addr = Position(id); class SymbolTable { Table T; int TID; int cur_pos; int offset; SymbolTable* prior;

23 在符号表的链表中查找某个变量是否已经申明 position(id) { st = cst; i = st.cur_pos; find = false; while (1) { while ( i == 0 && st.prior!= null ) { st = st.prior; i = st.cur_pos; if (i == 0 && st.prior == null) ' 未定义 return null; while( i > 0 ) { if(st[i - 1].name == id) ' 找到 ' return V [st.id, i]; i-- ;

24 变量声明的 SDT D T L; L L, id; { if(nodulplicate(id)) AddVarible(id, T.type); L id; { if(nodulplicate(id)) AddVarible(id, T.type); 这个文法是 LR 的, 还是 LL 的? 下面的是书上的, 乱搞 1) F {top = new Env(); D.offset= 0 D 2) D T id; { top.put(id, T.type, offset); D 1.offset = D.offset + T.width; D 1 { D.offset = D 1.offset ; 3) D

25 变量申明时, 在当前符号表中查找变量名是否有重复现象 NoDulplicate( id ) { i = cst.cur_pos; while( i >0 ) { if(cst[i-1].name == id) ' 申明出现重名 ' return fasle; i-- ; return true;

26 申明一个变量时, 往当前符号表中添加一行, 表达该变量 AddVarible( id,type_id ) { APPEND INTO cst.table VALUES( cst.cur_pos, id, type_id, cst.offset); cst.cur_pos ++; cst.offset += width(type_id); return;

27 以 Block 为单元为局部变量分配内存 块中的局部变量 int main( ) { int p = 2; MyFun( p ); if (p > 0) { float p = 4; s = substr(s 1, p); int i ;... top p i top p i p top

28 对于每个 Block 中的局部变量, 起始时在栈中为其分配内存, 末尾时释放 S { M S N M { M.instr_pos = nextinstr; gen(null); st = new SymbolTable(); st. prior =cst; cst = st; N { if (cst.offset >0 ) { backreplace(m.instr_pos, push, cst.offset); gen('pop(', cst.offset,')'); cst = cst.prior;

29 中间代码的特性 (5) 源程序中数据 ( 变量的申明 / 定义 ) 和代码混合交叉在一起, 须要时就定义, 数据是以名字来标识 中间代码中, 数据和代码进行了分离 数据都规一到符号表中 在中间代码中, 数据的标识, 不再是名字, 而是它在符号表中的位置, 即 Tid.Rid 在机器代码中, 数据的标识, 是它的内存地址 中间代码将变量都规一到符号表中, 变量的内存地址于是就是符号表在内存的地址 ( 即基地址 )+offset 第七章再介绍

30 3. 其它数据结构 goto 标签表 操作 label =NewLabel(); AddLabel(label ':'); gen('goto' label); 全局计数器 goto 标签表 row_id tag value 1 L L 这个表仅仅只有在 LL 分析中用到, 在 LR 分析中不须要 AddLabel(label ':') 这个函数, 就是把 nextinstr 的值赋给指定的标签行的 value 字段 goto 的值, 在随后中间代码优化, 或者翻译成机器码时, 查此表, 得到它的实际值

31 观察 c=0 if (c>10) goto L 1 goto L 0 L 1 : c=c-1 if(b>c) goto L 3 goto L 2 L 3 : b=x+y if(a>b) goto L 5 goto L 4 L 3 : a=x*y L 0 : L 2 : L 4 : x=1 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; x=1 在 LL(1) 中, 对 L SL 1, 要展开 S 时, 不知道 L 1 将会是按照 L SL 1 还是 L 展开? 导致每个语句的 S.next =newlabel( );

32 c=0 if (c>10) goto L 1 goto L 0 L 1 : c=c-1 if(b>c) goto L 3 goto L 2 L 3 : b=x+y if(a>b) goto L 5 goto L 4 L 3 : a=x*y L 0 : L 2 : L 4 : x=1 观察 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; x=1 在 LL(1) 分析中, 对 L SL 1, 要展开 S 时, 就要确定 S.next 的值, 因为随后在 B 中生成 goto 语句时, 要用到 在 LR(1) 分析中不一样, 规约出 S 后,S.next 的值才确定下来, 此 时看当前输入符, 如果是 '', 说明 S 是当前块中的最后一个语句 ;

33 临时变量 临时变量 :E.addr = new temp(); 其含义是在当前符号表中, 添加一行 返回所添加的这一行的 标识 id, 即 Tid. Rid 注意 : 每申明一个变量, 也是往当前符号表中添加一行, 随后要使用这个变量时, 再基于名字 (id) 到符号表中来查出它所指的行, 返回该行的标识 id, 即 Tid. Rid, 作为中间代码中对该变量的标识

34 6.3 类型和变量声明 类型检查 (Type Checking) 规则 : 保证运算分量的类型和运算符的预期类型要匹配 翻译 : 确定变量的类型, 需要的内存空间 计算数组元素的 地址 ( 即存储空间布局 ( 相对地址 ) 类型转换 选择正确 的运算符 ;

35 类型表达式 类型表达式 (type expression) 表示类型的结构, 其定义如下 : 基本类型是一个类型表达式 如 :boolean integer,float, void 等 类名是一个类型表达式 类型构造算子作用于类型仍是类型表达式 array[ 数字, 类型表达式 ] record { < 字段类型 > 对的列表 list 类型 set 类型

36 类型表达式 从函数的角度来看待类型 : 类型构造算子 : 是用类型作为参数, 构造出新的类型 ; 从类型 s 到类型 t 的函数记作 s t; 按照函数的写法应该是 t (s) 例如 :list( ) 的结果是列表类型, 其元素的类型为 ; class Cell { int info; Cell* next; 类型名和递归类型 ; 可以给类型取名, 例如上面的 Cell 某种类型的变量,

37 数组类型的类型表达式, 及其长度求解的 SDD 产生式 T BC B int B float C [num]c 1 C 语义规则 C.inh_t = B.t C.inh_w = B.w T.t = C.t, T.w = C.w B.t = integer, B.w=4 B.t = float, B.w=8 C 1.inh_t = C.inh_t C 1.inh_w = C.inh_w C.t = array(num, C 1.t) C.t= C.inh_t C.w =C.inh_w LL 文法, 还是 LR 文法? T B t int syn syn inhc inh [ 2 ] C 1 syn sy inh [ 3 ] n C 2 例, int [2][3] 类型表达式为 array(2, array(3,integer)

38 上述 SDD 的 SDT 1)T B{C.inh_t = B.t; C.inh_w = B.w; C { T.t = C.t; T.w = C.w; 2)B int {B.t= integer; B.w = 4; 3)B float {B.t= float; B.w = 8; 4)C { C 1.inh_t = C.inh_t; C 1.inh_w = C.inh_w; [num {S.inh= num; ] C 1 { C.t = array(s.inh, C 1.t); C.w =S.inh* C 1.w S 5)C {C.t = C.inh_t; C.w = C.inh_w; 当 S 变成栈顶时, 要弹出它, 然后用它的产生式的右部倒着压入栈 中, 现在 S, 而且这个产生式中没有动作 即 S 直接出栈

39 在 LR 语法和 LR 分析中的 SDT 例如,int [2][3] 的类型表达式为 array(2, array(3,integer)) 1) T BC { T.t= B.t; T.w= B.w; while(int i=s.pop()) { B.t = array(num, B.t); T.w=T.w* i; delete s; AddType(id, T.t, T.w); 2) B int { B.t = integer; B.w = 4 3) B float { B.t = float; B.w = 8 4) C C 1 [num] { s.push(num); 5) C [num] { s = new stack(); s.push(num); s 是一个全局变量, 该方案可行吗?

40 记录类型的定义文法和 SDT T record id { I I I 1 T id; I T id; LL 文法, 还是 LR 文法? T record id { H I { UpdateWidth( Rid, I.width); I I 1 T id;{ AddItem( H.Rid, id, T.type); I.width = I 1.width +T.width; I T id;{ AddItem( H.Rid, id, T.type); I.width = T.width; H {H.Rid = AddType( id, record);

41 程序中的变量 每申明一个变量, 便在符号表中添加一行 在中间代码表中, 变量的真实表达为 :V Tid.Rid 变量要先申明后使用, 因此每遇到一个变量, 都要到符号表 中检查, 检查它是否已经申明 ; 就近匹配原则, 确定是指哪个变量 ; 变量申明的重复性检查 ; int main( ) { int p = 2; MyFun( p ); if (p > 0) { float p = 4; s = substr(s 1, p);

42 局部变量的存储布局 变量有类型概念 类型又有宽度概念, 即内存大小 (Bytes), 变量有值和地址两个两个概念 变量值放在内存中, 基于其内存地址来访问变量的值 ; 变量的类型信息存储在类型表中 ; 变量信息存储在符号表中 每个块 (block) 都有自己的符号表 ; root 块的符号表存放了所有全局变量 root 块的子块为函数块

43 变量的作用域和内存布局 scheme 在一个函数里面, 其所有局部变量放在一个连续的存储空间中, 变量在该空间的放置顺序与声明顺序一致 ; 每申明一个变量,SDT 所做处理 : 在当前块的符号表中, 检查是否出现名字重复的变量定义 ; 如果无, 则在当前符号表中, 增加一行 ( 变量实例 ): 书上的是 :top.put(id.lexeme, T.type, offset); 我们的是 :AddVarible( ); 见前面的内容

44 将表达式 三地址指令序列的 SDD 产生式 1)S id=e; 2)E E 1 + E 2 3)E -E 1 4)E (E 1 ) 5)E id 语义规则 S.code =E.code gen(top.get(id.lexeme) '=' E.addr) E.addr = new temp(), E.code =E 1.code E 2.code gen(e.addr '= E 1.addr '+' E 2.addr) E.addr = new temp() E.code =E 1.code gen(e.addr '=' 'minus' E 1.addr ) E.addr = E 1.addr E.code =E 1.code E.addr = top.get(id.lexeme) E.code =''

45 增量式翻译方案 SDT 1)S id=e; 2)E E 1 + E 2 3)E -E 1 { gen(top.get(id.lexeme) '=' E.addr); { E.addr = new temp(); gen(e.addr '= E 1.addr '+' E 2.addr); { E.addr = new temp() gen(e.addr '=' 'minus' E 1.addr ); 4)E (E 1 ) { E.addr = E 1.addr; 5)E id { E.addr = top.get(id.lexeme);

46 数组元素在中间代码中表达 一个一维数组, 元素从 0 到 n-1 编号, 在内存中依次 连续存 储 其起始地址为 base, 第 i 个元素的地址为 :base+i*w, w 为元素的类型的宽度 ; K 维数组 : 将其视为一个一维数组, 其元素的类型为一个 k- 1 维数组 A[i 1 ][i 2 ] [i k ] 的地址 : base+(( ((i 1 *n 2 +i 2 )*n 3 +i 3 ) )*n k +i k )*w 在符号表中有 A 的条项,A 的条项中记录了 A 的类型,base 就是 A 的地址 ;

47 数组元素的文法含义 L L[E] L id[e] 例如 : a[i][j] LL 文法, 还是 LR 文法? L 1 是 a 的元素, L 2 是 L 1 的元素 L 1 a [ E ] L 2 [ E ] j 数组定义 :int a[10][20], 对于数组元素 a[5][6] a.type = array(10, array(20, integer)); L 1.type = a.type.elem = array(20, integer); L 2.type = = L 1.type.elem = integer; i

48 求数组元素的偏移地址 L 2 L 是 a 的元素 L [ E ] a [ E ] i j L id[e];{ L.array = top.get(id.lexeme); L.type =L.array.type.elem; L.addr = new Temp(); gen( L.addr '=' E.addr '*' L.type.width);

49 求数组元素的偏移地址 L 是 L 1 的元素 L L 1 [ E ] a [ E ] i j L L 1 [E]; { L.array = L 1.array_id ; L.type =L 1.type.elem; t = new Temp(); L.addr = new Temp(); gen( t '= E.addr '*' L.type.width); gen( L.addr '=' L 1.addr '+' t);

50 数组元素作为因子 L 的代码只计算了偏移量 ; 数组元素的值 : L 的数组基址加上偏移量 ; 使用三地址指令 x=a[i] 5)E L { E.addr = new temp(); AddCode(E.addr '=' L.array'[' L.addr ']');

51 给数组元素赋值 使用三地址指令 a[i]=x S L = E; { gen(l.array '[' L.addr ']' '=' E.addr);

52 c int a[2][3], c, i, j; 求赋值语句 c = c+a[i][j] 的三地址码序列 addr E addr= c c S = addr a [ E addr=i ] type=array(2, array(3, integer)) addr i addr E + addr=t 5 注释语法分析树 E L L type=array(3,integer) array = a addr=t 1 addr=t 4 array = a; type=integer addr=t 3 [ E addr=j ] j addr t 1 = i * 12 t 2 = j * 4 t 3 = t 1 + t 2 t 4 = a[ t 3 ] t 5 = c + t 4 c= t 5

53 类型检查和转换 类型系统 : 编译时, 目标代码中的元素有值, 类型, 存储地址 的概念 ; 编译时就解决类型匹配问题 保证运行时, 不再存在 有关类型的问题要处理, 不会出错 : 强类型的语言 ; 编译时来发现错误, 以提高运行时效率 确定临时变量的大小 例如 float b; int i; i= &b;

54 类型检查的两种方式 类型综合例如, 对于表达式 E 1 +E 2, 已知 E 1 和 E 2 的类型, 那么运算的结果的类型是什么? 类型推导 根据语言结构的使用方式来确定该结构的类型例 :null(x) 是一个测试列表是否为空的函数, 则根据函数 null(x) 可推断出 x 必定是一个列表, 但 x 的元素类型未知 不要求名字先定义的语言需要类型推导, 如 :ML

55 类型转换 设表达式 x+i,x 为浮点数 i 为整数, 则结果应该是浮点数 x 和 i 使用不同的二进制表示方式 浮点数相加, 和整数相加使用不同的指令 t1 = (float) i t2 = x + t1

56 类型的 widening 和 narrowing Java 类型转换规则区分了拓宽转换和窄化转换 编译器自动完成的转换为隐式转换, 程序员用代码指定的转换为显式转换

57 处理类型转换的 SDT E E 1 +E 2 { E.type = max(e 1.type, E 2.type); a 1 =widen(e 1.addr, E 1.type, E.type); a 2 =widen(e 2.addr, E 2.type, E.type); E.addr = new Temp( ); gen(e.addr '=' a1 '+' a2); Addr widen(addr a, Type t, Type w) { if (t=w) return a; else if (t=integer and w= float) { temp = new Temp(); gen(temp '=' '(float)' a); return temp;

58 函数 / 运算符的重载 重载 (overload) 是面向对象程序设计语言的一个特征 例 :Java 语言中 + 算符可表示串连接或加法运算, 由操作数的类型来区分 用户自定义的函数也可以重载, 如 : Void err( ) { Void err(string S) { 通过查看参数个数, 类型, 顺序, 就能解决的函数重载问题

59 语义分析和中间代码生成 类型定义 : 放在类型表中, 有 id,name,size; 项表 : name, type, size, offset,tid, id; 变量申明 :type,name,size,offset: 先申明, 后使用 ( 包括函数 ); 同一 block 中, 变量不能重名 ; 每一个块都有自己的符号表, 变量都放到符号表中, 中间件代码不再以名字标识数据, 而用地址标识数据 ; 赋值语句, 算术表达式, 中间代码生成 ; 数组元素的中间代码表示 ; 类型检查和类型转换 : 运算结果的与宽的运算分量的看齐 ;

60 LL 分析中实现 while 语句翻译的框架 产生式 : S while(b) S 1 L 1 L 2 B S1 L 1 : if ( B ) goto L 2 goto B.false L 2 : S 1.code goto L 1 S.next: S.next 继承属性 : S.next B.false=S.next; B.true = newlabel(); 综合属性 : S.code; B.code; S.code=L 1 : B.code L 2 : S 1.code goto L 1 S.next:

61 wihile 语序例子,SDD c=20; while(c>10) c=c-1; x=1 c=20 L 0 : if (c>10) goto L 1 goto L 2 L 1 : c=c-1 goto L 0 L 2 : x=1 产生式 语义规则 S while (B) S 1 begin = newlable( ); B.true = newlable( ); B.false =S.next; S 1.next= begin; S.code =label(begin) B.code label(b.true) S.code

62 LL 分析中,while 语句的 SDT 产生式 : S while (B) S 1 产生式 : S while ( B ) Y S 1 Z c=20 L 0 : if (c>10) goto L 1 goto L 2 L 1 : c=c-1 goto L 0 L 2 : x=1 while ( { begin = newlabel(); B.true= newlabel(); B.false = S.next;S 1.next= begin; Y. label = B.true; Z.Label= begin; Z.nextLabel= S.next; AddLabel( begin ':'); B ) {AddLabel( Y.Label ':'); Y S 1 { gen(' goto' Z.Label); AddLabel( Z.nextLabel ':'); Z Y ; Z

63 LL 分析中的 if 语句 产生式 : S if (B) S 1 else S 2 L 1 B S1 L 1 : if ( B ) goto L 1 goto L 2 S 1.code L 2 S.next S2 goto S.next L 2 : S 2.code S.next: 继承属性 : S.next B.false=newLabel(); B.true =newlabel(); 综合属性 : S.code; B.code; S.code=B.code L 1 : S 1.code goto S.next L 2 : S 2.code S.next:

64 if 语句例子,SDD c=20; if (a>b) d=x+y; else d=x*y x=1 c=20 if(a>b) goto L 3 goto L 4 L 3 : d=x+y L 4 : goto L 5 d=x*y L 5 : x=1 产生式 3)S if (B) S 1 else S 2 语义规则 B.true = newlable( ); B.false = newlable( ); S 1.next= S.next; S 2.next= S.next; S.code =B.code label(b.true) S 1.code gen('goto' S.next) label(b.false) S 2.code

65 LL 分析中实现 if 语句翻译的 SDT 产生式 : S if (B) S 1 else S 2 产生式 : S if ( B) Y S 1 else Z S 2 W c=20 if(a>b) goto L 3 goto L 4 L 3 : d=x+y L 4 : goto L 5 d=x*y L 5 : x=1 if ( { B.true= newlabel(); B.false = newlabel();s 1.next= S.next; S 2.next= S.next; Y. label = B.true; Z.Label= B.false; Z.nextLabel =S.next; W. label = S.next; B) {AddLabel( Y.Label ':'); Y S 1 else { gen(' goto' Z.nextLabel); AddLabel( Z.Label ':'); Z S 2 AddLabel( W.Label ':'); Y ; Z ; W

66 表达式的类型 算术表达式 E; 优先级 :(),*/, +/- 布尔表达式 B; 优先级 :(),!,&&, 正则表达式 R; 优先级 :(),*, 联接,

67 在 LL 分析中, 布尔表达式的翻译 产生式 :S if (B)S 1 c=20; if (a>b) d=x+y; x=1 c=20 if(a>b) goto L 3 goto L 5 L 3 : d=x+y L 5 : x=1 继承属性 : S.next B.false=S.next; B.true =newlabel(); S 1.next=S.next; 三个非终结符 :S,B,S 1 S.code=B.code L 3 : S 1.code L 5 :

68 在 LL 分析中, 布尔表达式的翻译 产生式 :S if (B)S 1 else S 2 c=20; if (a>b) d=x+y; else d=x*y x=1 c=20 if(a>b) goto L 3 goto L 4 L 3 : d=x+y L 4 : goto L 5 d=x*y L 5 : x=1 继承属性 : S.next B.false=newLabel(); B.true =newlabel(); S 1.next=S.next; S 2.next=S.next; 四个非终结符 :S,B,S 1, S 2 S.code=B.code L 1 : S 1.code goto S.next L 2 : S 2.code S.next:

69 在 LL 分析中, 布尔表达式的翻译 产生式 :S while (B)S 1 c=20; while (a>b) b=x+y; x=1 c=20 L 0 : if(a>b) goto L 3 goto L 4 L 3 : b =x+y goto L 5 L 4 : x=1 继承属性 : begin= newlabel(); S.next B.false=S.next; B.true =newlabel(); S 1.next=begin; 三个非终结符 :S,B,S 1 S.code=L 1 : B.code L 3 : S 1.code goto S 1.next S.next:

70 翻译布尔表达式 B 的 SDD 产生式 语义规则 B E 1 rel.op E 2 B.code =E 1.code E 2.code gen('if' E 1.addr rel.op E 2.addr 'goto' B.true) gen('goto' B.false)

71 在 LL 分析中, 布尔表达式 :B B 1 && B 2 的翻译 if (x > 200 && x!= y) x = 0; 将其视作 :if (B 1 && B 2 ) x = 0; if x > 200 goto L 2 goto L 3 L 2 : if x!= y goto L 4 goto L 3 L 4 : x=0 L 3 : B 1 B 2 继承属性 : B 1.true =newlabel(); B 1.false = B.false; B 2.true =B.true; B 2.false = B.false;

72 翻译布尔表达式的 SDD 产生式 语义规则 B B 1 && B 2 B 1.true = newlabel( ); B 1.false = B.false; B 2.true = B.true; B 2.false = B.false; B.code =B 1.code label (B 1.true) B 2.code 注意 : 该文法不是 LL 文法, 因产生式含左递归 SDD 仅只表达了逻辑关系, 不是 SDT

73 在 LL 分析中, 布尔表达式 :B B 1 B 2 的翻译 if (x > 200 x!= y) x = 0; 将其视作 :if (B 1 B 2 ) x = 0; 三地址码如下 : if x > 200 goto L 4 goto L 5 L 5 : if x!= y goto L 4 goto L 3 L 4 : x=0 L 3 : B 1 B 2 继承属性 : B 1.true =B.true; B 1.false = newlabel(); B 2.true =B.true; B 2.false = B.false;

74 在 LL 分析中, 翻译布尔表达式的 SDD 产生式 B B 1 B 2 语义规则 B 1.true = B.true; B 1.false = newlabel( ); B 2.true = B.true; B 2.false = B.false; B.code =B 1.code label (B 1.false) B 2.code 注意 : 该文法不是 LL 文法, 因产生式含左递归 SDD 仅只表达了逻辑关系, 不是 SDT

75 在 LL 分析中, 布尔表达式的翻译例子 if (x<100 x > 200 && x!= y) x = 0; 优先级 : 先 &&, 后 S.next = L 1 ; B.true =newlabel() = L 2 ; B.false = S.next = L 1 ; B 1.true =B.true = L 2 ; B 1.false =newlabel() = L 3 ; B 2.true =B.true = L 2 ; B 2.false = B.false = L 1 ; B 2.1.true =newlabel() = L 4 ; B 2.1.false = B 2.false = L 1 ; B 2.2.true = B 2.true = L 2 ; B 2.2.false = B 2.false = L 1 ; 三地址码如下 : if x < 100 goto L 2 goto L 3 L 3 : if x >200 goto L 4 goto L 1 L 4 : if x!= y goto L 2 goto L 1 L 2 : x=0 L 1 :

76 LL 语法分析中程序文法的表达 P S 1 S if (B) S T T else S 3 S id = E 4 S while(b) S 5 S T id 6 S {L L SL L 程序 if 语句赋值语句 while 语句变量定义语句语句序列当前输入符为 或者 $, 选择 L E E+E E*E (E) id B B && B B B (B) E > E id true false

77 程序例子 c=0 L 0 : if (c>10) goto L 1 goto S (while).next L 1 : L 3 : L 4 : c=c-1 if(a>b) goto L 3 goto L 4 d=x+y goto S (if).next d=x*y goto S (if).next c=0; while(c>10) { c=c-1; if (a>b) then { d=x+y; else { d=x*y; x=1 S (if).next: goto L 0 S (while).next: x=1

78 S { L S L c = 0 S L while (B) S S c > 10 { L x = 1 S L c=c-1 S L if ( B ) S else S d=x+y d=x*y L LL 语法分析树例子 { c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; x=1

79 LL 分析中实现语句翻译的 SDT 例子 3 产生式 : P S P { S.next= newlabel(); S 产生式 : S {L P { { L.next = S.next;; S 产生式 : L S L 1 { if ( 当前输入符 =='if' 'while' ) S.next= newlabel(); L 1.next= L.next; S L 1 产生式 : L 不做任何事情, 本来是要给综合属性赋值

80 DFA 的优势 LR 语法分析实用的原因 I 4 S id = E I 0 P S S {S S if(b) S S while(b) S S id = E if id S { { I 1 P S I 2 S { S S SS S if(b) S S while(b) S S id = E S I 5 S {S S S S S if(b) S S while(b) S S id = E S I 7 S {S I 8 S SS I 3 S if( B ) S S {S S if(b) S S while(b) S if S id = E I S 6 S if( B ) S

81 LR 分析中实现控制语句翻译的 SDT 产生式 : S while(b) S 1 L 1 B LL 分析中, LR 分析中, L 2 S1 定义了继承属性 : 则定义综合属性 : S.next S.next S.nextList; B.true B.falseList; B.false B.trueList; 实现同一目标 : 生成中间代码 S.code=L 1 : B.code L 2 : S 1.code goto L 1 S.next:

82 goto 分两种 : 前向, 后向 c=20; while(c>10 a>b) c=c-1; x=1 c=20 L 0 : if (c>10) goto L 1 if (a>b) goto L 1 goto L 2 L 1 : c=c-1 goto L 0 L 2 : x=1 前向 后向 综合属性 : S.nextList; B.falseList; B.trueList 一旦变得已知, 就要记录下来, 用于回填 对 L 0, 在后面要用它, 因此要记录下来

83 对前向 goto, 使用 S.nextList, B.falseList,B.trueList 来记录要回填的行 c=20; while(c>10 a>b) c=c-1; x=1 L 0 : if (c>10) goto L 1 if (a>b) goto L 1 goto L 2 L 1 : 产生式 :S while(b) S 1 nextinstr 中间代码表 : Rid 1 c=20 code 2 if (c>10) goto X 3 if (a>b) goto X 4 goto X B 被规约出来, 得到 B.falseList = {4; B.trueList = {2,3 接下来就要生成 S 1 的代码了, 此刻,B.true= 5,B.trueList 中 goto 目标地址变成已知, 于是执行回填操作 5

84 LR 分析中, 综合属性的含义 c=20; while(c>10 a>b) c=c-1; x=1 c=20 L 0 : if (c>10) goto L 1 if (a>b) goto L 1 goto L 2 L 1 : c=c-1 goto L 0 L 2 : x=1 B B 1 B 2 B.trueList = B 1.trueList B 2.trueList B.falseList = B 2.falseList 综合属性 : B.trueList 综合属性 : B.falseList; 综合属性 : S.nextList = B.falseList;

85 LR 分析中实现 while 语句翻译的 SDT 产生式 : S while (B) S 1 产生式 : S while (M B) S 1 c=0 L 0 : if (c>10) goto L 1 if (a>b) goto L 1 goto L 5 L 1 : c=c-1 goto L 0 L 5 : x=1 S while (M B) { backpatch(b.truelist, nextinstr); S 1 { backpatch(s 1.nextlist, M.instr); gen('goto' M.instr); S.nextlist = B.falselist; M { M.instr = nextinstr ;

86 L 1 : L 3 : L 3 : a=x*y L 0 : L 2 : L 4 : x=1 LR 分析中, 一个语句的 next 变得确定的时刻 c=0 if (c>10) goto L 1 goto L 0 c=c-1 if(b>c) goto L 3 goto L 2 b=x+y if(a>b) goto L 5 goto L 4 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; x=1 在 S 规约出来之后, 看当前输入符, 如果不是, 意味着该语句后 接另一语句, 即 S SS 此时 S.next 变得确定, 就是 nextinstr; 如果是 '', 则说明是 S 是子句的末尾句, 它的.next 还不确定

87 LR 分析中, 语句与语句之间的关系 c=0 if (c>10) goto L 1 goto L 0 L 1 : c=c-1 if(b>c) goto L 3 goto L 2 L 3 : b=x+y if(a>b) goto L 5 goto L 4 L 3 : a=x*y L 0 : L 2 : L 4 : x=1 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; x=1 父子关系 :S if (B) S 1 { S.nextlist = B.falselist + S 1.nextlist; 兄弟关系 :S S 1 { backpatch(s 1.nextlist,nextInstr); S 2 {S.nextlist = S 2.nextlist;

88 LR 分析中实现 if 语句翻译的 SDT 产生式 : S if (B) S 1 else S 2 产生式 : S if (B) S 1 else S 2 if ( a>b ) goto L 1 if ( c>10 ) goto L 1 goto L 2 L 1 : d= x+y goto S.next L 2 : d= x*y S.next: S if (B) { backpatch(b.truelist, nextinstr); S 1 else { S.nextlist = merge(s 1.nextlist, makelist(nextinstr)); gen('goto _'); backpatch(b.falselist, nextinstr); S 2 { S.nextlist = merge(s.nextlist, S 2.nextlist);

89 LR 分析中实现布尔表达式翻译的回填 SDT B E 1 rel E 2 { B.truelist = makelist(nextinstr); B.falselist = makelist(nextinstr + 1); gen('if' E 1.addr rel.op E 2.addr 'goto _'); gen('goto _');

90 LR 分析中实现布尔表达式的回填翻译 SDT B B 1 && { Backpatch(B 1.truelist, nextinstr); B 2 { B.truelist = B 2.truelist; B.falselist = merge(b 1.falselist, B 2.falselist); B B 1 { Backpatch(B 1.falselist, nextinstr); B 2 { B.falselist = B 2.falselist; B.truelist = merge(b 1.truelist, B 2.truelist);

91 回填例子 :x<100 x>200 && x!=y 假设从 nextinstr = 100 开始 if (x<100 x > 200 && x!= y ) x = 0; B 1 t={100 f={101 i=102 B 5 t={100,104 f={103,105 t={104 i=104 B 4 f={103, : if x<100 goto _ 101: goto _ 102: if x>200 goto _ 103: goto _ 104: if x!=y goto _ 105: goto _ 106: x=0 107: x<100 B 2 t={102 f={103 x>200 && t={104b 3 f={105 x!=y B.code Label(B.true) S 1.code Label(B.false)

92 中间代码优化 减少 goto 指令 例 : 将 if (x<100 x > 200 && x!= y ) x = 0; 翻译成三地址 码 if x<100 goto L 2 goto L 3 L 3 : if x> 200 goto L 4 goto L 1 L 4 : if X!=y goto L 2 goto L 1 L 2 : x = 0 L 1 : 多余 iffalse x>200 goto L 1 iffalse x!=y goto L 1 if(b) S 1 B 的指令之后就是 S 1, B.true 不须要, 设为 fall

93 goto 的优化 : 在 LL 分析中,goto 的目标, 可能也是 goto c=0 L 0 : if (c>10) goto L 1 goto S (while).next L 1 : L 3 : L 4 : c=c-1 if(a>b) goto L 3 goto L 4 d=x+y goto S (if).next d=x*y S (if).next: goto L 0 S (while).next: x=1 c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; x=1

94 L 1 : L 3 : 观察 : 在 LL 分析中, 可能一行的前面有多个 goto 标签 c=0 c=0; if (c>10) goto L 1 if(c>10) { goto L 0 c=c-1; c=c-1 if (b>c) { if(b>c) goto L 3 b=x+y; goto L 2 if (a>b) { b=x+y a=x*y; if(a>b) goto L 5 goto L 4 a=x*y x=1 L 3 : L 0 : L 2 : L 4 : x=1 原因是 : 控制语句嵌套, 而且被嵌套的控制语句在其所在的块中 为最后一个语句 存在嵌套关系的三个 if 语句的 next 都是 x=1 语句 ;

95 LR 分析中实现其它语句翻译的 SDT 产生式 : S id = E S id = E; { S.nextlist =null; 产生式 : S {S 1 S {S 1 { S.nextlist =S 1.nextlist ; 产生式 : S S 1 S 2 S S 1 { backpatch(s 1.nextlist, nextinstr); S 2 { S.nextlist = S 2.nextlist;

96 我们走到哪儿了? 给定上下文无关文法 G, 在第四章, 解决了的问题 : G 是不是 LL(1) 文法, 是不是 LR(1) 文法的问题 ; 文法 LL 文法的预测分析表,LR 文法的语法分析表 语法分析器源程序生成工具 ; 语义分析, 中间代码的生成, 不是独立的环节, 而是在语法分析的过程 (LL 分析中的展开,LR 分析中的规约,) 中附带完成 ; 第五章, 在文法的产生式上加上动作, 构造 SDT 有了 SDT, 语法分析, 语义分析, 中间代码生成, 这三个工作的源程序就可由语法分析器生成工具来自动得到 ;

97 LR 语法分析中程序文法的表达 P S 1 S if (B) S 2 S if (B) S else S 3 S id = E 4 S while(b) S 5 S T id 6 S {S 7 S SS B B && B B B (B) E> E id true false E E+E E*E (E) id

98 LR 语法分析树例子 S c = 0 S { S S S S x = 1 while ( B ) S c > 10 { S S S { c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; x=1 c=c-1 if ( B ) S else S d=x+y d=x*y

99 语言的 DFA I 4 S id = E I 0 P S S {S S if(b) S S while(b) S S id = E if id S { { I 1 P S I 2 S { S S SS S if(b) S S while(b) S S id = E S I 5 S {S S S S S if(b) S S while(b) S S id = E S I 7 S {S I 8 S SS I 3 S if( B ) S S {S S if(b) S S while(b) S if S id = E I S 6 S if( B ) S

100 S { L S L c = 0 S L while (B) S S c > 10 { L x = 1 S L c=c-1 S L if ( B ) S else S d=x+y d=x*y L 对 LL 分析的观察 { c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; x=1 在 LL(1) 中,L SL 1 对于 S, 它怎么知道自己是不 是当前块中的最后一个语句?

101 观察 c=0 if (c>10) goto L 1 goto L 0 L 1 : c=c-1 if(b>c) goto L 3 goto L 2 L 3 : b=x+y if(a>b) goto L 5 goto L 4 L 3 : a=x*y L 0 : L 2 : L 4 : x=1 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; x=1 在 LL(1) 中, 对 L SL 1, 要展开 S 时, 不知道 L 1 将会是按照 L SL 1 还是 L 展开? 导致每个语句的 S.next =newlabel();

102 翻译布尔表达式的 SDD 产生式 6)B B 1 B 2 语义规则 B 1.true = B.true; B 1.false = newlabel( ); B 2.true = B.true; B 2.false = B.false; B.code =B 1.code label(b 1.false) B 2.code 产生式 6)B B 1 B 2 语义规则 if B.true = fall then B 1.true = newlabel(); else B 1.true = B.true; B 1.false = fall; B 2.true = B.true; B 2.false = B.false; if B.true = fall then B.code =B 1.code B 2.code label(b 1.true) else B.code =B 1.code label(b 1.false) B 2.code

103 求布尔表达式的值, 比如 :x= a<b S id =B 等价于 if (B) id=true else id = false; 随堂测试 : 写出在 LL 分析中的 SDT; 写出在 LR 分析中的 SDT;

104 中 布尔表达式的回填翻译 对布尔表达式 B, 因为有继承属性 ture 和 false, 自然也要引入两个综合属性 truelist: 对于 goto 指令, 如果其目标是 B.true, 则其 id( 即在三地址码表中所在的行号 ) 在 truelist 中 ; Falselist: 包含跳转指令的列表, 为 false 时执行这些指令辅助函数 : Makelist(i) : 创建一个只含 i 的列表, 返回该列表 ; Merge(p 1,p 2 ): 合并 p 1 和 p 2 两个列表, 返回合并后的列表 Backpatch(p,i): 将 i 作为 goto 目标地址, 回填到 p 所含各指令

105 布尔表达式的回填翻译 SDT 1)B true; { B.truelist = makelist(nextinstr); gen('goto _'); 2)B false; { B.falselist = makelist(nextinstr); gen('goto _'); 3)B E 1 rel E 2 { B.truelist = makelist(nextinstr); B.falselist = makelist(nextinstr + 1); gen('if' E 1.addr rel.op E 2.addr 'goto _'); gen('goto _');

106 布尔表达式的回填翻译 SDT 4)B (B 1 ); { B.truelist = B 1.truelist; B.falselist = B 1.falselist ; 5)B!(B 1 ); { B.truelist = B 1.falselist; B.falselist = B 1.truelist;

107 布尔表达式的回填翻译 SDT 6)B B 1 && { Backpatch(B 1.truelist, nextinstr); B 2 { B.truelist = B 2.truelist; B.falselist = merge(b 1.falselist, B 2.falselist); 7)B B 1 { Backpatch(B 1.falselist, nextinstr); B 2 { B.falselist = B 2.falselist; B.truelist = merge(b 1.truelist, B 2.truelist);

108 回填例子 :x<100 x>200 && x!=y 假设从 nextinstr = 100 开始 100: if x<100 goto _ 101: goto _ B 1 t={100 f={101 x<100 B 5 t={100,104 f={103,105 f={103,105 t={104 Mi=102 B 4 B 2 t={102 f={103 && M t={104 B 3 f={105 i= : if x>200 goto _ 103: goto _ 104: if x!=y goto _ 105: goto _ x>200 x!=y

109 回填例子 :x<100 x>200 && x!=y 假设从 nextinstr = 100 开始 if (x<100 x > 200 && x!= y ) x = 0; B 1 t={100 f={101 i=102 B 5 t={100,104 f={103,105 t={104 i=104 B 4 f={103, : if x<100 goto _ 101: goto _ 102: if x>200 goto _ 103: goto _ 104: if x!=y goto _ 105: goto _ 106: x=0 107: x<100 B 2 t={102 f={103 x>200 && t={104b 3 f={105 x!=y B.code Label(B.true) S 1.code Label(B.false)

110 L 1 : L 3 : 观察 : 在 LL 分析中, 可能一行的前面有多个 goto 标签 c=0 c=0; if (c>10) goto L 1 if(c>10) { goto L 0 c=c-1; c=c-1 if (b>c) { if(b>c) goto L 3 b=x+y; goto L 2 if (a>b) { b=x+y a=x*y; if(a>b) goto L 5 goto L 4 a=x*y x=1 L 3 : L 0 : L 2 : L 4 : x=1 原因是 : 控制语句嵌套, 而且被嵌套的控制语句在其所在的块中 为最后一个语句 存在嵌套关系的三个 if 语句的 next 都是 x=1 语句 ;

111 观察 : 在 LL 分析中,goto 的目标, 可能也是 goto c=0 L 0 : if (c>10) goto L 1 goto S (while).next L 1 : L 3 : L 4 : c=c-1 if(a>b) goto L 3 goto L 4 d=x+y goto S (if).next d=x*y S (if).next: goto L 0 S (while).next: x=1 c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; x=1 原因是 : 要展开 if 语句时, 无法知道它是其所在块的最后一个语句 只有当它被匹配完之后, 看到当前输入符为 '' 时, 才能知道它是其所在块中的 last 语句 但为时已晚, 因为开始时就要确定其 next

112 LR 分析中, 能克服上述两个问题 c=0 if (c>10) goto L 1 goto L 0 L 1 : c=c-1 if(b>c) goto L 3 goto L 2 L 3 : b=x+y if(a>b) goto L 5 goto L 4 L 3 : a=x*y L 0 : L 2 : L 4 : x=1 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; x=1 a=x*y; 语句规约出来后, 看当前输入符, 它是, 意味着该语句 在其所在块中是最后一个语句, 意味着它的 next 并不确定, 是其 父的 next 即其父.nextlist = 它的.next

113 c=0 if (c>10) goto L 1 goto L 0 L 1 : c=c-1 if(b>c) goto L 3 goto L 2 L 3 : b=x+y if(a>b) goto L 5 goto L 4 L 3 : a=x*y L 0 : L 2 : L 4 : x=1 LR 分析中, 一个语句的 next 变得确定的时刻 c=0; if(c>10) { c=c-1; if (b>c) { b=x+y; if (a>b) { a=x*y; x=1 一个语句要被规约出来的时候, 看当前输入符, 如果不是, 意 味着该语句在其所在的块中不是 last 语句 此时该语句的 next 变 得确定, 就是 nextinstr;

114 在 LL 分析中,goto 的目标可能也是 goto, LR 分析能优化它 c=0 L 0 : if (c>10) goto L 1 goto S (while).next L 1 : L 3 : L 4 : c=c-1 if(a>b) goto L 3 goto L 4 d=x+y goto S (if).next d=x*y S (if).next: goto L 0 S (while).next: x=1 c=0; while(c>10) { c=c-1; if (a>b) d=x+y; else d=x*y; x=1 此例中 S while(b) S 1 ; 这里 S 1 {S 2, S 2 S a S b,s b 是 if 语句 是其所在块的 last 语句, 因此 S b.next = S 2.next =S 1.next =L 0 当 S b 要规约出来时, 因当前输入符是, 意味着 S 1 到了末尾

115 其它语句的回填 (3) S A; { S.nextlist =null; S {S 1 { S.nextlist =S 1.nextlist ; S S 1 { backpatch(s 1.nextlist, nextinstr); S 2 { S.nextlist = S 2.nextlist;

116 Break Continue 语句 break,continue 语句只能用在循环语句中, 如 while 中 否则就是语法错误 这是一个上下文相关问题 ; 因此, 不存在用产生式来表达, 属于语义分析中的内容 ;

117 Break Continue 的翻译方案 循环语句可能嵌套, 因此要设一个全局的循环标志栈 每进入一个循环语句时, 就将其 begin 压入该栈中, 规约时, 从该栈中弹出 当遇到一个 break/continue 语句时, 如果循环标志栈为空 ; 则表明当前不在循环语句中, 出现了语法错误 ;

118 Break Continue 的翻译方案 (cont.) 另有全局变量 :list * breaklist 每遇到一个 break 语句时, breaklist =merge(breaklist, makelist(nextinstr)); 然后生成一条悬空 goto 语句 :Gen('goto _'); 每遇到一个 continue 语句, 则生成一条 goto 语句 :Gen('goto' element[top]); 当规约出一个循环语句 S 时 : 1) 从栈中弹出当前循环语句的 begin; 2) S->nextlist =merge(s->nextlist, breaklist); 3) 复位 breaklist:s_breaklist = null;

119 6.8 switch 语句的 SDT switch 语句结构 : switch (E) { case V 1 : S 1 ; case V 2 : S 2 ; case V n-1 :S n-1 ; default: S n ; 其文法 :S switch(e) {T default: S T T case E: S case E: S

120 翻译法 1 T=E L 1 : if T V 1 goto L 2 S 1 的代码 goto next L 2 : if T V 2 goto L 3 S 2 的代码 goto next L 3 : L n-1 : if T V n-1 goto L n S n-1 的代码 goto next L n : next: S n 的代码

121 翻译法 2 L 1 : L n-1 : L n : T=E goto test 关于 S 1 的中间码 goto next 关于 S n-1 的中间码 goto next 关于 S n 的中间码 goto next test: if T=V 1 goto L 1 if T=V 2 goto L 2... if T=V n-1 goto L n-1 goto L n next:

122 用来翻译 switch 语句的 case 三地址代 码指令 Case t V 1 L 1 Case t V 2 L 2 Case t V n-1 L n-1 Case t t L n next:

123 函数及其调用的中间代码 在三地址码中, 函数调用被拆分为准备进行调用时的参数求值, 然后是调用本身 设 a 为 int 类型的数组, n = f(a[i]); 的三地址码 : t 1 =i*4 t 2 =a[t 1 ] param t 2 t 3 = call f, 1 n = t 3

124 函数定义和调用的文法,SDT 函数定义文法 :F T id(p) {S P P, T id T id 函数调用文法 : E id(a) A A, E E 语义分析 :1) 函数先定义, 后调用 ; 要有可区分性 ; 2) 函数返回值要与函数的类型一致 ; 3) 函数调用, 参数要匹配 ; 同理, 要建立函数定义表, 和函数参数表, 来实现上述语义分析 ; 请写出实现上述语义分析的 SDT;

125 过程调用的翻译 翻译方法 : 把实参的地址逐一放在转子指令的前面. 例如, CALL S(A,X+Y) 翻译为 : t 1 =X+Y param A /* 第一个参数的地址 */ param t1 /* 第二个参数的地址 */ call S, 2 /* 转子 */

126 第六章中间代码生成 语义分析和中间代码生成 中间代码表示 类型检查和翻译 中间代码生成 DAG 图 三地址码 静态单赋值 表达式翻译 控制流翻译 回填 过程翻译

127 谢谢谢谢!