大连理工大学编译方法中间代码及解释程序课案.docx

大连理工大学编译方法中间代码及解释程序课案.docx

《大连理工大学编译方法中间代码及解释程序课案.docx》由会员分享，可在线阅读，更多相关《大连理工大学编译方法中间代码及解释程序课案.docx（73页珍藏版）》请在冰点文库上搜索。

大连理工大学编译方法中间代码及解释程序课案

第七章语义分析与代码生成

7.1语法制导翻译

编译程序的实质性工作是翻译，即为源程序生成目标代码。

为此，我们必须知道程序的含义是什么（语义分析）？

应该翻译成什么（代码生成）？

在三、四章，我们主要讨论了源程序的识别，即判定一个源程序是否符合源语言的文法。

在讨论语法分析时曾说过，上下文无关文法不足以描述编程语言的全部语法特征。

为了说明这一点，让我们来看一个例子：

VAR

i:

integer;

BEGIN

j:

=i*i

END;

如果j没有在外层块中说明，那么赋值语句中出现的j就是非法的。

这是一种上下文敏感的成分。

为了清楚地说明这一点，假定j是在自顶向下分析过程中由非终极符<变量>导出的，在这次推导之前的句型为

αVARj:

integer;β<变量>γ

其中α,β,γ为符号串。

推导后的句型为

αVARj:

integer;βjγ

为了保证变量在使用前必须说明，需要有如下形式的规则：

VARj:

integer;β<变量>→VARj:

integer;βj

而不是

<变量>→j

即<变量>只有在一定的上下文中才可以展开成j。

上下文敏感成分的分析实质上是语法分析的内容。

但是，因为我们的语法分析是以上下文无关文法为基础的，没有考虑上下文敏感成分的处理，所以必须在语义分析时加以考虑。

这相当于把语言的敏感成分划归为语言的语义范畴（尽管在概念上并非如此）。

比如说在处理说明

VARj:

integer

时，语义分析应该将这个说明所提供的信息填入符号表，即完成对符号表的插入操作；当然也需要完成其它的语义分析工作，而后在确定是否可用规则

<变量>→j

进行推导时，就可通过对符号表的检索操作来完成。

如果符号表中有标识符j，而且j又是个变量标识符，就可以用此规则进行推导。

除了敏感成分的处理之外，为了生成目标代码，所需要完成的一切操作都属于语义分析的范畴。

考虑如下条件语句：

IFETHENS1ELSES2

为它生成的目标代码应具有图7.1的结构（称为它的目标结构），其中，计算E的目标指令、S1和S2的目标指令是在处理表达式和语句时生成的，处理条件语句时所生成的指令就是“jumpfl0”和“jumpl1”。

前者的含义为表达式E的值为false时，程序转向l0的指令继续执行，后者为无条件转到l1的指令执行。

问题在于编译程序在处理条件语句时是从左向右进行的。

因此，当要生成jumpf指令时，不知道l0的值，因为S1的目标这时尚未生成，不知道它究竟有多少条指令。

在生成jump这条指令时也有同样问题。

为了解决这个问题，在生成jumpf和jump指令时，应先记录这两条指令本身的位置，等以后再回填它们的转向目标。

假设当前要生成的指令位置为lc，条件语句的处理算法如下：

IFsy=ifsyTHEN

insymbol;

expression;{处理表达式}

IF表达式类型<>boolsTHEN

error（n）

ENDIF;

lc1:

=lc;

生成jumpf指令；lc:

=lc+1;

IFsy=thensyTHEN

insymbol;

statement;{处理语句}

IFsy=elsesyTHEN

lc2:

=lc;

生成jump指令；

lc:

=lc+1;

回填jumpf指令的转向目标；

insymbol;图7.1

statement;{处理语句}

回填jump指令的转向目标；

ELSE

回填jumpf指令的转向目标

ENDIF

ENDIF

ENDIF；

可以看出，除了检查表达式类型外（敏感成分的处理），语义分析工作还包括转向目标的回填等操作。

与第四章给出的条件语句的语法分析算法相比，上述算法只是增加了如下几个操作：

:

IF表达式类型<>boolsTHEN

error（n）;

ENDIF;

lc1:

=lc;

