编译原理课设实验报告文档格式.docx

编译原理课设实验报告文档格式.docx

《编译原理课设实验报告文档格式.docx》由会员分享，可在线阅读，更多相关《编译原理课设实验报告文档格式.docx（46页珍藏版）》请在冰点文库上搜索。

4

5

6

7

8

9

111

10

+

d

-

.

e

15

12

18

141

131

191

171

161

=

非=

>

201

<

211

241

23

221

}

\

*

（

）

281

271

261

251

{

，

；

301

29

311

！

其他

a）语法分析器（递归下降法）

采用自上而下的递归下降分析法，从文法的开始符号出发，根据文法规则正向推导出给定句子。

对文法中的每个非终结符编写一个函数（或子程序）,每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。

描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用。

为每个非终结符编制一个递归下降分析函数，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构和顺序编写，完成相应非终结符匹配，通过所有子程序的相互调用，完成整个终结符号串的分析。

（1）当遇到终结符a时，则编写语句

if（当前读来的输入符号==a）读下一个输入符号；

（2）当遇到非终结符A时，则编写语句调用A（）；

（3）当遇到规则A→ε时，则编写语句

if（当前读来的输入符号

FOLLOW（A））

error（）；

递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL

（1）文法。

语法结构定义采用扩充的BNF表示法,避免了直接左递归规则，并且也没有公共左因子。

对于非终结符E→T{+T}，函数T（）用while语句描述如下：

T（）

{

F（）;

while（sym==‘*’）

{

Scanner（）;

}

}

b）语义分析和中间代码生成器（语法制导翻译法）

1语义分析的任务：

1）静态语义审查：

审查每个语法结构的静态语义,即验证语法结构合法的程序,是否真正有意义。

2）执行真正的翻译：

如果静态语义正确,语义处理则要执行真正的翻译,即生成程序的某种中间代码的形式或直接生成目标代码。

2语法制导翻译法的基本思想

为文法的每个产生式都配备一个语义动作或语义子程序。

在语法分析的过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式的语义动作,从而实现语义处理。

在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序（或语义规则描述的语义处理的加工动作）进行翻译。

3属性文法和语义规则

语法制导翻译法使用属性文法为工具来描述程序设计语言的语义。

属性文法包含一个上下文无关文法和一系列语义规则（为文法的每一个规则配备的计算属性的计算规则）。

这些语义规则附在文法的每个产生式上,在语法分析过程中,执行语义规则描述的动作,从而实现语义处理。

也就是说,附在文法的每个产生式上语义规则描述了语义处理的加工动作。

4四元式中间代码结构

四元式主要由四部分组成：

（OP，arg1,arg2,result）

其中OP是运算符；

arg1,arg2分别是第一和第二两个运算对象（当OP是一目运算时，常常将运算对象定义为arg1）；

result是编译程序为存放中间运算结果而临时引进的变量，常称为临时变量，如Ti，也可以是用户自定义变量，如X。

5采用自下而上的语法制导翻译法语义动作的设计

（1）自下而上的语法制导翻译特点：

栈顶形成句柄，归约时执行相应语义动作

文法翻译到四元式的语义描述：

1）语义变量place

表示存放非终结符E值的变量名或其数值。

2）语义函数gen（op,argv1,argv2,result）

功能是生成一个四元式。

3）语义函数NewTemp（）

功能是产生一个新的临时变量名字，如T1，T2等。

4）语义变量index为四元式序列指针。

5）语义变量真出口etc和假出口efc

真（假）出口表示布尔表达式C为真（假）时控制流向的转移目标，布尔表达式的真（假）出口不能在产生其四元式的同时得知，因此设置两个语义变量

C.etc:

记录表达式C所对应的四元式需回填真出口的四元式的地址所构成的链

C.efc:

记录表达式C所对应的四元式需回填假出口的四元式的地址所构成的链

6）语义变量语句出口chain

在翻译语句时，其出口的转向点通常不能确定，用链表记录这些出口的位置，以便在适当的时机回填。

S.chain表示语句S全部出口组成的链即出口链，以待一次性回填。

7）语义变量语句入口head

使用语义变量LS.head记录while语句首地址，即对应的第一个四元式语句序号，以回填转移地址,。

8）函数merg（p1,p2）

功能是把以p1,p2为链首的两条链合并为一,返回合并后的链首；

9）回填函数bp（p,t）

功能是将p所链结的每个四元式的第四区分量都回填t;

（2）非终结符语义动作：

1）<

项>

:

:

=<

因子>

{*<

|/<

即T

F|T*F|T/F

T

F

{T.place=F.place}

T*F

{T.place=NewTemp（）;

gen（"

*"

T1.place,F.place,T.place）}

T/F

/"

2）<

表达式>

{+<

|-<

即E

T|E+T|E+T

同1）

3）<

条件>

=<

关系运算符>

，<

|<

=|>

|>

=|==|!

即C

EopE,op

{C.etc=index;

C.efc=index+1;

gen（"

goto"

+op,E1.place1,E2.place2,"

0"

）;

goto"

"

"

4）<

赋值语句>

=ID=<

即AS

ID=E

{gen（"

="

E.place,"

ID）;

bp（AS.chain,index）;

5）<

条件语句>

=if<

语句块>

[else<

]

即CS

ifCB|ifCBelseB

{bp（C.etc,index）;

CS.Chain=C.efc;

...（B（））

CS.chain=merge（B1.chain,index）;

bp（C.efc,index）;

CS.chain=merge（B2.chain,CS.chain）}

6）<

循环语句>

=do<

while<

即LS

doBwhileC

{LS.head=index;

...（C（））

bp（C.etc,LS.head）;

CS.chain=merge（B.chain,C.efc）}

bp（CS.chain,index）;

c）目标代码生成

采用汇编语言代码作为目标代码生成器的输出，

在四元式序列中有3类量，常量，程序变量和临时变量。

一般地，常量对应立即数出现在目标指令中；

程序变量是程序中用户自定义变量，通常是存放在存储单元中的存储器变量，在数据段定义为同名字变量（使用伪指令DW）；

而临时变量则是在生成四元式时由编译程序引进的，因为寄存器变量的存取比存储变量的存取快得多，因此，为临时变量安排寄存器。

1寄存器描述表和地址描述表

为了反映寄存器使用情况及变量值的存放情况，引进寄存器描述表registerStatus与地址描述表registerT。

寄存器描述表动态反映了寄存器的使用状态，即寄存器是处于空闲状态还是被临时变量占用，以便分配寄存器给临时变量。

由于本课设中程序变量存储在存中，源代码单语句所有临时变量都为语句出口后的非活跃变量，因此，每执行完一条源代码语句，可视作寄存器中容不再使用，描述符清零。

地址描述表指明临时变量所在的寄存器，寄存器描述符为字符串数组，索引为临时变量编号，可能多个临时变量同存在一寄存器。

2目标指令与四元式编号对照表

控制转移指令分两种:

条件控制转移（"

+op,argv1,argv2,Lable）和无条件控制转移（"

Lable）。

往往在生成目标代码的时候还不了解控制转移到的目标指令的编号，因此需要回填。

为此，引进目标指令与四元式编号对照表lable，lable[i]反应了四元式i对应的若干目标指令中第一条的编号，在生成目标代码时在第四分量中只填入四元式编号i，待所有目标指令完全生成后再统一回填lable[i]。

3寄存器分配函数

寄存器的分配由函数char*GetfreeR（）实现。

为当前值不在寄存器的临时变量分配空闲寄存器。

4四元式对应目标代码

根据四元式生成规则,1中argv2为程序变量，2,3,4,5中res为首次出现的临时变量Ti，6,7中label为语句标号Li。

序号

四元式

目标代码

备注

（=,argv1,"

argv2）

（1）MOVR,argv1

MOVargv2,R

（2）MOVargv2,R

（1）argv1为现行值不在寄存器的临时变量，R是新分配给argv1的寄存器

（2）argv1为立即数或现行值在寄存器R的临时变量

（+,argv1,argv2,res）

ADDR,argv2

（2）ADDR,argv2

（1）argv1现行值不在寄存器，R是新分配给argv1的寄存器,对res=Ti置registerT[i]=R

（2）argv1现行值在寄存器R,对res=Ti置registerT[i]=R

（-,argv1,argv2,res）

SUBR,argv2

（2）SUBR,argv2

（*,argv1,argv2,res）

IMULR,argv2

（2）IMULR,argv2

（/,argv1,argv2,res）

（1）PUSHAX

（2）PUSHDX

（1）MOVAX,argv1

CWD

（3）MOVR,argv2

（3）IDIVR

（4）IDIVargv2

（2）POPDX

（1）POPAX

（1）argv1现行值不在AX且AX被占用

（2）DX被占用

（3）argv2为立即数（常量）

（4）argv2为临时变量（寄存器变量）或程序变量（存储器变量）

对res=Ti置registerT[i]=R

（goto,"

label）

JMPLabel

对于label=Li

Label="

L"

+atoi（label[i]）

（gotoop,argv1,argv2,label）

CMPR,argv2

（2）CMPR,argv2

（3）CMPargv1,argv2

JXLabel

（1）argv1为立即数（常量）或argv1,argv2同为存储器操作数（程序变量）

（2）argv1现行值在寄存器R

（Op,JX）=（==,JE）|（!

=,JNE）|（>

=,JGE）|（>

JG）|（<

=,JLE）|（<

JL）

说明：

使用到的80X86宏汇编指令：

一般传送指令MOVOPD,OPS

将字转换成双字指令（将AX中的符号扩展至DX中）：

CBW

加指令：

ADDOPD,OPS

减指令：

SUBOPD,OPS

有符号乘指令：

IMULOPD,OPS

有符号除指令：

IDIVOPS（字除法：

（DX,AX）/（OPS）

AX（商）,DX（余数））

比较指令：

CMPOPD,OPS

转移指令：

JE相等转移

JNE不相等转移

JG大于转移

JGE大于或等于转移

JL小于转移

JLE小于或等于转移

JMP无条件转移

指令限制：

（1）目的操作数不能是立即操作数；

（2）操作结束后，运算结果送人目的地址中；

（3）源操作数和目的操作数不能同时为存储器操作数；

（4）IMULOPD,OPS中OPD为寄存器

（5）IDIVOPS中OPS不能是立即操作数

1.流程框图

1）词法分析器

scaner（）函数流程图

2）语法分析器（递归下降法）

P（）函数流程图

B（）函数流程图

SS（）函数流程图

3）语义分析及中间代码生成

初始化:

flag,nVar,index,nSuffix置0

Parse（）函数流程图

4）目标代码生成

2.函数相关说明

1）词法分析部分

函数Scaner（）;

识别源程序的一个单词符号

词法分析程序所用的全局变量如下：

rwtab[]关键字对应到编码值的映射表。

prog[]字符数组，存放源程序

ch字符变量，存放当前读进的源程序字符。

syn整型，当前单词种别编码

token[]字符数组,存放当前构成单词符号的字符串。

sum双精度型，存放当前常量的数值。

variable[]用户自定义变量信息表。

flag1表示刚读取一个变量或常数，"

+/-"

为运算符;

0反之，"

可能为数值符号

将从键盘输入的字符串存储到prog[]数组，用scaner（）函数从prog[]中取出有独立意义的字符串存到token[]中：

1、首字符为字母，且其后为字母与数字的组合，syn对应到码值10，进一步检查此组合字符串是否在关键字表中，若在其中，则修改syn对应到相应码值；

2、数字串的组合中：

整数数字串、小数数字串码值、（含有字母e）指数数字串，将其二进制数值存入sum；

3、其他符号先判断是否为符号组合一部分，若为符号组合，则继续扫描，syn应到相应码值；

若为单个符号，则回退，syn对应到相应码值。

main（）：

先从键盘输入待编码字符串，存入prog[]中，用#判断是否输入结束，然后调用scaner（）函数，得到对应码值，有print函数显示输出。

d）语法分析部分（递归下降法）

（1）函数Scaner（）

功能:

读进源程序的下一个单词符号

并将它放在全程变量sym。

（2）函数error（）

出错处理程序。

数组prog[]、token[]、rwtab[]，函数scanner（）作用同上。

递归下降算法分析：

调用scaner（）函数，对应出码值若不为0，则报错；

然后调用语句串分析函数；

判断是否含有end；

若含有则再次调用scaner（）函数，对应得相应码值；

判断是否由#提示结束；

若是，则打印分析成功，若否则转报错处理。

3.输入与输出（包括出错处理）

a）词法分析程序

词法分析程序的输入是字符串形式的源程序，词和词之间可以用空白字符（空格、回车、制表符）隔开。

词法分析程序的输入是一个二元组，形式为：

（单词种别码，单词自身的值）。

若输入的字符串带有不合法的字符，则对应的字符（串）在输出中不以二元组的形式显示，而以“error!

!

”表示出错。

例如：

输入mainwhileif123.455e+123#

输出：

（1,main）

（9,while）

（6,if）

（20,1.23455e+125）

（0,#）

b）语法分析程序

语法分析程序的输入与词法分析的输入一致，即字符串形式的源程序，词和词之间可以用空白字符（空格、回车、制表符）隔开。

语法程序的输出是判断所输入字符串是否是该语言的句子的结果，也即“success！

”或者“fail！

”，分别表示所输入的字符串是该语言的一个句子和字符串不是该语言的一个句子。

出错时结果为“fail！

”。

输入123.345e+123+（1*3+（2+4）/212）+12#

结果为“success！

”

4.程序运行结果（屏幕截图）

5.编译器使用说明

语法分析器的输入为字符串形式的源程序，词与词之间可以用空白字符（空格、回车、制表符）隔开；

”或者“fail！

”，分别表示所输入的字符串是该语言的一个句子和字符串不是该语言的一个句子。

是则输出“success”,出错则输出“fail”。

6.心得与体会

大部分系统软件和应用软件的开发，通常要用到编译的原理和技术。

设计词法分析器的串匹配技术已用于正文编辑器、信息检索系统和模式识别程序;

上下文无关文法和语法制导定义已用于创建诸如排版、绘图系统和语言结构化编辑器中，代码优化技术已用于程序验证器和从非结构化的程序产生结构化程序的编程之中。

通过动手编写程序对词法语法的分析有了更加深入的体会，巩固了编译原理的基本知识，亲自动手实践编译程序，使我对编译更加感兴趣。

此次实验只是实现了编译器最基本的功能，不由得感叹实际的编译器实在太强大了！

继续认真学习，勤于思考，学习编译中的精妙思想，做好课设！

7.源程序清单

#include"

stdafx.h"

#include<

stdio.h>

stdlib.h>

string.h>

math.h>

locale>

conio.h>

/************************************************************************/

/*词法分析*/

#definemax10

char*rwtab[9]={"

main"

int"

float"

double"

char"

if"

else"

do"

while"

};

charprog[100];

//源程序

intp;

//当前处理字符位置

charch;

//当前处理字符

intflag;

//1表示刚读取一个变量或常数，"

0反之，"

intsyn;

//种别编