计算机操作系统内存分配实验报告记录
计算机操作系统内存分配实验报告记录
————————————————————————————————作者：————————————————————————————————日期：
一、实验目的
熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。
二、实验内容和要求
主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。
可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。
实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。
三、实验主要仪器设备和材料
实验环境
硬件环境：PC或兼容机
软件环境：VC++ 6.0
四、实验原理及设计分析
某系统采用可变分区存储管理，在系统运行当然开始，假设初始状态下，可用的内存空间为640KB，存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。
（作业1 申请130KB、作业2 申请60KB、作业3 申请100KB 、作业2 释放 60KB 、作业4 申请 200KB、作业3释放100KB、作业1 释放130KB 、作业5申请140KB 、作业6申请60KB 、作业7申请50KB）
当作业1进入内存后，分给作业1（130KB），随着作业1、2、3的进入，分别分配60KB、100KB，经过一段时间的运行后，作业2运行完毕，释放所占内存。此时，作业4进入系统，要求分配200KB内存。作业3、1运行完毕，释放所占内存。此时又有作业5申请140KB，作业6申请60KB，作业7申请50KB。为它们进行主存分配和回收。
1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。
空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1”。
设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使用空闲低端的空间。
设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明
链的变化情况以及各作业的申请、释放情况显示打印出来。
2.采用可变分区存储管理，分别采用首次适应算法、最佳适应算法和最坏适应算法实现主存分配和回收。
3、主存空间分配
（1）首次适应算法
在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到
第一个能满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作
业，余下的空闲区仍留在空闲区链中。
（2）最佳适应算法
在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到
一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小，从中
划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中（3）最坏适应算法
在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到
一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都大，从中
划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链
中。
4、主存空间回收
当一个作业执行完成撤离时，作业所占的分区应该归还给系统。归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的合并问题，要求考虑四种情况：
（1）释放区下邻空闲区（低地址邻接）
（2）释放区上邻空闲区（高地址邻接）
（3）释放区上下都与空闲区邻接
（4）释放区上下邻都与空闲区不邻接
五、程序流程图
main函数里的流程图
选择
a=1，首次a=2，最佳a=3，最坏
初始化
整理分
显示空闲
选择操
i=1，分配i=0，退i=2，回收
结
分配空间里的流程图
回收空间里的流程图
p->data.l
分配
分配空
a=a=a=输入申按顺序
初始化q ，输入申初始化q ，p->data.l p 的状态
剩下 p->data.le 输入申Y Y N N 返回到整理
六、相关数据结构及关键函数说明
本程序采用了一个struct free_table 数据结构，里面包含分区序号（num ）、起始地址（address ）、分区长度（length ）和分区状态（state ）。还用了线性表的双性链表存储结构（struct Node ），里面包含前区指针（prior ）和后继指针（next ）。一开始定义一条（含有first 和end ）的链，用开始指针和尾指针开创空间链表。然后分别按三种算法进行分配和回收。
p 的
回收p ，p 的前一个为
p 的后一个是end
p 的后一个状态空
与后面空闲块相连
将p 的状态改为空闲
将p 的状态改
为空闲
回收空
p 的后一个是end
Y
N
Y
N
Y
N
p 的前一个状态空
p 的前一个状态空
p 的后一个状态空
p 的后一个状态空
p 的后一个状态空
p 的后一个状态空
Y
Y
Y
N
N
N
与前面空闲块相连
p 的
与前面空闲块相连
与后面空闲块相连
Y
N 返回到整理
在该程序中关键函数有，sort（）、allocation（）、recovery（）、和First_fit（）、Best_fit （）、Worst_fit（）；其中sort（）函数是用来整理分区序号的，如在删序号3时，她与前面序号2相连在一起了，然后序号2中的长度总满足申请的内存大小，就会在序号2中分配，然后序号在2的基础上加1，一直加，加到与原本序号3的下一个序号也就是4相等，这时sort（）就开始有明显的工作了；allocation（）是分配空间的，也是过渡到三个算法中的，当三个算法中满足或者不满足分配请求，都会又返回值给allocation（）；recovery（）是用来回收内存的，里面包含了四种情况相连结果，即释放区上与空闲区邻接、释放区下与空闲区邻接、释放区上下都与空闲区邻接、释放区上下都与空闲区不邻接这四种情况的结果。
七、源代码
#include
#include
#define OK 1 //完成
#define ERROR 0 //出错
typedef int Status;
typedef struct free_table//定义一个空闲区说明表结构
{
int num; //分区序号
long address; //起始地址
long length; //分区大小
int state; //分区状态
}ElemType;
typedef struct Node// 线性表的双向链表存储结构
{
ElemType data;
struct Node *prior; //前趋指针
struct Node *next; //后继指针
}Node,*LinkList;
LinkList first; //头结点
LinkList end; //尾结点
int flag;//记录要删除的分区序号
Status Initblock()//开创带头结点的内存空间链表
{
first=(LinkList)malloc(sizeof(Node));
end=(LinkList)malloc(sizeof(Node));
first->prior=NULL;
first->next=end;
end->prior=first;
end->next=NULL;
end->data.num=1;
end->data.address=40;
end->data.length=600;
end->data.state=0;
return OK;
}
void sort()//分区序号重新排序
{
Node *p=first->next,*q;
q=p->next;
for(;p!=NULL;p=p->next)
{
for(q=p->next;q;q=q->next)
{
if(p->data.num>=q->data.num)
{
q->data.num+=1;
}
}
}
}
//显示主存分配情况
void show()
{ int flag=0;//用来记录分区序号
Node *p=first;
p->data.num=0;
p->data.address=0;
p->data.length=40;
p->data.state=1;
sort();
printf("\n\t\t》主存空间分配情况《\n");
printf("**********************************************************\n\n");
printf("分区序号\t起始地址\t分区大小\t分区状态\n\n");
while(p)
{
printf("%d\t\t%d\t\t%d",p->data.num,p->data.address,p->data.length);
if(p->data.state==0) printf("\t\t空闲\n\n");
else printf("\t\t已分配\n\n");
p=p->next;
}
printf("**********************************************************\n\n"); }
//首次适应算法
Status First_fit(int request)
{
//为申请作业开辟新空间且初始化
Node *p=first->next;
LinkList temp=(LinkList)malloc(sizeof(Node));
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while(p)
{
if((p->data.state==0)&&(p->data.length==request))
{//有大小恰好合适的空闲块
p->data.state=1;
return OK;
break;
}
else if((p->data.state==0) && (p->data.length>request))
{//有空闲块能满足需求且有剩余
temp->prior=p->prior;
temp->next=p;
temp->data.address=p->data.address;
temp->data.num=p->data.num;
p->prior->next=temp;
p->prior=temp;
p->data.address=temp->data.address+temp->data.length;
p->data.length-=request;
p->data.num+=1;
return OK;
break;
}
p=p->next;
}
return ERROR;
}
//最佳适应算法
Status Best_fit(int request)
{
int ch; //记录最小剩余空间
Node *p=first;
Node *q=NULL; //记录最佳插入位置
LinkList temp=(LinkList)malloc(sizeof(Node));
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while(p) //初始化最小空间和最佳位置
{
if((p->data.state==0) && (p->data.length>=request) )
{
if(q==NULL)
{
q=p;
ch=p->data.length-request;
}
else if(q->data.length > p->data.length)
{
q=p;
ch=p->data.length-request;
}
}
p=p->next;
}
if(q==NULL) return ERROR;//没有找到空闲块
else if(q->data.length==request)
{
q->data.state=1;
return OK;
}
else
{
temp->prior=q->prior;
temp->next=q;
temp->data.address=q->data.address;
temp->data.num=q->data.num;
q->prior->next=temp;
q->prior=temp;
q->data.address+=request;
q->data.length=ch;
q->data.num+=1;
return OK;
}
return OK;
}
//最差适应算法
Status Worst_fit(int request)
{
int ch; //记录最大剩余空间
Node *p=first->next;
Node *q=NULL; //记录最佳插入位置
LinkList temp=(LinkList)malloc(sizeof(Node));
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while(p) //初始化最大空间和最佳位置
{
if(p->data.state==0 && (p->data.length>=request) )
{
if(q==NULL)
{
q=p;
ch=p->data.length-request;
}
else if(q->data.length < p->data.length)
{
q=p;
ch=p->data.length-request;
}
}
p=p->next;
}
if(q==NULL) return ERROR;//没有找到空闲块
else if(q->data.length==request)
{
q->data.length=1;
return OK;
}
else
{
temp->prior=q->prior;
temp->next=q;
temp->data.address=q->data.address;
temp->data.num=q->data.num;
q->prior->next=temp;
q->prior=temp;
q->data.address+=request;
q->data.length=ch;
q->data.num+=1;
return OK;
}
return OK;
}
//分配主存
Status allocation(int a)
{
int request;//申请内存大小
printf("请输入申请分配的主存大小(单位:KB):");
scanf("%d",&request);
if(request<0 ||request==0)
{
printf("分配大小不合适，请重试！");
return ERROR;
}
switch(a)
{
case 1: //默认首次适应算法
if(First_fit(request)==OK) printf("\t****分配成功！****");
else printf("\t****内存不足，分配失败！****");
return OK;
break;
case 2: //选择最佳适应算法
if(Best_fit(request)==OK) printf("\t****分配成功！****");
else printf("\t****内存不足，分配失败！****");
return OK;
break;
case 3: //选择最差适应算法
if(Worst_fit(request)==OK) printf("\t****分配成功！****");
else printf("\t****内存不足，分配失败！****");
return OK;
break;
}
}
Status deal1(Node *p)//处理回收空间
{
Node *q=first;
for(;q!=NULL;q=q->next)
{
if(q==p)
{
if(q->prior->data.state==0&&q->next->data.state!=0)
{
q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=q->prior;
q->data.state=0;
q->data.num=flag-1;
}
if(q->prior->data.state!=0&&q->next->data.state==0)
{
q->data.length+=q->next->data.length;
q->next=q->next->next;
q->next->next->prior=q;
q->data.state=0;
q->data.num=flag;
}
if(q->prior->data.state==0&&q->next->data.state==0)
{
q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=q->prior;
q->data.state=0;
q->data.num=flag-1;
}
if(q->prior->data.state!=0&&q->next->data.state!=0)
{
q->data.state=0;
}
}
}
return OK;
}
Status deal2(Node *p)//处理回收空间
{
Node *q=first;
for(;q!=NULL;q=q->next)
{
if(q==p)
{
if(q->prior->data.state==0&&q->next->data.state!=0)
{
q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=p->prior;
q->data.state=0;
q->data.num=flag-1;
}
if(q->prior->data.state!=0&&q->next->data.state==0)
{
q->data.state=0;
}
if(q->prior->data.state==0&&q->next->data.state==0)
{
q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=q->prior;
q->data.state=0;
q->data.num=flag-1;
}
if(q->prior->data.state!=0&&q->next->data.state!=0)
{
q->data.state=0;
}
}
}
return OK;
}
//主存回收
Status recovery(int flag)
{
Node *p=first;
for(;p!=NULL;p=p->next)
{
if(p->data.num==flag)
{
if(p->prior==first)
{
if(p->next!=end)//当前P指向的下一个不是最后一个时
{
if(p->next->data.state==0) //与后面的空闲块相连
{
p->data.length+=p->next->data.length;
p->next->next->prior=p;
p->next=p->next->next;
p->data.state=0;
p->data.num=flag;
}
else p->data.state=0;
}
if(p->next==end)//当前P指向的下一个是最后一个时
{
p->data.state=0;
}
}//结束if(p->prior==block_first)的情况
else if(p->prior!=first)
{
if(p->next!=end)
{
deal1(p);
}
else
{
deal2(p);
}
}//结束if(p->prior!=block_first)的情况
}//结束if(p->data.num==flag)的情况
}
printf("\t****回收成功****");
return OK;
}
//主函数
void main()
{
int i; //操作选择标记
int a;//算法选择标记
printf("**********************************************************\n");
printf("\t\t用以下三种方法实现主存空间的分配\n");
printf("\t(1)首次适应算法\t(2)最佳适应算法\t(3)最差适应算法\n");
printf("**********************************************************\n");
printf("\n");
printf("请输入所使用的内存分配算法:");
scanf("%d",&a);
while(a<1||a>3)
{
printf("输入错误，请重新输入所使用的内存分配算法:\n");
scanf("%d",&a);
}
switch(a)
{
case 1:printf("\n\t****使用首次适应算法：****\n");break;
case 2:printf("\n\t****使用最佳适应算法：****\n");break;
case 3:printf("\n\t****使用最坏适应算法：****\n");break;
}
Initblock(); //开创空间表
while(1)
{
show();
printf("\t1: 分配内存\t2: 回收内存\t0: 退出\n");
printf("请输入您的操作：");
scanf("%d",&i);
if(i==1)
allocation(a); // 分配内存
else if(i==2) // 内存回收
{
printf("请输入您要释放的分区号：");
scanf("%d",&flag);
recovery(flag);
}
else if(i==0)
{
printf("\n退出程序\n");
break; //退出
}
else //输入操作有误
{
printf("输入有误，请重试！");
continue;
}
}
}
八、执行结果和结果分析
初始化首次适应算法：
当作业1、2、3顺利分配内存空间后：
回收序号2里面的内存：
分配作业4：
回收序号3里面的内存（与上邻序号2相连了）
回收序号1里的内存（与下邻序号2相连了）
继续分配（会发现总是按顺序查找满足要求的第一个空闲块，一旦发现就会分配）：
编译原理实验报告语法分析程序的设计
编译原理实验报告语法分析程序的设计 文档编制序号：[KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688]
实验5语法分析程序的设计（2） 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。 二、实验内容 设计一个文法的算法优先分析程序，判断特定表达式的正确性。 三、实验要求 1、给出文法如下： G[E] E->T|E+T; T->F|T*F; F->i|(E); +*()i + * ( ) i 21）直接存放，2）为优先关系建立优先函数，这里由学生自己选择一种方式； 1、给出算符优先分析算法如下： k:=1; S[k]:=‘#’; REPEAT 把下一个输入符号读进a中； IF S[k]∈V T THEN j:=k ELSE j:=k-1; WHILE S[j] a DO BEGIN
REPEAT Q:=S[j]; IF S[j-1]∈V T THEN j:=j-1 ELSE j:=j-2 UNTIL S[j] Q 把S[j+1]…S[k]归约为某个N； k:=j+1; S[k]:=N; END OF WHILE; IF S[j] a OR S[j] a THEN BEGIN k:=k+1;S[k]:=a END ELSE ERROR UNTIL a=‘#’ 1、根据给出算法，利用适当的数据结构实现算符优先分析程序； 2、利用算符优先分析程序完成下列功能： 1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束； 2）读入文本文件中的表达式； 3）调用实验2中的词法分析程序搜索单词； 4）把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息； 5）完成上述功能，有余力的同学可以对正确的表达式计算出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤
计算机操作系统内存分配实验报告记录
计算机操作系统内存分配实验报告记录
————————————————————————————————作者：————————————————————————————————日期：
一、实验目的 熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。 二、实验内容和要求 主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。 可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。 实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。 三、实验主要仪器设备和材料 实验环境 硬件环境：PC或兼容机 软件环境：VC++ 6.0 四、实验原理及设计分析 某系统采用可变分区存储管理，在系统运行当然开始，假设初始状态下，可用的内存空间为640KB，存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。 （作业1 申请130KB、作业2 申请60KB、作业3 申请100KB 、作业2 释放 60KB 、作业4 申请 200KB、作业3释放100KB、作业1 释放130KB 、作业5申请140KB 、作业6申请60KB 、作业7申请50KB） 当作业1进入内存后，分给作业1（130KB），随着作业1、2、3的进入，分别分配60KB、100KB，经过一段时间的运行后，作业2运行完毕，释放所占内存。此时，作业4进入系统，要求分配200KB内存。作业3、1运行完毕，释放所占内存。此时又有作业5申请140KB，作业6申请60KB，作业7申请50KB。为它们进行主存分配和回收。 1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。 空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1”。 设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使用空闲低端的空间。 设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明
存储管理实验报告
实验三、存储管理 一、实验目的： ? 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。 在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为虚拟存储器。通过本实验理解在分页式存储管理中怎样实现虚拟存储器。 在本实验中，通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。 二、实验题目： 设计一个可变式分区分配的存储管理方案。并模拟实现分区的分配和回收过程。 对分区的管理法可以是下面三种算法之一：（任选一种算法实现） 首次适应算法 循环首次适应算法 最佳适应算法 三．实验源程序文件名:cunchuguanli.c
执行文件名:cunchuguanli.exe 四、实验分析： 1)本实验采用可变分区管理，使用首次适应算法实现主存的分配和回收 1、可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并 且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。 为了说明那些分区是空闲的，可以用来装入新作业，必须有一张空闲说明表 ? 空闲区说明表格式如下：? 第一栏 第二栏 其中，起址——指出一个空闲区的主存起始地址，长度指出空闲区的大小。 长度——指出从起始地址开始的一个连续空闲的长度。 状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业完成后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。 2、当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。 有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分
操作系统实验内存分配
精心整理西安邮电大学 （计算机学院） 课内实验报告 1. （1 （2 （3 原因，写出实验报告。 2.实验要求： 1）掌握内存分配FF，BF，WF策略及实现的思路； 2）掌握内存回收过程及实现思路； 3）参考本程序思路，实现内存的申请、释放的管理程序，调试运行，总结程序设计中出现的问题并找出原因，写出实验报告。
3.实验过程： 创建进程： 删除其中几个进程：(默认以ff首次适应算法方式排列) Bf最佳适应算法排列方式： wf最差匹配算法排列方式： 4.实验心得： 明 实验中没有用到循环首次适应算法，但是对其他三种的描述还是很详细，总的来说，从实验中还是学到了很多。 5.程序源代码： #include
#define PROCESS_NAME_LEN 32 //进程名长度 #define MIN_SLICE 10 //最小碎片的大小#define DEFAULT_MEM_SIZE 1024 //内存大小 #define DEFAULT_MEM_START 0 //起始位置 /*内存分配算法*/ #define MA_FF 1 #define MA_BF 2 #define MA_WF 3 /*描述每一个空闲块的数据结构*/ struct free_block_type { }; /* /* { }; /* /* void display_menu(); int set_mem_size(); void set_algorithm(); void rearrange(int algorithm); int rearrange_WF(); int rearrange_BF(); int rearrange_FF(); int new_process(); int allocate_mem(struct allocated_block *ab);
操作系统实验之内存管理实验报告
学生学号 实验课成绩 武汉理工大学 学生实验报告书 实验课程名称 计算机操作系统 开 课 学 院 计算机科学与技术学院 指导老师姓名 学 生 姓 名 学生专业班级 2016 — 2017 学年第一学期
实验三 内存管理 一、设计目的、功能与要求 1、实验目的 掌握内存管理的相关内容，对内存的分配和回收有深入的理解。 2、实现功能 模拟实现内存管理机制 3、具体要求 任选一种计算机高级语言编程实现 选择一种内存管理方案：动态分区式、请求页式、段式、段页式等 能够输入给定的内存大小，进程的个数，每个进程所需内存空间的大小等 能够选择分配、回收操作 内购显示进程在内存的储存地址、大小等 显示每次完成内存分配或回收后内存空间的使用情况 二、问题描述 所谓分区，是把内存分为一些大小相等或不等的分区，除操作系统占用一个分区外，其余分区用来存放进程的程序和数据。本次实验中才用动态分区法，也就是在作业的处理过程中划分内存的区域，根据需要确定大小。 动态分区的分配算法：首先从可用表/自由链中找到一个足以容纳该作业的可用空白区，如果这个空白区比需求大，则将它分为两个部分，一部分成为已分配区，剩下部分仍为空白区。最后修改可用表或自由链，并回送一个所分配区的序号或该分区的起始地址。 最先适应法：按分区的起始地址的递增次序，从头查找，找到符合要求的第一个分区。
最佳适应法：按照分区大小的递增次序，查找，找到符合要求的第一个分区。 最坏适应法：按分区大小的递减次序，从头查找，找到符合要求的第一个分区。 三、数据结构及功能设计 1、数据结构 定义空闲分区结构体，用来保存内存中空闲分区的情况。其中size属性表示空闲分区的大小，start_addr表示空闲分区首地址，next指针指向下一个空闲分区。 //空闲分区 typedef struct Free_Block { int size; int start_addr; struct Free_Block *next; } Free_Block; Free_Block *free_block; 定义已分配的内存空间的结构体，用来保存已经被进程占用了内存空间的情况。其中pid作为该被分配分区的编号，用于在释放该内存空间时便于查找。size表示分区的大小，start_addr表示分区的起始地址，process_name存放进程名称，next指针指向下一个分区。 //已分配分区的结构体 typedef struct Allocate_Block { int pid; int size; int start_addr; char process_name[PROCESS_NAME_LEN]; struct Allocate_Block *next; } Allocate_Block; 2、模块说明 2.1 初始化模块 对内存空间进行初始化，初始情况内存空间为空，但是要设置内存的最大容量，该内存空间的首地址，以便之后新建进程的过程中使用。当空闲分区初始化
北京科技大学编译原理实验报告
编译原理实验报告 学院: 计算机与通信工程学院专业: 计算机科学与技术 班级: 学号: 姓名: 实验成绩：
词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ：= + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图：
3.2词法分析程序流程图： 四、词法分析程序的C++语言程序源代码： #include"stdio.h" #include"stdlib.h" #include"string.h" #define _KEY_WORD_END "waiting for your expanding" typedef struct 开始 变量初始化 是否文件结束？ 返回 拼数 Syn=11 返回 拼字符串 是否是关键字？ Syn 为对应关键字的单词种别码 Syn=10 给不同的符号相同的 Syn 值 报错 是 否 数字 字母 是 否 运算符, 界符等 其他
可变分区存储管理方式的内存分配和回收实验报告
一．实验目的 通过编写和调试存储管理的模拟程序以加深对存储管理方 案的理解，熟悉可变分区存储管理的内存分配和回收。 二．实验内容 1．确定内存空间分配表； 2．采用最优适应算法完成内存空间的分配和回收； 3．编写主函数对所做工作进行测试。 三．实验背景材料 实现可变分区的分配和回收，主要考虑的问题有三个：第一，设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计内存分配算法；第三，在设计的数据表格基础上设计内存回收算法。 首先，考虑第一个问题，设计记录内存使用情况的数据表格，用来记录空间区和作业占用的区域。 由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写己分
配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。 “已分分区表”的结构定义 #definen10//假定系统允许的最大作业数量为n struct {floataddress;//已分分区起始地址 floatlength;//已分分区长度、单位为字节 intflag;//已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名 }used_table[n];//已分分区表 “空闲区表”的结构定义 #definem10//假定系统允许的空闲区最大为m struct {floataddress;//空闲区起始地址
编译原理实验报告二
编译原理实验报告 题目构造识别字符串的自动机学院 专业 班级 学号 学生姓名 指导教师 西安思源学院教务处制 二〇一年
实验二构造识别符号串的自动机 一、实验目的 1 掌握形式语言与自动机的概念 2 了解正规集及有穷自动机的关系 3 能构造识别相应符号串的自动机 4 能构造词法分析程序所识别的各类单词的自动机 二、实验环境 Microsoft Visual C++ 6.0 三、实验内容 1 用高级语言编写程序：该程序能接受C++所有的标识符。 2 用高级语言编写程序：该程序能接受C++所有的常数(整数和定点小数)。 3 用高级语言编写程序：该程序能接受C++的所有保留字。 4 用高级语言编写程序：该程序能接受C++的所有界符、运算符。 四、设计说明 void main() { void find_word(); void show_all(); void Input(); Input(); cout<<"运行结果如下"<
编译原理词法分析实验报告
词法分析器实验报告 一、实验目的 选择一种编程语言实现简单的词法分析程序，设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 各种单词符号对应的种别码： 表各种单词符号对应的种别码 词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根
据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn 用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。
计算机操作系统内存分配实验报告
一、实验目的 熟悉主存的分配与回收。理解在不同的存储管理方式下.如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。 二、实验内容和要求 主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配.就是解决多道作业或多进程如何共享主存空间的问题。所谓回收.就是当作业运行完成时将作业或进程所占的主存空间归还给系统。 可变分区管理是指在处理作业过程中建立分区.使分区大小正好适合作业的需求.并且分区个数是可以调整的。当要装入一个作业时.根据作业需要的主存量查看是否有足够的空闲空间.若有.则按需要量分割一个分区分配给该作业；若无.则作业不能装入.作业等待。随着作业的装入、完成.主存空间被分成许多大大小小的分区.有的分区被作业占用.而有的分区是空闲的。 实验要求使用可变分区存储管理方式.分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行.分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时.要求设计一个实用友好的用户界面.并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。 三、实验主要仪器设备和材料 实验环境 硬件环境：PC或兼容机 软件环境：VC++ 6.0 四、实验原理及设计分析 某系统采用可变分区存储管理.在系统运行当然开始.假设初始状态下.可用的内存空间为640KB.存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。 （作业1 申请130KB、作业2 申请60KB、作业3 申请100KB 、作业2 释放 60KB 、作业4 申请 200KB、作业3释放100KB、作业1 释放130KB 、作业5申请140KB 、作业6申请60KB 、作业7申请50KB） 当作业1进入内存后.分给作业1（130KB）.随着作业1、2、3的进入.分别分配60KB、100KB.经过一段时间的运行后.作业2运行完毕.释放所占内存。此时.作业4进入系统.要求分配200KB内存。作业3、1运行完毕.释放所占内存。此时又有作业5申请140KB.作业6申请60KB.作业7申请50KB。为它们进行主存分配和回收。 1、采用可变分区存储管理.使用空闲分区链实现主存分配和回收。 空闲分区链：使用链指针把所有的空闲分区链成一条链.为了实现对空闲分区的分配和链接.在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针.由状态位指示该分区是否分配出去了；同时.在分区尾部还设置有一后向指针.用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间.当该分区分配出去后.状态位就由“0”置为“1”。 设置一个内存空闲分区链.内存空间分区通过空闲分区链来管理.在进行内存分配时.系统优先使用空闲低端的空间。 设计一个空闲分区说明链.设计一个某时刻主存空间占用情况表.作为主存当前使用基础。初始化空间区和已分配区说明链的值.设计作业申请队列以及作业完成后释放顺序.实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明链的变化情况以及各作业的申请、释放情况显示打印出来。
编译原理实验报告总结
学年第学期《编译原理》实验报告 学院（系）：计算机科学与工程学院 班级：11303070A 学号：11303070*** 姓名：无名氏 指导教师：保密式 时间：2016 年7 月
目录 1．实验目的 (1) 2．实验内容及要求 (1) 3．实验方案设计 (1) 3.1 编译系统原理介绍 (1) 3.1.1 编译程序介绍 (2) 3.1.2 对所写编译程序的源语言的描述 (2) 3.2 词法分析程序的设计 (3) 3.3 语法分析程序设计 (4) 3.4 语义分析和中间代码生成程序的设计 (4) 4. 结果及测试分析 (4) 4.1软件运行环境及限制 (4) 4.2测试数据说明 (5) 4.3运行结果及功能说明 (5) 5．总结及心得体会 (7)
1．实验目的 根据Sample语言或者自定义的某种语言，设计该语言的编译前端。包括词法分析，语法分析、语义分析及中间代码生成部分。 2．实验内容及要求 （1）词法分析器 输入源程序，输出对应的token表，符号表和词法错误信息。按规则拼单词，并转换成二元形式；滤掉空白符，跳过注释、换行符及一些无用的符号；进行行列计数，用于指出出错的行列号，并复制出错部分；列表打印源程序；发现并定位词法错误； （2）语法分析器 输入token串，通过语法分析，寻找其中的语法错误。要求能实现Sample 语言或自定义语言中几种最常见的、基本的语法单位的分析：算术表达式、布尔表达式、赋值语句、if语句、for语句、while语句、do while语句等。 （3）语义分析和中间代码生成 输入token串，进行语义分析，修改符号表，寻找其中的语义错误，并生 成中间代码。要求能实现Sample语言或自定义语言中几种最常见的、基本的语法单位的分析：算术表达式、布尔表达式、赋值语句、if语句、for语句、while 语句、do while语句等。 实验要求：功能相对完善，有输入、输出描述，有测试数据，并介绍不足。3．实验方案设计 3.1 编译系统原理介绍 编译器逐行扫描高级语言程序源程序，编译的过程如下： (1).词法分析 识别关键字、字面量、标识符(变量名、数据名)、运算符、注释行(给人看的，一般不处理)、特殊符号(续行、语句结束、数组)等六类符号，分别归类等待处理。 (2).语法分析 一个语句看作一串记号(Token)流，由语法分析器进行处理。按照语言的文法检查判定是否是合乎语法的句子。如果是合法句子就以内部格式保存，否则报错。直至检查完整个程序。 (3).语义分析 语义分析器对各句子的语法做检查：运算符两边类型是否相兼容；该做哪些类型转换(例如，实数向整数赋值要"取整")；控制转移是否到不该去的地方；是
内存管理实验报告
内存管理实验报告
信息科学与技术学院实验报告 课程名称: 实验项目: 实验地点:指导教师: 日期: 实验类型:（验证性实验综合性实验设计性实验） 专业: 计算机外包班级: 14外三姓名: 周鹏飞学号: 1414104033 一、实验目的及要求 通过此次实验，加深对内存管理的认识，进一步掌握内存的分配，回收算法的思想。 二、实验仪器、设备或软件 Windows操作系统PC一台；VC++6.0 三、实验内容及原理 原理：设计程序模拟内存的动态分区内存管理方法。内存空闲区使用空闲分区表进行管理，采用最先适应算法从空闲分区表中寻找空闲区进行分配，内存回收时不考虑与相邻空闲分区的合并。 假定系统的内存共640k,初始状态为操作系统本身占用40k.t1时刻，为作业A,B,C分配80k,60k,100k的内存空间；t2时刻作业B完成；t3时刻为作业D分配50k的内存空间；t4时刻作业C，A完成；t5时刻作业D完成。要求编程序分别输出t1,t2,t3,t4,t5时刻内存的空闲区的状态。 实验内容： #include
#define size 10 //不再切割剩余分区的大小 typedef struct PCB_type { char name;//进程名 int address;//进程所占分区首地址 int len;//进程所占分区的长度 int valid;//PCB标识符（有效，无效） }PCB； Typedef struct seqlist //进程信息队列 { PCB PCBelem[maxPCB];// maxPCB为为系统中允许的最多进程数 int total; //系统中实际的进程数 }PCBseql;//分区类型的描述 typedef struct Partition { int address;//分区起址 int len;//分区的长度 int valid;//有标识符（有效，无效） }Part;//内存空闲分区表（顺序表）描述 typedef struct Partlist //空白分区链 ｛ Part Partelem[maxPart];//maxPart为系统中可能的最多空闲分区数 int sum;//系统中世纪的分区数 ｝Partseql;//全局变量 PCBseql *pcbl;//进程队列指针 Partseql *part1；//空闲队列指针 #intclude “MainManager.h” void initpcb() //初始化进程表vpcb1 { int i; pcb1->PCBelem[0].address=0; pcb1->PCBelem[0].len=0; pcb1->PCBelem[0].name=’s’; pcb1->PCBelem[0].valid=1; pcb1->total=0; for(i=1;i 武汉理工大学 学生实验报告书 实验课程名称编译原理课程实验 开课学院计算机科学与技术学院指导老师姓名饶文碧 学生姓名徐强国 学生专业班级软件 1602 2018 —2019 学年第1 学期 实验课程名称：编译原理 依次输入关键字，自定义标识符 BBBJKJL KJKJ4234，整数 3432，特 殊符号和其他符号:. {} []。 二、实验结果及分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）输出为: 三、实验小结、建议及体会 通过这次的词法分析实验，我遇到了不少问题。对于输入字符串的直接处理，首先是分类情况的不完整（起初忽略了对关键字的判断），造成输出结果与预想有很大偏差。总结下:作为编译的第一步，词法分析将高级语言一步步分解，然后转化为自己的语言,这是一个严谨有十分有趣的过程。 核心代码: struct word //存储关键字，特殊符号 { int code; char T[max]; }; word important[5]; //结构体变量存储关键字 word num; //结构体变量存储数字 word identifier; //结构体变量存储标识符 word special_symbol[7]; //结构体变量存储特殊符号 int function(word* a, word b, word c, word* d, char* input, int k) { char getword[max]; int j = 0; if (input[j] == ' ') // 判断空格 { k = k + j + 1; function(a, b, c, d, input + j + 1, k); } else if (input[j] == '=' || input[j] == '+' || input[j] == ',' || input[j] == '(' || input[j] == ')') //判断特殊符号 { if (input[j] == '*') { getword[j] = input[j]; j = j + 1; if (input[j] == '*') { } else { } else { } getword[j] = input[j]; cout << '(' << d[3].code << ',' << d[3].T << ')' << endl; j = j - 1; cout << '(' << d[2].code << ',' << d[2].T << ')' << endl; getword[j] = input[j]; for (int i = 0; i < 7; i++) { if (i == 3) continue; 一．实验名称 模拟实现动态分区存储管理 二．实验要求 编写程序实现动态分区存储管理方式的主存分配与回收。具体内容包括：先确定主存空间分配表；然后采用最优适应算法完成主存空间的分配与回收；最后编写主函数对所做工作进行测试。 三．解决方案 实现动态分区的分配与回收，主要考虑两个问题：第一，设计记录主存使用情况的数据结构，用来记录空闲区和作业占用的区域；第二，在该数据结构基础上设计主存分配算法和主存回收算法。 由于动态分区的大小是由作业需求量决定的，故分区的长度预先不能固定，且分区的个数也随主存分配和回收变动。总之，所有分区的情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主存中的起始地址和长度。由于分配时，空闲区有时会变成两个分区（空闲区和已分配区），回收主存分区时，可能会合并空闲区，这样如果整个主存采用一张表格记录已分配区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分配，然后填写已分配区表，主要操作在空闲区。由此可见，主存的分配与回收主要是对空闲区的操作。这样为了便于对主存空间的分配与回收，可建立两张分区表记录主存使用情况：“已分配区表”记录作业占用分区，“空闲区表”记录空闲区。 然后在数据结构上进行主存的分配，其主存分配算法采用最优适应算法，即按祖业要求挑选一个能满足作业要求的最小空闲区分配。具体实现时，把空闲区按长度以某种方式（递增方式）登记在“空闲区表”中，分配时顺序查找“空闲区表”，查到的第一个空闲区就是满足作业要求的最小分区。在实现回收时，先在“已分配区表”中找到将作业归还的区域，且变为空，检查“空闲区”表中未分配区域，查找是否有相邻空闲区，最后合并空闲区，修改“空闲区表”。设计程序时可选择进行主存分配或主存回收，所需参数为：若是主存分配。输入作业名和所需主存空间大小；若是回收，输入回收作业的作业名，以循环进行主存分配和回收。 四．实验代码 #include 《编译原理》实验报告软件131 陈万全132852 一、需求分析 通过对一个常用高级程序设计语言的简单语言子集编译系统中词法分析、语法分析、语义处理模块的设计、开发，掌握实际编译系统的核心结构、工作流程及其实现技术，获得分析、设计、实现编译程序等方面的实际操作能力，增强设计、编写和调试程序的能力。 通过开源编译器分析、编译过程可视化等扩展实验，促进学生增强复杂系统分析、设计和实现能力，鼓励学生创新意识和能力。 1、词法分析程序设计与实现 假定一种高级程序设计语言中的单词主要包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序。 输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。 输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将结果放到某个文件中。对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；VALUE字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的CLASS字段上放置相应单词的类别码的助记符，VALUE字段则为“空”。 2、语法分析程序设计与实现 选择对各种常见高级程序设计语言都较为通用的语法结构——算术表达式的 一个简化子集——作为分析对象，根据如下描述其语法结构的BNF定义G2[<算术表达式>]，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。 G2[<算术表达式>]： <算术表达式>→<项> | <算术表达式>+<项> | <算术表达式>-<项> <项>→<因式>|<项>*<因式>|<项>/<因式> <因式>→<运算对象> | (<算术表达式>) 若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F和i 代表，则G2可写成： G2[E]：E → T | E+T | E-T T → F | T*F | T/F F → i | (E) 输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID······输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。 3、语义分析程序设计与实现 对文法G2[<算术表达式>]中的产生式添加语义处理子程序，完成运算对象是简单变量（标识符）和无符号数的四则运算的计值处理，将输入的四则运算转换为四元式形式的中间代码。 输入：包含测试用例（由标识符、无符号数和+、?、*、/、(、)构成的算术表达式）的源程序文件。 输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。 若源程序中有错误，应指出错误信息 二、设计思路 1、词法分析程序设计与实现 1)单词分类 为了编程的实现。我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。 主存空间的分配与回收实验报告 实验报告 课程名称：操作系统 实验名称：主存空间的分配与回收学号： 110310014 学生姓名：于钊 班级：信管1101班 指导教师：吴联世 实验日期： 2013 年12月5日 3、采用最先适应算法（顺序分配算法）分配主存空间。 按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。 由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。 4、当一个作业执行完成撤离时，作业所占的分区应该归还给系统，归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在上述中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。 2）程序结构（流程图） 首次适应分配模拟算法 主存回收算法 3）实现步骤 实现动态分区的分配与回收，主要考虑三个问题：第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法；第三，在设计的数据表格基础上设计主存回收算法。 1．设计记录主存使用情况的数据表格 由于动态分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主存中的起始地址和长度。由于分配时，空闲区有时会变成两个分区：空闲区和已分分区，回收主存分区时，可能会合并空闲区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分配，然后填写已分配区表，主要操作在空闲区；某个作业执行完后，将该分区贬词空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，主存的分配与回收主要时对空闲区的操作。这样为了便于对主存空间的分配与回收，就建立两张分区表记录主存的使用情况：“已分配区表”记录作业占用分区，“空闲区表”记录空闲区。 这两张表的实现方法一般由两种：链表形式、顺序表形式。在本实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分配区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因此在多数情况下，无论是“已分配表区”还是“空闲区表”都是空闲栏目。已分配区表中除了分区起始地址、长度武汉理工大学编译原理实验报告
内存最佳分配实验报告
编译原理实验报告
主存空间的分配与回收实验报告