实验二参考程序：（来源于网络，没进行测试，同学们自己调试）
说明：规则左部和规则右部之间的“—>”不需要输入；终结符不支持字符串；文法输入符号串结
尾需加“$”。
==================================================================
#include "stdio.h"
int data[20][20]={0}; /* 算符优先关系表*/
char s[100]; /* 符号栈s */
char lable[20]; /* 文法终极符集*/
char input[100]; /* 文法输入符号串*/
int k; /* 符号栈s的指针*/
char a; /* 用来存放当前输入符号*/
int j; /* 栈的查找指针*/
char q; /* 工作单元*/
int r; /* 文法规则数*/
char st[10][30]; /* 用来存储文法规则*/
char first[10][10]; /* 文法非终结符FIRSTVT集*/
char last[10][10]; /* 文法非终结符LASTVT集*/
int fflag[10]={0}; /* 标志第i个非终结符的FIRSTVT集是否已求出*/
int lflag[10]={0}; /* 标志第i个非终结符的LASTVT集是否已求出*/
int deal(); /* 判断输入串是否符合文法的定义*/
int has(char c); /* 判断字符c是否是终极符*/
int num(char c); /* 求字符c在算符优先关系表中的下标*/
void out(int j,int k,char *s); /* 打印s栈*/
void firstvt(char c); /* 求非终结符c的FIRSTVT集*/
void lastvt(char c); /* 求非终结符c的LASTVT集*/
void table(); /* 创建文法优先关系表*/
int main(){
int i,j;
printf("请输入文法规则数：");
scanf("%d",&r);
printf("请输入文法规则：\n");
for(i=0;i<r;i++){
scanf("%s",st[i]); /* 存储文法规则，初始化FIRSTVT集和LASTVT集*/
/* first[i][0]和last[i][0]分别表示st[i][0]非终极符的FIRSTVT集和LASTVT集中元素的个数
*/
first[i][0]=0;
last[i][0]=0;
}
printf("请输入文法终结符：");
scanf("%s",lable);             /*请输入文法终结符*/
for(i=0;lable[i]!='\0';i++);
lable[i]='$';
lable[i+1]='\0';
table();
/* 分别输出每个非终结符的FIRSTVT集和LASTVT集*/
/*for(i=0;i<r;i++){
for(j=0;j<first[i][0];j++){
printf("%c ",first[i][j+1]);
}
printf("\n");
}
for(i=0;i<r;i++){
for(j=0;j<last[i][0];j++){
printf("%c ",last[i][j+1]);
}
printf("\n");
}*/
printf("请输入文法输入符号串:");
scanf("%s",input);
deal();
/* 打印算符优先分析表*/
/*printf("\n%s\n",lable);
for(i=0;i<6;i++){
for(j=0;j<6;j++){
printf("%d\t",data[i][j]);
}
printf("\n");
}*/
return 0;
}
void table(){
int i,j,k,t,x=0,y=0;
int m,n;
char text[20][10];
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++;
}else{
text[x][y]=st[i][j];
y++;
}
}
text[x][y]='\0';
x++;
y=0;
}
/* 输出转化后的文法规则串*/
/*for(i=0;i<x;i++){
printf("%s\n",text[i]);
}*/
for(i=0;i<x;i++){
for(j=1;text[i][j+1]!='\0';j++){
if(has(text[i][j])&&has(text[i][j+1])){
m=num(text[i][j]);
n=num(text[i][j+1]);
data[m][n]=2;
}
if(text[i][j+2]!='\0'&&has(text[i][j])&&has(text[i][j+2])&&!has(text[i][j+1])){
m=num(text[i][j]);
n=num(text[i][j+2]);
data[m][n]=2;
}
if(has(text[i][j])&&!has(text[i][j+1])){
for(k=0;k<r;k++){
if(st[k][0]==text[i][j+1])
break;
}
m=num(text[i][j]);
for(t=0;t<first[k][0];t++){
n=num(first[k][t+1]);
data[m][n]=1;
}
}
if(!has(text[i][j])&&has(text[i][j+1])){
for(k=0;k<r;k++){
if(st[k][0]==text[i][j])
break;
}
n=num(text[i][j+1]);
for(t=0;t<last[k][0];t++){
m=num(last[k][t+1]);
data[m][n]=3;
}
}
}
}
m=num('$');
for(t=0;t<first[0][0];t++){
n=num(first[0][t+1]);
data[m][n]=1;
}
n=num('$');
for(t=0;t<last[0][0];t++){
m=num(last[0][t+1]);
data[m][n]=3;
}
data[n][n]=2;
}
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==0||st[i][m]=='|'){
if(has(st[i][m+1])){
first[i][n]=st[i][m+1];
n++;
}
else {
if(has(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(has(st[i][m])){
last[i][n]=st[i][m];
n++;
}
else {
if(has(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;
}
}
/* 算符优先关系表中0代表没关系1代表< 2代表= 3代表> */
int deal(){
int i;
int x,y;
int z; /* 输入串的长度*/
k=1;
s[k]='$'; /* 栈置初值*/
for(i=0;input[i]!='\0';i++) /* 计算输入串的长度*/
;
z=i--;
i=0;
while((a=input[i])!='\0'){
if(has(s[k]))
j=k;
else
j=k-1;
x=num(s[j]);
y=num(a);
if(data[x][y]==3){ /* 规约*/
out(1,k,s);
printf("> ");
printf("%c ",a);
out(i+1,z,input);
printf("规约\n");
do{
q=s[j];
j=j-1;
if(!has(s[j]))
j=j-1;
x=num(s[j]);
y=num(q);
}while(data[x][y]!=1);
k=j+1;
s[k]='#'; /* 用#代替所有的非终极符*/
if(k==2&&a=='$'){
out(1,k,s);
printf("= ");
printf("%c ",a);
out(i+1,z,input);
printf("结束\n");
printf("输入串符合文法的定义！");
return 1; /* 输入串符合文法的定义*/
}
}else if(data[x][y]==1||data[x][y]==2){ /* 移进*/
out(1,k,s);
printf("< ");
printf("%c ",a);
out(i+1,z,input);
printf("移进\n");
k++;
s[k]=a;
i++;
}
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 num(char c){
int i;
for(i=0;lable[i]!='\0';i++){
if(c==lable[i])
return i;
}
return -1;
}
int has(char c){
int i;
for(i=0;lable[i]!='\0';i++){
if(c==lable[i])
return 1;
}
return 0;
}