编译原理实验报告(设计和验证型).doc

课 程 实 验 报 告

专 业 年 级 计算机科学与技术
课 程 名 称 编 译 原 理
指 导 教 师
学 生 姓 名
学 号
实 验 日 期

实 验 地 点
实 验 成 绩

教务处制
2010年 月 日
实验报告
专业班级

姓名

学号

课程名称
编译原理
实验名称
一个顺序栈的基本运算实验
实验编号
实验一
实验形式
设计性
实验类型
认识与验证型
实验学时
2学时
[实验目的]
1．了解掌握栈的相关知识。
2．学习并使用栈，并能建立栈。
[实验要求]
1. 建立一个字符栈。
2. 所建栈有进栈、出栈、初始化栈、判断栈空、判断栈满、清栈和取栈顶元素这几个函数。
[实验内容]
建立一个字符栈，并有相应的配套函数。把字符串uwdweoqei#入栈并输出。
[实验步骤]
#define wyo char
typedef struct{
wyo data[50];
int top;
}stack;
void InitStack(stack *s)//栈初始化
{
s->top=-1;
}
int StackEmpty(stack *s)//判栈空,空为
{
if(s->top==-1)
return 1;
else
return 0;
}
int StackFull(stack *s)//判栈满,满为
{
if(s->top==50)
return 1;
else
return 0;
}
void ClearStack(stack *s)//清栈
{
s->top=-1;
}
void Push(stack *s,wyo e)//入栈
{
if(!StackFull(s))
s->data[++s->top]=e;
else
cout<<"栈满不能入栈。";
}
wyo Pop(stack *s)//出栈
{
if(!StackEmpty(s))
return s->data[s->top--];
else
{
cout<<"栈空不能出栈。";
return -1;
}
}
wyo Seqtop(stack *s)//取栈顶元素
{
if(!StackEmpty(s))
return s->data[s->top];
else
{
cout<<"栈空不能出栈。";
return -1;
}
}
void main()
{
stack x;
char y=NULL;
InitStack(&x);
cout<<"输入进栈字符串,以#号结束:";
while(y!='#')
{
cin>>y;
Push(&x,y);
}
cout<<endl<<"输出栈内字符串:";
while(StackEmpty(&x)!=1)
cout<<Pop(&x);
Pop(&x);
}
[实验结果与分析]

栈是按先来后出的原理，所以当输入栈内元素时的顺序进输入栈时的顺序相反。而且当栈满时不能在把元素放入栈内，当栈空时也不可能有出栈操作。
[教师评语]

成绩评定：

指导教师签名：

实验报告
专业班级

姓名

学号

