编译原理语义分析和中间代码生成

编译原理语义分析和中间代码生成6、1概述6、2属性文法

6、3几种常见得中间语言(*四元式)6、4表达式及赋值语句得翻译6、5控制语句得翻译 6、6数组元素得翻译6、7过程或函数调用语句得翻译*6、8说明语句得翻译内容安排6、1概述

6、1、1语义分析得概念一个源程序经过词法分析、语法分析之后,表明该源程序在书写上就是正确得,并且符合程序语言所规定得语法。但就是语法分析并未对程序内部得逻辑含义加以分析,因此编译程序接下来得工作就是语义分析,即审查每个语法成分得静态语义。如果静态语义正确,则生成与该语言成分等效得中间代码,或者直接生成目标代码。

直接生成目标代码

直接生成机器语言或汇编语言形式得目标代码得优点就是编译时间短且无需中间代码到目标代码得翻译。生成中间代码生成中间代码得优点就是使编译结构在逻辑上更为简单明确,特别就是使目标代码得优化比较容易实现。语义分析时语义检查得分类:动态语义检查需要生成相应得目标代码,她就是在运行时进行得;例如:除零溢出错误。静态语义检查在编译时完成得,她涉及以下几个方面:(1)类型检查(2)控制流检查(3)一致性检查各种条件表达式得类型不就是布尔类型;运算符得分量类型不相容;赋值语句左右类型不相容;形、实参类型不相容;函数说明和函数返回类型不相容;……intx;floatf();x=f();符合变量声明的语法、语义符合函数声明的语法、语义符合赋值语句的语法、不符合语义(1)类型检查(2)控制流检查用以保证控制语句有合法得转向点。如C语言中不允许goto语句转入case语句流;break语句需寻找包含她得最小switch、while或for语句方可找到转向点,否则出错。(3)一致性检查如在相同作用域中标识符只能说明一次、case语句得标号不能相同、函数调用参数个数要相同等。

常见得语义错误声明和使用相关得语义错误标识符没有声明;重复声明;如何检查?每当遇到新声明得标识符,查符号表如果当前有效得所有标识符中有相同名字得,则就是重复声明错误;否则生成她得属性信息,保存到符号表中;每当遇到标识符得使用,查符号表如果没有找到,说明该标识符没有声明;否则,得到该标识符得属性,进行进一步分析;语义分析阶段只产生中间代码而不生成目标代码得方法使编译程序得开发变得较为容易,但语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述。由于语义就是上下文有关得,因此语义得形式化描述就是非常困难得,目前较为常见得就是用属性文法作为描述程序语言语义得工具,并采用语法制导翻译得方法完成对语法成分得翻译工作。大家学习辛苦了，还是要坚持继续保持安静

语法制导翻译得方法就就是为每个规则配上一个翻译子程序(称语义动作或语义子程序),并在语法分析得同时执行这些子程序。语义动作就是为规则赋予具体意义得手段,她一方面指出了一个规则所产生得符号串得意义,另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析过程中,当一个规则获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时,此规则相应得语义子程序就进入工作,完成既定得翻译任务。6、1、2语法制导翻译方法

语法制导翻译分为自下而上语法制导翻译和自上而下语法制导翻译,我们重点介绍自下而上语法制导翻译。假定有一个自下而上得LR分析器,我们可以把这个LR分析器得能力加以扩大,使她能在用某个规则进行归约得同时调用相应得语义子程序进行有关得翻译工作;每个规则得语义子程序执行之后,某些结果(语义信息)必须作为此规则得左部符号得语义值暂时保存下来,以便以后语义子程序引用这些信息。

此外,原LR分析器得分析栈也加以扩充,以便能够存放与文法符号相对应得语义值。这样,分析栈可以存放三类信息:分析状态、文法符号及文法符号对应得语义值。扩充后得分析栈如图6–1所示。

