编译原理 教学课件 ppt 作者 康慕宁 林奕 讲稿_4

1、第4章 语法制导的代码生成,一个编译器的目的是把源程序翻译成目标程序（也称为目标代码）。目标代码必须和源程序有相同的语义，也就是说，即使二者的表示方法不同，但对于给定的输入，必须计算出相同的结果。 仅关心源程序的词法和语法的正确性，这些是编译程序的前端的工作，即识别语法上正确的源程序。 本章我们把注意力转到编译程序的后端，即如何生成目标代码。 语义处理含有两个主要功能，一个是检查每个语法结构的表态语义，验证一个语法上合法的程序是否真正有意义，另一个是在表态语义正确的前提下，进行代码的翻译，即生成程序的另一种表示形式的中间语言代码或直接生成目标代码。 传统的方法是采用所谓“语法制导”方式完成这个翻译工作的。 分析器严格按照被分析的源程序的语法和语义，构造合适的中间（或目标多或少）代码序列。其中，对语法的依赖多于对语义的依赖。,4.1 常见的中间语言简介,逆波兰表示 波兰逻辑学家J.Lukasiewicz于1929年提出了一种表示表达式的方法。 按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。 特点：表达式中各个运算是按运算符出现的顺序进行的，故无需使用括号来指示运算顺序，因而又

2、称为无括号式。下面我们对照地给出一些表达式的两种表示。,（1）在两种表示中，运算对象出现的顺序相同。 （2）在后缀表示中，运算符按实际计算顺序从左到右排列，且每一运算符总是跟在其运算对象之后。,由于后缀表示中的各个运算是按顺序执行的，因此，它的计值很容易实现。 仅需从左到右依次扫视表达式中的各个符号，每遇一运算对象，就把它压入栈顶暂存起来； 每遇一个二元（或一元）运算符时，就取出栈顶的两个（或一个）运算对象进行相应的运算，并用运算结果去替换栈顶的这两（或一）个运算对象。 继续扫视余留的符号，直到扫视完整个表达式为止。 当上述过程结束时，整个表达式的值将留于栈顶。,逆波兰表示不仅能用于表示表达式，还可用于表示其他的语法结构。 此时的运算符不再限于算术运算符、关系运算符和逻辑运算符。 每个运算符的操作对象也可以不止两个。 例如，赋值语句x=a+b*c可按后缀式写为x abc*+=。,为了用后缀式表示一些控制语句，我们假定将后缀式的各符号存放在一个一维数组Pn中。 此外，还需引入一些转移操作符。 p J无条件把控制转至Pp（即从Pp开始继续执行，下同）。 e p JZ e是某表达式e的后缀表

3、示，当e的值为0时，转向Pp。 e1 e2 p JLe1和e2分别是表达式e1和e2的后缀表示，当e1e2时，转向Pp。 类似地，我们还可以定义JN（非零转）、JP（正号转）、JM（负号转）等。,条件语句 IF e THEN S1 ELSE S2 可写成 e p1 JZ S1 p2 JR S2 其中，e，S1和S2分别是e，S1，S2的后缀表示。另外，p1表示S2在数组P中的起始位置；p2表示位于S2之后那个符号的位置。,p1,p2,4.1.2 四元式,四元式是一种更接近目标代码的中间代码形式。由于这种形式的中间代码便于优化处理，因此，在目前许多编译程序中得到了广泛的应用。 四元式实际上是一种“三地址语句”的等价表示。它的一般形式为： (op, arg1, arg2, result) 其中，op为一个二元（也可是一元或零元）运算符；arg1、arg2分别为它的两个运算（或操作）对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。四元式还可写为类似于Pascal语言赋值语句的形式： result:=arg1 op arg2,需要指出的是，每个四元式只能有一个

