语义分析与代码生成

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

7.1 语法制导翻译

编译程序的实质性工作是翻译，即为源程序生成目标代码。为此，我们必须知道程序的含义是什么（语义分析）？应该翻译成什么（代码生成）？

在三、四章，我们主要讨论了源程序的识别，即判定一个源程序是否符合源语言的文法。在讨论语法分析时曾说过，上下文无关文法不足以描述编程语言的全部语法特征。为了说明这一点，让我们来看一个例子：

?

VAR

i:integer; BEGIN

? j:=i*i

? END;

?

如果j没有在外层块中说明，那么赋值语句中出现的j就是非法的。这是一种上下文敏感的成分。为了清楚地说明这一点，假定j是在自顶向下分析过程中由非终极符<变量>导出的，在这次推导之前的句型为

αVARj:integer;β<变量>γ

其中α,β,γ为符号串。推导后的句型为

αVARj:integer;βjγ

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

VAR j:integer;β<变量>→VAR j:integer;βj

而不是

<变量>→j

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

上下文敏感成分的分析实质上是语法分析的内容。但是，因为我们的语法分析是以上下文无关文法为基础的，没有考虑上下文敏感成分的处理，所以必须在语义分析时加以考虑。这相当于把语言的敏感成分划归为语言的语义范畴（尽管在概念上并非如此）。比如说在处理说明

VAR j:integer

时，语义分析应该将这个说明所提供的信息填入符号表，即完成对符号表的

174

插入操作；当然也需要完成其它的语义分析工作，而后在确定是否可用规则

<变量>→j

进行推导时，就可通过对符号表的检索操作来完成。如果符号表中有标识符j，而且j又是个变量标识符，就可以用此规则进行推导。

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

IF E THEN S1 ELSE S2

为它生成的目标代码应具有图7.1的结构（称为它的目标结构），其中，计算E的目标指令、S1和S2的目标指令是在处理表达式和语句时生成的，处理条件语句时所生成的指令就是“jumpf l0”和“jump l1”。前者的含义为表达式E的值为false时，程序转向l0的指令继续执行，后者为无条件转到l1的指令执行。问题在于编译程序在处理条件语句时是从左向右进行的。因此，当要生成jumpf指令时，不知道l0的值，因为S1的目标这时尚未生成，不知道它究竟有多少条指令。在生成jump这条指令时也有同样问题。为了解决这个问题，在生成jumpf和jump指令时，应先记录这两条指令本身的位置，等以后再回填它们的转向目标。假设当前要生成的指令位置为lc，条件语句的处理算法如下：

IF sy=ifsyTHEN insymbol;

expression;{处理表达式} IF表达式类型< >boolsTHEN error (n) ENDIF; lc1:=lc;

生成jumpf指令；lc:=lc+1; IF sy=thensy THEN insymbol;

statement;{处理语句} IF sy=elsesy THEN lc2:=lc;

生成jump指令； lc:=lc+1;

回填jumpf指令的转向目标；

insymbol; 图7.1 statement;{处理语句}

回填jump指令的转向目标； ELSE

回填jumpf指令的转向目标

175

ENDIF ENDIF ENDIF；

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

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

:IF表达式类型< >bools THEN

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 目标机

为了完成代码生成工作，必须有一个提供运行环境的目标机。最直接的方法是，在哪个机器上运行的编译程序就生成那个机器的目标代码，或生成那个机器的汇编语言程序，然后经过汇编程序汇编成可以执行的机器语言程序。汇编后产生的目标代码可以具有绝对地址，从而可以装到内存的固定区域去执行；也可以具有浮动的（相应的）地址，再由装入程序（或者是连接装配程序）来为地址代真（即转换成绝对地址），即可用于执行。无论是哪

176

一种情况，都需要知道机器的硬件，诸如有多少个累加器、特殊寄存器、地址空间的大小等。但事实上，代码生成也可先脱离特定的硬件环境。一种逐渐流行的方法是为一个抽象机生成代码，然后，在特定的机器上写一个解释程序来解释抽象机的指令。下面我们将介绍一个抽象机，它是专为PASCAL-S设计的，与任何特定的计算机无关，不妨称为PASCAL-S处理机。尽管PASCAL-S处理机在硬件上并不存在，但它的指令不难落实到任何特定的计算机上。

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

ps：程序状态字 ir：指令寄存器 pc：指令计数器 t：栈顶寄存器 b：基地址寄存器

display：地址寄存器组

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

程序存贮区CODE用于存放目标代码，这部分存贮区在目标代码的执行期间保持不变，可看作只读存贮（ROM）。表格区用来存放程序的静态信息。栈区用作程序执行的数据空间。

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

（1）标记部分。 （2）参数部分（可能为空）。 （3）局部量。 （4）处理语句时所需要的临时工作空间。 对应PASCAL-S中过程或函数的数据区， 标记部分用来存放

（1）函数的返回结果。 （2）过程或函数的返回地址。 （3）静态链。 （4）动态链。 （5）过程或函数标识符在tab中的位置。 其中静态链与动态链指向栈区S的其它单 元，返回地址指向代码区CODE中的单元，第图7.2 （5）项则指向表格区中的单元。

PASCAL-S处理机是一个栈式的机器，它没有传统的累加器，所有对数据的操作均在栈顶进行。例如，加法指令是把栈顶两个单元的内容相加，并把结果留在栈顶；条件转向指令根据栈顶单元的内容决定是否转向，等等。

下面我们来介绍PASCAL-S机的指令系统。因为这个指令系统是根据源语言PASCAL-S的特点而设计的，所以为了深刻理解各指令的意义，需

177

要与后面将讨论的目标结构结合起来学习。

每条指令的格式为 操作码 操作数1 操作数2 当然，有些指令只有一个操作数，还有的指令没有操作数。

1.双操作指令（4条）

0 x y LODA:

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

1 x y LODV:

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

2 x y LOD*：

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

3 x y UPD：

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

2.单操作指令（23条）

8 y STAD：

调用y所确定的标准函数，自变量的值在栈顶，调用后的函数值取代原来的栈顶。表7.1中给出了编号y与标准函数的对应关系。

表7.1

y 0 1 2 3 4 5 6 函 数 整数abs 实数abs 整数sqr 实数sqr odd chr ord y 7 8 9 10 11 12 13 函 数 succ pred round trunc sin cos exp y 14 15 16 17 18 函 数 ln sqrt arctan eof eoln

9 y ADDL:

将栈顶单元的内容加y。 10 y JUMP：

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

11 y JUMPF:

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

12 y JUMPX:

y为情况表的入口地址。根据栈顶单元的内容从情况表中确定转向目标，然后完成转向并退掉栈顶单元。 13 y ENTRY:

178

ENTRY总是成对出现。第一条中的y为情况标号的值，第二条中的y为相应的情况子句的入口地址。CASE语句的情况表由若干对ENTRY组成。

14 y FORIUP:

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

FOR i:=E1 TO E2 DOS S

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

图7.3

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

FOR2UP与FOR1UP配对使用。FOR2UP用于循环的重复条件测试。如果循环变量的值小于终值，则循环变量的值加上1，并转循环入口y；否则退掉栈顶三个单元。

16 y FOR1DOWN:

17 y FOR2DOWN:

这两条指令与前两条类似，它们用于如下形式的循环语句中： FOR i:=E1 DOWNTO E2 DO S 18 y MARK:

这条指令为过程语句或函数调用的第一条指令，y为过程或函数标识符在符号表的位置。该指令在栈顶分配5个单元作为标记部分，并将y填入所分配的第5个单元中。

19 y CALL：

这条指令为过程或函数调用的最后一条指令。y为btab [j].psize—1；由于栈顶指针t指向参数区最后一个单元，所以t-y恰为本层数据区的开始位置。在MARK与CALL之间的指令用于为形参分配存贮。CALL指令用于填写本层display内容（t-y）；填写标记部分（静态链，动态链，返回地址）；为局部量分配存贮，根据标识符表中的入口地址转过程体。

20 y INDEX1:

21 y INDEX:

179