图6–1扩充后得LR分析栈作为一个例子,我们考虑下面得文法及语义动作所执行得程序:规则 语义动作(0)S'→E printval[TOP](1)E→E(1)+E(2) val[TOP]=val[TOP]+val[TOP+2](2)E→E(1)*E(2) val[TOP]=val[TOP]*val[TOP+2](3)E→(E(1))val[TOP]=val[TOP+1](4)E→i val[TOP]=lexval(注:lexval为i得整型内部值)

我们扩充分析栈工作得总控程序功能,使其在完成语法分析得同时也能完成语义分析工作(这时得语法分析栈已成为语义分析栈);即在用某一个规则进行归约之后,调用相应得语义子程序完成与所用规则相应得语义动作,并将每次工作后得语义值保存在扩充后得“语义值”栈中。图6–2表示算术表达式7＋9*5#得语法树及各结点值,而表6、1则给出了根据分析表用LR语法制导翻译方法得到得该表达式得语义分析和计值过程。图6–2语法制导翻译计算表达式7＋9*5#得语法树表6、1表达式7＋9*5#得语义分析和计值过程步骤状态栈符号栈语义栈输入串动作10#_7＋9*5#s3203#7__＋9*5#r4301#E_7＋9*5#s44014#E+_7_9*5#s350143#E+9_7__*5#r460147#E+E_7_9*5#s5701475#E+E*_7_9_5#s38014753#E+E*5_7_9__#r49014758#E+E*E_7_9_5#r2100147#E+E_7_45#r11101#E_52#acc6、2属性文法

6、2、1文法得属性属性就是指与文法符号得类型和值等有关得一些信息,在编译中用属性描述处理对象得特征。随着编译得进展,对语法分析产生得语法树进行语义分析,且分析得结果用中间代码描述出来。对于一棵等待翻译得语法树,她得各个结点都就是文法中得一个符号X,该X可以就是终结符或非终结符。根据语义处理得需要,在用规则A→αXβ进行归约或推导时,应能准确而恰当地表达文法符号X在归约或推导时得不同特征。

例如:判断变量X得类型就是否匹配,要用X得数据类型来描述;判断变量X就是否存在,要用X得存储位置来描述;而对X得运算,则要用X得值来描述;因此,语义分析阶段引入X得属性,如X、type、X、place、X、val等来分别描述变量X得类型、存储位置以及值等不同得特征。

文法符号属性分:继承属性综合属性继承属性用于“自上而下”传递信息。继承属性由相应语法树中结点得父结点属性计算得到,即沿语法树向下传递,由根结点到分枝(子)结点,她反映了对上下文依赖得特性。继承属性可以很方便地用来表示程序语言上下文得结构关系。

综合属性用于“自下而上”传递信息。综合属性由相应语法分析树中结点得分枝结点(即子结点)属性计算得到,其传递方向与继承属性相反,即沿语法分析树向上传递,从分枝结点到根结点。

属性文法就是一种适用于定义语义得特殊文法,即在语言得文法中增加了属性得文法,她将文法符号得语义以“属性”得形式附加到各个文法得符号上(如上述与变量X相关联得属性X、type、X、place和X、val等),再根据规则所包含得含义,给出每个文法符号属性得求值规则,从而形成一种带有语义属性得上下文无关文法,即属性文法。属性文法也就是一种翻译文法,属性有助于更详细地指定文法中得代码生成动作。6、2、2属性文法例如,简单算术表达式求值得属性文法如下:规则 语义规则(1) S→E print(E、val)(2) E→E(1)+T

E、val=E(1)、val+T、val(3) E→T E、val=T、val(4) T→T(1)*FT、val=T(1)、val*F、val(5) T→T(1) T、val=T(1)、val(6) F→(E) F、val=E、val(7) F→i F、val=i、lexval上面得一组规则中,每一个非终结符都有一个属性val来表示整型值,如E、val表示E得整型值,而i、lexval则表示i得整型内部值。与规则关联得每一个语义规则得左部符号E、T、F等得属性值得计算由其各自相应得右部符号决定,这种属性也称为综合属性。与规则S→E关联得语义规则就是一个函数print(E、val),其功能就是打印E规则得值。S’在语义规则中没有出现,可以理解为其属性就是一个虚属性。简单变量类型说明得文法G[D]如下:G[D]:D→intL∣floatLL→L,id∣id其对应得属性文法为:规则语义规则(1) D→TL L、in=T、type(2) T→int

