编译原理 第7,8章

1、Compiler Construction Principles 语义分析的任务：语义分析的任务： 静态语义审查静态语义审查 审查每个语法结构的静态语义审查每个语法结构的静态语义, 即验证语法结构合法的程序即验证语法结构合法的程序,是否是否 真正有意义。真正有意义。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 例如例如: 赋值语句赋值语句 X:=A+B* *C 对运算对象进行类型检查对运算对象进行类型检查, 对变对变 量进行先定义后使用检查量进行先定义后使用检查 如果静态语义正确如果静态语义正确

2、, 语义处理则要语义处理则要 执行真正的翻译执行真正的翻译, 即生成程序的某种中即生成程序的某种中 间代码的形式或直接生成目标代码。间代码的形式或直接生成目标代码。 执行真正的翻译执行真正的翻译 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 且采用语法制导翻译法且采用语法制导翻译法 完成对语法成完成对语法成 分的翻译工作分的翻译工作。它不是一种形式系统它不是一种形式系统, 但它比较接近形式化。但它比较接近形式化。 目前多数编译程序使用目前多数编译程序使用属性文法为工具属性文法为工具 来描述程序设计

3、语言的语义。来描述程序设计语言的语义。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles (1) 属性属性 对文法的每一个符号对文法的每一个符号, 引进一些属引进一些属 性性, 这些属性代表与文法符号相关的信这些属性代表与文法符号相关的信 息息, 如类型、值、存储位置等。与属性如类型、值、存储位置等。与属性 相关的信息相关的信息, 即属性值即属性值,可以在语法分析可以在语法分析 过程中计算和传递。过程中计算和传递。 1. 属性文法属性文法 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术

4、和中间代码生成 Compiler Construction Principles 属性分为两类属性分为两类: 综合属性综合属性其计算规则按其计算规则按“自下而上自下而上”方方 式进行式进行, 即规则左部符号的某些属性根即规则左部符号的某些属性根 据其右部符号的属性和据其右部符号的属性和(或或)自己的其他自己的其他 属性计算而得。属性计算而得。 属性加工的过程即是语义的处理过程。属性加工的过程即是语义的处理过程。 综合属性和继承属性综合属性和继承属性。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles

5、继承属性继承属性其计算规则按其计算规则按“自上而下自上而下”方方 式进行式进行, 即规则右部符号的某些属性根即规则右部符号的某些属性根 据其左部符号的属性和据其左部符号的属性和(或或)右部其他符右部其他符 号的某些属性计算而得。号的某些属性计算而得。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles (2) 属性文法属性文法AG=(G,V,E) 为文法的每一个产生式配备的计算属为文法的每一个产生式配备的计算属 性的计算规则性的计算规则, 称为称为语义规则语义规则(描述语义描述语义 处理的加工动作处理的

6、加工动作) 。 属性文法包含一个上下文无关文法属性文法包含一个上下文无关文法G 和一系列和一系列语义规则语义规则E。 语义规则语义规则: 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 这些语义规则附在文法的每个产生这些语义规则附在文法的每个产生 式上式上,在语法分析过程中在语法分析过程中, 执行语义规则执行语义规则 描述的动作描述的动作, 从而实现语义处理。也就从而实现语义处理。也就 是说是说, 附在文法的每个产生式上语义规附在文法的每个产生式上语义规 则描述了语义处理的加工动作。则描述了语义处理

7、的加工动作。 目前流行的语义描述和语义处理的目前流行的语义描述和语义处理的 方法主要是属性文法和语法制导翻译方方法主要是属性文法和语法制导翻译方 法。法。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles S Axy 语义处理的语义处理的 加工动作加工动作 语法制导翻译法使用属性文法为工具语法制导翻译法使用属性文法为工具 来说明程序设计语言的语义来说明程序设计语言的语义。 Compiler Construction Principles 为文法每一产生式设计相应的求值的语义为文法每一产生式设计相应的求

