Chapt6_第6章 语法制导翻译技术PPT课件下载推荐.pptx
- 文档编号:2941704
- 上传时间:2023-05-01
- 格式:PPTX
- 页数:79
- 大小:686.30KB
Chapt6_第6章 语法制导翻译技术PPT课件下载推荐.pptx
《Chapt6_第6章 语法制导翻译技术PPT课件下载推荐.pptx》由会员分享,可在线阅读,更多相关《Chapt6_第6章 语法制导翻译技术PPT课件下载推荐.pptx(79页珍藏版)》请在冰点文库上搜索。
,第6章语法制导翻译技术,语义往往是上下文有关的,只宜于用口语描述,语义形式化很困难。
目前,比较流行的语义描述和语义处理方法是语法制导翻译技术。
语法制导翻译技术基础:
形式描述的属性翻译文法特点:
把语法与语义分开,但又在语法分析的同时进行相应的语义工作提高了实用性,6.1翻译文法,例:
设计一个翻译器,它能将中缀表达式翻译成波兰后缀表达式。
假设输入串是a+b*c,则,翻译器,输入串a+b*c,输出串abc*+,问题:
如何实现这个翻译过程呢?
先看输入串a+b*c的推导过程:
中缀表达式文法:
EE+TETTT*FTF,F(E)FaFbFc,EE+TE+T*FE+T*cE+F*cE+b*cT+b*cF+b*ca+b*c,由推导过程EE+TE+T*FE+T*cE+F*cE+b*cT+b*cF+b*ca+b*c,得到输入串的语法树:
记住翻译目标是:
abc*+,E,E,+,T,T,T,*,F,添加叶子结点,用表示输出操作(输出其后的字符)。
E,E,+,T,T,T,*,F,*,+,Fa将符号的叶子结点从左到右连起来,得到abc*+(注意,这种带有的符号串称为动作序列。
)执行这个符号序列,得到abc*+,这就是翻译结果!
TFa,E,问题:
如何得到这棵带动作符号的语法树呢?
在中缀表达式文法(输入文法)的基础上加入动作符号,,得到翻译文法。
E,F(E),EE+TETFa,TT*FTF,FbFc,EE+T+ETTT*F*,F(E)FaaFbb,TF,Fcc,输入文法,翻译文法,例用输入文法推导a+b*c的过程如下:
EE+TE+T*FE+T*cE+F*cE+b*cT+b*cF+b*ca+b*c,用翻译文法进行相同的推导:
EE+T,F(E),ETFa,TT*FTF,EE+T+ETTT*F*,F(E)FaaFbb,FbFcTFFcc,输入文法,翻译文法,输入序列,EE+T+E+T*F*+E+T*cc*+E+F*cc*+E+bb*cc*+T+bb*cc*+F+bb*cc*+aa+bb*cc*+活动序列,将活动序列中的输入序列去掉,得到动作序列:
abc*+,翻译文法是上下文无关文法的推广,是在描述语言文法规则的右部适当位6置.加1入翻语义译动文作法得到的。
为了区分文法符号与语义动作,在文法的表示中,将代表语义动作的符号前面加动作符号标记来表示。
输入序列:
用输入文法通过推导可以得到的终结符号串。
活动序列:
用翻译文法通过推导得到的符号串。
动作序列:
从某活动序列中去掉所有输入序列,即由所有动作符号组成的符号串。
6.1翻译文法,6.1翻译文法,上例的翻译文法可表示成:
G(E)=Vn,Vt,P,E,其中Vn=E,T,FVt=a,b,c,+,*,+,*,a,b,cP=EE+T+,ET,TF,Faa,TT*F*,Fbb,Fcc在高级程序设计语言的翻译中有各种各样的翻译文法其中的动作符号代表不同的语义动作。
在翻译文法中,如果的动作就是输出其后的符号,可称该文法为符号串翻译文法。
符号串翻译文法是翻译文法中的一种特定类型。
6.2语法制导翻译,其中:
a+b*cabc*+,为输入序列为动作序列,如果执行该动作序列中的动作,则产生输出序列abc*+,这就是输入序列a+b*c的翻译结果。
由于这种翻译结果是通过翻译文法获得的,所以就称为语法制导翻译。
语法制导翻译:
就是给定一输入序列,根据翻译文法获得翻译该符号串的活动序列,从活动序列中分离出动作符号串,然后执行该动作符号串所规定的动作,从而得到翻译结果。
例:
根据前面的算术表达式翻译文法,对于输入符号串a+b*c,推导出的活动序列为:
aa+bb*cc*+,6.2语法制导翻译,按语法制导翻译的方法来实现语言的翻译首先要根据输入语言的文法,分析各条产生式的语义,即分析他们要求计算机所完成的操作。
分别编出完成这些操作的子程序或程序段(称为语义子程序或语义动作)把这些子程序或程序段的名字作为动作符号插入到输入文法各产生式右部的适当位置上,从而实现翻译文法。
6.3自顶向下语法制导翻译自顶向下的语法制导翻译有递归下降翻译和LL
(1)翻译。
递归下降翻译:
递归下降翻译器的实现思路与递归下降分析基本相同,要求也一样,即不能有左递归,头符号集不能相交,只需在适当的位置插入实现动作符号的子程序。
6.3自顶向下语法制导翻译,例算术表达式翻译文法如下:
EE+T+ET,TT*F*TFF(E)Fii注:
为输出,其后的符号串。
解:
去掉文法中的左递归,修改后文法为:
ET+T+TF*F*,F(E)|ii,处理E的递归下降翻译程序流程图,处理T的递归下降翻译程序流程图,TF*F*,F(E)|ii处理F的递归下降翻译程序流程图,6.3自顶向下语法制导翻译自顶向下的语法制导翻译有递归下降翻译和LL
(1)翻译。
LL
(1)翻译:
LL
(1)翻译器的实现思路与LL
(1)分析法基本相同,要求也一样,即不能有左递归,头符号集不能相交,只需在文法适当的位置插入实现动作符号的子程序,并在LL
(1)分析表中加入相应的动作符号。
6.3自顶向下语法制导翻译,例(P126)考虑下面的输入文法:
AaBcDAbBcBaADcDDb,输入文法的LL
(1)分析表,设其翻译文法为:
AvawBxcyDzBcrDcDn,AbBamADsb,6.3自顶向下语法制导翻译,翻译文法的LL
(1)分析表,注意:
对于翻译文法,动作符号像其它符号一样入栈。
但当动作符号处于栈顶时,无论当前的输入符号是什么,都要执行由该动作符号所规定的操作,并将该动作符号从栈顶弹出,且不移动读符号指针。
6.3自顶向下语法制导翻译,假如翻译器的分析栈的栈顶符号为A,且当前输入符号为a,那么将发生的动作是弹出A,zDycxBwav入栈。
由于此时栈顶为动作符号v,因此v出栈,并执行由该动作符号所规定的操作,对于该符号串翻译文法就是要输出v,即out(v)。
紧接着,a出栈,读下一个符号c。
然后,动作符号w为栈顶,因此w出栈,并执行由该动作符号所规定的操作,对于该符号串翻译文法就是要输出w,即out(w)。
ac#,v出栈并执行,a出栈,读入c,w出栈并执行,ac#,6.3自顶向下语法制导翻译,翻译文法的LL
(1)翻译的总控程序总结:
1)当翻译器的控制执行程序根据栈顶符号和当前输入符号查该表得到元素为空时,则转错误处理程序。
2)若控制执行程序识别栈顶符号为动作符号时,不管当前输入符号是什么,将该动作符号从栈中弹出并转相应的子程序以完成所需的翻译(执行动作)。
对于符号串翻译文法,其语义动作为输出动作符号中的符号串。
6.4属性翻译文法,引例声明语句文法:
TYPEID;
,ID其中TYPE代表类型,其值可为int或real或bool。
问题:
将输入符号串“inta,b;
”翻译为:
intaintb思考:
能否通过在文法产生式右部添加动作符号实现该翻译?
6.4,引例声明语句文法:
,ID,属性翻译文法输入:
inta,b;
输出:
inta,intb,其中TYPE代表类型,其值可为int或real或bool。
输入串inta,b;
”的推导过程:
TYPEID;
TYPEID,ID;
TYPEID,ID问题:
无法将文法符号TYPE、ID与输入符号int、a、b关联起来!
6.4属性翻译文法,6.4属性翻译文法,属性:
对文法符号引进一些属性,这些属性代表与文法符号相关的信息,如类型、值、代码序列、符号表内容等。
属性值可以在语法分析过程中计算和传递。
属性一般用标识符表示,通常写在相应文法符号的下边,它的意义局限于它所在的产生式。
属性加工的过程就是语义的处理过程。
属性的分类综合属性继承属性通常规定,每个文法符号的综合属性和继承属性的交集为空。
6.4属性翻译文法,综合属性:
综合属性的计算规则是按“自下而上”方式进行,即文法产生式左部符号的某些属性根据其右部符号的属性和/或自己的其它属性计算而得。
在语法树中,如果一个结点的某一属性,其值由子结点的属性值来计算,则该属性为综合属性。
综合属性可用“”来表示。
对终结符号其综合属性具有指定的初始值该初始值由词法分析程序提供。
例ApXq,rYs,tp=q+s,r=p+t其中,p是综合属性,r不是综合属性,q,s,t不能确定,需参考其它产生式的属性计算规则才能确定。
6.4属性翻译文法,继承属性:
继承属性的计算规则是按“自上而下”方式进行,即文法产生式右部符号的某些属性根据其左部符号的属性和/或右部的其它符号的某些属性计算而得。
在语法中,如果一个结点的某一属性,其值由该结点的父结点和/或兄弟结点的属性值来计算,则该属性为继承属性。
继承属性可用“”来表示。
开始符号的继承属性具有初始值。
例ApXq,rYs,tp=q+s,r=p+t显然,r是继承属性。
6.4属性翻译文法,例算术表达式的属性翻译文法:
SEqANSWERrEpEq+TrEpTq,r=qp=q+rp=q,FpNUMq,p=q,6.4属性翻译文法语义规则(语义动作或翻译子程序):
为输入文法配备计算属性的计算规则,称为语义规则。
如上例中,p=q+r就是语义规则。
产生式只能产生符号串,它并未指明所产生的符号串的含义是什么。
语义规则给出了一个产生式所产生的符号串的含义,而且还根据这种含义规定了对应的加工动作。
这些加工动作包括查填各类表格、改变编译程序的某些变量的值、打印各种错误信息以及生成中间形式代码等。
6.4属性翻译文法,属性翻译文法(或属性文法):
对于某个压缩的上下文无关文法,当为文法符号引进一组属性,且让该文法中的产生式附加上语义规则时,称该上下文无关文法为属性翻译文法。
6.4属性翻译文法,语义分析的翻译过程:
步骤1分析输入符号串,建立语法树;
步骤2从语法树得到描述结点属性间依赖关系的依赖图,由此依赖图得到语义规则的计算次序;
步骤3进行语义规则计算,得到翻译结果。
语义分析翻译过程的分类:
自顶向下的翻译自底向上的翻译,6.4属性翻译文法,自顶向下的语义分析翻译过程的示例声明语句文法:
,ID,其中TYPE代表类型,其值可为int或real或bool。
属性翻译文法:
TYPEtIDnSET_TYPEn1,t1;
t2=t,t1=t,n1=n,IDnSET_TYPEn1,t1t2=t,t1=t,n1=n3)其中,过程SET_TYPE输出变量名及其类型。
给出输入符号串“inta,b;
”的语义分析翻译过程。
输入:
aintbint,6.4属性翻译文法,解:
输入符号串“inta,b;
”的语义分析翻译过程:
声明语句TYPEintIDa变量表;
,IDb变量表inta,b;
的语法树声明语句,SET_TYPEn1,t2,IDn,TYPEt,变量表t2;
SET_TYPE,n1,t1,n,变量表,t2,,ID,inta,b;
的语法树加入动作符号和属性,t2=t,t1=t,n1=n,t2=t,t1=t,n1=n,6.4属性翻译文法,声明语句,;
SET_TYPEa,int,IDa,TYPEint,变量表int,SET_TYPEb,int,变量表int,,IDbinta,b;
的翻译树,输出aintbint,解:
声明语句,TYPEtIDnSET_TYPEn1,t2变量表t2;
的语法树加入动作符号和属性,t2=t,t1=t,n1=n,t2=t,t1=t,n1=n,6.4属性翻译文法,SEANSWEREE+TETTT*FTFF(E)FNUM,SEqANSWERrr=q,p=q+rp=qp=q*rp=q,EpEq+TrEpTqTpTq*FrTpFqFp(Eq)FpNUMq,p=qp=q,自底向上的语义分析翻译过程的示例输入算术表达式3+2*3,应输出9,给出输入符号串3+2*3的语义分析翻译过程。
翻译文法属性翻译文法,SEE+T,T*F,T,FF,NUM3,NUM3NUM23+2*3的语法树,S,E9,+,E3,F3,*,T2,T3,F3F2,NUM3NUM3NUM23+2*3的翻译树,解:
输入符号串3+2*3的语义分析翻译过程:
6.4属性翻译文法,输出9ANSWER9T6,6.4属性翻译文法,例设计一个属性翻译文法,要求对于输入的中缀表达式,经过翻译将输出具有下面性质的四元组代码序列输出符号串中的每个双目运算都用一个四元式表示。
四元组中的四元式的顺序与执行时要完成的运算顺序相同。
每个四元式有四个参数,自左向右的顺序为运算符,左操作数,右操作数,运算结果例如,翻译器处理表达式a+b将生成如下的四元式ADD,a,b,t1其中t1是临时变量,保存表达式的结果。
翻译器处理表达式a+a*b将生成MULT,a,b,t1ADD,a,t1,t2,6.4属性翻译文法,解:
第一步先设计满足上述要求的翻译文法。
翻译文法:
EE+TADDETTT*FMULTTFF(E)FID,输入文法:
EE+TETTT*FTFF(E)FID,6.4属性翻译文法,其中,NEWT是一个函数,每次调用它时返回一个新的临时变量名,临时变量名按产生顺序分别为t1、t2、等。
动作符号ADDy,z,t输出“ADD,y,z,t”,动作符号MULTy,z,t输出“MULT,y,z,t”,第二步,构造属性和求值规则,把翻译文法构造成属性翻译文法。
6.4属性翻译文法,IDaIDa表达式a+a*b的语法树,Et2,Tt1,+,Ea,*,TaTa,FaFa,IDaIDa表达式a+a*b的翻译树,ADDa,t1,t2FbMULTa,b,t1IDb,产生新变量t2,输出:
ADD,a,t1,t2,产生新变量t1,输出:
MULT,a,b,t1,6.5属性文法的自顶向下翻译,声明语句,;
SET_TYPEa,int,IDa,TYPEint,变量表int,SET_TYPEb,int,IDb,,,变量表int,属性值依赖于上一级的,自顶向下的语义分析翻译过程示例-回顾属性翻译文法:
t2=t,t1=t,n1=n,IDnSET_TYPEn1,t1t2=t,t1=t,n1=n3)输入符号串“inta,b;
”的翻译树如属性下值。
依赖于左,边的a和int,6.5属性文法的自顶向下翻译,分析按照自顶向下的有序方式对某个属性求值时,应当确保所需要的基本值已知。
我们需要对属性计算规则设定约束条件!
要求文法必须是L-属性文法。
6.5属性文法的自顶向下翻译,L-属性翻译文法满足下面三个条件:
给定一产生式,其右部符号的继承属性值是以左部符号的继承属性或出现在给定符号左边的产生式右部符号的任意属性为变元的函数。
给定一产生式,其左部符号的综合属性值是以左部符号的继承属性或某个右部符号的任意属性为变元的函数。
给定一动作符号,其综合属性值是以该动作符号的继承属性为变元的函数。
6.5属性文法的自顶向下翻译,例假设文法中有产生式为:
AI1S2,S3BI4CS5DS6I7,I8EI9根据L-属性的限制条件,I4=F(I1)、I4=123、I7=G(I1)合法,而I4=H(S2)、I4=K(S6,I4)则不合法。
例(P134)假设文法中有产生式为:
Aa1a2Bb1b2Cc1c2A、B和C的属性可以按下面的顺序进行求值,1)A的继承属性a1;
3)B的综合属性b2;
5)C的综合属性c2;
2)B的继承属性b1;
4)C的继承属性c1;
6)A的综合属性a2。
6.5属性文法的自顶向下翻译,为了进行属性翻译的程序设计,我们采用下述约定:
1)产生式中的属性名字用作变量和参数的名字。
LabEiRj写成子程序(函数)时,表示为:
intL(inta,intb)inti,j;
2)所有出现在左部的同名非终结符,应具有相同的属性名表。
在左部同名非终结符属性名表的同一化过程中,属性名称的改动范围仅局限于产生式左部。
属性重新命名以后,应修改某些属性求值规则。
产生式LabEiRj,例i,j=b,a=i+2,LxyHzw按约定2,应改成LabEiiRjLabHzw,w=y,z=2,x=z+yi,j=b,a=i+2w=b,z=2,a=z+b,6.5属性文法的自顶向下翻译,为了进行属性翻译的程序设计,我们采用下述约定:
3)如果两个属性有相同的值,那么可给它们相同的名字,但对于左部符号的属性值相等时,不能改变成相同的名字。
例对规则LabaBcCd,当c,d=a时,可写成:
LabaBaCa但当b=a时,上式不能写成LaaaBaCa这是因为过程L(inta,intb)不可写成L(inta,inta)。
6.5属性文法的自顶向下翻译,采用C语言编写L-属性文法递归下降翻译程序时采用的方法:
1)形式参数:
产生式左部非终结符的属性名表设计成相应过程的形式参数表。
继承属性值形参(即简单变量)综合属性指针变量。
2)局部变量:
在产生式中,与左部属性名不同的属性名变成相应过程的局部变量。
3)非终结符的代码:
产生式右部的每个非终结符的过程调用,该非终结符的属性作为实参。
要注意:
如果实参是简单变量,形参是指针变量,调用时实参应为简单变量的地址。
6.5属性文法的自顶向下翻译,采用C语言编写L-属性文法递归下降翻译程序时采用的方法:
4)输入符号的代码:
对文法中出现的每个输入符号(即终结符号),将赋值语句插入到过程中它所对应的NEXTSYM之前,把保存在读符号程序NEXTSYM中的终结符号属性(某个全局变量中)赋给输入符号属性中的每个属性变量。
5)动作符号的代码:
对出现在文法中的每个动作符号插入代码便于对动作符号的综合属性进行计算,并且把结果赋给对应于该综合属性的变量,然后输出相应的符号。
对文法中出现的每个输入符号(即终结符号),将赋值语句插入到过程中它所对应的NEXTSYM之前,把保存在读符号程序NEXTSYM中的终结符号属性(某个全局变量中)赋给输入符号属性中的每个属性变量。
对出现在文法中的每个动作符号,插入代码便于对动作符号的综合属性进行计算,并且把结果赋给对应于该综合属性的变量,然后输出相应的符号。
6)属性规则的代码:
与每个产生式有关的属性求值规则,插入其代码以便对属性求值规则的右部求值,并把结果赋给该规则左部的每个变量。
可以把这些代码放在属性计算规则的所有自变量已知之后,且函数值被使用之前的任何地方。
7)主程序:
C语言都是从MAIN函数开始运行。
在MAIN函数中,对文法的开始符号,其相应的每一个综合属性的名字变成主程序的局部变量,然后调用开始符号对应的过程。
在调用时,如果实参对应开始符号的继承属性,则对每个继承属性以该属性的初始值作为值参传入,对每个综合属性取该属性的局部变量的地址传入。
6.5属性文法的自顶向下翻译,例算术表达式属性翻译文法如下,用C语言实现其递归下降翻译器。
EtTpEpt,t0=NEWTt=p,t0=NEWTt=p,Ept+TrADDp,r,t0Et0tEptTtFpTptTpt*FrMULTp,r,t0Tt0tTptFp-(Ep)|IDp,6.5属性文法的自顶向下翻译,main()/主程序intes=0,t;
printf(请输入算术表达式(操作数只能是单个字母):
);
ch=getchar();
printf(输出四元式为:
n);
es=E(,/调分析表达式E的翻译程序,EtTpEpt,if(es=0)printf(n翻译成功!
elseprintf(n表达式有语法错误!
6.5属性文法的自顶向下翻译,/产生式EtTpEpt的翻译子程序,t为综合属性,形参用指针变量intE(int*t)intes=0;
intp;
es=T(,E(int*t),intp,T(&
p),E(p,t)return,/产生式Ept+TrADDp,r,t0Et0t|的翻译子程序,其中,p为继承属性,形参用整型变量,t为综合属性,形参用指针变量,intE1(intp,int*t),intr,es=0,t0;
if(ch=+)ch=getchar();
es=T(,t0=NEWT();
/产生一个临时变量printf(ADD,%c,%c,%cn,p,r,t0);
es=E1(t0,t);
return(es);
else*t=p;
return(0);
E(intp,int*t)intr,t0;
t0=NEWT(),E(t0,t),return,*t=p,n,+?
ynextsymT(&
r),n,/返回一个临时变量,顺序产生A、B、.、Z,最多产生26个临时变量intNEWT()staticinti=64;
/设置i为静态变量确保下次调用时i为上次调用的结果i=i+1;
return(i);
6.5属性文法的自顶向下翻译,6.5属性文法的自顶向下翻译,/产生式TtFpTpt的翻译子程序,t为综合属性,形参用指针变量intT(int*t)intes=0,p;
/调分析F子程序/调分析T子程序,es=F(,T(int*t),intp,F(&
p),T(p,t)return,/产生式Tpt*FrMULTp,r,t0Tt0t|的翻译子程序intT1(intp,int*t),intr,es=0,t0;
if(ch=*)ch=getchar();
es=F(,t0=NEWT();
/产生一个临时变量,return(es);
return(0);
T(int
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Chapt6_第6章 语法制导翻译技术 Chapt6_ 语法 制导 翻译 技术