4、运算符，所以，一个复杂的表达式需由多个四元式构成的序列来表示。例如，表达式A+B*C可写为序列 T1:=B*C T2:=A+T1 其中，T1，T2是编译系统所产生的临时变量名。 当op为一元、零元运算符（如无条件转移）时，arg2甚至arg1应缺省，即result:=op arg1或 op result ;对应的一般形式为： (op,arg1, ,result) 或 (op, , ,result) 在实际产生的四元式中，op往往用一整型数表示（操作符的代码），它可能附带有不止一种属性。例如，加运算可以分为定点加法和浮点加法两种，我们可用不同的整数值区分这两种加法。 四元式中运算对象arg1、arg2和结果域result，它们可以是指向符号表中某项的指示字，也可以是某个临时变量的序号. 因此，在实际的翻译过程中，还需要进行相应的查填符号表工作。 在本章中，我们只作原理性讨论。,4.1.3 其他表示法,除前面所述的逆波兰式、四元式外，常见的中间语言还有三元式表示和树形表示，以及接近Pascal形式的P代码，接近C格式的C代码等。 在本章以下的各节中，我们将分别对一些常见语法结构的语法制导翻

5、译进行讨论。为方便起见，我们假定翻译过程所采用的是自底向上的语法分析，并且假定翻译所产生的中间代码都是四元式。,4.2 赋值语句的翻译,为简便起见，暂且假定赋值语句中全部变量为同一类型。此外，在翻译过程中也暂不考虑做语义检查。 为构造各个语义子程序，我们先定义若干个辅助函数和语义变量（这里我们用C语言形式给出）。,int LookUp(char* Name) 以Name（变量名）为名字查符号表，若查到则返回相应登记项的序号（1）否则返回0。 int Enter(char*Name) 以Name为名字在符号表中登录新的一项，返回值为该项的序号。 int Entry(char*Name) 以Name为名字查、填符号表，即若Name已在表中，则返回其在表中的序号，否则将Name作为新元素填入表中，返回其在表中的序号。 int NewTemp(void) 产生临时变量的函数，每次调用都定义一个新的临时变量，返回值为该变量在符号表中的编号。为直观起见，我们把所产生的临时变量记为T1,T2。 X.PLACE文法符号X的一个属性，其值为整型，用于描述X相应的变量（它可以是用户定义的变量或编译系统生成

6、的临时变量）在符号表中登记项的序号。 int GEN(int Op, int Arg1,int Arg2,int Result)根据所给实参产生一个四元式：(Op,Arg1, Arg2,Result)，且存入四元式表中，返回值为该四元式的序号。Arg1或Arg2为0时表示该参数缺省。注意，虽然运算符是以整数码形式出现的，为便于阅读，在以后的描述中我们仍写出运算符本身。,简单赋值语句的翻译文法, StatementAssignSt AssignStVariable=Expr GEN(=,$3.PLACE, 0 , $1.PLACE); ExprExpr + Expr $.PLACE=NewTemp( ); GEN(+, $1.PLACE,$3.PLACE,$.PLACE); | Expr * Expr $.PLACE=NewTemp( ); GEN(*, $1.PLACE,$3.PLACE,$.PLACE); | ( Expr ) $.PLACE=$2.PLACE; | identifier $.PLACE=Entry($1); Variableidentifier $.PLACE=En

7、try($1);,上面的文法中，终结符号identifier具有的属性为该变量的词文（标识符），由词法分析程序提供的全局变量yytext给出。 文法符号属性的引用采用了语法分析器生成工具YACC的表示方法，$,$1,$2分别表示产生式左部符号、左部第一个文法符号、第二个文法符号的属性。 由于每个非终结符号的属性可能不止一个，故在C语言描述中往往用一个结构来存放它的全部属性。 例如，Expr和Variable的属性至少有两个，故可定义 struct AttrOfExprVar int PLACE; /*用于表示符号表中的序号或临时变量的编号*/ char Type; /*表示该表达式的类型*/ ,注意，上面所给文法是二义性的。由于我们能按某种规定赋予各运算符优先顺序和结合规则，所以我们仍能对它所产生的句子进行有效的语法分析和翻译。 Expr代表了一个变量（产生式6）或一个子表达式（产生式5）的运算（四元式）序列，该序列的运算结果存放于一个临时变量中，这个变量在变量表中的编号将作为Expr的PLACE属性被传递给了Expr。 我们未考虑表达式运算中的类型冲突问题。 在各四元式的op代码中，