8、值的语义 描述描述(语义动作语义动作)： 例如，设有简单算术表达式的文法：例如，设有简单算术表达式的文法： EEE | E* *E | (E) | digit 1.E E(1)E(2) E.val E(1).val E(2).val 2.E E(1)* *E(2) E.val E(1).val* *E(2).val 3.E (E(1) E.val E(1).val 4.E digit E.val Lex.digit 7+8* *8,3+8,6* *8, Compiler Construction Principles E.val = 47 E.val = 8 E.val = 40 E.val

9、= 7 E.val = 8 + 8 * 8 7 1.E E(1)E(2) E.val E(1).val E(2).val 2.E E(1)* *E(2) E.val E(1).val*E(2).val 3.E (E(1) E.val E(1).val 4.E digit E.val Lex.digit 句子句子 7+8* *8 E E E E E Compiler Construction Principles 2. 语法制导翻译法语法制导翻译法 为文法的每个产生式都配备一个语义为文法的每个产生式都配备一个语义 动作或语义子程序。动作或语义子程序。 在语法分析的过程中，每当使用一条在语法分析的

10、过程中，每当使用一条 产生式进行推导或归约时，就执行相应产生式进行推导或归约时，就执行相应 产生式的语义动作产生式的语义动作, 从而实现语义处理。从而实现语义处理。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 (1) 语法制导翻译法语法制导翻译法 的基本思想的基本思想 Compiler Construction Principles (2) 语法制导翻译法语法制导翻译法 在语法分析过程中，依随分析的过程，在语法分析过程中，依随分析的过程， 根据每个产生式所对应的语义子程序根据每个产生式所对应的语义子程序(或或 语义规则描述的语义处理的加工动作语义规则描述的语义

11、处理的加工动作)进进 行翻译的方法。行翻译的方法。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 自底向上分析法自底向上分析法 自顶向下分析法自顶向下分析法 Compiler Construction Principles LR分析法语法制导分析实现方法分析法语法制导分析实现方法 l1 为产生式设计语义动作为产生式设计语义动作 l2 建立分析表建立分析表 l3 扩充扩充LR分析栈分析栈 l4 修改总控程序修改总控程序 Compiler Construction Principles 3. 编译中常用的中间代码编译中常用的中间代码: 逆波兰式逆波兰式四元式四元式

12、三元式三元式树形表示树形表示 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 逆波兰式逆波兰式 逆波兰式除去了原表达式中的括号，逆波兰式除去了原表达式中的括号， 并将运算对象写在前面，运算符写在后并将运算对象写在前面，运算符写在后 面，因而又称为后缀式。面，因而又称为后缀式。 例如：例如：逆波兰式逆波兰式 a* *bab* * (a+b)* *( (c+d)ab+cd+* * 中缀表达式中缀表达式 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Con

13、struction Principles 逆波兰式表示法同中缀表示法相比其逆波兰式表示法同中缀表示法相比其 优点是优点是: 不再有括号不再有括号,且运算符出现的顺序体且运算符出现的顺序体 现了中缀表达式现了中缀表达式 的运算顺序的运算顺序 2. 易于计算机处理易于计算机处理 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 一般表达式计值时，要处理两类符一般表达式计值时，要处理两类符 号，一类是运算对象，另一类是运算符，号，一类是运算对象，另一类是运算符， 通常用两个工作栈分别处理。但处理用通常用两个

14、工作栈分别处理。但处理用 逆波兰式表示的表达式却只用一个工作逆波兰式表示的表达式却只用一个工作 栈。栈。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 当计算机自左到右顺序扫描逆兰波当计算机自左到右顺序扫描逆兰波 式时，若当前符号是运算对象则进栈，式时，若当前符号是运算对象则进栈， 若当前符号是运算符，设为若当前符号是运算符，设为K元运算符，元运算符， 则将栈顶的则将栈顶的K个元素依次取出，同时进个元素依次取出，同时进 行行K元运算，并将运算结果置于栈顶，元运算，并将运算结果置于栈顶， 表达式处理

15、完毕时，其计算结果自然呈表达式处理完毕时，其计算结果自然呈 现在栈顶。现在栈顶。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 逆波兰式逆波兰式ab+cab+c* *的处理过程如下图：的处理过程如下图： b aT1 c T1T2 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 逆波兰形式可以推广到其他语法结构：逆波兰形式可以推广到其他语法结构： 赋值语句赋值语句 V=E 逆波兰式逆波兰式 VE= 条件语

16、句条件语句逆波兰式逆波兰式 if E S1 ; else S2ES1S2￥ 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 三元式和树形表示三元式和树形表示 三元式主要由三部分组成：三元式主要由三部分组成： （OP，arg1, arg2） 其中其中OP是运算符，是运算符， arg1,arg2分别是第一和第二两个运算对象。分别是第一和第二两个运算对象。 当当OP是一目运算时，常常将运算对象定是一目运算时，常常将运算对象定 义为义为arg1。 第第8 8章章 语法制导翻译技术和中间代语法制导翻译技术和中

17、间代 码生成码生成 Compiler Construction Principles 例如例如 a+ +b* *c 的的 三元式序列：三元式序列： (1) ( * * , b , , b , c ) (2) ( + , a , + , a , (1) ) 运算对象是指向符号表的某一项或指向运算对象是指向符号表的某一项或指向 三元式表的某一项。三元式表的某一项。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 1. 三元式出现的顺序和语法成份的三元式出现的顺序和语法成份的 计值顺序相一致。计值顺序相一

18、致。 三元式的特点：三元式的特点： 2. 三元式之间的联系是通过指示器三元式之间的联系是通过指示器 实现的。实现的。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 树形表示树形表示 A * * B + C* *D + C * A * BD 末端结点表示一个运算对象末端结点表示一个运算对象, 每一个内每一个内 结点表示一个一元或二元运算符。结点表示一个一元或二元运算符。 树形表示是三元式的翻版树形表示是三元式的翻版 (3)+ (1)*(2)* CABD 第第8 8章章 语法制导翻译技术和中间代码生成

19、语法制导翻译技术和中间代码生成 Compiler Construction Principles 四元式主要由四部分组成：四元式主要由四部分组成： （OP，arg1, arg2, result） 其中其中OP是运算符，是运算符， arg1,arg2分别是第一和第二两个运算对象。分别是第一和第二两个运算对象。 当当OP是一目运算时，常常将运算对象定义是一目运算时，常常将运算对象定义 为为arg1。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 四元式的第四个分量四元式的第四个分量result是编译程

20、序是编译程序 为存放中间运算结果而临时引进的变量，为存放中间运算结果而临时引进的变量， 常称为临时变量，如常称为临时变量，如Ti，也可以是用户，也可以是用户 自定义变量，如自定义变量，如X。 例如例如 X a* *bc/d 的的 四元式序列：四元式序列： (1) ( * *, a, b, T1 ) (2) ( / /, c, d, T2 ) (3) ( + +, T1, T2, T3 ) (4) ( = =, T3, - -, X ) 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 2. 四元式之间

21、的联系是通过临时变量实四元式之间的联系是通过临时变量实 现的，这样易于调整和变动四元式。现的，这样易于调整和变动四元式。 1. 四元式出现的顺序和语法成份的计值四元式出现的顺序和语法成份的计值 顺序相一致。顺序相一致。 四元式的特点：四元式的特点： 3. 便于优化处理。便于优化处理。 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 编译系统中，有时将四元式表示成另一编译系统中，有时将四元式表示成另一 种更直观，更易理解的形式种更直观，更易理解的形式三地址代三地址代 码或三地址语句。码或三地址语句。

22、result : arg1 OP arg2 三地址语句三地址语句:语句中是三个量的赋值语句语句中是三个量的赋值语句, 每个量占一个地址。每个量占一个地址。 三地址代码形式定义为：三地址代码形式定义为： 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 例如例如 X a* *bc/d 的的 四元式序列：四元式序列： (1) ( * *, a, b, T1 ) (2) ( / /, c, d, T2 ) (3) ( + +, T1, T2, T3 ) (4) ( = =, T3, - -, X ) 相应的

23、三地址语句序列为：相应的三地址语句序列为： （1）T1a* *b （2）T2c/d （3）T3T1T2 （4）XT3 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 例例1. a + b * * ( c + d )的逆波兰式的逆波兰式 a bc d + * * + 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles t1= a t2= c t3= t2 + d t8= t1+ t4 a + b * * ( c

24、 + d )的四元式表示的四元式表示 t4= b* * t3 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles i( i /( /( i i ) )的逆波兰式的逆波兰式 i( i /( /( i i ) )的四元式的四元式 t1= i i t2= i / / t1 t3= i t2 i i i i / 例例2. 第第8 8章章 语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 Compiler Construction Principles 4. 采用自下而上的语法制导翻译法语义采用自下而

25、上的语法制导翻译法语义 动作的设计动作的设计 （1）搞清楚）搞清楚源结构和目标结构源结构和目标结构 （2）自下而上的语法制导翻译特点：）自下而上的语法制导翻译特点： 栈顶形成句柄，栈顶形成句柄，归约时执行相应语义归约时执行相应语义 动作动作 （3）给出从源结构到目标结构的）给出从源结构到目标结构的变换变换 方法方法 第第8 8章章 语法制导翻译技术和中间代语法制导翻译技术和中间代 码生成码生成 Compiler Construction Principles 例1. 设文法及其相应的语义动作如下: SbTc print “1” Sa print “2” TR print “3” RR/S pr

26、int “4” RS print “8” 采用自下而上语法制导翻译,给出输入串 bR / bTc / bSc / ac的翻译结果 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles 分析: 首先对输入串 bR / bTc / bSc /ac画 出语法树: S c Tb R S/R /R S/R cTb a S c Tb R S 再考虑归约时 执行相应语义 动作 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles S c Tb R S/R /R S/R cTb a S c Tb R S

27、 SbTc print “1” Sa print “2” TR print “3” RR/S print “4” RS print “8” 14 翻译结果为: 83142431 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles S c Tb R S/R /R S/R cTb a S c Tb R S RR/S SbTc Sa TR RS 输出为: 1483142431 输入是bR / bTc / bSc /ac 给出相应语义动作(翻 译方案) print “1” print “2” print “3” print “4” print “

28、8” 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles 例2 简单算术表达式求值的语义描述 例如，设有简单算术表达式的文法： EEE | E*E | (E) | digit 1.E E(1)E(2) E.val E(1).val E(2).val 2.E E(1)*E(2) E.val E(1).val*E(2).val 3.E (E(1) E.val E(1).val 4.E digit E.val Lex.digit 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles 例3 简

29、单算术表达式翻译到四元式的 语义描述 例如，设有简单算术表达式的文法： EEE | E*E | (E) | i 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles E EE E*E (E) | i 源结构目标结构 （1）T1a*b （2）T2c*d （3）T3T1T2 a*bc*d 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles 语义函数 emit（Targ1 OP arg2） 功能是生成一个三地址语句，并送 到输出文件中。 语义函数 newtemp( ) 功能是产生一个新的临时

30、变量名字， 并回送新的临时变量名的整数码。 如T1，T2等。 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles (2) 不进符号表，临时变量单词值部 分用整数码表示。 (1) 送到符号表。 对临时变量有两种不同的处理方法: 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles 语义过程 Lookup（） 功能是审查是否出现在符号表中， 在则返回其指针，否则返回NULL。 语义变量 E.place 表示存放非终结符E值的变量名在符号 表中的入口地址或临时变量名的

31、整数码。 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles 1. E E(1) E(2) 2. E E(1) * E(2) E.place newtemp( ); emit(E.placeE(1).place E(2).place ) E.place newtemp( ); emit(E.placeE(1).place*E(2).place ) 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles 3. E （E(1)） E.place E(1).place； 4. E i p Lo

32、okup (); if (p != NULL) E.place p; else error( ); 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles 3. 算术表达式a+b*c翻译到三地址语句的过程： 03 0 $ $a 01$E 014$E+ 0143$E+b a a a 状态栈符号栈语义栈输入串 a+b*c$ +b*c$ +b*c$ b*c$ *c$ 变量在符号表的 入口用变量本身 表示 第8章 语法制导翻译技术和中间代 码生成 EEE | E*E | (E) | i Compiler Construction Prin

33、ciples 9 0 状 态 ACTIONGOTO + i * ()$E S3 S9S8S4 S2S3 S2S3 S8S4 S2 S8 S2S3 r4r4r4r4 r1r1r1 r2 r3 r2 r3r3 r2r2 r3 1 2 3 4 8 6 7 8 1 6 7 8 acc 2.为文法构造LR分析表如下图： 第8章 语法制导翻译技术和中间代 码生成 Compiler Construction Principles *c$ c$ $ $ $ $ t1=b*c t2=a+t1 状态栈符号栈语义栈输入串 01478 0147$E+E $E+E* 014783$E+E*c 014788$E+E*E

34、0147$E+E 01$E ab abc at1 ab ab t2 acc 第8章 语法制导翻译技术和中间代 码生成 EEE | E*E | (E) | i Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 一.布尔表达式的文法 计算逻辑值 程序设计语言中布尔表达式有两个作用: 用作控制语句中的条件式 布尔表达式是由布尔算符(、和) 施于布尔变量或关系表达式而成。 Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 对某些语言,如 PL / 1,允许更通用的表 达式

35、,其中,布尔算符、算术算符和关系算 符可施于任何类型的表达式,并不区别布 尔值和算术值。 为简单起见,只考虑如下文法生成的 布尔表达式: Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 E E (1) E (2) E E (1) E (2) E E (1) E ( E (1) ) E i (1) rop i (2) E true E false E i Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 二. 布尔表达式的计值方法 1. 如同计算算术表达式一样,步

36、步计 算出各部分真、假值,最后计算出整个表 达式的值。 2. 根据布尔运算的特殊性,采取某种 优化措施,可避免计算整个表达式的值。 Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 AB 解释成 AB 解释成 A 解释成 if A then true else B if A then B else false if A then false else true 三. 布尔表达式的翻译方法 1. 同翻译算术表达式一样,翻译布尔表达式。 Compiler Construction Principles 布尔表达式到四元式的翻译布尔表

37、达式到四元式的翻译 1. E E (1) E (2) E.place newtemp( )； emit ( E.place E(1).placeE(2).place ) 2. E E (1) E (2) E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 3. E ( E (1) ) E.place E(1).place； 4. E i (1) rop i (2) E.place newtemp( )； emit (i

38、f i (1).place rop.op i (2).place goto next+3); emit ( E.place 0 ); emit ( goto next+2); emit ( E.place 1 ); Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 8. E true E.place newtemp( )； emit ( E.place 1) E.place newtemp( )； emit ( E.place 0) 6. E false 或 E.place i . place； 6. E i Compiler

39、Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 例如布尔表达式 a = bc d 对应如 下四元式序列: 101 if a = b goto 104 102 t1= 0 103 goto 108 104 t1= 1 108 t2= c d 106 t3 = t1 t2 Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 2. 控制语句中布尔表达式的翻译 条件语句的语法为: 根据条件语句的语义,条件语句的代码结构为: if E then S(1) else S(2) E的代码 S(1

40、)的代码 S(2)的代码 Jump out out: 真 假 Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 E是布尔表达式,根据布尔运算的特殊 性,布尔表达式的目标结构为: 假 E(1)的代码 E(2)的代码 真 S(1)S(2) 真假 真 E(1)的代码 E(2)的代码 假 S(2)S(1) 假真 Compiler Construction Principles (1) 真出口和假出口: 真出口表示布尔表达式E为真时控制 流向的转移目标 假出口表示布尔表达式E为假时控制 流向的转移目标 布尔表达式到四元式的翻译布尔表达式到

41、四元式的翻译 Compiler Construction Principles (2) 作为条件转移的E,把E翻译成的代码 是一串条件转或无条件转的四元式 对于E为 a rop b 的形式生成代码为: if a rop b goto 真出口 goto 假出口 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 Compiler Construction Principles (q) 例如语句 if a bc d then S(1) else S(2) 的四元式为: 100 if a b goto 104 101 goto 102 102 if c d goto 104 103 goto ( p+

42、1) 104 ( 关于 S(1) 的四元式) (p) goto (q) (p+1) ( 关于 S(2) 的四元式) E(1)的真出口 为104, E(1)的 假出口为102 E(2)的真出口 为104, E(2)的 假出口为(p+1) E的真出口 为104, E的 假出口为 (p+1) 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 布尔表达式的真、假出口不能在产生其 四元式的同时得知 例如 E(1)的真出口为104需分析到S(1)时才 能得知,因此 E.tr: 记录表达式 E

43、 所对应的四元式需回 填真出口的四元式的地址所构成的链 E.fa: 记录表达式 E 所对应的四元式需回 填假出口的四元式的地址所构成的链 (3) 设置两个语义变量: Compiler Construction Principles (q) 例如语句 if a bc d then S(1) else S(2) 的四元式为: 100 if a b goto 104 101 goto 102 102 if c d goto 104 103 goto ( p+1) 104 ( 关于 S(1) 的四元式) (p) goto (q) (p+1) ( 关于 S(2) 的四元式) 布尔表达式到四元式的翻译布尔

44、表达式到四元式的翻译 E(1).tr=100, E(1).fa=101 E(2).tr=102, E(2).fa=103 Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 E.fa=103; E.tr=100和102所构成的链 E(1) E(2)归约E时, Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 把以 p1, p2为链首的两条链合并为一, 返回合并后的链首 (4) 链结函数和回填函数: merg (p1, p2) : Compiler Construct

45、ion Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 merg (int p1, int p2) if p2=0 return( p1 ) ; else p= p2 ; while ( 四元式p的第四分量内容不为0) p=四元式p的第四分量内容; 把p1填进四元式p的第四分量; return( p2 ) ; Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 r1 ( 0 ) q1 ( r1 ) q2 ( r2 ) p1 ( q1 ) r2 ( 0 ) p2 ( q2 ) p1 Compiler Cons

46、truction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 merg (int p1, int p2) if p2=0 return( p1 ) ; else p= p2 ; while ( 四元式p的第四分量内容不为0) p=四元式p的第四分量内容; 把p1填进四元式p的第四分量; return( p2 ) ; 100 102 102 Compiler Construction Principles (q) 例如语句 if a bc d then S(1) else S(2) 的四元式为: 100 if a b goto 0 101 goto 102 102 i

47、f c d goto 100 103 goto ( p+1) 104 ( 关于 S(1) 的四元式) (p) goto (q) (p+1) ( 关于 S(2) 的四元式) 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 bp ( int p, int t ) : 将 p 所链结的每个四元式的第四 区分量都回填 t ; Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 bp ( int p, int t ) q=p

48、; while (q != 0 ) r = 四元式 q 的第四分量内容; 把 t 填进四元式 q 的第四分量; q=r ; 10 2 10 4 10 0 0 10 2 10 0 Compiler Construction Principles (q) 例如语句 if a bc d then S(1) else S(2) 的四元式为: 100 if a b goto 104 101 goto 102 102 if c d goto 104 103 goto ( p+1) 104 ( 关于 S(1) 的四元式) (p) goto (q) (p+1) ( 关于 S(2) 的四元式) 布尔表达式到四元

49、式的翻译布尔表达式到四元式的翻译 Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 (8) 为及时回填转移地址, 使用语义变量 E.code 记录表达式E的第一个四元式语句 序号。 (6) 定义语义变量 next 为四元式表指针。 E (1).code=100 E (2).code=102 E .code=100 Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 布尔表达式语义动作的设计 1. E E (1) E (2) bp( E(1).fa, E(2).cod

50、e) ； E.code= E(1).code ; E.tr=merg( E(1).tr, E(2).tr ) ; E.fa= E(2).fa ; Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 布尔表达式语义动作的设计 2. E E (1) E (2) bp( E(1).tr, E(2).code) ； E.code= E(1).code ; E.tr= E(2).tr ; E.fa=merg( E(1).fa, E(2).fa ) ; Compiler Construction Principles 布尔表达式语义动作的设计

51、 3. E ( E (1) ) E.code= E(1).code ; E.tr=E(1).tr ; E.fa= E(1).fa ; 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 Compiler Construction Principles 布尔表达式语义动作的设计 4. E i (1) rop i (2) E.tr= next ; E.code= next ; E.fa= next+1; emit ( if i (1).place rop.op i (2).place goto _ ) ; emit( goto _ ) ; 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 Compi

52、ler Construction Principles 布尔表达式语义动作的设计 8. E true E.tr= next ; E.code= next ; emit( goto _ ) ; 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 布尔表达式语义动作的设计 6. E false E.fa= next ; E.code= next ; emit( goto _ ) ; Compiler Construction Principles 布尔表达式到四元式的翻译布尔表达式到四元式的翻译 布尔表达式语义动作的设计 8. E i E.tr= next ; E.fa=