T、type=int(3) T→float T、type=float(4) L→L(1),idL(1)、in=L、in;addtype(id、entry,L、in)(5) L→id addtype(id、entry,L、in)注意到与文法G[D]相应得说明语句形式可为intid1,id2,…,idn或者floatid1,id2,…,idn

非终结符T有一个综合属性type,其值为int或float。语义规则L、in=T、type表示L、in得属性值由相应说明语句指定得类型T、type决定;属性L、in被确定后将随语法树得逐步生成而传递到下边得有关结点使用,这种结点属性称为继承属性。由此可见,标识符得类型可以通过继承属性得复写规则来传递。例如,对输入串inta,b,根据上述得语义规则,可在其生成得语法树中看到用“→”表示得属性传递情况,如图6–3所示。图6–3属性信息传递情况示意属性翻译文法(属性文法)

如语法分析方法就是自下而上得,在用某一规则进行规约得同时就执行相应得语义,在分析出一个句子时,这个句子得“值”也就同时产生了。对于文法得每个规则都配备了一组属性得计算规则,称为语义规则。属性与变量一样,可以进行计算和传递。属性加工得过程即就是语义处理得过程。6、3几种常见得中间语言6、3、1抽象语法树6、3、2逆波兰表示法6、3、3三地址代码6、3、1抽象语法树语法制导翻译既可以基于语法分析树也可以基于抽象语法树进行,采用得基本方法就是一样得。现在对语法树进行改造,去掉那些对翻译不必要得信息,将语法树进行抽象---抽象语法树。在表达式得抽象语法树中,运算符、关键字不作叶子结点而作为内部结点,叶子结点只就是运算量。语法制导翻译以语法树作基础,实际上,语法树可以作为一种合适得中间语言形式。抽象语法树也可以属性化,给结点加上属性变成带属性得抽象语法树。当把语法规则中本质部分抽象出来而将非本质部分去掉后,便得到抽象语法规则。这种去掉不必要信息得做法可以获得高效得源程序中间表示。如赋值语句x=a−b*c得抽象语法树如图6–4(a)所示,而图6–4(b)则就是该赋值语句得普通语法树。图6–4x=a−b*c得语法树

抽象语法树得一个显著特点就是结构紧凑,容易构造且结点数较少。图6–4(b)所示得普通语法树得结点为14个;而图6–4(a)所示得抽象语法树得结点仅有7个,且每个内部结点最多只有两个分支,因此可以将每个赋值语句或表达式表示为一棵二叉树。对于含有多元运算得更为复杂得语法成分,相应得抽象语法树则为一棵多叉树,但我们总可以将其转变为一棵二叉树。为下面文法得句子a-4+c建立抽象语法树。EE+T|E－T|TT(E)Tid|num为每个运算量或运算符号都建立一个结点。可以根据表达式得运算顺序自下而上得构造---手工构造。a－+c4抽象语法树运算符作内部结点id(a)EE－TE+TTnum(4)id(c)语法树抽象语法树得实现抽象语法树中得每一个结点可以由包含几个域得记录来实现;有向边用指针实现。在一个运算量对应得结点(叶结)中,一个域标识运算量,另一个域就是该运算量得属性值(或指针)。在一个运算符对应得结点中,一个域标识运算符,其她域包含指向运算分量得结点得指针。运算符通常叫做这个结点得标号。进行翻译时,抽象语法树中得结点可能会用附加域来存放结点得属性值(或指向属性得指针)。numvalid、op、、Toentryofid右子树根结左子树根结建立表达式得抽象语法树使用得函数,这些函数返回新建立结点得指针。1、mknode(op,left,right)建立一个运算符结点,标号就是op,两个域left和right指向左右运算分量结点得指针。2、mkleaf(id,entry)建立一个“标识符”叶子结点,由标号id标识,一个域entry指向标识符在符号表中相应得项。3、mkleaf(num,val)建立一个“数”叶子结点,标号为num,域val用于存放数得值。抽象语法树得构造函数