8、本身就应含有类型信息。 许多语言允许混合运算，不过在运算前应先进行类型转换，使运算对象具有相同的类型。因此，我们还应定义类型转换算符，以便产生对运算对象进行转换的四元式,4.3 布尔表达式的翻译,布尔表达式是布尔运算量和逻辑运算符按一定语法规则组成的式子。 逻辑运算符通常有、 3种； 逻辑运算量则可以是逻辑常量（True或False）、布尔变量、关系表达式以及由括号括起来的布尔表达式。 不论是布尔变量还是布尔表达式，都只能取逻辑值True或False。 在计算机内通常用1（或非零整数）表示真值（True），用0表示假值（False）。 关系表达式是形如E1 rop E2的式子，其中E1和E2为简单算术表达式，Rop为关系运算符（,=,=,!=）。若E1和E2之值使该关系式成立，则此关系表达式之值为True，否则为False。,布尔表达式的语义在于指明计算一个逻辑值的规则，它在程序设计语言中有两个基本的作用：一是在某些控制语句中作为实现控制转移的条件；二是用于计算逻辑值本身。 布尔表达式的计值原理与算术表达式的计值原理非常相似，也是从左至右，并按运算符间的优先关系和结合规则来进行。在常见

9、的程序设计语言中，各类运算符的优先顺序（由高至低）如下： 括号； 算术运算符*、/、+、； 关系运算符、=、； 逻辑运算符、。 其中，嵌套的括号按从里至外的顺序；算术运算符及逻辑运算符中的、按左结合规则；所有的关系运算符均无结合性等。 常见程序设计语言表示、的方法各有不同，为了方便起见，下面我们以Pascal语言的布尔表达式文法进行讨论。 EE and E|E or E| not E| (E)| i | i rop i,对于布尔表达式的计值和翻译，当然可采用与算术表达式类似的方式来进行。 例如，对于布尔表达式A or B and C，可翻译为如下的四元式： (&,B,C,T1 ) (|,A,T1,T2 ) 在上面的四元式表示中，我们使用了C语言的布尔运算符来描述四元式中的运算符。,对于一个布尔表达式而言，我们的最终目的仅仅是为了判定它的真假值。 在实际计算时，有时不需要将一个布尔表达式从头算到尾，而只需计算它的一个子表达式，便能确定整个布尔表达式的真假值。 例如，对于A or B，只要知道A为真，则无论B取何值，表达式的结果一定为真; 对于A and B，只要知道A为假，则无论B取何值，其结果必为假。 可见，对于3种逻辑运算，可作如下等价的解释： A and B(A) ? B : 0 A or B(A) ? 1 : B （4.1） Not A(A) ? 0 : 1 上面的解释中，我们采用了C语言条件表达式的格式,且用1（或非零值）表示真值，用0表示假值。,利用对3种逻辑运算的解释，可将任何布尔表达式表述为等价的条件表达式结构。例如，对于布尔表达式A or (B and ( not C or D)，其等价的表述是： A？1：(B？(C？0：1)？1：D)：0) 显然，采用此种结构可产生更为有效的中间代码。 对上式的计算，根据A，B，C，D的不同取值，将有不同的计算结果及运算的终止点。 例如，当A=1 (真) 时，结果为1且终止于左边第一个“1”处。 这种终止点我们称为该布尔表达式的出口，同时，把使布尔表达式取

《编译原理 教学课件 ppt 作者 康慕宁 林奕 讲稿_4》由会员E****分享，可在线阅读，更多相关《编译原理 教学课件 ppt 作者 康慕宁 林奕 讲稿_4》请在金锄头文库上搜索。