课程名称
编译原理
实验名称
一个优先关系矩阵（或算符优先关系表）
实验编号
实验二
实验形式
设计性
实验类型
认识与验证型
实验学时
2学时
[实验目的]
1.掌握LL(1)方法的定义.
2.学会求FIRST和FOLLOW集合.
3.学会建立预测分析表.
[实验要求]
设计一段程序验证一个字符串是否合法.
[实验内容]
LL（1）文法:A->BD,D->FD,D->ε,F->+B,F->-B,B->CE,E->GE,E->ε,G>*C,G->/C,C->(A),C->i
分别验证字符串i+(i-i*i)/i-i和i+(i-i*i)/ii是否合法.
[实验步骤]
#define wyo char
typedef struct{
wyo data[50];
int top;
}stack;
void InitStack(stack *s)//栈初始化
{
s->top=-1;
}
int StackEmpty(stack *s)//判栈空,空为
{
if(s->top==-1)
return 1;
else
return 0;
}
int StackFull(stack *s)//判栈满,满为
{
if(s->top==50)
return 1;
else
return 0;
}
void ClearStack(stack *s)//清栈
{
s->top=-1;
}
void Push(stack *s,wyo e)//入栈
{
if(!StackFull(s))
s->data[++s->top]=e;
else
cout<<"栈满不能入栈。";
}
wyo Pop(stack *s)//出栈
{
if(!StackEmpty(s))
return s->data[s->top--];
else
{
cout<<"栈空不能出栈。";
return -1;
}
}
wyo Seqtop(stack *s)//取栈顶元素
{
if(!StackEmpty(s))
return s->data[s->top];
else
{
cout<<"栈空不能出栈。";
return -1;
}
}
int cha(char x)
{
switch(x)
{
case '+':return 0;
case '-':return 1;
case '*':return 2;
case '/':return 3;
case '(':return 4;
case ')':return 5;
case 'i':return 6;
case '#':return 7;
default:return -1;
}
}
int yan(stack n)//验证输入的字符串是否正确
{
char A[8][3]={{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{'B','D',NULL}, {NULL,NULL,NULL},{'B','D',NULL}, {NULL,NULL,NULL}},
B[8][3]={{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{'C','E',NULL}, {NULL,NULL,NULL},{'C','E',NULL}, {NULL,NULL,NULL}},
C[8][3]={{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{'(','A',')'}, {NULL,NULL,NULL},{'i',NULL,NULL}, {NULL,NULL,NULL}},
D[8][3]={{'F','D',NULL}, {'F','D',NULL}, {NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{'@',NULL,NULL}, {NULL,NULL,NULL},{'@',NULL,NULL}},
E[8][3]={{'@',NULL,NULL}, {'@',NULL,NULL}, {'G','E',NULL}, {'G','E',NULL}, {NULL,NULL,NULL},{'@',NULL,NULL}, {NULL,NULL,NULL},{'@',NULL,NULL}},
F[8][3]={{'+','B',NULL}, {'-','B',NULL}, {NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL}},
G[8][3]={{NULL,NULL,NULL},{NULL,NULL,NULL},{'*','C',NULL}, {'/','C',NULL}, {NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL}},
X,x;
stack N;
InitStack(&N);
Push(&N,'#');
Push(&N,'A');
while(true)
{
X=Seqtop(&N);
x=Seqtop(&n);
if(x>='0'&&x<='9')
x='i';
if(cha(X)>-1&&cha(X)<7)
if(X==x)
{Pop(&N);Pop(&n);}
else
{cout<<"匹配不成功"<<endl;return 0;}
else
if(X=='#')
if(x=='#')
{cout<<"匹配成功"<<endl;return 1;}
else
{cout<<"匹配不成功"<<endl;return 0;}
else
{
char Y[8][3];
int y;
if(x>='0'&&x<='9')
y=cha('i');
else
y=cha(x);
switch(X)
{
case 'A':for(int i=0;i<3;i++)
Y[y][i]=A[y][i];
break;
case 'B':for(int i=0;i<3;i++)
Y[y][i]=B[y][i];
break;
case 'C':for(int i=0;i<3;i++)
Y[y][i]=C[y][i];
break;
case 'D':for(int i=0;i<3;i++)
Y[y][i]=D[y][i];
break;
case 'E':for(int i=0;i<3;i++)
Y[y][i]=E[y][i];
break;
case 'F':for(int i=0;i<3;i++)
Y[y][i]=F[y][i];
break;
case 'G':for(int i=0;i<3;i++)
Y[y][i]=G[y][i];
break;
}
if(Y[y][0]!=NULL)
{
if(Y[y][0]=='@')
Pop(&N);
else
{
Pop(&N);
if(Y[y][2]!=NULL)Push(&N,Y[y][2]);
if(Y[y][1]!=NULL)Push(&N,Y[y][1]);
if(Y[y][0]!=NULL)Push(&N,Y[y][0]);
}
}
else
{cout<<"匹配不成功"<<endl;return 0;}
}
}
}
void main()
{
stack x,z;
char y=NULL;
InitStack(&x);
InitStack(&z);
cout<<"输入需要验证的字符串,以#号结束:"<<endl;
while(y!='#')
{
cin>>y;
Push(&x,y);
}
while(StackEmpty(&x)!=1)
Push(&z,Pop(&x));
yan(z);
}
[实验结果与分析]

[教师评语]

成绩评定：

指导教师签名：

实验报告
专业班级

姓名

学号

课程名称
编译原理
实验名称
中缀表达式转换为后缀表达式
实验编号
实验三
实验形式
设计性
实验类型
认识与验证型
实验学时
2学时
[实验目的]
1．掌握并了解什么是中缀表达式，什么是后缀表达式。
2．学会如何把中缀表达式转换为后缀表达式。
[实验要求]
在实验一的基础上，设计一个函数，此函数的功能是把中缀表达式转换为后缀表达式。
[实验内容]
输入字符串k+k-k+(k*k+k-k)/k-k,输出这个字符串的后缀表达式。
[实验步骤]
#define wyo char
char M[50];
int m(0);
typedef struct{
wyo data[50];
int top;
}stack;
void InitStack(stack *s)//栈初始化
{
s->top=-1;
}
int StackEmpty(stack *s)//判栈空,空为
{
if(s->top==-1)
return 1;
else
return 0;
}
int StackFull(stack *s)//判栈满,满为
{
if(s->top==50)
return 1;
else
return 0;
}
void ClearStack(stack *s)//清栈
{
s->top=-1;
}
void Push(stack *s,wyo e)//入栈
{
if(!StackFull(s))
s->data[++s->top]=e;
else
cout<<"栈满不能入栈。";
}
wyo Pop(stack *s)//出栈
{
if(!StackEmpty(s))
return s->data[s->top--];
else
{
cout<<"栈空不能出栈。";
return -1;
}
}
wyo Seqtop(stack *s)//取栈顶元素
{
if(!StackEmpty(s))
return s->data[s->top];
else
{
cout<<"栈空不能出栈。";
return -1;
}
}
int you(char ch)//确定运算符优先级
{
switch(ch)
{
case '(':return 0;
case '+':
case '-':return 1;
case '/':
case '*':return 2;
case ')':return 3;
default:return -1;
}
}
void li()//中缀表达示转换为后缀表达示
{
stack x,y;
InitStack(&x);
InitStack(&y);
char z=NULL;
cout<<"输入中缀表达式，以#号结束："<<endl;
while(z!='#')
{
cin>>z;
Push(&x,z);
}
while(StackEmpty(&x)!=1)
Push(&y,Pop(&x));
while(Seqtop(&y)!='#')
{
if(you(Seqtop(&y))==-1)//y栈顶为数字时，把y出栈入M队列
{
M[m++]=Pop(&y);
continue;
}
if(you(Seqtop(&y))==0)//y栈顶为（时，把y出栈入X栈
{
Push(&x,Pop(&y));
continue;
}
if(you(Seqtop(&y))==3)//y栈顶为）时，把y出栈，把x栈里（后的符号都入M队列，在把（出栈
{
Pop(&y);
while(you(Seqtop(&x))!=0)
M[m++]=Pop(&x);
Pop(&x);
continue;
}
if(you(Seqtop(&y))==2||you(Seqtop(&y))==1)//当x为空时把y栈顶入x栈。如x不为空，y栈顶的优先级小于等于x栈顶优先级时把x栈顶入M队列直到y>x,最后把y入x
{
if(StackEmpty(&x)==1)
Push(&x,Pop(&y));
else
{
while(you(Seqtop(&y))<=you(Seqtop(&x)))
{
M[m++]=Pop(&x);
if(StackEmpty(&x)==1)
break;
}
Push(&x,Pop(&y));
}
continue;
}
}
while(StackEmpty(&x)!=1)//把X余下的元素入M队列
M[m++]=Pop(&x);
cout<<"后缀表达式为：";
for(int i=0;i<=m;i++)//输出后缀表达式
cout<<M[i];
cout<<endl;
}
void main()
{
li();
}
[实验结果与分析]

中缀表达式的运算符在两个操作数中间，后缀表达式的运算符在两个操作数之后。而且后缀表达式中不会出现左右括号。
[教师评语]

成绩评定：

指导教师签名：

实验报告
专业班级

姓名

学号

课程名称
编译原理
实验名称
后缀表达式计算实验（根据预测分析表或算符优先关系表的分析方法和程序）
实验编号
实验四
实验形式
设计性
实验类型
认识与验证型
实验学时
2学时
[实验目的]
掌握并运用后缀表达式计算简单的数学运算.
[实验要求]
设计一段程序实现简单的数学运算.算式里要有(、)、+、-、*、/。（注：计算是数字和中间结果是一位数。）
[实验内容]
LL（1）文法:A->BD,D->FD,D->ε,F->+B,F->-B,B->CE,E->GE,E->ε,G>*C,G->/C,C->(A),C->i
2+(8-2*2)/4-1
[实验步骤]
#define wyo char
char M[50];
int m(0);
typedef struct{
wyo data[50];
int top;
}stack;
void InitStack(stack *s)//栈初始化
{s->top=-1;}
int StackEmpty(stack *s)//判栈空,空为
{
if(s->top==-1)
return 1;
else
return 0;
}
int StackFull(stack *s)//判栈满,满为
{if(s->top==50)
return 1;
else
return 0;}
void ClearStack(stack *s)//清栈
{s->top=-1;}
void Push(stack *s,wyo e)//入栈
{
if(!StackFull(s))
s->data[++s->top]=e;
else
cout<<"栈满不能入栈。";
}
wyo Pop(stack *s)//出栈
{
if(!StackEmpty(s))
return s->data[s->top--];
else
{
cout<<"栈空不能出栈。";
return -1;
}
}
wyo Seqtop(stack *s)//取栈顶元素
{
if(!StackEmpty(s))
return s->data[s->top];
else
{
cout<<"栈空不能出栈。";
return -1;
}
}
int cha(char x)
{
switch(x)
{
case '+':return 0;
case '-':return 1;
case '*':return 2;
case '/':return 3;
case '(':return 4;
case ')':return 5;
case 'i':return 6;
case '#':return 7;
default:return -1;
}
}
int yan(stack n)//验证输入的字符串是否正确
{
char A[8][3]={{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{'B','D',NULL}, {NULL,NULL,NULL},{'B','D',NULL}, {NULL,NULL,NULL}},
B[8][3]={{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{'C','E',NULL}, {NULL,NULL,NULL},{'C','E',NULL}, {NULL,NULL,NULL}},
C[8][3]={{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{'(','A',')'}, {NULL,NULL,NULL},{'i',NULL,NULL}, {NULL,NULL,NULL}},
D[8][3]={{'F','D',NULL}, {'F','D',NULL}, {NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{'@',NULL,NULL}, {NULL,NULL,NULL},{'@',NULL,NULL}},
E[8][3]={{'@',NULL,NULL}, {'@',NULL,NULL}, {'G','E',NULL}, {'G','E',NULL}, {NULL,NULL,NULL},{'@',NULL,NULL}, {NULL,NULL,NULL},{'@',NULL,NULL}},
F[8][3]={{'+','B',NULL}, {'-','B',NULL}, {NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL}},
G[8][3]={{NULL,NULL,NULL},{NULL,NULL,NULL},{'*','C',NULL}, {'/','C',NULL}, {NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL},{NULL,NULL,NULL}},
X,x;
stack N;
InitStack(&N);
Push(&N,'#');
Push(&N,'A');
while(true)
{
X=Seqtop(&N);
x=Seqtop(&n);
if(x>='0'&&x<='9')
x='i';
if(cha(X)>-1&&cha(X)<7)
if(X==x)
{Pop(&N);Pop(&n);}
else
{cout<<"匹配不成功"<<endl;return 0;}
else
if(X=='#')
if(x=='#')
{cout<<"匹配成功"<<endl;return 1;}
else
{cout<<"匹配不成功"<<endl;return 0;}
else
{
char Y[8][3];
int y;
if(x>='0'&&x<='9')
y=cha('i');
else
y=cha(x);
switch(X)
{
case 'A':for(int i=0;i<3;i++)
Y[y][i]=A[y][i];
break;
case 'B':for(int i=0;i<3;i++)
Y[y][i]=B[y][i];
break;
case 'C':for(int i=0;i<3;i++)
Y[y][i]=C[y][i];
break;
case 'D':for(int i=0;i<3;i++)
Y[y][i]=D[y][i];
break;
case 'E':for(int i=0;i<3;i++)
Y[y][i]=E[y][i];
break;
case 'F':for(int i=0;i<3;i++)
Y[y][i]=F[y][i];
break;
case 'G':for(int i=0;i<3;i++)
Y[y][i]=G[y][i];
break;
}
if(Y[y][0]!=NULL)
{
if(Y[y][0]=='@')
Pop(&N);
else
{
Pop(&N);
if(Y[y][2]!=NULL)Push(&N,Y[y][2]);
if(Y[y][1]!=NULL)Push(&N,Y[y][1]);
if(Y[y][0]!=NULL)Push(&N,Y[y][0]);
}
}
else
{cout<<"匹配不成功"<<endl;return 0;}
}
}
}
void jisuan()
{
int x,y,i,n=0,ans[50];
for(int i=0;i<m;i++)
if(M[i]<='9'&&M[i]>='0')
ans[n++]=M[i]-'0';
else
switch(M[i])
{
case '+':x=ans[--n];y=ans[--n];ans[n++]=y+x;break;
case '-':x=ans[--n];y=ans[--n];ans[n++]=y-x;break;
case '*':x=ans[--n];y=ans[--n];ans[n++]=y*x;break;
case '/':x=ans[--n];y=ans[--n];ans[n++]=y/x;break;
}
cout<<"计算结果为："<<ans[--n]<<endl;
}
int you(char ch)//确定运算符优先级
{
switch(ch)
{
case '(':return 0;
case '+':
case '-':return 1;
case '/':
case '*':return 2;
case ')':return 3;
default:return -1;
}
}
void li()//中缀表达示转换为后缀表达示
{
stack x,y;
InitStack(&x);
InitStack(&y);
char z=NULL;
cout<<"输入中缀表达式，以#号结束："<<endl;
while(z!='#')
{
cin>>z;
Push(&x,z);
}
while(StackEmpty(&x)!=1)
Push(&y,Pop(&x));
if(yan(y)==1)
{
while(Seqtop(&y)!='#')
{
if(you(Seqtop(&y))==-1)//y栈顶为数字时，把y出栈入M队列
{
M[m++]=Pop(&y);
continue;
}
if(you(Seqtop(&y))==0)//y栈顶为（时，把y出栈入X栈
{
Push(&x,Pop(&y));
continue;
}
if(you(Seqtop(&y))==3)//y栈顶为）时，把y出栈，把x栈里（后的符号都入M队列，在把（出栈
{
Pop(&y);
while(you(Seqtop(&x))!=0)
M[m++]=Pop(&x);
Pop(&x);
continue;
}
if(you(Seqtop(&y))==2||you(Seqtop(&y))==1)//当x为空时把y栈顶入x栈。如x不为空，y栈顶的优先级小于等于x栈顶优先级时把x栈顶入M队列直到y>x,最后把y入x
{
if(StackEmpty(&x)==1)
Push(&x,Pop(&y));
else
{
while(you(Seqtop(&y))<=you(Seqtop(&x)))
{
M[m++]=Pop(&x);
if(StackEmpty(&x)==1)
break;
}
Push(&x,Pop(&y));
}
continue;
}
}
while(StackEmpty(&x)!=1)//把X余下的元素入M队列
M[m++]=Pop(&x);
cout<<"后缀表达式为：";
for(int i=0;i<=m;i++)//输出后缀表达式
cout<<M[i];
cout<<endl;
jisuan();
}
}
void main()
{
li();
}
[实验结果与分析]

[教师评语]

成绩评定：

指导教师签名：