编译6语法制导翻译技术和中间代码生成讲述.ppt

* * 语法制导翻译方法： 自底向上的语法制导翻译方法 自顶向下的语法制导翻译方法 二、语法制导翻译的步骤 1、为所给文法每个产生式设计相应的语义规则。 例：为一个简单表达式计值的文法： E→E+E|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} 为文法产生式写语义规则或语义子程序是难点. * * 2.采用LR分析方法，则构造LR分析表 状态 ACTION GOTO + digit * ( ) # E 0 S3 S2 1 1 S4 S5 acc 2 S3 S2 6 3 r4 r4 r4 r4 4 S3 S2 7 5 S3 S2 8 6 S4 S5 S9 7 r1 S5 r1 r1 8 r2 r2 r2 r2 9 r3 r3 r3 r3 * * 3. 将原LR语法分析栈扩充，增加语义值栈。 4. 根据语义分析栈的工作过程设计总控程序，使语法分析与语义分析工作同时完成。 例：计算表达式7+8*5的语法树，以及用LR语法制导翻译法得到该表达式的计值过程： Sn xn xn·val … … … S1 x1 … S0 # x1·val 状态栈 文法符号栈 语义值栈 * * 步 骤 状态栈 语义栈 符号栈 输入 符号栈 主要 动作 1 0 _ # 7+8*5# S3 2 03 _ #7 +8*5# r4 3 01 _7 #E +8*5# S4 4 014 _7_ #E+ 8*5# S3 5 0143 _7_ #E+8 *5# r4 6 0147 _7_8 #E+E *5# S5 7 01475 _7_8 #E+E* 5# S3 8 014753 _7_8_ #E+E*5 # r4 9 014758 _7_8_5 #E+E*E # r2 10 0147 _7_40 #E+E # r1 11 01 _47 #E # acc 注：自底向上语法制导翻译的特点： 当栈顶形成句柄执行归约时，调用相应的语义动作。 语法分析与语义分析同步操作。 * * * 1 中间语言 中间语言：它介于源程序到目标语言程序中间程序的语言 中间语言程序：用中间语言表示的程序。 作用：用于编译程序，将源程序翻译成等价的中间语言程序，再将中间语言程序转化成目标程序（即将语义分析和目标代码生成分开处理） 源程序 中间语言程序 目标程序 中间语言是表示语法制导翻译的结果。 等价变换 转化 6.4 中 间 语 言 * * 好处： 中间语言与机器无关，使采用中间语言进行翻译的编译程序系统易于移植。 易于优化翻译后的代码。 使编译程序的结构在逻辑上更简单明确。 2 中间语言的表示 常见：逆波兰表示 四元式表示和三地址代码 三元式和树形表示 * * 6.4.1 逆波兰表示 由波兰逻辑学家J.Lukasiewicz(卢卡西维兹)首先提出用来表示表达式的方法，后来推广到表示程序设计语言中的其它语法成分。 表达式的逆波兰表示 表达式的表示： 中缀表示： 运算符居中，运算对象在左右两边:a+b 波兰表示： 前缀表示：运算符在前，运算对象在后：+ab 后缀表示：运算对象在前，运算符在后：ab+… (逆波兰表示) * * 例：逆波兰表示的例子 中缀表示(一般表示) 逆波兰表示 a+b*c abc*+ a*(b+c/d) abcd/+* a*b+c ab*c+ a*b+(c-d)/e ab*cd-e/+ * * (1)表达式逆波兰表示的定义： 设E是一般表达式，则： 一般表达式 逆波兰表达式 若E为变量或常量 E （E） E的逆波兰式 E(1)opE(2)(二目运算) E(1)的逆波兰式E(2)的逆波兰式op opE(单目运算) E的逆波兰式op * * 在编译过程中，生成逆波兰表示的语义规则描述： 产生式 语义规则 E→E(1)opE(2) E.code=E(1).code||E(2) .code||op E→(E(1) ) E.code=E(1) .code E→i E.code= i 其中：E.code表示E的逆波兰式；||表示逆波兰式的连接。 * * (2)逆波兰表示的特点 a.标识符(运算对象)出现的顺序（从