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

语法制导翻译和中间代码学时8.1概述8.2属性文法8.3语法制导翻译8.4中间代码的形式逆波兰式、三元式、树形表示、四元式8.5一些语句的翻译赋值语句布尔表达式控制语句中的布尔表达式

For循环语句8.6数组的翻译第2页,共50页，2024年2月25日，星期天概述程序设计语言的语义静态语义——是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域/可见性规则两大类动态语义——程序单位描述的计算编译程序的语义处理工作静态语义审查解释执行动态语义（计算）生成代码...第3页,共50页，2024年2月25日，星期天语义处理静态语义分析：审查语法结构的静态语义确定标识符的数据类型类型检查和转换：检查运算对象的数据类型是否合法，必要时进行类型转换一致性检查：一个对象只能被声明一次作用域检查控制流检查：控制语句转到合法的地方继续执行翻译（若静态语义分析正确后才翻译）第4页,共50页，2024年2月25日，星期天概述语义形式化 语义建模文法模型——属性文法命令式或操作式模型——操作语义学应用式模型——指称语义学公理式模型——公理语义学第5页,共50页，2024年2月25日，星期天属性文法表达式文法E—>T+T|TorTT—>n|bE

T1+T2{T1.type=intT2.type=T1.type E.type:=int}E

T1orT2{T1.type=bool T2.type=T1.type E.type:=bool}T

n{T.type:=int}T

b{T.type:=bool}第6页,共50页，2024年2月25日，星期天操作语义学通过执行该段程序所改变的计算机状态来反映语义。包括变量的所有值，可执行程序本身，各种系统定义的内部数据结构。用一组形式定义的操作来说明执行一条指令相应的状态怎样变化。For(expr1;expr2;expr3)expr1;{Loop:ifexpr2=0gotoout

。。。…}expr3;gotoloopout:...第7页,共50页，2024年2月25日，星期天指称语义学基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体实例向数学意义对象的映射的函数特点：不但对全部程序赋予全文而且对程序设计语法每一个语法成分短语（表达式，命令，声明…）都给予含义。每一个语法成分（短语）的含义是以它的自身成分的含义的术语来定义的。语义函数：程序设计语言的语义利用映射函数来证明。语义函数将短语映射到它的指称。第8页,共50页，2024年2月25日，星期天Valuation[101]表示把Valuation施用于101Valuation[N]------把它施用于N

定义:Valuation（用四个方程)因为有四个形式numeralValuation[0]

0Valuation[1]

1Valuation[N0]

2

Valuation[N]Valuation[N1]

2

Valuation[N]+1

所以：

Valuation[110]=2

Valuation[11]=2

(2

Valuation[1]+1)=2

(2

1+1)=6第9页,共50页，2024年2月25日，星期天公理语义学一个语言的每个语法成分的含义定义为公理和演绎规则，用于推导出该成分执行的效果。公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式对程序的变量进行约束,以此说明这个语句的含义。一般的记号{P}S{Q}如果在语句S执行前P为真，则在语句S执行并终止后Q为真。第10页,共50页，2024年2月25日，星期天演绎规则的例子赋值：x:=expr{P(expr)}x:=expr{P(x)}While:{P∧B}S{P}{P}whileBdoSend{P∧(notB)}if--then--else{B∧P}S1{Q},{(notB)∧P}S2{Q}{P}ifBthenS1elseS2{Q}第11页,共50页，2024年2月25日，星期天8.2属性文法预备知识源程序与目标程序，语法结构完全不同，但语义相同，所以表达的结果完全相同。语义分析的2种处理方法：

1）语法分析之后，直接调用相应的“语义子程序”进行语义处理 2）语法分析之后，先生成“语法树”或其他形式，再进行语义处理语义分析的处理结果：

1）目标代码 2）中间代码：复杂性介于源程序语言和机器语言之间第12页,共50页，2024年2月25日，星期天常用的语义分析方法——语法制导翻译语法制导翻译：首先，使用属性文法为工具，描述程序设计语言的语义规则。在语法分析时，每应用一个产生式（推导或归约），同时完成该产生式上所附的语义规则描述的动作，从而完成语义处理。语义分析的方法第13页,共50页，2024年2月25日，星期天用于描述语义规则的文法。对文法的每个符号引入一些属性，这些属性代表与文法符号相关的信息，例如：类型、值、代码序列、符号表内容等。属性值可以在语法分析过程中进行计算和传递。属性的加工过程就是语义的处理过程。属性文法