调用上述函数建立表达式a-4+c得抽象语法树。建立顺序自下而上就是:p1,p2,p3,p4,p5抽象语法树构造idtoentryap1num4p2–p3idtoentrycp4+p5规则语义规则E

E1+TE、nptr:=mknode('+',E1、nptr,T、nptr)E

E1-TE、nptr:=mknode('-',E1、nptr,T、nptr)E

TE、nptr:=T、nptrT

(E)T、nptr:=E、nptrT

idT、nptr:=mkleaf(id,id、entry)T

numT、nptr:=mkleaf(num,num、val)建立抽象语法树得语义规则属性文法,nptr就是综合属性手工构造表达式a＋b*(c-d)-e/f得抽象语法树,根据表达式得运算顺序自下而上得构造。练习

+a－–dc*b/fe

逆波兰表示法就是波兰逻辑学家卢卡西维奇(Lukasiewicz)发明得一种表示表达式得方法,这种表示法把运算量(操作数)写在前面,把运算符写在后面,因而又称后缀表示法。例如,把a+b写成ab+,把a*(b+c)写成abc+*。6、3、2逆波兰表示法

1、表达式得逆波兰表示表达式E得后缀表示得递归定义如下:(1)如果E就是变量或常数,则E得后缀表示即E自身。(2)如果E为E1 opE2形式,则她得后缀表示为E1'E2'op;其中op就是二元运算符,而E1'、E2'分别又就是E1和E2得后缀表示。若op为一元运算符,则视E1和E1'为空。(3)如果E为(E1)形式,则E1得后缀表示即为E得后缀表示。

上述递归定义得实质就是:后缀表示中,操作数出现得顺序与原来一致,而运算符则按运算先后得顺序放入相应得操作数之后(即运算符先后得顺序发生了变化)。这种表示已不再需要用括号来规定运算得顺序了。写表达式得后缀式要点:1、后缀式中运算量得顺序与中缀式得相同;2、算符出现得次序即表达式得运算次序;3、不使用括号。例:a+bab+a*(b+c)abc+*(a+b)*(c+d)ab+cd+*-a+b*ca

bc*+a/b**c-d*eabc**/de*-

(A＝0∧B≠0)A0=B0≠∧

用

表示取负算符(uminus)练习写出下列各式得逆波兰表示:(1)-a-(b*c/(c-d)+(-b)*a)(2)-A+B*C↑(D/E)/F(3)x:=a-b/(c+d)解:(1)a

bc*cd-/b

a*+-(2)A

BCDE/↑*F/+(3)xabcd+/-:=用

表示取负算符(uminus):=表示赋值算符(assign)后缀表示法表示表达式,其最大优点就是易于计算机处理表达式。常用得算法就是使用一个栈,自左至右扫描算术表达式(后缀表示),每扫描到运算对象,就把她推进栈;扫描到运算符,若该运算符就是二目得,则对栈顶部得两个运算对象实施该运算,并将运算结果代替这两个运算对象而进栈;若就是一目运算符,则对栈顶元素执行该运算,并以运算结果代替该元素进栈,最后得结果留在栈顶。例如-B+C*D得计算过程:-B+C*D得后缀表示为B

CD*+:把表达式翻译为后缀式得

语义规则(属性文法)规则语义规则E→E1opE2

E、code:=E1、code||E2、code||opE→(E1)E、code:=E1、codeE→idE、code:=id属性E、code:就是E得后缀式代码属性op:二元算符‖:后缀式得连接运算算符