这两条指令是为计算数组元素的地址而设计的，y是指向数组表的指针。它的功能是将（栈顶单元内容—数组下界）*L加到次栈顶单元的内容上并退掉栈顶单元。在INDEX1中，L=1；在INDEX中，L=atab [y].elsize。

22 y LODB：

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

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

把y装到栈顶。

25 y LODR：

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

26 y FLOAT:

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

27 y READ：

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

28 y WRITE0:

y为指向串表stab的指针。这条指令是输出从y开始的一串字符，（输出字符的个数在栈顶单元中）并退掉栈顶单元。 29 y WRITE1:

30 y WRITE2:

这两条指令是输出简单变量的值，变量类型由y指定。WRITE1输出栈顶单元的内容并退掉栈顶单元（输出域宽为缺省值）。WRITE2按栈顶单元所示域宽输出次栈顶的内容并退掉栈顶两个单元。 3.无操作数指令（33条）

31 HALT：

终止目标程序执行。 32 EXITP:

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

33 EXITF:

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

34 FETCH:

180

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

35 NOT：

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

36 NEGATE:

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

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

write (x:y:z)；

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

38 STORE:

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

63 WRITELN:

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

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

并退掉栈顶单元。表7.2给出了各种运算所对应的操作码及助记符。

表7.2 运 算 实数相等 实数不等 实数小于 实数小等 实数大于 实数大等 整数相等 整数不等 整数小于 整数小等 整数大于 整数大等 助记符 EQR NEQR LTR LER GTR GER EQI NEQI LTI LEI GTI GEI 操作码 39 40 41 42 43 44 45 46 47 48 49 50 运 算 逻辑加 逻辑与 整数加 整数减 实数加 实数减 整数乘 整数除 求余数 实数乘 实数除 助记符 OR AND ADDI SUBI ADDR SUBR MULI DIVI MODI MULR DIVR 操作码 51 56 52 53 54 55 57 58 59 60 61

我们之所以这样设计目标机，一方面是因为可以避免考虑特定计算机的具体细节，另一方面是因为可以简化编译程序的代码生成。然而，由于这个目标机在实际上并不存在，因此，为了使目标程序可以真正执行，必须设法实现这个目标机。我们的办法是用PASCAL语言写一个解释程序来执行这个目标机的指令。

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

CONST

maxlevel =7; tabsize =100;

181

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] OF integer;{地址寄存器组} code : ARRAY [0..codesize] OF order;{代码区} tab : ARRAY [0..tabsize] OF

PACKED RECORD name :PACKED ARRAY [1..10] OF char; link :0..tabsize; obj :object; typ :types; ref :integer; normal :boolean; lev :0..maxlevel; adr :integer END;

atab: ARRAY [1..atabsize] OF PACKED RECORD

inxtyp :types; eltyp :types; elref :integer; low :integer;

182

hig :integer; elsize :integer; size :integer END;

btab:ARRAY [1..btabsize] OF PACKED RECORD

last,lastpar:0..tabsize; psize,vsize:integer END;

rconst :ARRAY [1..rconstsize] OF real; stab :PACKED ARRAY [0..stabsize] OF char; s :ARRAY [1..stacksize] OF RECORD

CASE cn:types OF ints : (I:integer); reals : (r:real); bools : (b:boolean); chars : (c:char) END;

各寄存器及栈区初始化； REPEAT

ir :=code [pc]; pc :=pc+1;

CASE ir.f OF 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 UNTIL h1=h2;

183

栈区}

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

STAD

ADDL JUMP JUMPF

JUMPX

FOR1UP

:CASE ir.y OF

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;

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

:IF NOT s[t].b THEN pc:=ir.y ENDIF; t:=t-1; :h1:=s[t].i; t:=t-1; h2:=ir.y; h3:=0; REPEAT

IF code[h2].f<>ENTRY THEN h3:=1;

ps:=caschk{情况语句出错} ELSE

IF code[h2].y=h1 THEN h3:=1;

pc:=code[h2+1].y ELSE

h2:=h2+2 ENDIF ENDIF

UNTIL h3<>0; :h1:=S[t-1].i;

IF h1<=s[t].i THEN s[s[t-2].i].i:=h1 ELSE t:=t-3; pc:=ir.y ENDIF

184

FOR2UP :h2:=s[t-2].i; h1:=s[h2].i+1;

IF h1<=s[t].i THEN s[h2].i:=h1;

FOR1DOWN

FOR2DOWN

MARK

CALL

pc:=ir.y ELSE t:=t-3 ENDIF; :h1:=s[t-1].i;

IF h1>=s[t].i THEN s[s]t-2[.i].i:=h1 ELSE

pc:=ir.y; t:=t-3 ENDIF; :h2:=s[t-2].i; h1:=s[h2].i-1

IF h1>=s[t].i THEN s[h2].i:=h1; pc:=ir.y ELSE t:=t-3 ENDIF;

:h1:=btab[tab[ir.y].re].vsize; t:=t+5;

s[t-1].i:=h1-1; s[t].i:=ir.y; :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;

FOR h3:=t+1 TO h4 DO s[h3].i:=0 ENDFOR;

185

INDEX1

INDEX

LODB

b:=h1; t:=h4;

pc:=tab[h2].adr; :h1:=ir.y;

h2:=atab[h1].low; h3:=s[t].i;

IF h3

ps:=inxchk {下标越界错} ELSE

IF h3>atab[h1].high THEN ps:=inxchk ELSE t:=t-1;

s[t].i:=s[t].i+(h3-h2) ENDIF ENDIF; :h1:=ir.y;

h2:=atab[h1].low; h3:=s[t].i;

IF h3

IF h3>atab[h1].high THEN ps:=inxchk ELSE t:=t-1;

s[t].i:=s[t].i+(h3-h2)*atab[h1].elsize ENDIF ENDIF; :h1:=s[t].i; t:=t-1; h2:=ir.y+t;

WHILE t

186

COPYB :h1:=s[t-1].i; h2:=s[t].i; h3:=h1+ir.y;

WHILE h1

s[h1]:=s[h2]; h1:=h1+1;

LODL

LODR

FLOAT

READ

WRITE0

WRITE1

h2:=h2+1 END; t:=t-2; :t:=t+1; s[t].i:=ir.y; :t:=t+1;

s[t].r:=rconst[ir.y]; :h1:=t-ir.y;

s[h1].r:=s[h1].i;

:IF eof(prd) THEN ps:=redchk {读错} ELSE

CASE ir.y OF

ints:read(prd,s[s[t].i].i); reals:read(prd,s[s[t].i].r); chars:read(prd,s[s[t].i].c); ENDCASE; t:=t-1; :h1:=s[t].i; h2:=ir.y; t:=t-1; REPEAT

write(prr,stab[h2]); h1:=h1-1; h2:=h2+1 UNTIL h1=0; :CASE ir.y OF

ints:write(prr,s[t].i:fld[1]); reals:write(prr,s[t].r:fld[2]); bools:IF s[t].b THEN

write(″true″)

187

ELSE

write(″false″) ENDIF;

chars:write(prr,chr(s[t].i))

WRITE2

HALT EXITP

EXITF

FETCH NOT NEGATE WRITER

STORE

EQR

NEQR DIVR

ENDCASE; t:=t-1;

:CASE ir.y OF

ints:write(prr,s[t-1].i:s[t].i); reals:write(prr.s[1].r:s[t].i); bools:IF s[t] THEN

write(″true″) ELSE

write(″false″) ENDIF;

chars:write(prr,chr(s[t-1].i:s[t].i)) ENDCASE; t:=t-2;

:ps:=finish; {正常停机} :t:=b-1;

pc:=s[b+1].i; b:=s[b+3].i; :t:=b;

pc:=s[b+1].i; b:=s[b+3].i; :s[t]:=s[s[t].i]; :s[t].b:=NOTs[t].b; :s[t].i:=-s[t].i;

:write(prr,s[t-2].r:s[t-1].i); t:=t-3;

:s[s[t-1].i]:=s[t]; t:=t-2; :t:=t-1;

s[t].b:=s[t].r=s[t+1].r; :t:=t-1;