(attributegrammar)第14页,共50页，2024年2月25日，星期天属性文法的组成：一个上下文无关文法

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

(attributegrammar)第15页,共50页，2024年2月25日，星期天属性文法举例例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)}第16页,共50页，2024年2月25日，星期天属性文法举例例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;}第17页,共50页，2024年2月25日，星期天语法制导翻译的实质： 根据每个产生式所对应的语义规则，随语法分析的每一步（推导或归约），执行相应的语义动作。语法制导翻译的过程：对单词符号串进行语法分析，构造语法分析树；然后根据需要构造属性依赖图，遍历语法树，并在语法树的各结点处按语义规则进行计算。8.3语法制导翻译概论第18页,共50页，2024年2月25日，星期天属性：综合属性：可以在分析输入串的同时，自下而上地来计算。如：val继承属性：一个结点的继承属性值是由此结点的父结点和（或）兄弟结点的某些属性来决定的。如：L.in属性文法的计算：可以是普通意义上的数学运算，也可以是打印输出等动作。属性文法的类型和计算第19页,共50页，2024年2月25日，星期天设表达式为3＊5+4，则语义动作打印数值19.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的带注释的分析树第20页,共50页，2024年2月25日，星期天

DL.in=realL.in=realL.in=realT.type=realrealid2id1id3.Realid1,id2,id3，，第21页,共50页，2024年2月25日，星期天语法制导的翻译一个翻译是符号串对的一个集合。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。各个编译阶段定义一个翻译，词法分析：（字符串，单词串）语法分析：（单词串，语法树）代码生成（语法树，汇编语言）第22页,共50页，2024年2月25日，星期天

把下述产生式定义的算术表达式映射到后缀波兰表示：

EE+TET

TT

FTF

F(E)

Fa

E=ET+

E=T

T=TF

T=F

F=E

F=a产生式

翻译规则第23页,共50页，2024年2月25日，星期天

确定输入a+a

a的输出：

(E,E)(E+T,ET+)

(T+T,TT+)

(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+)第24页,共50页，2024年2月25日，星期天8.4中间代码的形式中间代码的常见形式：逆波兰记号三元式树形表示四元式第25页,共50页，2024年2月25日，星期天逆波兰记号（后缀式）特点：将运算对象写在前面，把运算符号写在后面标识符顺序与表达式中的一致运算符顺序与计算顺序一致无括号表达式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=为什么要使用逆波兰式？更易于计算机处理，表示简洁、计算方便。第26页,共50页，2024年2月25日，星期天逆波兰式的复杂性：压栈的可能是地址（如变量赋值），不是值；栈中不一定产生结果。逆波兰式的计算机处理方法：自左向右扫描逆波兰式，遇到运算对象入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。第27页,共50页，2024年2月25日，星期天三元式和树形表示三元式的格式：

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

(1) (*,b,c)

(2) (*,b,d)

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

(4) (=,(3),a)=a+**bcbd第28页,共50页，2024年2月25日，星期天四元式四元式的格式：

(算符,第一运算对象,第二运算对象,结果)如：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)

第29页,共50页，2024年2月25日，星期天8.5简单语句的翻译说明：1）

表示id所表示的单词，用作语义变量2）lookup()

审查是否出现在符号表是：返回指向该登录项的指针否：返回nil3）emit

将四元式输出到中间文件（或目标文件）上4）newtemp

生成一临时变量5）E.place

存放E值的变量名在符号表的登录项 若变量为临时变量，则直接存放一整数码第30页,共50页，2024年2月25日，星期天简单赋值语句的翻译例3将赋值语句翻译成四元式的语义描述：S

id:=E

E

E1+

E2

E

E1*

E2

E

-E1

E

(E1)

E

id

第31页,共50页，2024年2月25日，星期天S

id:=E

{ P:=lookup();

ifP

nilthen

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

else

error();

}第32页,共50页，2024年2月25日，星期天(2)

E

E1+E2

{E.place:=newtemp;

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

}(3)