生成jumpf指令；

lc:

=lc+1;

:

lc2:

=lc;

生成jump指令；

lc:

=lc+1;

回填jumpf指令的转向目标；

:

回填jump指令的转向目标；

:

回填jumpf指令的转向目标；

这相当于说上面的处理算法是根据如下文法规则写成的：

→IF<表达式>THEN<语句>ELSE<语句>

→IF<表达式>THEN<语句>

即在文法规则中嵌入了相应的语义加工操作。

于是，语义分析及代码生成可以随着语法分析的进行，通过嵌入相应的语义加工操作来完成。

这种方法称为语法制导翻译，因为语言的文法规则确定了相应的语义分析类型及生成代码的性质，而且分析算法的主体控制是相应的文法规则。

本章后面将结合实例讨论各种典型的语言结构的语义分析及代码生成。

7.2目标机

为了完成代码生成工作，必须有一个提供运行环境的目标机。

最直接的方法是，在哪个机器上运行的编译程序就生成那个机器的目标代码，或生成那个机器的汇编语言程序，然后经过汇编程序汇编成可以执行的机器语言程序。

汇编后产生的目标代码可以具有绝对地址，从而可以装到内存的固定区域去执行；也可以具有浮动的（相应的）地址，再由装入程序（或者是连接装配程序）来为地址代真（即转换成绝对地址），即可用于执行。

无论是哪一种情况，都需要知道机器的硬件，诸如有多少个累加器、特殊寄存器、地址空间的大小等。

但事实上，代码生成也可先脱离特定的硬件环境。

一种逐渐流行的方法是为一个抽象机生成代码，然后，在特定的机器上写一个解释程序来解释抽象机的指令。

下面我们将介绍一个抽象机，它是专为PASCAL-S设计的，与任何特定的计算机无关，不妨称为PASCAL-S处理机。

尽管PASCAL-S处理机在硬件上并不存在，但它的指令不难落实到任何特定的计算机上。

PASCAL-S处理机上有如下一些寄存器和一个存贮区：

ps：

程序状态字

ir：

指令寄存器

pc：

指令计数器

t：

栈顶寄存器

b：

基地址寄存器

display：

地址寄存器组

存贮区分为程序存贮区、表格区和栈区，如图7.2所示。

程序存贮区CODE用于存放目标代码，这部分存贮区在目标代码的执行期间保持不变，可看作只读存贮（ROM）。

表格区用来存放程序的静态信息。

栈区用作程序执行的数据空间。

栈区由一系列数据段组成，每个数据段包括如下内容：

图7.2

（1）标记部分。

（2）参数部分（可能为空）。

（3）局部量。

（4）处理语句时所需要的临时工作空间。

对应PASCAL-S中过程或函数的数据区，标记部分用来存放

（1）函数的返回结果。

（2）过程或函数的返回地址。

（3）静态链。

（4）动态链。

（5）过程或函数标识符在tab中的位置。

其中静态链与动态链指向栈区S的其它单元，返回地址指向代码区CODE中的单元，第（5）项则指向表格区中的单元。

PASCAL-S处理机是一个栈式的机器，它没有传统的累加器，所有对数据的操作均在栈顶进行。

例如，加法指令是把栈顶两个单元的内容相加，并把结果留在栈顶；条件转向指令根据栈顶单元的内容决定是否转向，等等。

下面我们来介绍PASCAL-S机的指令系统。

因为这个指令系统是根据源语言PASCAL-S的特点而设计的，所以为了深刻理解各指令的意义，需要与后面将讨论的目标结构结合起来学习。

每条指令的格式为

操作码

操作数1

操作数2

当然，有些指令只有一个操作数，还有的指令没有操作数。

1.双操作指令（4条）

LODA:

0

x

y

将x（层号）和y（位移量）所确定的地址装到栈顶。

LODV:

1

x

y

根据x（层号）和y（位移量）确定单元地址，把单元的内容装到栈顶。

LOD*：

2

x

y

根据x（层号）和y（位移量）确定存放地址的单元，把那个地址所指单元的内容装到栈顶。

UPD：

3

x

y

x,y均为层号，根据静态链更新display从第x+1层到第y层的内容。

2.单操作指令（23条）

STAD：

