编译原理课件.ppt

《编译原理课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、波兰表示的扩充逆波兰表示还可用于表示其它的语法结构。此时,运算符不再限于算术、关系和逻辑运算符，每个运算符的操作对象也可以不止两个。例如，赋值语句x:=a+b*c可按后缀式写为xabc*+:=。为了用后缀式表示一些控制语句，我们假定将后缀式的各符号存放在一个一维数组POST[n]中.还需引入一些转移操作符：pBR—无条件转至POST[p]（从POST[p]继续执行）；e’pBZ—e’是e的后缀表示，当e’之值为零时，转向POST[p]；e1’e2’pBL—e1’和e2’分别是e1和e2的后缀表示，当e1’

4、M(负号转)等等。于是，条件语句IFeTHENS1ELSES2可写成e’p1BZS1’p2BRS2‘其中，p1表示S2‘在数组POST中的起始位置；p2表示位于S2‘之后那个符号的位置。例：翻译表达式的S-属性文法⒈Expr→Expr‘+’Term{$$=$1;POST[p]=‘+’;p++;}⒉

5、Term{$$=$1;}⒊Term→Term’*’Factor{$$=$1;POST[p]=‘*’;p++;}⒋

6、Factor{$$=$1;}⒌Factor→‘(‘Expr‘)’{$$=$2;}⒍

7、iden{$$=p;POST[p]=$1;p++;}我们以第3式为例介绍其原理。首先，产生式左部Te

8、rm的首地址显然应与右部第一符号对应的首地址相同($$=$1;)。其次，按第3式归约时，或者说，翻译文法执行该语义动作时，右部符号Term和Factor对应的输出（即各自所代表的代码段）已经建立，并已存储在POST中，它们恰好就是运算符‘*’的两个运算对象，所以，现在将‘*’输出到POST中是合适的。最后，因POST[p]已被赋值（即翻译所得的部分代码已输出），应将下标计数加一。步骤分析栈SR余留输入串分析动作及归约所用产生式和子程序后缀表示0#A+B*C#移进1#A+B*C#归约F→i,SUB6A2#F+B*C#归约T→F,SUB4A3#T+B*C#归约E→T,SUB2A4#E+B*C#移

9、进A5#E+B*C#移进A6#E+B*C#归约F→i,SUB6AB7#E+F*C#归约T→F,SUB4AB8#E+T*C#移进AB9#E+T*C#移进AB10#E+T*C#归约F→i,SUB6ABC11#E+T*F#归约T→T*F,SUB3ABC*12#E+T#归约E→E+T,SUB1ABC*13#E#ABC*+对A+B*C进行分析翻译的过程5.3.2四元式和三元式四元式是一种更接近目标代码的中间代码形式，由于这种形式的中间代码便于优化处理，因此，在目前的许多编译程序中得到了广泛的应用。四元式是一种“三地址语句”的等价表示。它的一般形式为：(op,arg1,arg2,result)其中，op

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