语法制导翻译和中间代码学时

语法制导翻译和中间代码学时第1页，课件共41页，创作于2023年2月8.1属性文法预备知识源程序与目标程序，语法结构完全不同，但语义相同，所以表达的结果完全相同。语义分析的2种处理方法： 1）语法分析之后，直接调用相应的“语义子程序”进行语义处理 2）语法分析之后，先生成“语法树”或其他形式，再进行语义处理语义分析的处理结果： 1）目标代码 2）中间代码：复杂性介于源程序语言和机器语言之间第2页，课件共41页，创作于2023年2月静态语义分析：审查语法结构的静态语义

确定标识符的数据类型

类型检查和转换：检查运算对象的数据类型是否合法，必要时进行类型转换

一致性检查：一个对象只能被声明一次

作用域检查

控制流检查：控制语句转到合法的地方继续执行翻译（若静态语义分析正确后才翻译）语义处理的任务和功能第3页，课件共41页，创作于2023年2月常用的语义分析方法——语法制导翻译语法制导翻译：首先，使用属性文法为工具，描述程序设计语言的语义规则。在语法分析时，每应用一个产生式（推导或归约），同时完成该产生式上所附的语义规则描述的动作，从而完成语义处理。语义分析的方法第4页，课件共41页，创作于2023年2月用于描述语义规则的文法。对文法的每个符号引入一些属性，这些属性代表与文法符号相关的信息，例如：类型、值、代码序列、符号表内容等。属性值可以在语法分析过程中进行计算和传递。属性的加工过程就是语义的处理过程。属性文法

(attributegrammar)第5页，课件共41页，创作于2023年2月属性文法的组成：一个上下文无关文法

一系列语义规则（附在文法的每个产生式上）属性文法的形式：三元组A=(G,V,F)G:是一个上下文无关文法V:有穷属性集,每个属性与文法的一个终结符或非终结符关联F:关于属性的断言或谓词集.每个断言与一个产生式关联.而此断言只引用该产生式的终结符或非终结符相关联的属性属性文法

(attributegrammar)第6页，课件共41页，创作于2023年2月属性文法举例例1说明语句中各种变量的类型信息的语义规则：

产生式 语义规则DTLTcharTintTfloatLL1,idLid{L.in:=T.type}{T.type:=char}{T.type:=int}{T.type:=float}{L1.in:=L.inaddtype(id.entry,L.in)}{addtype(id.entry,L.in)}第7页，课件共41页，创作于2023年2月属性文法举例例2表达式类型检查和求值的语义规则：假设：类型不同的两个变量进行运算则语义错误。

产生式 语义规则LEEE1+TETTT1*FTFF(E)Fid{print(E.val);}{if(E1.type==T.type){ E.type:=E1.type; E.val:=E1.val+T.val;}elseerror(); }{E.type:=T.type;E.val:=T.val}{getType(F.type,id.entry);F.val:=id.lexval;}第8页，课件共41页，创作于2023年2月语法制导翻译的实质： 根据每个产生式所对应的语义规则，随语法分析的每一步（推导或归约），执行相应的语义动作。语法制导翻译的过程：对单词符号串进行语法分析，构造语法分析树；然后根据需要构造属性依赖图，遍历语法树，并在语法树的各结点处按语义规则进行计算。8.2语法制导翻译概论第9页，课件共41页，创作于2023年2月使用“依赖图”，从依赖图的拓扑排序中得到计算语义规则的顺序，再依照顺序对输入串进行语义分析。依赖图 一个有向图，用于描述分析树中的属性和属性之间的相互依赖关系。 构造依赖图举例：参见P172图8.4属性计算方法

树遍历：事先建立语法树，（深度优先）遍历直至计算出所有属性值。

一遍扫描：在语法分析的同时计算属性值。计算语义规则第10页，课件共41页，创作于2023年2月属性：综合属性：可以在分析输入串的同时，自下而上地来计算。如：val继承属性：一个结点的继承属性值是由此结点的父结点和（或）兄弟结点的某些属性来决定的。如：L.in属性文法：S-属性文法：L-属性文法的一个特例L-属性文法：例1就是一个L-属性文法属性文法的计算：可以是普通意义上的数学运算，也可以是打印输出等动作。属性文法的类型和计算第11页，课件共41页，创作于2023年2月S-属性文法：是L-属性文法的一个特例，只含有综合属性。例2是一个S-属性文法。S-属性文法翻译器：可以借助LR分析器实现。

