第8章语法制导翻译和中间代码生成(lly2).

第八章语法制导翻译和中间代码考察重点属性文法与语法制导翻译中间代码：逆波兰式、三元式、四元式、抽象语法树的表示常见语句的翻译（布尔表达式，控制语句，循环，数组）语义分析语义分析的任务：在词法分析和语法分析的基础上，分析所写源程序的含义，在理解含义的基础上为生成相应的目标代码作好准备或直接生成目标代码。1）静态语义检查例：类型检查、运算、维数、越界2）语义翻译（具体的动作）例：语句的翻译（中间代码或目标代码生成）语义分析方法：大多编译器采用语法制导翻译方法语义分析工具：在语法制导翻译方法中，常用属性文法来说明程序设计语言语义8.1属性文法属性文法(attributegrammar)是一个三元组:A=(G,V,F)F:关于属性的属性断言或谓词集.每个断言与一个产生式相联.而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性（语义子程序）V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连（并非每个终结符或非终结符都有属性，属性与具体产生式的语义相关）G:是一个上下文无关文法(形式化）表达式文法E→T+T|TorTT→n|true|falseE→T1+T2{T1.type=intT2.type=T1.typeE.type:=int}E→T1orT2{T1.type=boolT2.type=T1.typeE.type:=bool}T→n{T.type:=int}T→true{T.type:=bool}T→false{T.type:=bool}类型检查的属性文法：（值的属性？E→T1orT2设计?）语义规则LEEE1+TETTT1*FTFF(E)FdigitPrint(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.valF.valT.val:=F.valF.val:=E.valF.val:=digit.lexval产生式综合属性val综合属性在分析树中，如果一个结点的某一个属性由其子结点的属性确定，则称这种属性为该结点的综合属性。过程Print打印E表达式的值。以3*5+4为例说明在语法制导定义中，一条语义规则完成一个计算属性值的动作。digit是终结符，只使用综合属性，且其属性值由词法分析器提供，通常不要计算属性值。LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树如果一个语法制导定义仅仅使用综合属性，则称这种语法制导定义为S属性定义。通常采用自底向上的方法对其分析树加注释，即从树叶到树根，按照语义规则计算每个节点的属性值。继承属性一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。生产式语义规则DTLTintTrealLL1,idLidL.in:=T.typeT.type=integerT.type:=realL1.in:=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)继承属性L.in以说明语句reala1,a2,a3为例过程addtype是把每个标志符的类型信息登录在符号表中相关项中。语句reala1,a2,a3的分析树，采用自上而下的分析方法产生式语义规则DTLTintTrealLL1,idLidL.in:=T.typeT.type=integerT.type:=realL1.in:=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)DL.in=realL.in=realL.in=realT.type=realreala2a1a3..，，8.2语法制导翻译概论在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。说明：定义理解：语法制导翻译是在语法分析过程中同时进行的；一旦用到某个产生式推导/归约时，调用相应的语义子程序进行翻译。目的：用语法制导翻译的方法来说明程序设计语言的结构怎样被翻译成中间形式参见P.157-159对表达式2+3*5进行的分析8.3中间代码的形成中间代码的常见形式：逆波兰记号三元式（树形表示）四元式逆波兰记号（后缀式）结构特点：将运算对象写在前面，把运算符号写在后面表达式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a:=b*c+b*d？计算方法：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。特点：1）不需要括号（已考虑结合性与优先性）；2）适合计算机运算，但不适合人。逆波兰记号的扩充用途－ii@GotoLLjumpifEthenS1elseS2ES1S2￥A[n][m]nmAsubs复杂性：压栈的可能是地址（如变量赋值），不是值；栈中不一定产生结果。逆波兰示例（以算术表达式a+aa最左推导说明）把下述产生式定义的算术表达式映射到后缀波兰表示：EE+TETTTFTFF(E)FaE=ET+E=TT=TFT=FF=EF=a产生式翻译成分确定输入a+aa的输出：(E,E)(E+T,ET+)(T+T,TT+)(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+)三元式和树形表示格式：(算符,第一运算对象,第二运算对象)注意：运算结果用三元式编号表示。如：a:=b*c+b*d(1)(*,b,c)(2)(*,b,d)(3)(+,(1),(2))(4)(:=,(3),a):=a+**bcbd三元式表示树形表示四元式格式：(算符,第一运算对象,第二运算对象,结果)注意：运算结果用临时变量表示。如：a:=b*c+b*d(1)(*,b,c,t1)(2)(*,b,d,t2)(3)(+,t1,t2,t3)(4)(:=,t3,,a)特点:类似于三地址指令利于优化和代码生成四元式的直观表示a:=b*c+b*d(1)(*,b,c,t1)(2)(*,b,d,t2)(3)(+,t1,t2,t3)(4)(:=,t3,,a)注意：x:=b*c的四元式表示（三元式，后缀式）？四元式的扩展(jump,,,L)gotoL(jrop,B,C,L)ifBropCgotoL(jnz,A,,L)ifAthenL思考：ifAthenL0elseL1四元式？t1:=b*ct2:=b*dt3:=t1+t2a:=t38.4简单赋值语句的翻译四元式形式:t:=arg1oparg2语义属性：id.name,E.place函数：lookup(id.name);过程：emit(t:=arg1oparg2);函数：newtemp;返回指向id的指针输出四元式生成临时变量，返回指针E.place:值E的位置(1)Sid:=E{P:=lookup(id.name);ifPnilthenemit(P“:=”E.place)elseerror}(2)EE1+E2//-，*，/{E.place:=newtemp;emit(E.place“:=”E1.place“+”E2.place)}(3)E-E1{E.place:=newtemp;emit(E.place“:=”“uminus”E1.place)}(4)E(E1){E.place:=E1.place}(5)Eid{P:=lookup(id.name);ifPnilthenE.place:=Pelseerror}x=a+b-c例（有二义，设+优先，自下而上分析）思考：人如何处理？人的思维与语义子程序设计关系？产生式和语义描述（简单算术表达式赋值语句四元式）翻译—语法制导翻译思想8.5布尔表达式到四元式的翻译布尔表达式的作用作为控制语句的条件表达式用于逻辑计值E→E∧E│E∨E│～E│(E)│iropj│i注：①rop为关系运算符：=，，，=，=，②∧为“与”运算；∨为“或”运算；～为“非”运算③结合性为左结合性④优先级别为：～,rop，∧，∨，布尔表达式的计值方法方法一：逐步计算方法二：优化计算例如：1∨（～0∧0）∨0=1∨（1∧0）∨0=1∨0∨0=1∨0=1①A∨B②A∧B③～A解释为：ifAthenTRUEelseB解释为：ifAthenBelseFALSE解释为：ifAthenFALSEelseTRUE思考：优化后如何翻译为四元式？作为逻辑计值的布尔表达式的翻译例如：将A∨B∧C!=D翻译成四元式的形式（逐步计算）（!=，C，D，T1）（∧，B，T1，T2）（∨，A，T2，T3）思考：优化法如何翻译为四元式？控制语句中布尔表达式的翻译下面我们来观察“if-语句”和“while-语句”中布尔表达式的作用：仅仅用于执行流程的控制ifEthenS1elseS2whileEdoS……E的四元式代码S1的四元式代码GOTOLS2的四元式代码……TRUEFALSEE的四元式代码S的四元式代码GOTOLTRUEFALSE返回思考：若无GOTOL，结果会如何？我们通过观察“if-语句”和“while-语句”中布尔表达式的作用可以知道：E的四元式代码TRUEFALSEE的真出口，用E.true表示E的假出口，用E.false表示说明：在控制语句中布尔表达式常采用优化法进行翻译优化计算②A∨B①A∧B③～A解释为：ifAthenTRUEelseB解释为：ifAthenBelseFALSE解释为：ifAthenFALSEelseTRUE①E→E1∧E2E1的“真出口”就是E2的第一个四元式编号；E1的“假出口”就是E的“假出口”；E2的“真/假出口”就是E的“真/假出口”②E→E1∨E2E1的“真出口”就是E的“真出口”；E1的“假出口”就是E2的第一个四元式编号；E2的“真/假出口”就是E的“真/假出口”③E→～E1E1的“真出口”就是E的“假出口”；E1的“假出口”就是E的“真出口”；（jnz，A，，p）若A为真，则转到第p号四元式去执行（jrop，A，B，p）若AropB为真，则到第p号四元式去执行（j，，，p）无条件转到第p号四元式去执行为了翻译布尔表达式，我们引入下面三种四元式：思考：ifA∨BDthenx:=y+zelsex:=y-z如何翻译为四元式？E的四元式代码S1的四元式代码GOTOLS2的四元式代码……TRUEFALSEifEthenS1elseS2ifA∨BDthenx:=y+zelsex:=y-z100（jnz，A，，104）；A的“真出口”101（j，，，102）；A的“假出口”102（j，B，D，104）；BD的“真出口”103（j，，，107）；BD的“假出口”104（+，y，z，T1）；S1语句105（:=，T1，，x）；S1语句106（j，，，109）；跳过S2的代码107（-，y，z，T2）；S2语句108（:=，T2，，x）；S2语句109…………思考：在语义子程序中，如何确定一个布尔表达式的“真出口”和“假出口”呢？由于在分析过程中，一个布尔表达式的“真/假出口”往往不能在产生四元式的同时就填上。所以我们常采用“拉链——回填”的方式来处理。为此，对布尔表达式E我们赋予两个属性（语义值）：存放E的“真链”链头，该链上的所有四元式均是需要回填“真出口”的四元式的地址（编号）E.true存放E的“假链”链头，该链上的所有四元式均是需要回填“假出口”的四元式的地址（编号）E.false例如：E.true=rr(～，～，～，p)…p(～，～，～，q)…q(～，～，～，0)0表示链尾r(～，～，～，0)p(～，～，～，0)q(～，～，～，0)…………………………………………r(～，～，～，p)p(～，～，～，q)“拉链”（并链）过程：Merge(p1，p2)功能：