8

y

调用y所确定的标准函数，自变量的值在栈顶，调用后的函数值取代原来的栈顶。

表7.1中给出了编号y与标准函数的对应关系。

表7.1

y

函数

y

函数

y

函数

0

整数abs

7

succ

14

ln

1

实数abs

8

pred

15

sqrt

2

整数sqr

9

round

16

arctan

3

实数sqr

10

trunc

17

eof

4

odd

11

sin

18

eoln

5

chr

12

cos

6

ord

13

exp

ADDL:

9

y

将栈顶单元的内容加y。

JUMP：

10

y

转到y所指的指令继续执行。

JUMPF:

11

y

当栈顶单元的内容为false时退掉栈顶单元并转到y所指的指令去执行。

JUMPX:

12

y

y为情况表的入口地址。

根据栈顶单元的内容从情况表中确定转向目标，然后完成转向并退掉栈顶单元。

ENTRY:

13

y

ENTRY总是成对出现。

第一条中的y为情况标号的值，第二条中的y为相应的情况子句的入口地址。

CASE语句的情况表由若干对ENTRY组成。

FORIUP:

14

y

FOR1UP在如下形式的循环语句中用作循环的入口条件测试。

FORi:

=E1TOE2DOSS

当执行到FOR1UP指令时，运行时栈的状态如图7.3所示。

图7.3

指令FOR1UP在初值小于终值时，为循环变量i赋初值，否则退掉栈顶三个单元并转到y（循环出口）所指的指令继续执行。

FOR2UP:

15

y

FOR2UP与FOR1UP配对使用。

FOR2UP用于循环的重复条件测试。

如果循环变量的值小于终值，则循环变量的值加上1，并转循环入口y；否则退掉栈顶三个单元。

FOR1DOWN:

16

y

FOR2DOWN:

17

y

这两条指令与前两条类似，它们用于如下形式的循环语句中：

FORi:

=E1DOWNTOE2DOS

MARK:

18

y

这条指令为过程语句或函数调用的第一条指令，y为过程或函数标识符在符号表的位置。

该指令在栈顶分配5个单元作为标记部分，并将y填入所分配的第5个单元中。

CALL：

19

y

这条指令为过程或函数调用的最后一条指令。

y为btab[j].psize—1；由于栈顶指针t指向参数区最后一个单元，所以t-y恰为本层数据区的开始位置。

在MARK与CALL之间的指令用于为形参分配存贮。

CALL指令用于填写本层display内容（t-y）；填写标记部分（静态链，动态链，返回地址）；为局部量分配存贮，根据标识符表中的入口地址转过程体。

INDEX1:

20

y

INDEX:

21

y

这两条指令是为计算数组元素的地址而设计的，y是指向数组表的指针。

它的功能是将（栈顶单元内容—数组下界）*L加到次栈顶单元的内容上并退掉栈顶单元。

在INDEX1中，L=1；在INDEX中，L=atab[y].elsize。

LODB：

22

y

将一串相连单元的内容装到栈顶，这串单元的个数由y指定，第一个单元的地址在原来的栈顶单元中，修改栈顶指针。

COPYB:

23

y

以栈顶单元所包含的地址为开始地址，复制y个单元的内容到次栈顶所含地址为开始的y个单元中。

LODL：

24

y

把y装到栈顶。

LODR：

25

y

y为指向实数表的指针。

这条指令是将y所指向的实数装到栈顶。

FLOAT:

26

y

将栈中从栈顶开始数的第y个单元的内容变成浮点数。

READ：

27

y

将y所指定类型的数据读到栈顶单元的内容所指定的单元中，并退掉栈顶单元。

WRITE0:

28

y

y为指向串表stab的指针。

这条指令是输出从y开始的一串字符，（输出字符的个数在栈顶单元中）并退掉栈顶单元。

WRITE1:

29

y

WRITE2:

30

y

这两条指令是输出简单变量的值，变量类型由y指定。

WRITE1输出栈顶单元的内容并退掉栈顶单元（输出域宽为缺省值）。

WRITE2按栈顶单元所示域宽输出次栈顶的内容并退掉栈顶两个单元。

3.无操作数指令（33条）

HALT：

31

终止目标程序执行。