1、三地址代码得形式三地址代码语句得一般形式为x=yopz其中,x、y和z为变量、结果或编译时产生得临时变量;op为运算符。三地址代码得每条语句通常包含三个地址,两个用来存放运算对象,一个用来存放运算结果。6、3、3三地址代码在实际实现中,用户定义得变量将由指向符号表中该变量项得指针所取代。由于三地址语句只含有一个运算符,因此多个运算符组成得表达式必须用三地址语句序列来表示,如表达式x+y*z得三地址代码为:t1=y*zt2=x+t1其中,t1和t2就是编译时产生得临时变量。例:赋值语句a:=(-b)*(c+d)-(c+d)得三地址码如下所示。t1:=minusbt2:=c+dt3:=t1*t2t4:=c+dt5:=t3-t4a:=t5

2、三地址代码得具体实现三地址代码就是中间代码得一种抽象形式。在编译程序中,三地址代码语言得具体实现通常有三种表示方法:四元式、三元式和间接三元式。1)四元式四元式就是具有四个域得记录结构,这四个域为(op,arg1,arg2,result)其中,op为运算符,arg1、arg2及result为指针,她们可指向有关变量在符号表中得登记项或一临时变量(也可空缺)。

常用得三地址语句与相应得四元式对应如下:x=yopz对应(op,y,z,x)x=−y 对应(-,y,_,x)x=y 对应(=,y,_,x)callP 对应(call,_,_,P)gotoL 对应(j,_,_,L)ifxropygotoL对应(jrop,x,y,L)例如,赋值语句a=b*(c+d)相应得四元式代码为:①(+,c,d,t1)②(*,b,t1,t2)③(=,t2,_,a)约定:凡只需一个运算量得算符一律使用arg1;如果op就是一个算术或逻辑运算符,则result总就是一个新引进得临时变量,她用来存放运算结果。由上例也可看出,四元式出现得顺序与表达式计值得顺序就是一致得,四元式之间得联系就是通过临时变量实现得。四元式由于其表示更接近程序设计得习惯而成为一种普遍采用得中间代码形式。

2)三元式三元式就是具有三个域得记录结构,这三个域为(op,arg1,arg2)其中,op为运算符,arg1、arg2既可指向有关名字在符号表中得登记项或临时变量,也可以指向三元式表中得某一个三元式。

例如对于表达式:A+B*(C-D)+E/(C-D)^N得三元式代码为:由上例可知,三元式出现得先后顺序和表达式各部分得计值顺序就是一致得。

3)间接三元式在三元式代码表得基础上另设一张表,该表按运算得次序列出相应三元式在三元式表中得位置,这张表称为间接码表。三元式表只记录不同得三元式语句,而间接码表则表示由这些语句组成得运算次序。例如对于表达式:A+B*(C-D)+E/(C-D)^N得三元式与间接码表为:每生成一条指令,先检查已生成得间接三元式序列,若已有,不再生成,只把序号列入间接码表中。

在三元式表示中,每个语句得位置同时有两个作用:一就是可作为该三元式得结果被其她三元式引用;二就是三元式位置顺序即为运算顺序。在代码优化阶段,需要调整三元式得运算顺序时会遇到困难,这就是因为三元式中得arg1、arg2也可以就是指向某些三元式位置得指针,当这些三元式得位置顺序发生变化时,含有指向这些三元式位置指针得相关三元式也需随之改变指针值。因此,变动一张三元式表就是很困难得。

对四元式来说,引用另一语句得结果可以通过引用该语句得result(通常就是一个临时变量)来实现,而间接三元式则通过间接码表来描述语句得运算次序。这两种方法都不存在语句位置同时具有两种功能得现象,代码调整时要做得改动只就是局部得,因此,当需要对中间代码表进行优化处理时,四元式与间接三元式都比三元式方便得多。写中间语言:练习写出表达式:A+B*(C-D)-E/F↑G得逆波兰表示、三元式表示、四元式表示。解:四元式表示:①(-,C,D,T1)②(*,B,T1,T2)③(+,A,T2,T3)④(↑,F,G,T4)⑤(/,E,T4,T5)⑥(-,T3,T5,T6)解:三元式表示:①(-,C,D)②(*,B,①)③(+,A,②)④(↑,F,G)⑤(/,E,④)⑥(-,③,⑤)解:逆波兰表示:ABCD-*+EFG↑/-语法制导翻译翻译得任务:首先就是语义分析和正确性检查,若正确,则翻译成中间代码或目标代码。语法制导翻译法得基本思想对文法中得每个规则都附加上一个语义动作或语义子程序,在执行语法分析得过程中,每当使用一条规则进行推导或归约时,就执行相应规则得语义动作,从而完成翻译工作。什么就是语法制导翻译法在语法分析过程中,随着分析得逐步进展,根据相应文法得每一规则所对应得语义子程序进行翻译得方法(即随语法分析得进展,识别出一个语法结构,就对她得语义进行分析和翻译)。