s[t].b:=s[t].r< >s[t+1].r; ?

:t=t-1;

s[t].r:=s[t].r/s[t+1].r;

188

READLN :readln; WRITELN :writeln; ENDCASE; UNTIL ps< >run; IF ps< >finish THEN 运行时错误处理； 这就是解释执行的过程。这个解释程序的结构非常简单，几乎就是一个情况语句。事实上，高级语言的解释程序结构基本都是这样。

7.3 说明部分的处理

说明部分给语言带来了一定的冗余度。有些语言（如LISP）没有说明语句；有些语言虽然有说明语句（如BASIC，FORTRAN），但很少需要用；而其它语言（如PASCAL，ADA），则要求程序中所使用的每个实体都必须说明，说明的作用是把程序中的实体与某个标识符联系起来，用标识符作为这个实体的名字。通过缺省的命名规则（如FORTRAN中以I，J，K，L，M，N开头的名字若不特别说明则是用来标识整型变量的）或根据名字所出现的上下文（如在SNOBOL中，TEXT=‘STRINGA’意味着TEXT是一个字符串的名字），说明的使用是可以避免的。然而，人们并不总是希望避免使用说明，特别是当软件开发的主要目标是生产可靠的软件产品时更是这样。因为说明的作用是明确地声明程序员打算怎样使用所说明的实体，而编译程序根据某个实体的上下文可以推断它的使用情况。如果后者与前者不一致，编译程序就可以检查出来并通知给程序员，而如果不使用说明，这类错误就无法检查出来。因此，需要说明部分的语言可以编出较为可靠的程序。

从语义分析及代码生成的角度看，编译程序在处理说明部分时的主要任务是：

（1）分离出说明语句中所说明的每一个实体，并把它填到符号表中。 （2）在符号表中填入尽可能多的有关实体的属性。 从而，编译程序可以根据符号表中的信息来检查将来对某个实体的引用是否正确，并根据有关属性为源程序生成正确的目标代码。

下面我们将结合PASCAL-S的说明部分加以讨论。 7.3.1 常量说明

常量说明的作用在于提高程序的可读性与修改方便。例如在上一节，我们利用常量说明定义了栈区S的大小：

stacksize=1450； 由此可以很容易看出，

189

IF t>stacksize THEN?

是在测试栈是否溢出。如果需要修改栈区大小，只需修改常量说明，程序中所有用到stacksize的地方（如测试栈溢出的地方）就都同时得到了修改，而无需逐一进行修改。

PASCAL-S中常量说明的定义为

<常量说明>→CONST<标识符>=<常量>

{;<标识符>=<常量>}

请注意，文法中已嵌入了语义加工操作。处理完标识符后，可以知道常量的名字；处理完常量后可以知道常量的类型（整型、实型、字符型等）及其值。设id定义为

id:PACKED ARRAY[1..10] OF char; 用来存放所拼出的标识符，c定义为

c:RECORD

CASE tp:types OF

ints,chars,bools: (i:integer); reals: (r:real) END;

用来存放常量的类型及其值（字符型及布尔型常量的值是用其序号代表的），则嵌入的语义操作为：

: enter(id,konstant); : tab[t].typ:=c.tp; IF c.tp=reals THEN enterreal (c.r); tab[t].adr:=c1 ELSE tab[t].adr:=c.i ENDIF;

这两个操作对符号表完成了一次完整的插入（见5.2节）。相应的，常量的定义为

<常量>→<字符常量>|

[+|-]<无符号数>| [+|-]<常量标识符>

嵌入的语义操作如下：

: c.tp:=chars; c.i:=inum;{字符值的序号} : sign:=1; IF sy=minus THEN sign:=-1

190

ENDIF;

: IF sy=intcon THEN c.tp:=ints; c.i:=sign*inum ELSE IF sy=realcon THEN c.tp:=reals; c.r:=sign*rnum ENDIF ENDIF;

: x:=loc;{检索标识符表} IF (x< >0) AND (tab[x].obj=konstant) THEN c.tp:=tab[x].typ; IF c.tp=reals THEN c.r:=sign*rconst[tab[x].adr] ELSE IF c.tp=ints THEN c.i:=sign*tab[x].adr ENDIF ENDIF ENDIF;

根据这两个嵌入语义操作的文法规则，不难写出常量说明的处理算法。 7.3.2 类型说明

为数据规定类型可以更自然地描述数据，因而适于对实际问题的抽象。类型实质上代表着一组值以及可在这组值上施加的一组操作。例如，integer表示整数类型，它与集合

{?，-2，-1，0，1，2，?} {+，-，*，div,:=,<,?}

有关，即说明为integer的变量i可以取第一个集合中的值，可以参与第二个集合中的运算。

当然，类型可以在定义数据对象时引入，而不是非有名字不可。但利用类型说明为类型赋以名字更能反映类型概念本身，而且用有名类型来定义数据更能反映对数据的抽象。比较下面两个说明：

1.VAR

r1,r2,r3:RECORD

name:PACKED ARRAY[1..20]OF char; age:integer;

191

sex: (male,female) END;

2.TYPE

personal message =RECORD

name:PACKED ARRAY[1..20]OF char; age:integer;

sex: (male,female) END; VAR

r1,r2,r3:personal message;

第一个说明定义了r1,r2,r3为一个记录，它们将来可存放这种记录的值。第二个说明先定义了personal message（个人信息）为一个记录类型，然后定义r1,r2,r3为个人信息，它们将来可用于存放有关个人的信息。显然第二个说明更自然些。

PASCAL-S中，类型说明的定义为

<类型说明>→TYPE<标识符>=<类型>

{;<标识符>=<类型>}

处理完标识符后，需要将这个标识符（类型的名字）填到标识符表中，其它一些属性如typ,ref及adr等，则需在处理完类型后回填。但处理类型的时候，可能会对标识符表完成其它的插入操作，如对记录类型就需要将各域标识符插入标识符表中。因此，为了在标识符表中回填属性，需要记下类型名字在标识符表中的位置。于是，嵌入的语义操作为

:enter(id,type1); t1:=t;

:tab[t1].typ:=tp; tab[t1].ref:=rf; tab[t1].adr:=sz;

其中tp,rf,sz由处理类型的过程返回。关于类型的处理，我们将在讨论变量说明时一起介绍。 7.3.3 变量说明

变量说明是显式地为程序中所使用的变量命名并规定属性。由于变量在程序运行时拥有值，编译程序必须为变量分配存贮空间，并赋予变量一个地址，且当存贮分配是动态进行时，这个地址只能是相对地址。为变量分配存贮空间的大小取决于变量的数据类型。在PASCAL-S中，由于允许过程的递归调用，所以存贮分配是动态进行的，编译时所做的工作是为变量分配位移量。

192

变量说明的语法规则如下：

<变量说明>→VAR<标识符>{,<标识符>}:<类型

>

{;<标识符>{,<标识符>}:<类型

>}

当处理完逗号分隔的标识符时，尚不知其类型，所以无法填类型及地址属性，必须等处理完类型后回填。因此，需要记录这些标识符在标识符表tab中的位置（注意，这些标识符在标识符表tab中是连续存放的）。如果dx作为位移量分配的计数器（它在处理一个块的开始时被初始化），则各语义操作如下：

: t0:=t;

enter(id,vvariable);

: enter(id,vvariable); : t1:=t;

: WHILE t0

BEGIN

t0:=t0+1;

WITH tab[t0]DO typ:=tp; ref:=rf;

normal:=true; adr:=dx; dx:=dx+sz ENDWITH END;

其中tp、rf、sz由处理类型的过程返回。

现在我们来讨论类型的处理。首先考虑最简单的情况

<类型>→<类型标识符>

此时，类型的处理算法很简单，只需执行对符号表的检索操作并取出相应的属性即可。

: x:=loc(id);

IF(x< >0)AND(tab[x].obj=typel)THEN tp:=tab[x].typ; rf:=tab[x].ref; sz:=tab[x].adr; ENDIF;

其中各属性是在处理类型说明时填入的（或预定义的）。当引入新的数组或记录类型时，相应的算法要复杂些，它必须将这种新类型的信息填到数组表