EXITP:

32

这条指令是从过程返回的指令，它将栈顶指针恢复到执行MARK前的值；根据动态链恢复基地址寄存器的内容；按返回地址完成返回。

EXITF:

33

这条指令是从函数返回的指令，它将栈顶指针恢复到执行MARK前的值加1（栈顶为函数结果）；根据动态链恢复基地址寄存器的内容；按返回地址返回。

FETCH:

34

以栈顶单元的内容作地址，取这个地址所指单元的内容回送到栈顶。

NOT：

35

将栈顶单元的内容求反（栈顶单元的内容为布尔值）。

NEGATE:

36

将栈顶单元的内容乘上-1。

WRITER:

37

这条指令的意义是用如下语句打印实数x：

write（x:

y:

z）；

其中z在栈顶单元中，y在次栈顶单元中，而x在栈顶第三个单元中。

STORE:

38

将栈顶单元的内容存到次栈顶单元所指示的单元中。

READLN:

62

WRITELN:

63

这两条指令分别等价于PASCAL语言中的readln与writeln语句。

以下指令均是在栈顶两个单元间进行的数据操作，功能是

<次栈顶>

<次栈顶><运算><栈顶>

并退掉栈顶单元。

表7.2给出了各种运算所对应的操作码及助记符。

表7.2

运算

助记符

操作码

运算

助记符

操作码

实数相等

EQR

39

逻辑加

OR

51

实数不等

NEQR

40

逻辑与

AND

56

实数小于

LTR

41

实数小等

LER

42

整数加

ADDI

52

实数大于

GTR

43

整数减

SUBI

53

实数大等

GER

44

实数加

ADDR

54

整数相等

EQI

45

实数减

SUBR

55

整数不等

NEQI

46

整数乘

MULI

57

整数小于

LTI

47

整数除

DIVI

58

整数小等

LEI

48

求余数

MODI

59

整数大于

GTI

49

实数乘

MULR

60

整数大等

GEI

50

实数除

DIVR

61

我们之所以这样设计目标机，一方面是因为可以避免考虑特定计算机的具体细节，另一方面是因为可以简化编译程序的代码生成。

然而，由于这个目标机在实际上并不存在，因此，为了使目标程序可以真正执行，必须设法实现这个目标机。

我们的办法是用PASCAL语言写一个解释程序来执行这个目标机的指令。

目标机的各寄存器及存贮区可以用PASCAL的各种变量来模拟，比如：

CONST

maxlevel=7;

tabsize=100;

atabsize=30;

btabsize=20;

rconstsize=20;

stabsize=600;

codesize=800;

stacksize=1450;

TYPE

object=（konstant,vvariable,typel,prozedure,funktion）;

types=（notyp,ints,reals,bools,chars,arrays,records）;

order=PACKEDRECORD

f:

0..63;

x:

0..maxlevel;

y:

integer

END;

VAR

ps:

（run,finish,error）;{程序状态字}

ir:

order;{指令寄存器}

pc:

integer;{指令计数器}

t:

integer;{栈顶寄存器}

b:

integer;{基地址寄存器}

display:

ARRAY[0..maxlevel]OFinteger;{地址寄存器组}

code:

ARRAY[0..codesize]OForder;{代码区}

tab:

ARRAY[0..tabsize]OF

PACKEDRECORD

name:

PACKEDARRAY[1..10]OFchar;

link:

0..tabsize;

obj:

object;

typ:

types;

ref:

integer;

normal:

boolean;

lev:

0..maxlevel;

adr:

integer

END;

atab:

ARRAY[1..atabsize]OFPACKEDRECORD

inxtyp:

types;

eltyp:

types;

elref:

integer;

low:

integer;

hig:

integer;

elsize:

integer;

size:

integer

END;

btab:

ARRAY[1..btabsize]OFPACKEDRECORD

last,lastpar:

0..tabsize;

psize,vsize:

integer

END;

rconst:

ARRAY[1..rconstsize]OFreal;

stab:

PACKEDARRAY[0..stabsize]OFchar;

s:

ARRAY[1..stacksize]OF{栈区}

RECORD

CASEcn:

typesOF

ints:

（I:

integer）;

reals:

（r:

real）;

