《编译原理语义分析与中间代码生成.ppt》由会员分享，可在线阅读，更多相关《编译原理语义分析与中间代码生成.ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院语义分析与中间代码生成vv复习：编译程序的逻辑过程复习：编译程序的逻辑过程复习：编译程序的逻辑过程复习：编译程序的逻辑过程vv按照编译程序的逻辑工作过程，语法分析后，接下来就要进按照编译程序的逻辑工作过程，语法分析后，接下来就要进按照编译程序的逻辑工作过程，语法分析后，接下来就要进按照编译程序的逻辑工作过程，语法分析后，接下来就要进行语义分析了，语义分析后，再生成中间代码。实际应用中，行语义分析了，语义分析后，再生成中间代码。实际应
2、用中，行语义分析了，语义分析后，再生成中间代码。实际应用中，行语义分析了，语义分析后，再生成中间代码。实际应用中，往往在语法分析的同时，进行语义分析并生成中间代码，这往往在语法分析的同时，进行语义分析并生成中间代码，这往往在语法分析的同时，进行语义分析并生成中间代码，这往往在语法分析的同时，进行语义分析并生成中间代码，这就是语法制导翻译法。就是语法制导翻译法。就是语法制导翻译法。就是语法制导翻译法。vv语法制导翻译过程中，需要借助于属性文法进行语义描述和语法制导翻译过程中，需要借助于属性文法进行语义描述和语法制导翻译过程中，需要借助于属性文法进行语义描述和语法制导翻译过程中，需要借助于属性文法
3、进行语义描述和语义处理。语义处理。语义处理。语义处理。vv本章内容：本章内容：本章内容：本章内容：属性文法有关概念；属性文法有关概念；属性文法有关概念；属性文法有关概念；语法制导翻译基本思想；语法制导翻译基本思想；语法制导翻译基本思想；语法制导翻译基本思想；中间代码形式；中间代码形式；中间代码形式；中间代码形式；简单算术表达式、布尔表达式、赋值语句、条件语句、循环语句的翻简单算术表达式、布尔表达式、赋值语句、条件语句、循环语句的翻简单算术表达式、布尔表达式、赋值语句、条件语句、循环语句的翻简单算术表达式、布尔表达式、赋值语句、条件语句、循环语句的翻译。译。译。译。编译原理编译原理编译原理编译原
4、理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院属性文法属性文法表达式文法表达式文法表达式文法表达式文法 ET+T|T or T ET+T|T or T Tn|b Tn|b E E E ET T T T1 1 1 1+T+T+T+T2 2 2 2 T T T T1 1 1 1.type=int .type=int .type=int .type=int T T T T2 2 2 2.type=T.type=T.type=T.type=T1 1 1 1.type .type .type .type E.type=
5、int E.type=int E.type=int E.type=int E E E E T T T T1 1 1 1 or Tor Tor Tor T2 2 2 2 T T T T1 1 1 1.type=bool.type=bool.type=bool.type=bool T T T T2 2 2 2.type=T.type=T.type=T.type=T1 1 1 1.type.type.type.type E.type=bool E.type=bool E.type=bool E.type=bool T T T T n T.type=int n T.type=int n T.type=
6、int n T.type=int T T T T b T.type=bool b T.type=bool b T.type=bool b T.type=bool 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院属性文法属性文法vv对于某个压缩了的文法，当把每个文法符对于某个压缩了的文法，当把每个文法符号和一组属性相关联，并把产生式附加以号和一组属性相关联，并把产生式附加以语义规则的时候，就得到属性文法。语义规则的时候，就得到属性文法。vv语法制导的翻译过程：由于属性文法的规语法制导
7、的翻译过程：由于属性文法的规则和产生式是一一对应的关系，所以，由则和产生式是一一对应的关系，所以，由属性文法确定的语义分析可以在语法分析属性文法确定的语义分析可以在语法分析的过程中进行。这个过程称为语法制导的的过程中进行。这个过程称为语法制导的翻译。翻译。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院属性文法属性文法(attribute grammar)A=(G,V,F),A=(G,V,F),其中其中其中其中 G:G:一个一个一个一个CFG,CFG,属性文法的基础。属性文法的基础
8、。属性文法的基础。属性文法的基础。V:V:有穷的属性集有穷的属性集有穷的属性集有穷的属性集vv每个属性与一个文法符号相关联每个属性与一个文法符号相关联每个属性与一个文法符号相关联每个属性与一个文法符号相关联vv这些属性代表与文法符号相关的语义信息这些属性代表与文法符号相关的语义信息这些属性代表与文法符号相关的语义信息这些属性代表与文法符号相关的语义信息如类型、地址、值、代码、符号表内容等等如类型、地址、值、代码、符号表内容等等如类型、地址、值、代码、符号表内容等等如类型、地址、值、代码、符号表内容等等vv属性与变量一样，可以进行计算和传递属性与变量一样，可以进行计算和传递属性与变量一样，可以进
9、行计算和传递属性与变量一样，可以进行计算和传递vv属性加工的过程即是语义处理的过程属性加工的过程即是语义处理的过程属性加工的过程即是语义处理的过程属性加工的过程即是语义处理的过程vv属性加工与语法分析同时进行属性加工与语法分析同时进行属性加工与语法分析同时进行属性加工与语法分析同时进行vv属性的表示：属性的表示：属性的表示：属性的表示：标识符（或数），写在相应文法的下边标识符（或数），写在相应文法的下边标识符（或数），写在相应文法的下边标识符（或数），写在相应文法的下边点记法：点记法：点记法：点记法：E.Val,E.Place,E.TypeE.Val,E.Place,E.TypeF:F:关于属
10、性的属性断言或一组属性的计算规则关于属性的属性断言或一组属性的计算规则关于属性的属性断言或一组属性的计算规则关于属性的属性断言或一组属性的计算规则(称为语义规称为语义规称为语义规称为语义规则则则则).).vv断言或语义规则与一个产生式相联断言或语义规则与一个产生式相联断言或语义规则与一个产生式相联断言或语义规则与一个产生式相联,只引用该产生式左只引用该产生式左只引用该产生式左只引用该产生式左端或右端的终结符或非终结符相关的属性端或右端的终结符或非终结符相关的属性端或右端的终结符或非终结符相关的属性端或右端的终结符或非终结符相关的属性.编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工
11、程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院语义规则描述的工作语义规则描述的工作vv属性计算属性计算vv静态语义检查静态语义检查vv符号表操作符号表操作vv代码生成代码生成 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院继承属性和综合属性继承属性和综合属性vv两类属性：两类属性：两类属性：两类属性：综合属性综合属性综合属性综合属性(Synthesized Attribute)(Synthesized Attribute)：
12、归约型属性：归约型属性：归约型属性：归约型属性vv用于用于用于用于“自下而上自下而上自下而上自下而上”传递信息传递信息传递信息传递信息继承属性继承属性继承属性继承属性(Inherited Attribute)(Inherited Attribute)：推导型属性：推导型属性：推导型属性：推导型属性vv用于用于用于用于“自上而下自上而下自上而下自上而下”传递信息。传递信息。传递信息。传递信息。vv属性的计算：属性的计算：属性的计算：属性的计算：A AX1 X2 XnX1 X2 XnA A的综合属性的综合属性的综合属性的综合属性,计算计算计算计算 S(A)=f(A(X1),A(Xn)S(A)=f(
13、A(X1),A(Xn)XjXj的继承属性的继承属性的继承属性的继承属性,计算计算计算计算 I(Xj)=f(A(A),.A(Xn)I(Xj)=f(A(A),.A(Xn)vv文法符号属性的说明：文法符号属性的说明：文法符号属性的说明：文法符号属性的说明：非终结符既可有综合属性也可有继承属性，但文法开始符号没有继非终结符既可有综合属性也可有继承属性，但文法开始符号没有继非终结符既可有综合属性也可有继承属性，但文法开始符号没有继非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性承属性承属性承属性.终结符只有综合属性终结符只有综合属性终结符只有综合属性终结符只有综合属性.通常规定：通常规定
14、：通常规定：通常规定：文法符号的综合属性与继承属性无交。文法符号的综合属性与继承属性无交。文法符号的综合属性与继承属性无交。文法符号的综合属性与继承属性无交。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院综合属性的例子综合属性的例子vv非终结符非终结符非终结符非终结符E E、T T及及及及F F都有一都有一都有一都有一个综合属性个综合属性个综合属性个综合属性val,val,符号符号符号符号digitdigit有有有有一个综合属性，它的值由词一个综合属性，它的值由词一个综合属性，它
15、的值由词一个综合属性，它的值由词法分析器提供。法分析器提供。法分析器提供。法分析器提供。vv与产生式与产生式与产生式与产生式LELE对应的语义对应的语义对应的语义对应的语义规则仅仅是打印由规则仅仅是打印由规则仅仅是打印由规则仅仅是打印由E E产生的产生的产生的产生的算术表达式的值的一个过程，算术表达式的值的一个过程，算术表达式的值的一个过程，算术表达式的值的一个过程，可认为这条规则定义了可认为这条规则定义了可认为这条规则定义了可认为这条规则定义了L L的的的的一个虚属性。一个虚属性。一个虚属性。一个虚属性。vv某些非终结符加上标是为某些非终结符加上标是为某些非终结符加上标是为某些非终结符加上标
16、是为了区分一个产生式中同一非了区分一个产生式中同一非了区分一个产生式中同一非了区分一个产生式中同一非终结符多次出现终结符多次出现终结符多次出现终结符多次出现语语 义义 规规 则则 L EE E1+TETT T1*FTFF(E)FdigitPrint(E.val)E.val=E1.val+T.val E.val=T.val T.val=T1.val F.val T.val=F.valF.val=E.valF.val=digit.lexval产产 生生 式式 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大
17、学计算机科学与工程学院综合属性的自下而上定值综合属性的自下而上定值L LE.val=19E.val=19E.val=15E.val=15T.val=4T.val=4T.val=15T.val=15F.val=4F.val=4T.val=3T.val=3F.val=3F.val=3F.val=5F.val=5digit.lexval=4digit.lexval=4digit.lexval=5digit.lexval=5digit.lexval=3digit.lexval=3+*3*5+43*5+4的带注释的分析树的带注释的分析树的带注释的分析树的带注释的分析树设表达式为设表达式为设表达式为设表达
18、式为3 35+45+4，则语义动作打印数值，则语义动作打印数值，则语义动作打印数值，则语义动作打印数值1919 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院继承属性的例子继承属性的例子 继承属性继承属性继承属性继承属性L.inL.in产产产产 生生生生 式式式式语语语语 义义义义 规规规规 则则则则D D TLTL T T int int T T realreal L L L L1 1,id,idL L id idL.in=T.typeL.in=T.typeT.type=int
19、egerT.type=integerT.type=realT.type=real L L1 1.in=L.in.in=L.in addtype(id.entry,L.in)addtype(id.entry,L.in)addtype(id.entry,L.inaddtype(id.entry,L.in)编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院继承属性的自上而下定值继承属性的自上而下定值 DL.in=realL.in=realL.in=realT.type=realrealid
20、2id1id3Real id1,id2,id3，编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院语法制导翻译的基本思想语法制导翻译的基本思想vv为每条产生式配上一个翻译子程序（称为语义动作为每条产生式配上一个翻译子程序（称为语义动作为每条产生式配上一个翻译子程序（称为语义动作为每条产生式配上一个翻译子程序（称为语义动作或语义子程序）；或语义子程序）；或语义子程序）；或语义子程序）；语义动作的工作语义动作的工作语义动作的工作语义动作的工作vv指明符号串的意义；指明符号串的意义；指明符
21、号串的意义；指明符号串的意义；vv按照这种意义规定了对应的动作：按照这种意义规定了对应的动作：按照这种意义规定了对应的动作：按照这种意义规定了对应的动作：查添各种表格查添各种表格查添各种表格查添各种表格改变变量之值改变变量之值改变变量之值改变变量之值诊察与报告源程序错误诊察与报告源程序错误诊察与报告源程序错误诊察与报告源程序错误产生中间代码产生中间代码产生中间代码产生中间代码vv在语法分析的同时，当一个产生式获得匹配（对于在语法分析的同时，当一个产生式获得匹配（对于在语法分析的同时，当一个产生式获得匹配（对于在语法分析的同时，当一个产生式获得匹配（对于自上而下分析）或用于归约（对于自下而上分析
22、）自上而下分析）或用于归约（对于自下而上分析）自上而下分析）或用于归约（对于自下而上分析）自上而下分析）或用于归约（对于自下而上分析）时，就执行相应产生式的语义子程序。时，就执行相应产生式的语义子程序。时，就执行相应产生式的语义子程序。时，就执行相应产生式的语义子程序。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院中间代码中间代码vv中间代码（中间代码（Intermediate code）：）：源程序的一种内部表示，不依赖目标机的结构，源程序的一种内部表示，不依赖目标机的结构，源
23、程序的一种内部表示，不依赖目标机的结构，源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。易于机械生成目标代码的中间表示。易于机械生成目标代码的中间表示。易于机械生成目标代码的中间表示。vv几种中间语言几种中间语言后缀式（逆波兰表示法）后缀式（逆波兰表示法）后缀式（逆波兰表示法）后缀式（逆波兰表示法）三地址代码三地址代码三地址代码三地址代码 四元式四元式四元式四元式 三元式三元式三元式三元式 间接三元式间接三元式间接三元式间接三元式树树树树 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院
24、长春工业大学计算机科学与工程学院后缀式后缀式vv表达式的一种表示形式表达式的一种表示形式运算符直接跟在运算量后面运算符直接跟在运算量后面运算符直接跟在运算量后面运算符直接跟在运算量后面又称为逆波兰表示法又称为逆波兰表示法又称为逆波兰表示法又称为逆波兰表示法vv定义：设定义：设E是表达式，那么是表达式，那么如果如果如果如果E E是变量或者常量，是变量或者常量，是变量或者常量，是变量或者常量，E E的逆波兰表示为的逆波兰表示为的逆波兰表示为的逆波兰表示为E EE1 OP E2=E1 E2 OPE1 OP E2=E1 E2 OP，其中，其中，其中，其中E1,E2 E1,E2 为为为为 E1,E2E1
25、,E2的逆波兰表示。的逆波兰表示。的逆波兰表示。的逆波兰表示。(E)=E,(E)=E,其中其中其中其中EE为为为为E E 的逆波兰表示。的逆波兰表示。的逆波兰表示。的逆波兰表示。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv后缀式的生成后缀式的生成设置一个操作符栈，当扫描到操作数时，输出该操设置一个操作符栈，当扫描到操作数时，输出该操设置一个操作符栈，当扫描到操作数时，输出该操设置一个操作符栈，当扫描到操作数时，输出该操作数。当遇到操作符时，与栈顶操作符比较优先级，作数。当遇
26、到操作符时，与栈顶操作符比较优先级，作数。当遇到操作符时，与栈顶操作符比较优先级，作数。当遇到操作符时，与栈顶操作符比较优先级，若栈顶操作符优先级高于栈外操作符，则输出该栈若栈顶操作符优先级高于栈外操作符，则输出该栈若栈顶操作符优先级高于栈外操作符，则输出该栈若栈顶操作符优先级高于栈外操作符，则输出该栈顶操作符；反之，则栈外操作符入栈。顶操作符；反之，则栈外操作符入栈。顶操作符；反之，则栈外操作符入栈。顶操作符；反之，则栈外操作符入栈。vv后缀表达式的计值后缀表达式的计值自左向右扫描表达式，每遇到运算量就把它推进栈，自左向右扫描表达式，每遇到运算量就把它推进栈，自左向右扫描表达式，每遇到运算量
27、就把它推进栈，自左向右扫描表达式，每遇到运算量就把它推进栈，每遇到每遇到每遇到每遇到k k目算符就把它作用于栈顶的目算符就把它作用于栈顶的目算符就把它作用于栈顶的目算符就把它作用于栈顶的k k个项，并把个项，并把个项，并把个项，并把运算结果来代替这运算结果来代替这运算结果来代替这运算结果来代替这k k个项个项个项个项 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院逆波兰表示的例子逆波兰表示的例子vvA+B*(C-D)+E/(C-D)N =A B C D-*+E C D N /+v
28、va+b*c/(d+e)=abc*de+/+编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院逆波兰表示方法的扩充逆波兰表示方法的扩充vv赋值语句：赋值语句：赋值语句：赋值语句：V=e V=e=Ve=Ve=例子：例子：例子：例子：t=(a+b)*c/(d-e)=tab+c*de-/=t=(a+b)*c/(d-e)=tab+c*de-/=vv转向语句：转向语句：转向语句：转向语句：goto=jumpgoto=jumpvv条件语句：条件语句：条件语句：条件语句：If then else
29、=If then else =jumpfjump jumpfjumpe eL1L1jumpjumpf fx xL2L2jumjump py yL1L2 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院三地址代码三地址代码vv一般形式：一般形式：X=y op zX=y op zvv例子例子 x+y*z x+y*z 可表示为可表示为可表示为可表示为 T1=y*z T1=y*z T2=x+T1 T1 T2=x+T1 T1、T2T2为编译时产生的临时变量为编译时产生的临时变量为编译时产生的
30、临时变量为编译时产生的临时变量vv三地址语句的种类三地址语句的种类vv三地址代码的具体实现三地址代码的具体实现四元式四元式三元式三元式间接三元式间接三元式 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院四元式四元式vv一般形式：一般形式：一般形式：一般形式：vv例子：例子：例子：例子：a+b*c *b bc ct1t1 +a t1 +a t1t2t2vv单目运算的处理：单目运算的处理：单目运算的处理：单目运算的处理：为空。为空。为空。为空。vv一般来讲，四元式的运算符都有对应的机
31、器指令，一般来讲，四元式的运算符都有对应的机器指令，一般来讲，四元式的运算符都有对应的机器指令，一般来讲，四元式的运算符都有对应的机器指令，或者对应的子程序，因此从四元式生成指令代码是或者对应的子程序，因此从四元式生成指令代码是或者对应的子程序，因此从四元式生成指令代码是或者对应的子程序，因此从四元式生成指令代码是容易的。容易的。容易的。容易的。vv四元式之间的联系是通过临时变量实现的，便于进四元式之间的联系是通过临时变量实现的，便于进四元式之间的联系是通过临时变量实现的，便于进四元式之间的联系是通过临时变量实现的，便于进行代码优化。行代码优化。行代码优化。行代码优化。编译原理编译原理编译原理
32、编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院四元式表示的例子四元式表示的例子vvA+B*(C-D)+E/(C-D)N（1 1）(-C D T1)(-C D T1)（2 2）(*B T1 T2)(*B T1 T2)（3 3）(+A T2 T3)(+A T2 T3)（4 4）(-C D T4)(-C D T4)（5 5）(T4 N T5)(T4 N T5)（6 6）(/E T5 T6)(/E T5 T6)（7 7）(+T3 T6 T7)(+T3 T6 T7)编译原理编译原理编译原理编译原理 长春工业大学计
33、算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院三元式三元式vv如果我们不明显给出四元式的结果部分，而是用四如果我们不明显给出四元式的结果部分，而是用四如果我们不明显给出四元式的结果部分，而是用四如果我们不明显给出四元式的结果部分，而是用四元式的编号来表示结果，那么我们可以得到三元式。元式的编号来表示结果，那么我们可以得到三元式。元式的编号来表示结果，那么我们可以得到三元式。元式的编号来表示结果，那么我们可以得到三元式。形式如下：形式如下：形式如下：形式如下：vv例子：例子：例子：例子：a+b*c=a+b*c=*b c*b c*
34、b c*b c +a +a +a +a vv三元式的出现顺序与表达式的计值顺序一致。三元式的出现顺序与表达式的计值顺序一致。三元式的出现顺序与表达式的计值顺序一致。三元式的出现顺序与表达式的计值顺序一致。vv和四元式的比较：和四元式的比较：和四元式的比较：和四元式的比较：无须临时变量；无须临时变量；无须临时变量；无须临时变量；占用存储空间少；占用存储空间少；占用存储空间少；占用存储空间少；相互引用太多，使得难以进行代码优化。相互引用太多，使得难以进行代码优化。相互引用太多，使得难以进行代码优化。相互引用太多，使得难以进行代码优化。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学
35、院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院三元式表示的例子三元式表示的例子vvA+B*(C-D)+E/(C-D)N(1)(-C D )(1)(-C D )(2)(*B (1)(2)(*B (1)(3)(+A (2)(3)(+A (2)(4)(-C D )(4)(-C D )(5)(4)N )(5)(4)N )(6)(/E (5)(6)(/E (5)(7)(+(3)(6)(7)(+(3)(6)编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科
36、学与工程学院间接三元式间接三元式vv间接三元式：间接三元式：为了便于代码优化处理，用一张为了便于代码优化处理，用一张为了便于代码优化处理，用一张为了便于代码优化处理，用一张间接码表间接码表间接码表间接码表辅以辅以辅以辅以三三三三元式表元式表元式表元式表的办法来表示中间代码。的办法来表示中间代码。的办法来表示中间代码。的办法来表示中间代码。间接码表是一张指示器表，它将按运算的先后顺间接码表是一张指示器表，它将按运算的先后顺间接码表是一张指示器表，它将按运算的先后顺间接码表是一张指示器表，它将按运算的先后顺序列出有关三元式在三元式表中的位置。序列出有关三元式在三元式表中的位置。序列出有关三元式在三
37、元式表中的位置。序列出有关三元式在三元式表中的位置。当在代码优化过程中需要调整运算顺序时，只需当在代码优化过程中需要调整运算顺序时，只需当在代码优化过程中需要调整运算顺序时，只需当在代码优化过程中需要调整运算顺序时，只需重新安排间接码表即可。重新安排间接码表即可。重新安排间接码表即可。重新安排间接码表即可。vv例子：例子：X=(A+B)*C Y=D(A+B)编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院间接三元式表示的例子间接三元式表示的例子A+B*(C-D)+E/(C-D)N1
38、.1.(1)(-C D )(1)2.2.(2)(*B (1)(2)3.3.(3)(+A (2)(3)4.4.(4)(1)N )(1)5.5.(5)(/E (4)(4)6.6.(6)(+(3)(5)(5)(6)编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院树形表示（抽象语法树树形表示（抽象语法树AST）vv采用树形表示作为一种中间代码形式，有助于代码采用树形表示作为一种中间代码形式，有助于代码采用树形表示作为一种中间代码形式，有助于代码采用树形表示作为一种中间代码形式，有助于代码的
39、产生和优化。的产生和优化。的产生和优化。的产生和优化。vv树形表示的定义：树形表示的定义：树形表示的定义：树形表示的定义：简单变量或常数的树就是该变量或常数自身；简单变量或常数的树就是该变量或常数自身；简单变量或常数的树就是该变量或常数自身；简单变量或常数的树就是该变量或常数自身；如果表示如果表示如果表示如果表示e1e1和和和和e2e2的树为的树为的树为的树为T1T1和和和和T2T2，那么，那么，那么，那么，e1+e2,e1*e2,-e1+e2,e1*e2,-e1e1的树分别是：的树分别是：的树分别是：的树分别是：显然，树形表示是三元式表示的翻版。显然，树形表示是三元式表示的翻版。显然，树形表
40、示是三元式表示的翻版。显然，树形表示是三元式表示的翻版。vv抽象语法树（抽象语法树（抽象语法树（抽象语法树（Abstract Syntax TreeAbstract Syntax Tree）在语法树中去掉那些对翻译不必要的信息，获得更有效的在语法树中去掉那些对翻译不必要的信息，获得更有效的在语法树中去掉那些对翻译不必要的信息，获得更有效的在语法树中去掉那些对翻译不必要的信息，获得更有效的源程序中间表示源程序中间表示源程序中间表示源程序中间表示ASTAST可以拓广，用来表示数组元素、过程调用、控制结构、可以拓广，用来表示数组元素、过程调用、控制结构、可以拓广，用来表示数组元素、过程调用、控制结构
41、、可以拓广，用来表示数组元素、过程调用、控制结构、说明等。说明等。说明等。说明等。+e1e2-e1*e1e2 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院由语法树到由语法树到ASTvv步骤：步骤：去掉单非产生式子树，上提终结符结点；去掉单非产生式子树，上提终结符结点；去掉单非产生式子树，上提终结符结点；去掉单非产生式子树，上提终结符结点；运算符上提，取代其父结点；运算符上提，取代其父结点；运算符上提，取代其父结点；运算符上提，取代其父结点；去掉括号，运算符上提。去掉括号，运算符
42、上提。去掉括号，运算符上提。去掉括号，运算符上提。vv例子：例子：a*(a+a)编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院简单算术表达式和赋值句的翻译简单算术表达式和赋值句的翻译vv文法：文法：文法：文法：A Ai:=Ei:=EEE+E|E*E|-E|(E)|iEE+E|E*E|-E|(E)|ivv引入的语义属性：引入的语义属性：引入的语义属性：引入的语义属性：E.placeE.place与非终结符与非终结符与非终结符与非终结符E E相联系，表示存放相联系，表示存放相联系，表
43、示存放相联系，表示存放E E值的变量名在符号表值的变量名在符号表值的变量名在符号表值的变量名在符号表的入口或整数码（对临时变量）的入口或整数码（对临时变量）的入口或整数码（对临时变量）的入口或整数码（对临时变量）vv语义过语义过语义过语义过程：程：程：程：newtemp()newtemp():函数函数函数函数过过过过程。每次程。每次程。每次程。每次调调调调用，回送一个代表新用，回送一个代表新用，回送一个代表新用，回送一个代表新临临临临时变时变时变时变量名的整数量名的整数量名的整数量名的整数码码码码作作作作为为为为函数函数函数函数值值值值。lookup(i.name)lookup(i.name)
44、:函数函数函数函数过过过过程。程。程。程。对对对对i i所代表所代表所代表所代表标识标识标识标识符符符符查查查查找符号找符号找符号找符号表以表以表以表以获获获获知它在符号表中位置（入口）。知它在符号表中位置（入口）。知它在符号表中位置（入口）。知它在符号表中位置（入口）。emitemit():():语义过语义过语义过语义过程。程。程。程。产生一个三地址代码并填入中间代产生一个三地址代码并填入中间代产生一个三地址代码并填入中间代产生一个三地址代码并填入中间代码码码码表中。表中。表中。表中。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大
45、学计算机科学与工程学院长春工业大学计算机科学与工程学院产生式的语义描述产生式的语义描述（1 1）A Ai:=E i:=E p=lookup(i.name)p=lookup(i.name)；if(p=NULL)error();if(p=NULL)error();else emit(p=E.place)else emit(p=E.place)（2 2）EEEE(1)(1)+E+E(2)(2)E.place=newtemp();E.place=newtemp();emit(E.place emit(E.place=E E(1)(1).place.place+E E(2)(2).place).plac
46、e)（3 3）EEEE(1)(1)*E*E(2)(2)E.place=newtemp();E.place=newtemp();emit(E.place emit(E.place=E E(1)(1).place.place*E E(2)(2).place).place)（4 4）E-E E-E(1)(1)E.place=newtemp();E.place=newtemp();emit(E.place=uminus E emit(E.place=uminus E(1)(1).place).place)（5 5）E(EE(E(1)(1)E.place=E)E.place=E(1)(1).place.
47、place（6 6）Ei p=lookup(i.name)Ei p=lookup(i.name)；if(p=NULL)error();else E.place=p if(p=NULL)error();else E.place=p 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院布尔表达式的翻译布尔表达式的翻译vv布尔表达式基本作用：布尔表达式基本作用：用作计算逻辑值；用作计算逻辑值；用作计算逻辑值；用作计算逻辑值；用作控制条件。用作控制条件。用作控制条件。用作控制条件。vv 布尔表
48、达式文法：布尔表达式文法：EE EEE|EE|EE|E|E|(E)|id relop id|idE|(E)|id relop id|id结合性和优先级：结合性和优先级：结合性和优先级：结合性和优先级：vvrelop relop ；vv左结合。左结合。左结合。左结合。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院布尔表达式的翻译布尔表达式的翻译vv计算布尔表达式的值：计算布尔表达式的值：逐步计算；逐步计算；利用布尔表达式的性质采取优化措施：利用布尔表达式的性质采取优化措施：vvAB
49、ABABAB if A then true else B if A then true else B if A then true else B if A then true else BvvABABABAB if A then B else false if A then B else false if A then B else false if A then B else falsevvB B B B if B then false else true if B then false else true if B then false else true if B then false
50、else true 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院布尔表达式的翻译布尔表达式的翻译vv逐步计算的例子逐步计算的例子:A AB BC=DC=D(=,C,D,T1)(=,C,D,T1)(,B,T1,T2),B,T1,T2)(,A,T2,T3),A,T2,T3)编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院布尔表达式的翻译布尔表达式的翻译vv优化计算引入的