E

E1*E2{E.place:=newtemp;

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

}第33页,共50页，2024年2月25日，星期天(4)

E

-E1

{E.place=newtemp;

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

}

(5)

E

(E1)

{E.place=newtemp;

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

}

(6)

E

id

{p:=lookup();

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

elseerror();

}第34页,共50页，2024年2月25日，星期天布尔表达式的翻译1、布尔表达式的作用：计算逻辑值（返回真/假）控制流语句中的条件表达式

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

E

EandE E

EorE E

notE E

idropid E

true E

false第35页,共50页，2024年2月25日，星期天3.计算布尔表达式通常采用两种方法:(1).如同计算算术表达式一样,一步步算

1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=1(2).采用某种优化措施把AorB解释成 ifAthentrueelseB

把AandB解释成 ifAthenBelsefalse

把

A解释成 ifAthenfalseelsetrue第36页,共50页，2024年2月25日，星期天例如aorbandnotc

对应的四元式第一种翻译法

(1)(not,c,-,t1) (2)(and,b,t1,t2) (3)(or,a,t2,t3)布尔表达式的翻译第37页,共50页，2024年2月25日，星期天关于布尔表达式的数值表示法的翻译模式过程emit将三地址代码送到输出文件中nextstat给出输出序列中下一条三地址语句的地址索引每产生一条三地址语句后，过程emit便把nextstat加1第38页,共50页，2024年2月25日，星期天关于布尔表达式的数值表示法的翻译模式E→E1orE2{E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp; emit(E.place‘:=’E1.place‘and’E2.place)}E→notE1 {E.place:=newtemp; emit(E.place‘:=’‘not’E1.place)}E→(E1) {E.place:=E1.place}第39页,共50页，2024年2月25日，星期天关于布尔表达式的数值表示法的翻译模式E

id1relopid2{E.place:=newtemp;

emit(‘if’id1.placerelop.opid2.place ‘goto’nextstat+3);

emit(E.place‘:=’‘0’);

emit(‘goto’nextstat+2);

emit(E.place‘:=’‘1’)}E→id {E.place:=id.place}a<b翻译成100: ifa<bgoto103101: T:=0102: goto104103: T:=1104:第40页,共50页，2024年2月25日，星期天布尔表达式a<borc<dande<f的翻译结果100: ifa<bgoto103101: T1:=0 102: goto104103: T1:=1104: ifc<dgoto107105: T2:=0 106: goto108107: T2:=1108:ife<fgoto111109:T3:=0110:goto112111:T3:=1112:T4:=T2andT3113:T5:=T1orT4E

id1relopid2

{E.place:=newtemp; emit(‘if’id1.placerelop.opid2.place ‘goto’nextstat+3); emit(E.place‘:=’‘0’); emit(‘goto’nextstat+2); emit(E.place‘:=’‘1’)}E→id {E.place:=id.place}E→E1orE2

{E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp;emit(E.place‘:=’E1.place‘and’E2.place)}第41页,共50页，2024年2月25日，星期天控制语句S

ifEthenS1

elseS2

E.falseE的代码

E.trueE.false:S2的代码gotooutE.true:S1的代码out:控制语句中布尔表达式的翻译第42页,共50页，2024年2月25日，星期天例：把语句:ifa>corb<dthenS1elseS2翻译成如下的一串三地址代码

ifa>cgotoL2“真”出口

gotoL1L1: ifb<dgotoL2“真”出口

gotoL3“假”出口L2: (关于S1的三地址代码序列) gotoLnextL3: (关于S2的三地址代码序列)Lnext:第43页,共50页，2024年2月25日，星期天每次调用函数newlabel后都返回一个新的符号标号对于一个布尔表达式E，引用两个标号E.true是E为‘真’时控制流转向的标号E.false是E为‘假’时控制流转向的标号第44页,共50页，2024年2月25日，星期天产生布尔表达式三地址代码的语义规则 产生式 语义规则

E→E1orE2

E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code|| gen(E1.false‘:’)||E2.code

E1.codeToE.trueToE1.falseE2.codeToE.trueToE.false第45页,共50页，2024年2月25日，星期天产生布尔表达式三地址代码的语义规则

产生式 语义规则

E→E1andE