编译原理课件.ppt

1、5.3 常见中间语言简介,在着手讨论各种语法结构的语法制导翻译之前，我们首先应介绍一下目前经常使用的几种中间语言的形式。这是因为，语义子程序的设计，不仅依赖于相应语法结构中各个量的语义，而且还取决于要产生什么形式的中间代码.,5.3.1 逆波兰表示,波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。 特点:表达式中各个运算是按运算符出现的顺序进行的，故无须使用括号来指示运算顺序，因而又称为无括号式。下面我们对照地给出一些表达式的两种表示： 中缀表示后缀表示 A+BAB+ A+B*CABC*+ (A+B)*(

2、C+D)AB+CD+* x/yz-d*exyz/de*- (a=0b3)(exy) a0=b3exy,逆波兰式的特点,在两种表示中，运算对象出现的顺序相同； 在后缀表示中，运算符按实际计算顺序从左到右排列，且每一运算符总是跟在其运算对象之后。 由于后缀表示中的各个运算是按顺序执行的，因此，它的计值需从左到右依次扫视表达式中的各个符号， 每遇一运算对象，就把它压入栈顶暂存起来； 每遇一个二元（或一元）运算符时，就取出栈顶的两个（或一个）运算对象进行相应的运算，并用运算结果去替换栈顶的这两（或一）个运算对象； 继续扫视余留的符号，直到扫视完整个表达式为止。 当上述过程结束时，整个表达式的值将留于栈

3、顶。,逆波兰表示的扩充,逆波兰表示还可用于表示其它的语法结构。此时,运算符不再限于算术、关系和逻辑运算符，每个运算符的操作对象也可以不止两个。例如，赋值语句x:=a+b*c可按后缀式写为x abc*+:=。 为了用后缀式表示一些控制语句，我们假定将后缀式的各符号存放在一个一维数组POSTn中.还需引入一些转移操作符： p BR无条件转至POSTp（从POSTp 继续执行）； e p BZe是e的后缀表示，当e之值为零时，转向POSTp； e1 e2 p BLe1和e2分别是e1和e2的后缀表示，当 e1e2时，转向POSTp； 类似地，我们还可以定义BN(非零转)、BP(正号转)、BM(负号转

4、)等等。于是，条件语句IF e THEN S1 ELSE S2 可写成 e p1 BZ S1 p2 BR S2 其中， p1表示S2在数组POST中的起始位置； p2表示位于S2之后那个符号的位置。,例：翻译表达式的S-属性文法,Expr Expr + Term $=$1;POSTp =+;p+; | Term $=$1; Term Term * Factor $=$1;POSTp =*; p+; | Factor$=$1; Factor ( Expr ) $=$2; |iden$=p; POSTp =$1; p+;,我们以第3式为例介绍其原理。 首先，产生式左部Term的首地址显然应与右部第

5、一符号对应的首地址相同($=$1;)。 其次，按第3式归约时，或者说，翻译文法执行该语义动作时，右部符号Term和Factor对应的输出（即各自所代表的代码段）已经建立，并已存储在POST中，它们恰好就是运算符*的两个运算对象，所以，现在将*输出到POST中是合适的。 最后，因POSTp已被赋值（即翻译所得的部分代码已输出），应将下标计数加一。,对A+B*C进行分析翻译的过程,5.3.2 四元式和三元式,四元式是一种更接近目标代码的中间代码形式，由于这种形式的中间代码便于优化处理，因此，在目前的许多编译程序中得到了广泛的应用。 四元式是一种“三地址语句”的等价表示。它的一般形式为：(op,ar

6、g1,arg2,result) 其中，op为一个二元(也可是一元或零元)运算符; arg1,arg2分别为它的两个运算对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。四元式还可写为类似于PASCAL语言的赋值语句的形式： result := arg1 op arg2,四元式的格式,需要指出的是，每个四元式只能有一个运算符，所以，一个复杂的表达式只能由多个四元式构成的序列表示。 例如，表达式A+B*C可写为序列 T1:=B*C T2:=A+T1 当op为一元、零元运算（如无条件转移）时，arg2甚至arg1应缺省，即result:=op arg1或 op res

7、ult ；对应的一般形式为： (op,arg1,-,result) 或 (op,-,-,result) 。,三元式,为了节省临时变量的开销，有时也可采用一种三元式结构来作为中间代码，其一般形式为: (i) (op,arg1,arg2) 其中，(i)为三元式的编号，也代表了该式的运算结果；op,arg1,arg2的含义与四元式类似，区别在于arg可以是某三元式的序号，表示用该三元式的结果作为运算对象。例如，对于赋值语句a:=-b*(c+d)，若用三元式表示，则可写成 (U_minus, b, - ) ( + , c, d ) ( * , , ) ( := , ,a ) 式中的运算符U_minus

8、表示一元减运算。,翻译程序中使用的辅助函数,我们以算术表达式到三元式的翻译为例，说明如何为各产生式设计语义动作。为此，先介绍若干翻译过程中要使用的辅助函数： int LookUp(char *Name)以Name查符号表，若查到则返回相应登记项的序号(1),否则返回0。 int Enter(char* Name)以Name为名字在符号表中登录新的一项,返回值为该项的序号。 int Entry(char *Name)以Name为名字查、填符号表: int Entry(char *Name) int i=LookUp(Name); if(i) return i;else return Enter(

9、Name); ,翻译程序中使用的辅助函数,.注意，在实际的编译系统中，还应区分当前是否在处理说明部分：若是说明部分，则查表时i应为0（否则Name被重复定义）；若非，则i不能为0（否则Name尚未被定义）。 int Trip(int op,int arg1,int arg2)根据给定的参数产生一个三元式 (op,arg1,arg2) 并将它送入三元式表中，其返回值为表中序号。为区分参数arg表示的是三元式还是变量，约定当arg0表示变量在符号表中登记项序号；arg=0表示参数为空。,翻译三元式的S属性翻译文法,将表达式翻译成三元式的S属性翻译文法如下： ExprExpr $=$1; ExprE

10、xpr+Term $=Trip(+,$1,$3); |Term $=$1; |-Term $=Trip(U_minus,$2,0); TermTerm*Factor $=Trip(*,$1,$3); | Factor $=$1; Factor ( Expr ) $=$2; | iden $=Entry($1);,三元式和四元式之异同,在产生式8中，终结符iden的属性是它的词文yytext，用$1表示。每个非终结符都有一个属性，代表以该符号为根的语法树的一个子树的运算结果，该属性的取值可以是整型数，或为一三元式的序号，或为符号表项的序号。 比较三元式和四元式这两种表示方法可以看出，无论在一个三

11、元式序列还是四元式序列中，各个三元式或四元式都是按相应表达式的实际运算顺序出现的。其次，对同一表达式而言，所需的三元式或四元式的个数一般是相同的。 三元式比四元式更能节省存储空间,但不利于优化.可通过引入一些表格提高使用三元式的效率(略,见P200-201),间接三元式,增加执行表，作为对三元式的补充 如：x=(a+b)*c; b=a+b;y=c*(a+b); 三元式表示： 1 (+,a,b) 4 (=,b,1) 2 (*,1,c) 5 (+,a,b) 3 (=,x,2) 6 (*,c,5) 7 (=,y,6) 间接三元式表示： 三元式 执行表 1 (+,a,b) 1 2 (*,1,c) 2 3 (=,x,2) 3 4 (=,b,1) 4 5 (=,y,2) 1 2 5,5.3.3 其它表示法,除前面所述的逆波兰式、四元式、三元式外，常见的中间语言还有树形表示，接近PASCAL形式的P-代码，接近C格式的C-代码