实现原理：LR分析器中增加一个栈（语义值栈）用来存放综合属性的值，进行归约的同时，栈中正在归约的产生式右部符号的综合属性值弹栈，并调用相应语义子程序进行相应计算（完成属性文法中的语义规则），产生的新值入语义值栈。举例：参见P174图8.7S-属性文法和自下而上翻译第12页，课件共41页，创作于2023年2月L-属性文法：对于文法中的每个产生式AX1X2…Xn，其每个语义规则中的每个属性要么是综合属性，要么是Xj(1≤j≤n)的一个继承属性且该继承属性仅依赖于：产生式中X1,X2,…Xj-1的属性和A的继承属性。L-属性文法优点：允许一次遍历就计算出所有属性值。L-属性文法第13页，课件共41页，创作于2023年2月L-属性文法翻译器：可以借助LL分析器实现。

实现原理：在自顶向下分析的过程中，每应用一个产生式进行推导，同时完成该产生式上属性文法的计算。LL(1)分析方法的语义描述：语义动作不是附在产生式右部的末尾，而是嵌在两个符号之间。这样的语义描述称为翻译模式。举例：P174例8.3例8.4L-属性文法在自上而下分析中的实现第14页，课件共41页，创作于2023年2月翻译模式：语义动作不是附在产生式右部的末尾，而是嵌在两个符号之间。翻译模式是适合语法知道翻译的另一种描述形式。翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表现出来。翻译模式第15页，课件共41页，创作于2023年2月何时将属性文法改写成翻译模式？消除左递归时，原属性文法将被改成翻译模式。如何将属性文法改写成翻译模式？原文法：AA1Y{A.a=g(A1.a,Y.y)}

AX {A.a=f(X.x)} 翻译模式：AX{R.i=f(X.x)}R{A.a=R.s}RY{R1.i=g(R.i,Y.y)}R1

{R.s=R1.s}Rε{R.s=R.i}改写成翻译模式第16页，课件共41页，创作于2023年2月L-属性文法中，如何实现自下而上计算继承属性？方法1：去掉翻译模式中嵌入在产生式中间的动作。方法2：改变原文法或重新构造文法，用综合属性代替继承属性。自学（P176,177）L-属性文法在自下而上分析中的实现第17页，课件共41页，创作于2023年2月8.3中间代码的形式中间代码的常见形式：逆波兰记号三元式树形表示四元式第18页，课件共41页，创作于2023年2月逆波兰记号（后缀式）特点：将运算对象写在前面，把运算符号写在后面标识符顺序与表达式中的一致运算符顺序与计算顺序一致无括号表达式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=为什么要使用逆波兰式？更易于计算机处理，表示简洁、计算方便。第19页，课件共41页，创作于2023年2月逆波兰记号的扩充用途i--i@GotoLLjumpifEthenS1elseS2ES1S2￥A[n][m]nmAsubs逆波兰式的复杂性：压栈的可能是地址（如变量赋值），不是值；栈中不一定产生结果。逆波兰式的计算机处理方法：自左向右扫描逆波兰式，遇到运算对象入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。第20页，课件共41页，创作于2023年2月三元式和树形表示三元式的格式：

(算符,第一运算对象,第二运算对象)如：a=b*c+b*d的三元式和树形表示

(1) (*,b,c)

(2) (*,b,d)

(3) (+,(1),(2))

(4) (=,(3),a)=a+**bcbd第21页，课件共41页，创作于2023年2月四元式四元式的格式：

(算符,第一运算对象,第二运算对象,结果)如：a=b*c+b*d的四元式表示如下(*,a,b,t1)(*,b,d,t2)(+,t1,t2,t3)(:=,t3,-,a)t1:=a*bt2:=b*dt3:=t1+t2a:=t3或特点：利于代码优化和目标代码生成特例：gotoL

的四元式为（jump,-,-,L）

ifBropCgotoL的四元式为(jrop,B,C,L)

