编译原理课程设计Word下载.docx
《编译原理课程设计Word下载.docx》由会员分享，可在线阅读，更多相关《编译原理课程设计Word下载.docx（34页珍藏版）》请在冰点文库上搜索。
四、开发过程和完成情况
（一）本次课程设计实现的内容有：
10
1、基本内容10
2、选作内容10
（二）设计分析10
1.扩充赋值运算：
2.扩充++,--运算符功能10
3.FOR<
DO<
15
五、测试
1.测试+=、-=语句功能测试17
1）测试文件17
2）测试结果：
17
2.测试增加的FOR<
18
1）测试文件18
2）测试结果18
3.测试++、--语句功能测试19
1）测试代码19
2）测试结果19
六、问题讨论和体会
一、编译原理课程设计内容
（一）基本内容（成绩范围：
“中”、“及格”或“不及格”）
+=和-=
（二）选做内容（成绩评定范围扩大到：
“优”和“良”）
（1）增加类型：
①字符类型；
②实数类型。
①有返回值和返回语句；
②有参数函数。
二、实验环境与工具
（一）计算机及操作系统：
PC机，WindowsXP
（二）程序设计语言：
C
（三）教学型编译程序：
PL/0
三、设计方案
源、目标语言，实现工具（平台），运行平台
PL/0语言是Pascal语言的一个子集，我们这里分析的PL/0的编译程序包括了对PL/0语言源程序进行分析处理、编译生成类PCODE代码，并在虚拟机上解释运行生成的类PCODE代码的功能。
各功能模块描述
PL/0的编译程序和目标程序的解释执行程序可用Pascal，C或其他语言书写，因此PL/0语言可再配备相应书写语言的任何机器上实现。
编译过程采用一趟扫描方式，以语法语义分析程序为核心，词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就用词法分析程序，而当语法分析正确需生成相应的目标代码时，则调用代码生成程序。
此外，用表格管理程序建立变量，常量和过程标识符的说明与引用之间的信息联系。
用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。
当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。
PL0程序总流程图：
PL/0编译程序（包括主程序）是由18个嵌套及并列的过程或函数组成，现分别简要给出这些函数的功能及它们的层次结构。
过程或函数名
简要功能说明
pl0
主程序
error
出错处理，打印出错位置和错误编码
getsym
词法分析，读取一个单词
getch
漏掉空格，读取一个字符
gen
生成目标代码，并送入目标程序区
test
测试当前单词符号是否合法
block
分程序分析处理过程
enter
登录名字表
position（函数）
查找标识符在名字表中的位置
constdeclaration
常量定义处理
vardeclaration
变量说明处理
listode
列出目标代码清单
statement
语句处理
expression
表达式处理
term
项处理
factor
因子处理
condition
条件处理
interpret
对目标代码的解释执行程序
base（函数）
通过静态链求出数据区的基地址
（三）主要成分描述
1、符号表
所有符号都放在全程量一维数组TABLE表中。
TX为索引表的指针，表中的每个元素为记录型数据。
LEV给出层次，DX给出每层局部量当前已分配到的相对位置。
且TABLE表的表头索引TX和层次单元LEV都以BLOCK的参数形式出现。
每个过程中的变量的相对初始位置在BLOCK内置初值DX：
=3。
结构形式如下：
NAME
KIND
VAL/LEVEL
ADR
SIZE
全程量一维数组。
表项主要有5个：
名字（NAME），类型（KIND）,值/层次（VAL/LEVEL），过程名的ADR域，过程所需要的空间（SIZE）。
对于常量，变量和过程说明这三种情况，都需要把其相关的信息登记入符号表中。
这三种情况需要登记到符号表的内容分别如下：
●常量：
记录下该常量的名字（TBLE.NAME），登记该名字属于常量（TABLE.KIND），记录下该常量的值（TABLE.VAL）。
●变量：
记录该变量的名字（TABLE.NAME），记录下该名字为变量的类型（TABLE.KIND），登记下该变量所在的层次（TABLE.LEVEL），登记该变量存储位置（TABLE.ADR）。
●过程名：
记录下该过程名字（TABLE.NAME），记录下该名字属于过程
（TABLE.KIND），记录下该过程所在的层次（TABLE,LEVEL），记录下存储位置
（TABLE.ADR），过程所需要的数据空间（TABLE.SIZE）。
其对应的功能函数为enter，根据这些特点我们就可以在原来的基础上加入新的数据类型，如数组、char等，其存储结构为：
structtablestruct
{
charname[al];
/*名字*/
enumobjectkind;
/*类型：
const，var，arrayorprocedure*/
intval;
/*数值，仅const使用*/
intlevel;
/*所处层，仅const不使用*/
intadr;
/*地址，仅const不使用*/
intsize;
/*需要分配的数据区空间，仅procedure使用*/
};
进符号表的具体代码如下：
/*
*在名字表中加入一项
*
*k:
名字种类const,varorprocedure
*ptx:
名字表尾指针的指针，为了可以改变名字表尾指针的值
*lev:
名字所在的层次，以后所有的lev都是这样
*pdx:
dx为当前应分配的变量的相对地址，分配后要增加1
*/
voidenter（enumobjectk,int*ptx,intlev,int*pdx）
（*ptx）++;
strcpy（table[（*ptx）].name,id）;
table[（*ptx）].kind=k;
switch（k）
{
caseconstant:
if（num>
amax）
{
error（31）;
num=0;
}
table[（*ptx）].val=num;
break;
casevariable:
table[（*ptx）].level=lev;
table[（*ptx）].adr=（*pdx）;
（*pdx）++;
caseprocedur:
casearray:
/*数组名字的修改*/
table[（*ptx）].adr=（*pdx）-arraysize;
table[（*ptx）].size=arraysize;
}
2、运行时存储组织和管理
当源程序经过语法分析，如果未发现错误时，由编译程序调用解释程序，对存放再CODE中的目标代码从CODE[0]开始进行解释执行。
当编译结束后，记录源程序中标识符的TABLE表已没有作用。
因此存储区只需以数组CODE存放的只读目标程序和运行时的数据区S。
S是由解释程序定义的一堆整型数组。
由于PL/0语言的目标程序是一种假想的栈是存储空间。
遵循后进先出规则，对每个过程（包括主程序）当被调用时，才分配数据空间，退出过程时，所分配的数据空间被释放。
解释程序还定义了4个寄存器。
（a）I指令寄存器。
存放当前正在解释的一条目标指令。
（b）P程序地址寄存器。
指向下一条要执行的目标程序的地址（相当目标程序CODE数组的下标）。
（c）T栈顶寄存器。
由于每个过程当它被运行时，给它分配的数据空间（下边称数据段）可分成两部分。
静态部分：
包括变量存放区和三个联系单元。
动态部分：
作为临时工作单元和累加器用。
需要时随时分配，用完后立即释放。
（d）B基址寄存器。
指向每个过程被调用时，在数据
区S中给它分配的数据段起始地址，也称基址。
为了实现过程被调用时给它分配数据段，过程运行
结束后释放数据段以及嵌套过程之间标识符引用的寻址
问题，当过程被调用时，在栈顶分配三个联系单元，这
三个单元存放的内容分别为：
（a）SL静态链：
它是指向那个定义该过程的直接外过
程（或主过程）运行时最新数据段的基地址。
（b）DL动态链：
它是指向调用该过程目前正在运行过
程的数据段基地址。
（c）RA返回地址：
记录调用该过程时目标程序的断点，
即当时的程序地址寄存器P的值。
也就是调用程序
指令的下一条指令的地址。
PL/0编译程序给每个过程定义的变量在数据段内分配的
相对位置是从3开始顺序增加。
前面的三个单元为上面指出
的联系单元。
其中静态链的作用是当一个过程引用包围它的
过程（或主程序）所定义的标识符时，首先沿静态链跳过个
数为层差的数据段，找到定义该标识符过程的数据段基地址。
若标识符的属性是变量，则把该数据段基地址加上给此变量分
配的相对位置，就得到该变量在整个数据栈中的绝对位置；
若
标识符的属性是过程，则该数据段基地址正是被调用过程直接
外层的基地址，也就是被调用过程的静态链SL的值。
动态链
和返回地址的作用是当一个过程运行结束后，为了恢复调用该
过程前的执行状态而设置的。
3、语法分析方法
PL/0编译程序的语法分析采用了自顶向下的递归子程序法。
粗略地说：
就是对应每个非终结符语法单元，编一个独立地处理过程（或子程序）。
语法分析从读入第一个单词开始由开始符“程序”出发，沿语法描述图箭头所指出的方向进行分析。
当遇到非终结符时，则调用相应的处理过程，从语法描述图看也就进入一个语法单元，再沿用当前所进入的语法描述图的箭头方向进行分析，当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义程序（就是翻译程序）。
再读取下一个单词继续分析。
遇到分支点时将当前的单词与分支点上的多个终结符逐个比较，若都不匹配时可能时进入下一个非终结符语法单位或者时出错。
如果一个PL/0语言程序的单词序列在整个语法分析中，都能逐个得到匹配，直到程序结束符“．”，这时就说所输入的程序是正确的。
对于正确的语法分析做相应的语义翻译，生成目标代码。
此外，从PL/0的语法描述图中可以清楚地看到，对PL/0语言进行语法分析时，各个非终结符语法单元所对应的分析过程之间存在的调用关系图如右图所示。
这个调用关系也可称为PL/0语法的依赖图，在图中箭头所指向的程序单元表示存在调用关系，从图中不难看出这些子程序在语法分析时被直接或间接递归调用。
除主程序外，语法语义分析的处理由分程序BLOCK过程完成。
4、中间代码表示
PL/0编译程序所产生的目标代码是一个假想栈式计算机的汇编语言，可称为类PCODE指令代码，它不依赖任何实际计算机，中间代码生成是由过程GEN完成，GEN有3个参数，分别代表目标代码的功能码，层差和位移量其指令集极为简单，指令格式也很单纯，其格式如下：
fla
其中f代表功能码，l表示层次差，a的含意对不同的指令有所区别，见下面对每条指令的解释说明：
lit0a
将常数值取到栈顶，a为常数值
Lodla
将变量值取到栈顶，a为偏移量，l为层差
Stola
将栈顶内容送入某变量单元中，a为偏移量，l为层差
Calla
调用过程，a为过程地址，l为层差
Int0a
在运行栈中为被调用的过程开辟a个单元的数据区
jmp0a
无条件跳转至a地址
Jpc0a
条件跳转，当栈顶布尔值非真则跳转至a地址，否则顺序执行
opr00
过程调用结束后,返回调用点并退栈
opr01
栈顶元素取反
opr02
次栈顶与栈顶相加，退两个栈元素，结果值进栈
opr03
次栈顶减去栈顶，退两个栈元素，结果值进栈
opr04
次栈顶乘以栈顶，退两个栈元素，结果值进栈
opr05
次栈顶除以栈顶，退两个栈元素，结果值进栈
opr06
栈顶元素的奇偶判断，结果值在栈顶
opr07
opr08
次栈顶与栈顶是否相等，退两个栈元素，结果值进栈
opr09
次栈顶与栈顶是否不等，退两个栈元素，结果值进栈
opr010
次栈顶是否小于栈顶，退两个栈元素，结果值进栈
opr011
次栈顶是否大于等于栈顶，退两个栈元素，结果值进栈
opr012
次栈顶是否大于栈顶，退两个栈元素，结果值进栈
opr013
次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈
opr014
栈顶值输出至屏幕
opr015
屏幕输出换行
opr016
从命令行读入一个输入置于栈顶
四、开发过程和完成情况
1、基本内容（成绩范围：
2、选作内容：
（二）设计分析（代码见程序）
+=、-=
对于+=、-=赋值运算符，在程序中出现的情况只有如下一种，文法的EBNF表示为：
赋值语句:
=<
标识符>
[:
=|+=|++|--]<
其中的++和--在扩充自增自减运算符中分析，下面分析+=、-=运算符扩充功能。
1）扩充的语法描述见结构设计中的PL/0分程序和主要语句的语法描述中的描述图；
2）分析区别赋值运算符采用：
读标识符后再读一个字符，后根据读到的字符转去不同的赋值语句执行。
3）中间代码生成情况：
+=运算符，其他赋值运算符架构是一样的，只是执行加法改为相应的算数运算。
读到+=运算符单词
求+=运算符后的表达式
expressiondo（nxtlev,ptx,lev）;
取+=左部的标识符的值到栈顶
gendo（lod,lev-table[i].level,table[i].adr）;
执行加法
gendo（opr,0,2）;
保存赋值后的结果
gendo（sto,lev-table[i].level,table[i].adr）;
2.扩充++,--运算符功能
对于++和--运算符，扩充时要注意存在++,--有两个情况：
（1）、作为语句的时候；
（2）、作为表达式中的因子的时候。
1）作为语句的时候有四情况：
a++;
a--;
++a;
--a
语法描述图：
生成中间代码（不包括一维数组的自增自减）：
对于a++;
和a--;
--a;
语句的处理如下：
先将变量的值取出放在栈顶，后将1入栈，后执行加法或减法运算opr指令的2（加法）、3（减法），后将运算后的栈顶值存回变量。
和++a;
语句的中间代码：
a--;
和—a;
2）作为因子的时候，有两种情况：
a++和a--作为因子，比如：
b:
=a++;
语句
++a和--a作为因子，比如：
=--a;
语句
文法的表示形式为：
<
=...[++|--]<
|<
[++|--]...其中的...表示前后都可以有其他的项或因子其文法分析过程和为语句的情况差不多，在此不细说了，请见源程序。
生成中间代码（不包括一维数组的自增自减）：
①对于因子++a和--a的中间代码生成处理和a++;
等语句处理一样；
②对于因子a++和a—的中间代码生成处理如下：
先将变量的值取出放在栈顶，后将1入栈，后执行加法或减法运算opr指令的2（加法）、3（减法），后将运算后的栈顶值存回变量，后将变量的值又取出来放入栈顶，后将1入栈，如果是a++就执行减法，如果是a—就执行加法，以实现先用a的值后再加1.
因子a++的中间代码：
因子a—的中间代码：
在statement（）上修改：
代码如下：
getsymdo;
//进行修改,增加"
+="
和"
-="
if（sym==becomes）
{
getsymdo;
memcpy（nxtlev,fsys,sizeof（bool）*symnum）;
expressiondo（nxtlev,ptx,lev）;
if（i!
=0）
{
gendo（sto,lev-table[i].level,table[i].adr）;
}
}
elseif（sym==pbecomes）//实现"
gendo（lod,lev-table[i].level,table[i].adr）;
//将变量值取到栈顶
memcpy（nxtlev,fsys,sizeof（bool）*symnum）;
//nxtlev[plus]=true;
expressiondo（nxtlev,ptx,lev）;
//处理赋值符号右侧表达式
gendo（opr,0,2）;
//加法
elseif（sym==mbecomes）//实现"
//nxtlev[minus]=true;
gendo（opr,0,3）;
//减法
elseif（pplus==sym||mminus==sym）//实现后加或者后减操作,eg:
a++,a--
pflag=（sym==pplus）;
gendo（lod,lev-table[i].level,table[i].adr）;
//将要自加或者自减的变量压到栈顶
num=1;
gendo（lit,0,num）;
//将常数num压到栈顶
if（true==pflag）
gendo（opr,0,2）;
else
gendo（opr,0,3）;
gendo（sto,lev-table[i].level,table[i].adr）;
//存到相应的变量中
getsymdo;
error（13）;
/*没有检测到赋值符号*/
elseif（sym==pplus||sym==mminus）//实现前加或者前减操作,eg:
++a,--a
pflag=（pplus==sym）;
if（sym==ident）
i=position（id,*ptx）;
if（i==0）
error（11）;
/*变量未找到*/
if（table[i].kind!
=variable）
error（12）;
i=0;
//将变量压到栈顶,准备进行前加或者前减
gendo（lit,0,1）;
//***********************************完毕
在factor（）上修改代码如下：
if（pplus==sym||mminus==sym）
g
升级会员 