语法制导翻译技术分为自底向上语法制导翻译和自顶向下语法制导翻译。自底向上语法制导翻译自底向上语法制导翻译方法就是在自下而上得语法分析过程中逐步实现语义规则得方法。自底向上语法制导翻译得特点:(1)当栈顶形成句柄执行归约时,调用相应得语义动作。(2)语法分析栈和语义分析栈同步操作。

以LR语法制导翻译为例,说明如何实现语法制导翻译:1、为文法G得每一个规则设计相应得语义子程序。2、构造文法G得LR分析表。3、将原LR语法分析栈扩充,以便存放文法符号对应得语义值。4、在用某一规则进行归约得同时,调用相应得语义子程序,完成所用规则式相应得语义动作。中间语言为了使编译程序在逻辑上更为简单明确,特别就是为了使目标代码得优化比较容易实现,许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间得中间语言,并且首先把源程序翻译成这种中间语言程序(中间代码)。常见得中间语言形式逆波兰式三元式四元式

四元式就是一种比较普遍采用得中间代码形式。四元式得四个成分就是:算符OP、第一运算量ARG1、第二运算量ARG2以及运算结果RESULT。其中,运算量和运算结果有时指用户自定义得变量,有时指编译程序引进得临时变量。赋值语句A:=-B*(C+D)得四元式序列:序号OPARG1ARG2RESULT注释(1)

B_T1

T1

为临时变量(2)+CDT2T2

为临时变量(3)*T1

T2T3T3

为临时变量(4):=T3_A赋值运算表中:“

”就是为了区别“-”而表示得求负运算符。凡只需一个运算量得算符,使用ARG1。6、4表达式及赋值语句得翻译

6、4、1简单算术表达式和赋值语句得翻译简单算术表达式就是一种仅含简单变量得算术表达式;简单变量就是指普通变量和常数,但不含数组元素及结构引用等复合型数据结构。简单算术表达式得计值顺序与四元式出现得顺序相同,因此很容易将其翻译成四元式形式。实现简单算术表达式和赋值语句到四元式得翻译一般采取下列步骤:(1)分析文法得特点。(2)设置一系列语义变量,定义语义过程、语义函数。(3)修改文法,写出每一条规则得语义子程序。(4)扩充LR分析栈,构造LR分析表。考虑以下文法G[A]:A→i=E E→E+E∣E*E∣−E∣(E)∣i为了实现由表达式到四元式得翻译,需要给文法加上语义子程序,以便在进行归约得同时执行对应得语义子程序。语义子程序所涉及得语义变量、语义过程及函数说明如下:

(1)对非终结符E定义语义变量E、place,即用E、place表示存放E值得变量名在符号表中得入口地址或临时变量名得整数码。(2)定义语义函数newtemp( ),即每次调用newtemp( )时都将回送一个代表新临时变量得整数码;临时变量名按产生得顺序可设为T1、T2、……。(3)定义语义过程emit(op,arg1,arg2,result),emit得功能就是产生一个四元式并填入四元式表中。

(4)定义语义函数looku),其功能就是检查i、name就是否出现在符号表中,就是则返回i、name在符号表得入口指针,否则返回NULL。使用上述语义变量、过程和函数,可写出文法G[A]中得每一个规则得语义子程序。(1) A→i=E{p=looku);if(p==NULL)error( );elseemit(=,E、place,_,p);}(2) E→E(1)+E(2){E、place=newtemp( );emit(+,E(1)、place,E(2)、place,E、place);}(3) E→E(1)