第22页，课件共41页，创作于2023年2月8.4简单赋值语句的翻译说明：1）表示id所表示的单词，用作语义变量2）lookup()审查是否出现在符号表是：返回指向该登录项的指针否：返回nil3）emit将四元式输出到中间文件（或目标文件）上4）newtemp生成一临时变量5）E.place存放E值的变量名在符号表的登录项 若变量为临时变量，则直接存放一整数码第23页，课件共41页，创作于2023年2月8.4简单赋值语句的翻译例3将赋值语句翻译成四元式的语义描述：Sid:=E

EE1+

E2

EE1*

E2

E-E1

E(E1)

Eid

第24页，课件共41页，创作于2023年2月Sid:=E

{ P:=lookup();

ifPnilthen

emit(P,“:=”,E.place);

else

error();

}第25页，课件共41页，创作于2023年2月(2)

EE1+E2

{E.place:=newtemp;

emit(E.place,“:=”,E1.place,“+”,E2.place);

}(3)

EE1*E2{E.place:=newtemp;

emit(E.place,“:=”,E1.place,“*”,E2.place);

}第26页，课件共41页，创作于2023年2月(4)

E-E1

{E.place=newtemp;

emit(E.place,’:=’,’-’,E1.place);

}

(5)

E(E1)

{E.place=newtemp;

emit(E.place,’:=’,E1.place);

}

(6)

Eid

{p:=lookup();

if(p!=nil)E.place=p;

elseerror();

}第27页，课件共41页，创作于2023年2月8.5布尔表达式的翻译1、布尔表达式的作用：计算逻辑值（返回真/假）控制流语句中的条件表达式

if(~)then while(~)2、布尔表达式的文法

EEandE EEorE EnotE Eidropid Etrue Efalse第28页，课件共41页，创作于2023年2月3、布尔表达式的计算方法：一步一步计算出式中各部分真假，最终算出整个表达式的值采用优化措施，只计算部分表达式值即可 例如：aandb //a为0时，b无论是什么表达式的值都为0aorb //a为1时，b无论是什么表达式的值都为18.5布尔表达式的翻译第29页，课件共41页，创作于2023年2月例如aorbandnotc对应的四元式 (1)(not,c,-,t1) (2)(and,b,t1,t2) (3)(or,a,t2,t3)布尔表达式的翻译第30页，课件共41页，创作于2023年2月EnotE1

{ E.true:=E1.false; E.codebegin:=E1.codebegin; E.false:=E1.true;}(2)EE1andE2 { backpatch(E1.true,E2.codebegin); E.codebegin:=E1.codebegin; E.true:=E2.true; E.false:=merge(E1.false,E2.false); }(3)EE1orE2 { backpatch(E1.false,E2.codebegin); E.codebegin:=E1.codebegin; E.true:=merge(E1.true,E2.true); E.false:=E2.false; }布尔表达式译为四元式的语义描述：第31页，课件共41页，创作于2023年2月(4)E(E1)

{ E.true:=E1.true; E.codebegin:=E1.codebegin; E.false:=E1.false;}(5)Eid1ropid2 { E.true:=nextstat; E.codebegin:=nextstat; E.false:=nextstat+1;

emit(‘if’,id1.place,‘rop’,id2.place,‘goto’,–); emit(‘goto’,-); }(6)Eid { E.true:=nextstat; E.codebegin:=nextstat; E.false:=nextstat+1;

emit(‘if’,id1.place,‘goto’,–); emit(‘goto’,-); }第32页，课件共41页，创作于2023年2月控制语句SifEthenS1elseS2

E.falseE的代码

E.trueE.false:S2的代码gotooutE.true:S1的代码out:控制语句中布尔表达式的翻译第33页，课件共41页，创作于2023年2月举例将下列控制语句翻译成四元式ifa<borc<dande>fthenS1elseS2

控制语句中布尔表达式的翻译

ifa<bgoto(i+1) //i+1是S1的入口

ifc<dgoto(4)

goto(6)

ife>fgoto(i+1)

[关于S2的四元式]

┋(i)goto(n) //n是S1的出口(i+1)[关于S1的四元式]

┋(n)第34页，课件共41页，创作于2023年2月例forI:=1step1untilNdoM:=M+I

对应的四元式

For循环语句的翻译

I:=1

goto(4)

I:=I+1

ifI<=Ngoto(6)

goto(9)

T:=M+I

M:=T

goto(3)……第35页，课件共41页，创作于2023年2月

课堂练习1(1)(2)(5)(6)(7)2[逆波兰式、三元式、四元式序列]356