193

或块表中，而且，在处理当前的新类型时，又必须递归地调用它本身去处理数组的基类型或记录域的类型。下面我们先讨论记录类型的处理。

<类型>→RECORD{<标识符>{,<标识符>}:

<类型>;END

处理记录时，需要将记录的信息填到块表中，而记录的各个域则需填进标识符表tab，有些属性需要回填。由于各个域标识符是局部于它所在的记录的，所以在处理各个域之前需要执行符号表的进层操作，而各个域处理完后要执行符号表的复位操作。算法如下：

: enterblock;

level:=level+1; display[level]:=b; offset:=0; tp:=records; rf:=b;

: t0:=t;

enter(id,vvariable);

: enter(id,vvariable); : t1:=t;

调用处理类型的过程；{返回eltp,elrf,elsz}

: WHILE t0

BEGIN

t0:=t0+1;

tab[t0].typ:=eltp; tab[t0].ref:=elrf; tab[t0].normal:=true; tab[t0].adr:=offset; offset:=offset+elsz; END;

: sz:=offset;

btab[rf].vsize:=offset; btab[rf].psize:=0; level:=level-1;

最后，我们讨论数组类型的处理。

<类型>→ARRAY[<常量>..<常量>

{,<常量>..<常量>}]OF<类型>

它要求在数组表中建立如图7.4的串记录并返回rf及size，其中

elsizen=elsz {elsz由处理类型的过程返回} elsizei=sizei+1 {1<=i

194

sizei=(hi-li+1)*elsizei {1<=i<=n}

可以看出，这一串记录的建立是一个递归的过程，相当于把给定的多维数组看作是

ARRAY [l1..h1] OF ARRAY [l2..h2] OF

?

ARRAY [ln..hn] OF<类型>

图7.4

这样处理的好处是使数组元素的地址计算得到了简化。具体算法如下：

: tp:=arrays;

: IF low.tp=reals THEN

error(n)

ENDIF;{low由处理常量的过程返回}

: IF high.tp < > low.tp THEN

error(n)

ENDIF;{high由处理常量的过程返回} enterarray(low.tp,low.i,high.i); rf:=a;

: eltp:=ARRAY;

递归地调用处理数组的过程；

: atab[rf].eltyp:=eltp;

atab[rf].elref:=elrf; atab[rf].elsize:=elsz;

atab[rf].size:=(high.i-low.i+1)*elsz; sz:=atab[rf].size; 7.3.4 子程序说明

子程序使我们能利用语言所提供的基本结构来定义更高级的操作，从而，在编译时可以不受语言的基本结构的束缚，尽量使用问题本身的术语来描述它的解，就好象语言是可扩充的一样。PASCAL-S中有两种形式的子程序——过程与函数。它们都是在更高的层次上为一组操作命名，函数区别于过程的主要点是它需要返回一个值。

子程序说明是用来定义子程序的，包括两个部分：一部分定义子程序与

195

外界的接口，或称调用约定；这部分包括子程序名、参数的数目、类型及传递方式（对函数来说，返回值的类型也在这个接口中提供）。另一部分定义了子程序的操作，称为子程序体；这部分包括一些局部量的定义以及实现子程序操作的一些语句。

子程序定义后要在调用时执行。为了实现这一点，编译程序在处理子程序说明时必须为子程序生成目标代码，以便在调用子程序时执行。子程序的目标结构为

实现子程序操作的 入口地址：

各语句的目标代码

返回指令

此外，为了检查对子程序的调用是否正确，处理子程序说明时还必须将有关调用约定的信息保存起来。以过程说明为例，在扫描到过程标识符时，应将它登记在标识符表中，并在块表中建立相应记录。但有些信息在此时是无法填入的，因此要记住标识符及块表中相应记录的位置，以便回填。在处理参数表时，将各参数的属性如参数类型，传递方式（值参或变量参数）等插入标识符表中。参数表处理完后，需要回填块表中相应记录的lastpar及psize域。过程的各局部量说明及定义过程操作的语句部分要由各种说明的处理过程及语句的处理过程分别处理，结果是为各种局部量分配存贮（包括在表格区的分配及位移量分配），为过程体的语句生成代码。在此期间，需要回填块表中相应记录的vsize域以及标识符表中相应记录的adr域（过程入口地址）。当整个过程说明处理完后，要生成返回指令EXITP。注意，过程的形式参数及局部量是局部于过程的，所以在处理参数表之前要执行对符号表的进层操作，而在过程说明处理完后要执行复位操作。嵌入语义操作的文法规则为

<过程说明>→PROCEDURE<标识符>{<形参表>};

<说明部分>；<复合语句>；

各语义操作为

: enter(id,prozedure);

enter block; level:=level+1; display[level]:=b; prb :=b; prt :=t; dx :=5;

: btab[prb].lastpar:=t;

btab[prb].psize:=dx;

: tab[prt].adr:=lc;{入口地址} : 生成EXITP指令；

196

level:=level-1;

对函数说明来说，除了还要处理函数的类型之外（这可以通过检索标识符表来完成），所需要的加工操作与过程基本相同，这里就不讨论了。

7.4 语句部分的处理

语句部分完成所需要的计算，每个语句都导致一组计算机动作的执行。编译程序在处理语句时的主要工作是将语句所表达的计算翻译成一组目标指令，即代码生成。当然，在进行代码生成时，必须检查语句中所使用的实体与说明中的定义是否一致。

在PASCAL-S的编译程序中，代码生成就是向代码区CODE发送所生成的指令。令lc为一个指示器，它始终指向要生成的下一条指令在代码区CODE中的位置，则发送代码的工作可由如下三个过程完成：

PROCEDURE emit(operator:integer); {发送无操作数指令} code[lc].f:=operator; lc:=lc+1

END-PROCEDURE;

PROCEDURE emit1(operator,operand:integer); {发送单操作数指令} code[lc].f:=operator code[lc].y:=operand; lc:=lc+1

END- PROCEDURE;

PROCEDURE emit2(operator,operand1,operand2:integer); {发送双操作数指令} code[lc].f:=operator; code[lc].x:=operand1; code[lc].y:=operand2; lc:=lc+1

END-PROCEDURE;

每一种语句应该翻译成什么样的目标指令（称为目标结构），是由它的语义所规定的。在PASCAL-S中，基本语句包括：赋值、分支（IF与CASE）、循环（REPEAT，WHILE与FOR）、过程调用。下面我们分别讨论这些语句的目标结构及翻译算法。 7.4.1 表达式与赋值语句

197

赋值语句嵌入语义操作的文法规则为

<赋值语句>→<左部变量>:=<表达式>

其相应的目标结构如图7.5所示。 计算左部变量地址的目标指令 计算右部表达式值的目标指令 将表达式值存到变量单元的目标指令 图7.5

例如

x:=y+x

其中x和y都是普通实型变量。设当前lc=10，则生成的目标指令为

10 LODA lev(x) , adr(x) ; 11 LODV lev(y) , adr(y) ; 12 LODV lev(x) , adr(x) ; 13 ADDR ; 14 STORE ;

其中lev(x)、adr(x)，分别表示x的层号和位移量。这些指令在运行时的效果如图7.6所示。

图7.6 运行时栈的变化

在生成变量的目标指令时，要注意区分该变量是否是变量参数（即引用参数）。因为它与普通变量（非引用参数）生成的目标指令不同。

左部变量嵌入语义操作的文法规则为

<左部变量>→<变量>{<变量尾部>}

其相应的目标结构如图7.7所示。例如

r.z:=y+x;

其中r为记录型变量，x,y为实型变量。设当前lc=20，则生成的目标指令为（设r,x,y均为普通变量）

198

取左部变量地址 的目标指令

取左部变量地址 的目标指令 计算数组元素或 记录分量地址的 目标指令

图7.7

20 LODA lev(r) , adr(r) ; 21 ADDL adr(z) ; 22 LODV lev(y) , adr(y) ; 23 LODV lev(x) , adr(x) ; 24 ADDR ; 25 STORE ;

再例如

a[i1,i2,i3]:=y+x;

其中a为数组型变量，i1、i2、i3为整型变量，x、y为实型变量。设当前lc=30，则生成的目标指令为（设a,i1,i2,i3,x,y均为普通变量）

30 LODA lev(a) , adr(a) ; 31 LODV lev(i1) , adr(i1) ; 32 INDEX a0 ; 33 LODV lev(i2) , adr(i2) ; 34 INDEX a0+1 ; 35 LODV lev(i3) , adr(i3) ; 36 INDEX1 a0+2 ; 37 LODV lev(y) , adr(y) ; 38 LODV lev(x) , adr(x) ; 39 ADDR ; 40 STORE ;

对数组元素a[i1,?,in]，设其对应的数组说明为

ARRAY[l1..h1,?,ln..hn]OF REAL

则其地址为

数组开始地址+?(ik?lk)·elsizek

k?1n其中

elsizen=1;elsizek=(hk+1-lk+1+1)·elsizek+1地址的计算由INDEX与

INDEX1辅助实现（见7.1节）。下面我们给出左部变量的各语义操作：

: IF x.typ=funktion THEN emit2(LODA,lev(x)+1,0) ELSE IF变量x为变量参数THEN

199

emit2(LODV,lev(x),adr(x)) ELSE emit2(LODA,lev(x),adr(x)) ENDIF ENDIF;

: IF变量类型=records THEN 读入′.′；读入域名z; IF记录x中，没有域名z THEN error (n) ELSE emit1(ADDL,adr(z)) ENDIF ELSE 读入′[′; a:=x.ref REPEAT insymbol;调用处理表达式过程； IF atab[a].elsize=1 THEN emit1(INDEX1,a) ELSE emit1(INDEX,a) ENDIF a:=atab[a].elref; insymbol;{读入′,′或′] ′} UNTIL sy=′] ′ ENDIF;

以上为计算数组元素与记录域的地址的过程，后面我们还要多次用到。赋值语句右部的表达式由处理表达式的过程处理。处理完后，表达式值在栈顶，这时需要编存指令，一般情况下，一条“STORE”指令就够了，但当左部变量与右部表达式同为数组类型或记录类型时，可利用指令

COPYB size;

把右部变量值（共size个单元）传递给左部变量。

例如

a:=b;

其中a,b均为普通数组类型。设当前lc=50，则生成的目标指令为

50 LODA lev(a),adr(a); 51 LODA lev(b),adr(b); 52 COPYB a.size;

200

赋值语句的语义操作为

: IF左部变量a的类型=右部表达式类型THEN IF a的类型IN[ints reals chars,bools] THEN emit(STORE) ELSE emit1(COPYB,a.size) ENDIF ELSE IF(a的类型=reals)AND(右部表达式的类型=ints)THEN emit1(FLOAT,0); emit(STORE); ELSE error(n) ENDIF ENDIF;

赋值语句的右部是个表达式，当其左部变量为数组元素时，每个下标都是个表达式；表达式是语句中最常用的语法单位，其嵌入语义操作的文法规则为

<表达式>→<简单表达式>[<关系运算符><简单表达式>

]

<关系运算符>→=|< >|>|>=|<|<=

其相应的目标结构如图7.8所示。

计算简单表达式值 的目标指令

计算简单表达式x值 的目标指令 计算简单表达式y值 的目标指令 进行关系运算的目标指令 图7.8

例如 x>y

其中x,y均为普通简单实型变量。设当前lc=60，则生成的目标指令为

60 LODV lev(x) , adr(x) ; 61 LODV lev(y) , adr(y) ; 62 GTR ;

表达式的各语义操作为

: op:=sy; : IF(x.typ IN [notyp,ints,bools,chars]} AND (x.typ=y.typ)

THEN

CASE op OF

201

eql:emit(EQI) neq:emit NEQL lss:emit(LEI) leg:emit LEI gtr:emit(GTI) geq:emit(GEI)

ENDCASE ELSE

IF(x.typ=ints)AND(y.typ=reals)THEN emit1(FLOAT,1); x.typ:=reals; ELSE

IF(x.typ=reals)AND(y.typ=ints)THEN emit1(FLOAT,0); y.typ:=reals; ENDIF ENDIF;

IF(x.typ=reals)AND(y.typ=reals)THEN CASE op OF eql:emit(EQR); neq:emit(NEQR); lss:emit(LTR); leq:emit(LER); gtr:emit(GTR); geq:emit(GER);

ENDCASE ELSE error(n) ENDIF ENDIF;

x.typ:=bools;

简单表达式的嵌入语义操作的文法规则为

<简单表达式>→[<单目运算符>]<项>

{<加法运算符><项>}

<单目运算符>→+|- <加法运算符>→+|-|OR

其相应的目标结构如图7.9所示。

计算项的值的目标指令

计算项的值的目标指令 202

计算项x值的目标指令 计算项y1值的目标指令 进行加法运算的指令

图7.9

NEGATE （单目运算符为‘—’） 计算项x值的目标指令 NEGATE 计算项y1值的目标指令 进行加法运算的指令 ? 计算项yn值的目标指令 进行加法运算的指令

? 计算项yn值的目标指令 进行加法运算的指令 （单目运算符为‘—’）

例如

-x+y-z

其中x,y,z均为普通简单实型变量。设当前lc=70，则生成的目标指令为

70 LODV lev(x) , adr(x) ; 71 NEGATE

72 LODV lev(y) , adr(y) ; 73 ADDR ;

74 LODV lev(z) , adr(z) ; 75 SUBR ;

简单表达式的各语义操作为

: op:=sy;

: IF op=MINUS THEN emit(NEGATE) ENDIF; : op:=sy;

: IF op=orsy THEN

IF(x.typ=bools) AND (y.typ=bools) THEN emit(OR) ELSE error(n) ENDIF ELSE

IF(x.typ=ints) AND (y.typ=reals) THEN emit1(FLOAT,1); x.typ:=reals ELSE

IF(x.typ=reals) AND (y.typ=ints) THEN emit1(FLOAT,0);

203

y.typ:=reals ENDIF ENDIF;

IF x.typ=y.typ THEN IF x.typ=ints THEN IF op=plus THEN emit (ADDI) ELSE

emit (SUBI) ENDIF ELSE

IF op=plus THEN emit (ADDR) ELSE

emit (SUBR) ENDIF ENDIF ELSE error (n) ENDIF ENDIF;

项的嵌入语义操作的文法规则为

<项>→<因子>{<乘法运算符><因子>} <乘法运算符>→*|/|div|mod|and 例如

x*y/z

其中x,y,z均为普通简单实型量。设当前lc=80，则生成的目标指令为

80 LODV lev(x) , adr(x) ; 81 LODV lev(y) , adr(y) ; 82 MULR ; 83 LODV lev(z) , adr(z) ; 84 DIVR ;

项的各语义操作与简单表达式的各语义操作类似。作为练习，这留给读者自己完成（习题7.4）。

因子的嵌入语义操作的文法规则为

<因子>→（<表达式>） <因子>→<变量>

当因子为（<表达式>）时，其语义操作由<表达式>完成；当因子为<变量>

204

时其语义操作如下：

： CASE变量OF

无符号实数C :emit①(LODR,c1);{c1为c在实数表中的位置} 整常数N 字符常数S 简单变量X

记录分量r.z 数组元素

记录或数组B

NOT变量X

标准函数f(E)

:emit1(LODL,inum);{inum由insymbol返回，存放n的值}

:emit1(LODL,inum);{inum由insymbol返回，存放s的序号}

:IF X为变量参数THEN emit2(LOD*,lev(x),adr(x)) ELSE

emit2(LODV,lev(x),adr(x)) ENDIF

:IF X为变量参数THEN emit2(LODV,lev(r),adr(r)) ELSE

emit2(LODA,lev(r),adr(r)) ENDIF;

调用计算数组元素与记录域的地址的过程； :a[i1,?,in];

IF a为变量参数THEN emit2(LODV,lev(a),adr(a)) ELSE

emit2(LODA,lev(a),adr(a)) ENDIF;

调用计算数组元素与记录域的地址的过程； emit(FETCH); :IF B为变量参数THEN emit2(LODV,lev(B),adr(B)) ELSE

emit2(LODA,lev(B),adr(B)) ENDIF;{参考例a:=b} :调用变量过程本身； IF x.typ< >bools THEN error(n) ELSE emit(NOT);

:调用处理表达式过程； emit①(STAD,f编号);

205

ENDCASE;

7.4.2 控制语句

在PASCAL-S中，控制语句包括条件控制（IF和CASE）及循环控制（REPEAT，WHILE和FOR）。

IF语句嵌入语义操作的文法规则为

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

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

其相应的目标结构如图7.10所示。

图7.10

例如

IF a>0 THEN b:=0 ELSE c:=0

其中a,b,c均为普通整型变量。设当前lc=100，则生成的目标指令为

100 LODV lev(a) , adr(a) ; 101 LODL 0 ; a>0 102 GT1 ;

103 JUMPF 108 ;

104 LODA lev(b) , adr(b) ;

b:=0 105 LODL 0 ;

106 STORE ;

107 JUMP 111 ;

108 LODA lev(c) , adr(c) ;

c:=0 109 LODL 0 ;

110 STORE

lc→111

其中方框内的操作数是需要回填的。IF语句的 各语义操作请见7.1节。

CASE语句事实上是IF语句的拓广，它的 206

图7.11 嵌入语义操作的文法规则为

→CASE<表达式>OF

{<常量>{,<常量>}:<语句>;}END

其相应的目标结构如图7.11所示（其中JUMPX及ENTRY指令见7.2节）。 例如

CASE valid OF true:a:=4; false:a:=2 END;

其中valid为普通布尔型变量，a为普通整型量。设当前lc=200，则生成的目标指令为

200 LODV lev(valid), adr(valid) ; 201 JUMPX 210 ； 202 LODA lev(a) , adr(a) ; 203 LODL 4 ; a:=4 204 STORE ; 205 JUMP 215 ; 206 LODA lev(a) , adr(a) ; 207 LODL 2 ; a:=2 208 STORE ; 209 JUMP 215 ; 210 ENTRY 1 ; 211 ENTRY 202 ; 212 ENTRY 0 ; 213 ENTRY 206 ; 214 JUMP 0 ; lc→215

现在，我们来分析一下上述目标结构。在生成JUMPX指令时，尚不知情况表（ENTRY指令串）的入口地址，因此需要记住这条指令的位置，以便回填。情况表的位置在整个CASE语句的代码之后，为了构造它，必须在处理各“情况”时把各情况标号值及相应情况子句代码的开始位置记录下来。此外，在生成各情况子句的代码之后，需要生成一条转出口的指令，以便在运行时执行完情况子句后跳到后续语句去执行；而出口地址在生成指令时并不知道，所以这些转出口指令的位置也都需记录下来。由此，CASE语句各语义操作应为

: IF表达式类型< >离散类型THEN error(n)

207

ENDIF; lc1:=lc; emit(JMPX); i:=0; j:=0; : i:=i+1; casetab[i].val:=lab.i;{情况标号值} 图7.12 casetab[i].lc:=lc;{情况子句入口} : j:=j+1; exittab[j]:=lc;{转出口指令的位置} emit(JUMP); : code[lc1].y:=lc; FOR k:=1 TO i DO{构造情况表} emitl(ENTRY,casetab[k].val); emitl(ENTRY,casetab[k].lc) ENDFOR; emitl(JUMP,0); FOR k:=1 TO j DO{回填出口地址} code[emittab[k]].y:=lc ENDFOR;

循环语句有三种形式

（1）<循环语句>→REPEAT<语句>{;<语句>}UNTIL<表达式>其相应的目标结构如图7.12所示。

例如

REPEAT c:=c-1 UNTIL c=0;

其中c为普通整型变量。设当前lc=300，则生成的目标指令为

300 LODA level(c) , adr(c) ; 301 LODV level(c) , adr(c) ; 302 LODL 1 ; c:=c-1 303 SUBI ; 304 STORE ;

208

305 LODV level(c) , adr(c) ; 306 LODL 0 ; c=0 307 EQI ;

308 JUMPF 300 ; lc→309

REPEAT型循环语句的语义操作为

: lc1:=lc;

: IF表达式类型< >bools THEN

error(n) ENDIF;

emitl(JUMPF,lc1);

（2）<循环语句>→WHILE<表达式>DO<语句> 其相应的目标结构如图7.13所示。例如

WHILE b<10 DO b:=b+1;

其中b为普通整型变量设当前lc=400，则生成的目标指令为

400 LODV lev(b) , adr(b) ; 401 LODL 10 ; b<10 402 LET ; 403 JUMPF 410 ; 404 LODA lev(b) , adr(b) ; 405 LODV lev(b) , adr(b) ; 图7.13 406 LODL 1 ; b:=b+1 407 ADDI ; 408 STORE ; 409 JUMP 400 ； lc→410

WHILE循环语句的语义操作为

: lc1:=lc;

: IF表达式类型< >bools THEN error (n) ENDIF; lc2:=lc; emit(JUMPF); : emitl(JUMP,lc1); code[lc2].y:=lc; （3）<循环语句>→FOR<变量标识符>:=<表达式>TO

209

<表达式>DO<语句>

<循环语句>→FOR<变量标识符>:=<表达式>DOWNTO

<表达式>DO<语句>

其相应的目标结构如图7.14所示。

例如

FOR a:=1 TO 10 DO c:=c+1

其中a,c均为普通整型变量。设当前lc=500，则生成的目标指令为

500 LODA lev(a) , adr(a) ; 501 LODL 1 ; 502 LODL 10 ; 503 FOR1UP 510 ; 循环入口测试 504 LODA lev(c) , adr(c) ; 505 LODV lev(c) , adr(c) ; 506 LODL 1 ; c:=c+1 507 ADDI 1 ; 508 STORE ; 509 FOR2UP 504 ; 循环出口测试 lc→510

FOR循环语句的语义操作为

: emit2(LODA,lev(i),adr(i)); : IF表达式类型< >ints THEN error(n) ENDIF; : f:=tosy;

: f:=downtosy;

: IF表达式类型< >ints THEN error(n) ENDIF; lc1:=lc; IF f=tosy THEN emit(FOR1UP) ELSE emit(FOR1DOWN) ENDIF; lc2:=lc;

: IF f=tosy THEN emit(FOR2UP) ELSE

210

emit(FOR2DOWN) ENDIF;

code[lc1].y:=lc;

图7.14

7.4.3 子程序调用与返回

子程序调用与返回也影响着程序的控制流程，但它的语义与其它控制语句有很大不同，所以我们单独对它进行讨论。与子程序调用相关联的主要动作包括：

（1）为被调用的子程序分配数据区； （2）计算实在参数（值或地址）； （3）传递实在参数（传值或地址）； （4）保存返回地址； （5）转子程序体。

由于PASCAL-S的组织特点，相应的动作为 （1）为特定单元分配存贮； （2）计算并传递实在参数； （3）填写特定单元及寄存器； （4）为局部量分配存贮； （5）转子程序体。

函数调用基本上与过程调用一致。下面我们着重介绍过程调用语句。过程调用语句的嵌入语义操作的文法规则为

<调用语句>→<标识符>[(<实参>{,<实参>})] 其相应的目标结构如图7.15所示。

MARK i 计算并传递第1个实在参数 计算并传递第2个实在参数 ? 计算并传递第n个实在参数 211

返回地址:

CALL btab[j] . Psize-1 图7.15

例如

SUM(A,c+d);

其中A,c,d均为普通变量，而A对应的形式参数为变量参数，c+d对应的参数为值参数。设当前lc=600，则生成的目标指令为

600 MARK i ;{i为sum在标识符表中的位置} 601 LODA lev(A) , adr(A) ; 602 LODV lev(c) , adr(c) ; 603 LODV lev(d) , adr(d) ; 604 ADDI ;

605 CALL btab[j].psize-1;{j为sum在对应的块表中的位置} 下面我们详细地讨论实在参数的计算及传递。

如果与实在参数argumenti对应的形式参数是值参数，那么argumenti可以是一个表达式，而传递给形式参数的是它的值。当argumenti是一个简单类型的表达式时，“计算并传递第i个实在参数”所对应的指令就是计算这个表达式的指令（由处理表达式的过程产生），结果值在运行时栈的栈顶，也就是对应的形式参数分配的单元。如果argumenti是构造类型的，即数组或记录类型，因为处理这种表达式时生成的指令是将数组或记录的开始地址装到栈顶，因此还需要生成将数组和记录值装到栈顶的指令。于是，“计算并传递第i个实在参数”所对应的指令为

表达式过程处理argumenti生成的指令； LODB size；

其中size为数组或记录值所需的存贮单元数，这样才真正把实在参数的值传给了形式参数。

如果与实在参数argumenti对应的形式参数为变量参数，则argumenti只能是一个变量，而传递给形式参数的是相应实在参数的地址。当argumenti本身又是变量参数时（由于子程序调用允许嵌套，这种情况是存在的），“计算并传递第i个实在参数”所对应的指令为

LODV lev(argumenti),adr(argumenti);

因为argumenti单元中存的是实在参数的地址；而当argumenti为普通变量时，“计算并传递第i个实在参数”所对应的指令为 LODA lev(argumenti),adr(argumenti);

如果argumenti是数组元素或记录分量，则还需要生成计算数组元素或记录分量地址的指令，因为上面的指令只是装入了数组或记录的开始地址。

图7.16给出了运行时栈在执行过程调用指令前后的状态，参数区中存

212

放的是实在参数值或地址。注意，在MARK之后和CALL之前，栈顶指针是不断变化的。

图7.16

在处理过程调用时还需要考虑的一个问题是运行时display寄存器组的更新。因为运行时各变量的地址是根据层号和位移量计算的，即

display[lev]+adr

因此必须保证在过程调用及返回时能建立及恢复正确的display内容。在6.3节我们曾讨论过，如果调用的过程是在外层定义的非局部量，即过程调用所在的层号大于过程说明所在的层号，则在过程返回时要执行如下指令： UPD level1,level2

level1,level2分别为过程说明及过程调用所在的层号（见6.3节），但这条指令必须在处理过程调用时生成。在处理过程调用时，判断当前层号是否大于被调用过程所在层号，如果是，则在生成CALL指令之后再生成一条UPD指令，即让它成为过程返回后要执行的第一条指令。

与过程调用相对应的是过程的返回。在PASCAL-S中，过程返回是在过程体结束时发生的动作，它包括

（1）恢复运行时栈的原来状态（对函数而言，要把函数值留在栈顶）； （2）恢复基地址寄存器的内容； （3）根据返回地址完成转向。 于是，编译时应该生成指令 EXITP或EXITF

分别对应过程返回与函数返回。请注意，返回指令是在处理过程说明时生成的，由以上讨论，过程调用的各语义操作应为

: emit(MARK,i);{i为过程标识符在标识符表中的位置} : IF对应形参为值参THEN 调用处理表达式过程； IF表达式类型=对应值参类型THEN IF表达式类型=arrays或records THEN

213

emitl(LODB,size)

ENDIF ELSE

IF(表达式类型=ints)AND(对应值参类型=reals)THEN emit1(FLOAT,0) ELSE error(n) ENDIF ENDIF ELSE IF实参x本身为变量参数THEN emit2(LODV,lev(x),adr(x)) ELSE emit2(LODA,lev(x),adr(x)) ENDIF; IF x.typ=arrays或records THEN 调用计算数组元素与记录分量地址的过程 ENDIF； IF实参类型< >形参类型THEN error(n) ENDIF ENDIF;

: IF实参个数< >形参个数THEN error(n) ENDIF; emit1(CALL,btab[tab[i].ref].psize-1); IF tab[i].lev

对标准子程序的调用在道理上与普通子程序调用完全一样，所不同的是标准子程序的代码是事先编好的，而不是由编译程序生成的。通常，标准子程序的代码是放在库文件中的，编译程序所产生的目标代码只包含对标准子程序的调用，而不包含标准子程序的代码本身。因此说，编译程序产生的目标程序是不完整的，完整的目标程序是经过连接过程之后得到的。然而，在PASCAL-S编译程序中的情况不同。在这个编译程序中，对标准子程序的调用是直接翻译成目标指令的，所以，它产生的目标程序是完整的。关于标准函数调用的处理在表达式与赋值语句部分已介绍过，现在我们来讨论对标准过程的处理。

214

在PASCAL-S语言中提供了四个标准过程： read,readln,write,writeln

而PASCAL-S处理机则提供了如下的对应指令：

READ Y ； READLN ； WRITE0 Y ； WRITE1 Y ； WRITE2 Y ； WRITER Y ； WRITELN ；

读语句的嵌入语义操作的文法规则为：

<读语句>→read(<实参>{,<实参>}) <读语句>→readln[(<实参>{,<实参>})]

其相应的目标结构如图7.17所示。

取argument1地址 READ argument1.typ. 取argumentn地址 READ argumentsn.typ

取argument1地址 READ argument1.typ 取argumentn地址 READ argumentn.typ READLN 图7.17

例如

read(A,b)；

其中A为变量参数，b为普通变量。当前lc=700，则生成的目标指令为

700 LODV lev(A) , adr(A) ; 701 READ A.typ ; 702 LODA lev(b) , adr(b) ; 704 READ b.typ ;

读语句的各语义操作为

: n:=1; : n:=2; : IF实参x本身为变量参数THEN emit2(LODV,lev(x),adr(x)) ELSE emit2(LODA,lev(x),adr(x)) ENDIF; IF x.typ=arrays或records THEN

215

调用计算数组元素与记录分量地址的过程 ENDIF; emit1(READ,x.typ); : IF n=2 THEN emit(READLN) ENDIF；

写语句的嵌入语义操作的文法规则为

<写语句>→write(<表达式>[:<表达式>[:<表达式> ]]{,<表达式>[:<表达式>[:<表达式>]]})

<写语句>→writeln(<表达式>[:<表达式>[:<表达式> ]]{,<表达式>[:<表达式>[:<表达式>]]})

对应的目标结构如图7.18所示。

打印第1个参数指令 打印第2个参数指令 图7.18

打印第1个参数指令 打印第2个参数指令 ? 打印第n个参数指令

? 打印第n个参数指令 WRITELN 其中打印第i个参数指令的目标结构如图7.19所示。

LODL 串的长度 WRITE0串在串表中的开始位置 (a)实参是一个字符串 计算表达式的目标指令 计算域宽的目标指令 WRITE2 ints (c)实参是一个整型表达式， 后跟一个域宽

图7.19

打印第1个参数指令 打印第2个参数指令 (b)实参是一个整型表达式 计算表达式的目标指令 计算第一个域宽的目标指令 计算第二个域宽的目标指令 WRITER reals (d)实参是一个实型表达式

例如

writeln(A,c+d:7)

其中A为整型变量参数，c,d均为普通整型变量。当前lc=800，则生成的目标指令为

800 LOD* lev(A) , adr(A) ; 801 WRITE1 ints ;

216

802 LODV lev(c) , adr(c) ; 803 LODV lev(d) , adr(d) ; 804 ADDI ; 805 LODL 7 ; 806 WRITE2 ints ; 807 WRITELN ;

写语句的各语义操作为

: n:=3;

: n:=4;k:=0;

: IF实参类型=stringcon THEN emit1(LODL,sleng);{串的长度} emit1(WRITE0,inum);{串在串表中的开始位置} ELSE k:=1; IF表达式类型< >ints或reals THEN error(n) ENDIF; ENDIF; : k:=2; IF表达式类型< >ints THEN error(n) ENDIF; : k:=3; IF表达式类型< >ints THEN error(n) ENDIF; : CASE k OF 1:emit1(WRITE1,ints); 2:emit1(WRITE2,ints); 3:emit1(WRITE2,reals) ENDCASE; : CASE k OF 1:emit1(WRITE1,ints); 2:emit1(WRITE2,ints); 3:emit1(WRITE2,reals) ENDCASE; IF n=4 THEN emit(WRITELN);

217

这一章，我们讨论了PASCAL-S的语义分析及代码生成，主要讨论了各种说明和语句的处理。事实上，整个源程序的翻译完全可以归结为说明部分的处理和语句部分的处理，所需要注意的就是在整个源程序翻译完成后要生成一条终止目标程序执行的HALT指令。下面我们用一个完整的例子结束本章的讨论。

考虑如下的PASCAL-S源程序：

PROGRAM zeller (input output); VAR

day,month,year,zday,m,y1,y2:integer; BEGIN

read(day,month,year); IF month<3 THEN BEGIN

m:=month+10; year:=year-1 END ELSE

m:=month-2;

y1:=year DIV 100; y2:=year MOD 100;

zday:=(day+runc(2.6*m-0.1)+y2+y2 DIV 4+y1 DIV 4-2*y1+

49) MOD 7;

write(zday) END.

这个程序是计算以（日、月、年）形式给定的日期是星期几（星期日用0表示）。

下面是编译程序产生的符号表及目标程序，目标程序的开始地址为0。注意，如果源程序含有子程序，目标程序的开始地址（要执行的第一条指令）一般不是0（见习题7.11）。

表7.4 块表BTAB 实数表RCONST b 1 2 last 28 35 lastpar 1 28 psize 0 5 vsize 0 12

C2 1 2 值 2.6 0.1 218

表7.3 标识符表TAB t name link obj typ ref normal lev adr 28 27 prozedure notyp 2 true 0 0 29 day 0 vvariable ints 0 true 1 5 30 month 29 vvariable ints 0 true 1 6 31 year 30 vvariable ints 0 true 1 7 32 zday 31 vvariable ints 0 true 1 8 33 m 32 vvariable ints 0 true 1 9 34 y1 33 vvariable ints 0 true 1 10 35 y2 34 vvariable ints 0 true 1 11

目标程序为

0 LODA 1 , 5 ; 17 LODL 1 ; 34 MODI 1 READ ints ;

18 SUBI ; 35 STORE

2 LODA 1 , 6

;

19 STORE

;

36 LODA

8 ;

3 READ ints ; 20 JUMP 26 ; 37 LODV 1 , 5 4 LODA 1 , 7 ; 21 LODA 1 , 9 ; 38 LODR 1 5 READ ints ; 22 LODV 1 , 6

; 39 LODV 1 , 9

6 LODV 1 , 6 ; 23 LODL 2 ; 40 FLOAT 0 7 LODL 3 ; 24 SUBI ; 41 MULR

8 LTI

;

25 STORE

;

42 LODR 2 ;

9 JUMPF

21 ; 26 LODA

1

, 10 ;

SUBR

; 10 LODA 1 , 9 ; 27 LODV 1 , 7

;

44 STAD

10 11 LODV 1 , 6 ;

28 LODL 100 ; 45 ADDI

12 LODL 10 ; 29 DIVI

; 46 LODV 1 , 11

13 ADDI

; 30 STORE

;

47 ADDI ;

14 STORE

;

31 LODA

1

, 11 ; LODV

1 , 11 ;

15 LODA 1 , 7 ; 32 LODV 1 , 7 ; 49 LODL

4 16 LODV 1 , 7 ;

33 LODL 100 ; 50 DIVI

51 ADDI

; 57 LODV 1 , 10

; 63 MODI

219

; ;

1 ,

; ; ; ; ;

43

; ; ;

48 ; ;

;

52 LODV 1 , 10 ; 53 LODL 4 54 DIVI

;

55 ADDI 56 LODL 2

; ;

58 MULI 59 SUBI

; 64 STORE ;

66 WRITE1

; ; ints

; 65 LODV 1 , 8

; 60 LODL 49

61 ADDI

; 67 HALT ;

; 62 LODL 7

习 题

7.1 写出处理如下说明时所建立的符号表（包括标识符表、数组表、块表和实数表），各表指针可自行假定。

(a)TYPE

matrix=ARRAY[1..10,1..10]OF real; person=RECORD

name:ARRAY[1..10]OF char; sex:boolean; age:integer END;

cubic=ARRAY[1..5,1..5,1..5]OF real; class=ARRAY[1..50]OF person;

(b)VAR

you,he,i:RECORD

name:ARRAY[1..10]OF char; ex:boolean; age:integer END;

myclass:ARRAY[1..30]OF boolean; x,y,z:real;

(c)PROCEDURE routine(VAR total:real;i:integer);

VAR

i,j,k:integer;

a:ARRAY[0..100]OF real; u,v,w:real; BEGIN

? END;

7.2 在关于<形参表>的文法规则（见第四章）中插入语义操作来完成对它的处理。

220

7.3 写出处理如下语句时生成的目标指令。假定所有变量均非形式参数（其他条件可自行假定，下同）。

(a)a[i,j]:=x*y+b[i]/(x+y); (b)x:=x/y+a[i+1];

(c)IF x>0 THEN x:=x-1 ELSE x:=a[i]; (d)CASE ch OF

′a′, ′b′:tag:=0; ′0′, ′1′:tag:=1; ′+′, ′-′:tag:=2; END;

7.4 写出<项>的语义操作与。

7.5 在处理语句r:=(b*b-4*a*c)/(2*a)时，expression,simpleexpression, term,factor过程是以什么样的次序调用的？每次调用都生成什么指令？ 7.6 为如下条件语句生成的目标指令是什么？这种处理事实上做了什么规定？

IF x>0 THEN IF Y>0 THEN i:=1 ELSE J:=0 7.7 写出如下语句所生成的目标指令：

(a)REPEAT

k:=k+1

UNTIL castab [k].val=lab; (b)i:=0;

WHILE i<0 DO BEGIN i:=i+1;

tab [i].adr:=dx END;

(c)FOR i:=1 TO nt DO sum:=sum+at[i];

7.8 如果目标机中没有FOR1UP，FOR2UP，FOR1DOWN，FOR2DOWN指令，应该怎样设计FOR语句的目标结构？

7.9 写出下面语句的目标指令，假定大写字母代表变量参数。

(a)a[i]:=a[i]*X+Y[i]*X; (b)A[i]:=A[i]/R.x+Y[i]*R.x;

7.10 考虑如下过程调用：

p(f1,x1,x2,x3)

假定f1所对应的形式参数为变量参数，x1,x2,x3对应的形式参数为值参数，而x2、x3本身为变量参数，针对如下情况写出处理这个过程调用所生成的目标指令：

(a)f1,x1,x2,x3为简单类型；

221

(b)f1,x1,x2为简单类型，x3为数组类型。

7.11 翻译如下源程序时生成的目标程序是什么？这个目标程序是从哪一条指令开始执行的（即指令计数器PC的初值）？编译时产生的符号表具有什么内容？

PROCEDURE octalprint(input,output); VAR

decimal:integer;

PROCEDURE octalout(number:integer); BEGIN

IF number<8 THEN write(number:1) ELSE BEGIN

octalout(number DIV 8); write(number MOD 8:1); ENDIF END; BEGIN write(′? ′); read(decimal);

WHILE decimal>0 DO BEGIN

write(decimal:6, ′′:6); octalout(decimal); writeln; write(′? ′); read(decimal) END END.

7.12 编译如下源程序时产生的符号表及目标程序是什么？追踪目标程序执行时运行时栈及display的内容。

PROGRAM stack(output); TYPE

intarr=ARRAY[1..4]OF integer; VAR

m,n:integer; r:real; a:intarr;

222

PROCEDURE setup(ns:integer;check:real); VAR

k,l:integer;

FUNCTION total(VAR at:intarr;nt:integer):integer; VAR

i,sum:integer; BEGIN

FOR i:=1 TO nt DO sum:=sum+at[i]; total:=sum END; BEGIN

l:=27+total(a,ns); END; BEGIN n:=4;

setup(n,5.75) END.

7.13 如果想要把PASCAL中的GOTO语句扩充到PASCAL-S，需要考虑哪些因素？GOTO语句的目标结构如何设计？

223

本文来源：https://www.bwwdw.com/article/qgsp.html