算符优先文法.doc

实 验 报 告
实验名称
算符优先文法
专 业
计算机科学与技术
课程名称
编译原理
指导老师
赵智超
班 级
计算机一班
姓 名
夏红涛
学 号
12103140102
评 分

实验地点
1C26217
实验日期
2014-05-27
一、实验目的
1．设计、编制并调试一个算符优先分析算法，加深对此分析法的理解。
二、实验原理
定义：　
假定G是不含ε- 产生式的算符文法。对于任何一对终结符a、b，我们说：
（1）a等于b 当且仅当文法G中含有形如P→ ···ab···或P→···aQb···的产生式；
（2）a小于b 当且仅当G中含有形如P→···aR···的产生式，而R(+=>)b···或R(+=>)Qb···；
（3）a大于b 当且仅当G中含有形如P→···Rb···的产生式，而R(+=>)···a或R(+=>)···aQ；
如果一个算符文法G中的任何终结符对（a,b）最多满足下述三个条件之一： a=b,a<b,a>b
则称G是一个算符优先文法
三、实验过程及步骤（程序源代码、算法说明及调试过程）
#include <stdio.h> #include <stdlib.h> #include <iostream.h>
char data[20][20]; char s[100]; char lable[20];char input[100];
char string[20][10];
int k; char a; int j; char q; int r; int r1; int m,n,N;
char st[10][30]; char first[10][10]; char last[10][10]; int fflag[10]={0};
int deal();int zhongjie(char c); int xiabiao(char c);
void out(int j,int k,char *s); void firstvt(char c); void lastvt(char c);
void table();void main(){ int i,j,k=0;
printf("请输入文法规则数： "); scanf("%d",&r);
printf("请输入文法规则： \n"); for(i=0;i<r;i++)
{ scanf("%s",st[i]); last[i][0]=0;
for(i=0;i<r;i++) { for(j=0;st[i][j]!='\0';j++)
{ if(st[i][0]<'A'||st[i][0]>'Z') { printf("不是算符文法!\n"); exit(-1); }
if(st[i][j]>='A'&&st[i][j]<='Z') { if(st[i][j+1]>='A'&&st[i][j+1]<='Z')
{ printf("不是算符文法!\n"); exit(-1); } } } }
for(i=0;i<r;i++) { for(j=0;st[i][j]!='\0';j++)
{ if((st[i][j]<'A'||st[i][j]>'Z')&&st[i][j]!='-'&&st[i][j]!='>'&&st[i][j]!='|')
lable[k++]=st[i][j]; } }
lable[k]='#'; lable[k+1]='\0'; table();printf("每个非终结符的FIRSTVT集为：\n");
for(i=0;i<r;i++) { printf("%c: ",st[i][0]); for(j=0;j<first[i][0];j++)
{ printf("%c ",first[i][j+1]); } printf("\n"); }
printf("每个非终结符的LASTVT集为： \n");
for(i=0;i<r;i++) {printf("%c: ",st[i][0]);
for(j=0;j<last[i][0];j++) { printf("%c ",last[i][j+1]); printf("\n"); }
printf("算符优先分析表如下:\n");
for(i=0;lable[i]!='\0';i++) printf("\t%c",lable[i]); printf("\n");
for(i=0;i<k+1;i++) { printf("%c\t",lable[i]);
for(j=0;j<k+1;j++) { printf("%c\t",data[i][j]); } printf("\n"); }
printf("请输入文法输入符号串以#结束:"); scanf("%s",input); deal();}
void table(){ char text[20][10]; int i,j,k,t,l,x=0,y=0; int m,n; x=0;
for(i=0;i<r;i++) { firstvt(st[i][0]); lastvt(st[i][0]); }
for(i=0;i<r;i++) { text[x][y]=st[i][0]; y++; for(j=1;st[i][j]!='\0';j++)
{ if(st[i][j]=='|') { text[x][y]='\0'; x++; y=0; text[x][y]=st[i][0]; y++;
text[x][y++]='-'; text[x][y++]='>'; } else { text[x][y]=st[i][j]; y++; } }
text[x][y]='\0'; x++; y=0; }
r1=x; printf("转化后的文法为:\n"); for(i=0;i<x;i++)
{ printf("%s\n",text[i]); } for(i=0;i<x;i++) /
{ string[i][0]=text[i][0]; for(j=3,l=1;text[i][j]!='\0';j++,l++)
string[i][l]=text[i][j]; string[i][l]='\0'; }
for(i=0;i<x;i++) { for(j=1;text[i][j+1]!='\0';j++)
{ if(zhongjie(text[i][j])&&zhongjie(text[i][j+1]))
{ m=xiabiao(text[i][j]); n=xiabiao(text[i][j+1]);
if(text[i][j+2]!='\0'&&zhongjie(text[i][j])&&zhongjie(text[i][j+2])&&!zhong
jie(text[i][j+1]))
{ m=xiabiao(text[i][j]); n=xiabiao(text[i][j+2]); data[m][n]='='; }
if(zhongjie(text[i][j])&&!zhongjie(text[i][j+1])) { for(k=0;k<r;k++)
{ if(st[k][0]==text[i][j+1]) break; } m=xiabiao(text[i][j]);
for(t=0;t<first[k][0];t++) { n=xiabiao(first[k][t+1]); data[m][n]='<'; } }
if(!zhongjie(text[i][j])&&zhongjie(text[i][j+1])) { for(k=0;k<r;k++)
{ if(st[k][0]==text[i][j]) break; }
n=xiabiao(text[i][j+1]);
for(t=0;t<last[k][0];t++) { m=xiabiao(last[k][t+1]); data[m][n]='>'; } } } }
m=xiabiao('#');
for(t=0;t<first[0][0];t++) { n=xiabiao(first[0][t+1]); data[m][n]='<'; }
n=xiabiao('#'); for(t=0;t<last[0][0];t++)
{ m=xiabiao(last[0][t+1]); data[m][n]='>'; } data[n][n]='='; }
void firstvt(char c) int i,j,k,m,n; for(i=0;i<r;i++)
{ if(st[i][0]==c) break; }
if(fflag[i]==0) { n=first[i][0]+1; m=0;
do { if(m==2||st[i][m]=='|') { if(zhongjie(st[i][m+1]))
{ first[i][n]=st[i][m+1]; n++; }
else { if(zhongjie(st[i][m+2]))
{ first[i][n]=st[i][m+2]; n++;}
if(st[i][m+1]!=c) { firstvt(st[i][m+1]);
for(j=0;j<r;j++) { if(st[j][0]==st[i][m+1]) break; }
for(k=0;k<first[j][0];k++) { int t; for(t=0;t<n;t++)
{ if(first[i][t]==first[j][k+1]) break; }
if(t==n) { first[i][n]=first[j][k+1]; n++; } } } } }
m++; }while(st[i][m]!='\0');
first[i][n]='\0'; first[i][0]=--n; fflag[i]=1; } }
void lastvt(char c) { int i,j,k,m,n; for(i=0;i<r;i++)
{ if(st[i][0]==c) break; }
if(lflag[i]==0) { n=last[i][0]+1; m=0;
do { if(st[i][m+1]=='\0'||st[i][m+1]=='|')
{ if(zhongjie(st[i][m])) { last[i][n]=st[i][m]; n++; }
else { if(zhongjie(st[i][m-1])) { last[i][n]=st[i][m-1]; n++; }
if(st[i][m]!=c) { lastvt(st[i][m]); for(j=0;j<r;j++)
{ if(st[j][0]==st[i][m]) break; }
for(k=0;k<last[j][0];k++) { int t; for(t=0;t<n;t++)
{ if(last[i][t]==last[j][k+1]) break; }
if(t==n) { last[i][n]=last[j][k+1]; n++; } } } } }
m++; }while(st[i][m]!='\0'); last[i][n]='\0'; last[i][0]=--n; lflag[i]=1; } }
(1,k,s); printf("%c",a); out(i+1,z,input); printf("结束\n");
printf("输入串符合文法的定义！ \n"); return 1; } }
else if(data[x][y]=='<'||data[x][y]=='=')
{ out(1,k,s); printf("%c",a); out(i+1,z,input); printf("移进\n"); k++;
else { printf("\nflase"); return 0; } }
printf("\nflase"); return 0; }
void out(int j,int k,char *s) {int n=0; int i; for(i=j;i<=k;i++)
{ printf("%c",s[i]); n++;} for(;n<15;n++) { printf(" "); } }
int xiabiao(char c)
{ int i; for(i=0;lable[i]!='\0';i++) { if(c==lable[i]) return i; } return -1; }
int zhongjie(char c) { int i; for(i=0;lable[i]!='\0';i++) { if(c==lable[i])
return 1; } return 0; }
四、实验结果（含数据记录及分析等）

五、实验总结（含实验心得体会，收获与不足等）
这次实验让我更加熟悉了算符优先文法的工作流程以及构造方法。以前课堂上搞不懂的算法流程通过实验都能得到进一步的了解。