bools:

（b:

boolean）;

chars:

（c:

char）

END;

目标程序的执行则可以用如下语句模拟：

各寄存器及栈区初始化；

REPEAT

ir:

=code[pc];

pc:

=pc+1;

CASEir.fOF

LODA:

t:

=t+1;

s[t].i:

=display[ir.x]+ir.y;

LODV:

t:

=t+1;

s[t].i:

=s[display[ir.x]+ir.y];

LOD*:

t:

=t+1;

s[t]:

=s[s[display[ir.x]+ir.y].i];

UPD:

h1:

=ir.y;

h2:

=ir.x;

h3:

=b;

REPEAT

display[h1]:

=h3;

h1:

=h1-1;

h3:

=s[h3+2].i

UNTILh1=h2;

STAD:

CASEir.yOF

0:

s[t].i:

=abs（s[t].i）;

1:

s[t].r:

=abs（s[t].r）;

16:

s[t].r:

=atan（s[t].r）;

17:

s[t].b:

=eof（prd）;

18:

s[t].b:

=eoln（prd）

ENDCASE;

ADDL:

s[t].i:

=s[t].i+ir.y;

JUMP:

pc:

=ir.y;

JUMPF:

IFNOTs[t].bTHEN

pc:

=ir.y

ENDIF;

t:

=t-1;

JUMPX:

h1:

=s[t].i;

t:

=t-1;

h2:

=ir.y;

h3:

=0;

REPEAT

IFcode[h2].f<>ENTRYTHEN

h3:

=1;

ps:

=caschk{情况语句出错}

ELSE

IFcode[h2].y=h1THEN

h3:

=1;

pc:

=code[h2+1].y

ELSE

h2:

=h2+2

ENDIF

ENDIF

UNTILh3<>0;

FOR1UP:

h1:

=S[t-1].i;

IFh1<=s[t].iTHEN

s[s[t-2].i].i:

=h1

ELSE

t:

=t-3;

pc:

=ir.y

ENDIF

FOR2UP:

h2:

=s[t-2].i;

h1:

=s[h2].i+1;

IFh1<=s[t].iTHEN

s[h2].i:

=h1;

pc:

=ir.y

ELSE

t:

=t-3

ENDIF;

FOR1DOWN:

h1:

=s[t-1].i;

IFh1>=s[t].iTHEN

s[s]t-2[.i].i:

=h1

ELSE

pc:

=ir.y;

t:

=t-3

ENDIF;

FOR2DOWN:

h2:

=s[t-2].i;

h1:

=s[h2].i-1

IFh1>=s[t].iTHEN

s[h2].i:

=h1;

pc:

=ir.y

ELSE

t:

=t-3

ENDIF;

MARK:

h1:

=btab[tab[ir.y].re].vsize;

t:

=t+5;

s[t-1].i:

=h1-1;

s[t].i:

=ir.y;

CALL:

h1:

=t-ir.y;

h2:

=s[h1+4].i

h3:

=tab[h2].lev;

display[h3+1]:

=h1;

h4:

=s[h1+3].i+h1

s[h1+1].i:

=pc;

s[h1+2].i:

=display[h3];

s[h1+3].i:

=b;

FORh3:

=t+1TOh4DO

s[h3].i:

=0

ENDFOR;

b:

=h1;

t:

=h4;

pc:

=tab[h2].adr;

INDEX1:

h1:

=ir.y;

h2:

=atab[h1].low;

h3:

=s[t].i;

IFh3

ps:

=inxchk{下标越界错}

ELSE

IFh3>atab[h1].highTHEN

ps:

=inxchk

ELSE

t:

=t-1;

s[t].i:

=s[t].i+（h3-h2）

ENDIF

ENDIF;

INDEX:

h1:

=ir.y;

h2:

=atab[h1].low;

h3:

=s[t].i;

IFh3

ps:

=inxchk

ELSE

IFh3>atab[h1].highTHEN

ps:

=inxchk

ELSE

t:

=t-1;

s[t].i:

=s[t].i+（h3-h2）*atab[h1].elsize

ENDIF

ENDIF;

LODB:

h1:

=s[t].i;

t:

=t-1;

h2:

=ir.y+t;

WHILEt

B