第6章语法制导翻译和中间代码生成.

第六章语法制导翻译和中间代码生成6.1语义分析概述6.2语法制导翻译6.3中间语言6.4算术表达式和赋值语句的翻译6.5布尔表达式的翻译6.6控制语句的翻译2语义分析的任务在词法分析和语法分析的基础上进一步分析其含义。3静态语义分析：编译期间进行的语义分析。通常实现程序结构（控制结构和数据结构）相关的语义检查。动态语义分析：目标代码执行期间进行的语义分析。通常实现程序运行时的语义检查，如动态类型检查。我们只讨论静态语义分析。41.类型检查2.控制流检查3.唯一性检查4.名字相关性检查5.识别含义5检查运算的合法性（运算对象的一致性）。如：运算数是否与运算兼容；标识符是否已声明过；标识符的使用是否与其声明的类型兼容。6控制流语句必须使控制转移到合法的地方。如：跳转语句转移到的标号是否存在；跳转语句是否在合法的位置（如switch语句中必须包含break语句）7一个对象（如标识符，case语句的标号等）在一个分程序中只能被定义一次。8某些名字必须出现两次或多次。一些名字可能被要求配对出现，如：在Ada语言中循环或程序块的名字应出现在循环或程序块开始和结束的部分。9确认程序中各种成分组合到一起的含义，并作相应的语义处理，对可执行的语句生成中间语言或目标语言。10直接生成目标代码生成中间语言11根据源程序中各语法成分的语义，直接生成机器语言或汇编语言。特点：编译时间较短；存储空间较大；目标语言的质量较差。12介于源程序语言和机器语言之间的机内表示形式。特点：编译程序的逻辑结构简单；有利于编译程序的移植；便于目标语言的优化。13语法制导翻译法：是由源程序的语法结构所驱动的语义处理办法。语法制导翻译法：直观上说是为基础文法的每个产生式配上一个翻译子程序（称为语义子程序或语义动作，是一组语义规则），并且在语法分析的同时执行这些语义子程序。这样，语法分析工作和语义子程序的执行穿插进行，但以语法分析为主导。14语义动作（语义子程序、语义规则）是给产生式赋予具体意义的手段。产生式只能产生符号串，并没有指明所产生的符号串的意义。语义动作一方面指出了产生式所产生的符号串的意义，另一方面，又按这种意义规定了生成某种中间代码应做的加工动作。15语义加工子程序的任务产生中间代码；查、填符号表（如进行类型检查、调用合法性检查等）；改变编译程序的一些变量值；诊断源程序中的语义错误，等。16语法制导翻译是在语法分析的同时进行语义处理（翻译）。因此，语法制导翻译与两个因素密切相关：所采用的语法分析方法（自上而下或自下而上）语法分析到什么时候执行语义动作17语义动作执行的时间在自上而下语法分析过程中，当一个产生式匹配输入串成功时，执行与此产生式相应的动作。在自下而上语法分析过程中，当一个产生式被用于进行规约时，执行与此产生式相应的动作。两种语法制导翻译法：自下而上、自上而下。18为完成翻译任务，需要对每个文法符号（终结符或非终结符）赋予包含某些信息的“值”，如：类型、种属、值等分别用X.TYPE、X.CAT和X.VAL表示这些属性。如果一个产生式中同一个符号出现多次，就用下角标来区分。如:E→E+EE→E1+E219将对应于某产生式的语义动作写在该产生式的花括号内。如：(1)E→E1+E2{E.VAL:=E1.VAL+E2.VAL}(2)E→0{E.VAL:=0}(3)E→1{E.VAL:=1}20语义子程序是描述一定的输入和一定的输出之间的对应关系。这种描述与使用什么样的语法分析方法及分析算法的具体实现无关。因此，当语法规则或语义动作需要修改时，只要更改有关规则或动作，不用涉及其他方面。21中间语言是一种表达原程序并与之等效的代码方式介于高级语言和机器语言之间22后缀式（逆波兰表示）图表示法(DAG无环路有向图，抽象语法树)三地址代码三地址语句四元式、三元式、间接三元式23是一种表示表达式的方法；一般表达表达式的方法：中缀形式（习惯写法）：x+y前缀形式：+xy后缀形式：xy+最适合计算机使用，称为逆波兰表示。24a+bab+a+b*cabc*+a*b+c*dab*cd*+(a+b)*cab+c*(a-b)*(c+d)ab-cd+*-a+b*ca@bc*+一目运算-a+b*(c+d/(e+f))abcdef+/+*+25运算对象的顺序与在表达式中出现的顺序一致。运算符按执行顺序排列。没有括号。26一般，若e1,e2为任意的后缀表达式，Θ为任意双目运算符，则用Θ作用于e1和e2所代表的结果用后缀式e1e2Θ表示。推而广之，Θ为k目运算符，则Θ作用于e1e2…ek的结果用e1e2…ekΘ来表示。27根据给定的逆波兰表示，计算表达式值的方法：用一个栈来实现，从左到右扫描逆波兰表示:(1)若是运算对象，则进栈；(2)若是K目运算符，则对栈顶的k个运算对象执行该运算，并用计算结果代替这k个运算对象。28AB@CD*++的计算过程：步骤栈符号串说明12345678计算-BT1，B出栈，T1进栈B@CD*++AABAT1AT1CAT1CDAT1T2AT3T4@CD*++CD*++D*++*+++++B进栈计算A+T3T4，A+T3出栈，T4进栈C进栈D进栈计算C*DT2，C,D出栈，T2进栈计算T1+T2T3，T1T2出栈，T3进栈291.抽象语法树2.DAG图（无环路有向图）30用树来表示表达式或语句。可以作为一种合适的中间语言形式。在语法树中去掉那些对翻译无效的信息，从而获得更有效的源程序中间表示。这种变换后的语法树为抽象语法树。31运算符和关键字作为内部结点。运算对象作为叶子结点。32简单变量或常数的树就是该变量或常数本身。若E1和E2的树为T1和T2，则:E1+E2+T1T2E1*E2*T1T2-E1-T133a*b+c*d+*ba*dca*(b-c)-d-*-adcb树表示的后序遍历等价于逆波兰表示34与抽象语法树一样，对表达式的每个子表达式，DAG都有一个结点。DAG图的结构：一个内部结点代表一个运算符。该结点的孩子代表运算对象。35DAG图的公共子表达式的结点具有多个父结点。抽象语法树的公共子表达式对应重复子树。36a+a*(b-c)+(b-c)*d++*a*d-a-bcbc++**da-bc语法树DAG37a=b*-c+b*-c语法树DAG=a+*bc*-cb-=a+b*-c38例：X+Y*Z，中间代码为：T1:=Y*ZT2:=X+T1T1,T2为编译时产生的临时变量三地址代码一般形式：X:=YopZ结果操作数操作数操作符39T1:=-cT2:=b*T1T3:=-cT4:=b*T3T5:=T2+T4a:=T540三地址语句类似于汇编语言代码。可以带有符号标号，而且有各种流程控制语句。符号标号代表存放中间代码的数组中三地址代码语句的下标。41(1)二目运算的赋值语句x:=yopz(2)单目运算的赋值语句x:=opy(3)赋值语句x:=y(4)无条件转移语句gotoL（L为中间代码地址）(5)条件转移语句：ifxrelopygotoL（relop关系运算符)或ifagotoL（a为布尔表达式或常量）42(6)过程调用语句：paramx(x为参数)callp,n(n为实参个数)returny(返回语句，y为返回值)例：过程调用语句p(x1,x2,x3)三地址代码:paramx1paramx2paramx3callp,343(7)索引赋值x:=y[i]（把相对于地址y的后面第i个单元里的值赋给x）x[i]:=y（把y的值赋给相对于地址x后面的第i个单元）。(8)地址和指针赋值x:=&y（把y的地址赋给x）x:=*y（把y地址单元中的内容赋给x）44赋值语句id:=E的三地址代码包括：对表达式E求值，并置于临时变量T中;进行赋值id.place:=T（id.place表示存放id值的名字）在后续翻译中，我们假设对新的临时变量的引用没有限制。45三地址代码通常有三种表示方法：三元式间接三元式四元式46一般形式：(θ,O1,O2)其中：θ：运算符；O1,O2：运算对象例：A+B(+,A,B)A*B(*,A,B)47A*(B-C)/D+E的三元式：(1)(-,B,C)(2)(*,A,(1))(3)(/,(2),D)(4)(+,(3),E)48A+B*(C+D)-E/F的三元式：(1)(+,C,D)(2)(*,B,(1))(3)(/,E,F)(4)(+,A,(2))(5)(-,(4),(3))49三元式表与语法树表示的含义一样例:(A*B)+(C*D)+*BA*DC(1)(*,A,B)(2)(*,C,D)(3)(+,(1),(2))50为了便于代码优化处理，作为中间代码，常常不直接使用三元式的指针，而是另设一张间接码表（指示器表），该表按运算的先后顺序列出三元式在三元式表中的位置。51(A+B)*C+(A+B)/D间接码表三元式表(1)(1)(+,A,B)(2)(2)(*,(1),C)(1)(3)(/,(1),D)(3)(4)(+,(2),(3))(4)两次用到(1)是重复运算，A、B的值在执行中没有改变比较：单纯的三元式表:(1)(+,A,B)(2)(*,(1),C)(3)(+,A,B)(4)(/,(3),D)(5)(+,(2),(4))52单纯的三元式不但给出了运算，而且还给出了运算的执行顺序。间接三元式的三元式表不再指出执行的顺序，执行顺序由间接码表表示。在优化时，若要改变执行顺序，则只改变间接码表即可。（无需改动三元式组）53C:=A+B*CD:=A*E-B*C间接码表(1)(2)(3)(4)(1)(5)(6)三元式表(1)(*,B,C)(2)(+,A,(1))(3)(:=,C,(2))(4)(*,A,E)(5)(-,(4),(1))(6)(:=,D,(5))54优点由于另设了间接码表，因此，相同的三元式无需再填入三元式表中，由此可节省三元式表的空间。对于间接三元式表示，语义子程序应增加产生间接码表的动作，并在向三元式表填写三元式之前，必须先查看此式是否已在三元式表中。若已在，则无需再填写。缺点：造成大量查表。55四元式是一种被普遍采用的中间代码形式。最接近于机器语义，最便于优化。一般形式：(θ,O1,O2,T)其中：θ：运算符O1,O2：运算对象T：运算结果56A*(B-C)/D+E的四元式组：(-,B,C,T1)(*,A,T1,T2)(/,T2,D,T3)(+,T3,E,T4)四元式的排列顺序与计算顺序一致。57A:=-B*(C+D)-2.5(-,B,_,T1)(+,C,D,T2)(*,T1,T2,T3)(-,T3,2.5,T4)(:=,T4,_,A)58对同一程序段来说，生成的四元式与三元式个数一样。三元式比四元式少了“结果”一项，而用序号来代替，因此，三元式占的空间比四元式少。四元式之间的联系是通过临时变量进行的，与四元式的位置无关，因此便于在优化时进行移动和删除。59三元式与四元式个数一样。例：A+B-C*D三元式四元式(1)(+,A,B)(+,A,B,T1)(2)(*,C,D)(*,C,D,T2)(3)(-,(1),(2))(-,T1,T2,T3)60四元式更易于优化。例：A*B-C/D的四元式：(*,A,B,T1)(/,C,D,T2)(-,T1,T2,T3)(/,C,D,T2)(*,A,B,T1)(-,T1,T2,T3)不影响执行结果三元式：(*,A,B)(/,C,D)(-,(1),(2))(/,C,D)(*,A,B)(-,(2),(1))影响执行结果,需调整三元式61a:=b*-c+b*-c三地址码四元式三元式间接三元式T1:=-c(@,c,_,T1)(@,c,_)(0)(@,c,-)(0)T2:=b*T