实验原理
构造SLR(1)分析表
首先求得follow集
follow(E)={#,+,-,)}
follow(T)={#,+,-,),,/}
follow(F)={#,+,-,),,/}
画出DFA状态转换图
调试过程
没有判断
因为字符串中没有表示10以上的字符所以只能存之后的符号
最后就能得到正确答案
#include <stdio.h>
#include <string.h>
/**文法G[S]**/
//0 E'->E
//1 E->T
//2 E->E+T
//3 E->E-T
//4 T->F
//5 T->T*F
//6 T->T/F
//7 F->I
//8 F->(E)
//a*(b+c*(a-b))#
//a*b+c/d#
//四元式用到的全局变量
char sem[50]; //语义栈,存放id(指向标识符地址的指针)或四元式编号
int sem1=0; //语义栈指针
char t='1'; //假设为结果集变量
char id;
char Tri[15][30]; //存放四元式
int tr=0; //四元式集指针
//状态栈
int s1=0;
int states1[50]={0};
//符号栈
int f1=0;
char fuhao1[50]={'#'};
//输入栈
int in1=0;
char input1[50];
char flag; //定位action表或goto表中的某一个位置
//定义SLR(1)_action表
char action1[16][8]=
//数字:下一个状态集编号(10:':' 11:';' 12:'<' 13:'=' 14:'>' 15:'?') 字母:规约的产生式编号 *:结束规约
{// + - * / ( ) i #
{' ',' ',' ',' ','5',' ','4',' '}, //0
{'6','7',' ',' ',' ',' ',' ','*'}, //1
{'a','a','8','9',' ','a',' ','a'}, //2
{'d','d','d','d',' ','d',' ','d'}, //3
{'g','g','g','g',' ','g',' ','g'}, //4
{' ',' ',' ',' ','5',' ','4',' '}, //5
{' ',' ',' ',' ','5',' ','4',' '}, //6
{' ',' ',' ',' ','5',' ','4',' '}, //7
{' ',' ',' ',' ','5',' ','4',' '}, //8
{' ',' ',' ',' ','5',' ','4',' '}, //9
{'6','7',' ',' ',' ','?',' ',' '}, //10
{'b','b','8','9',' ','b',' ','b'}, //11
{'c','c','8','9',' ','c',' ','c'}, //12
{'e','e','e','e',' ','e',' ','e'}, //13
{'f','f','f','f',' ','f',' ','f'}, //14
{'h','h','h','h',' ','h',' ','h'}, //15
};
//定义goto表
//数字:产生式编号(10:':' 11:';' 12:'<' 13:'=' 14:'>' 15:'?')
char go[16][3]=
{ // E T F
{'1','2','3'}, //0
{' ',' ',' '}, //1
{' ',' ',' '}, //2
{' ',' ',' '}, //3
{' ',' ',' '}, //4
{':','2','3'}, //5
{' ',';','3'}, //6
{' ','<','3'}, //7
{' ',' ','='}, //8
{' ',' ','>'}, //9
{' ',' ',' '}, //10
{' ',' ',' '}, //11
{' ',' ',' '}, //12
{' ',' ',' '}, //13
{' ',' ',' '}, //14
{' ',' ',' '}, //15
};
//将文法存入二维数组
char G[9][20]=
{
{" "},
{"ET"},
{"EE+T"},
{"EE-T"},
{"TF"},
{"TT*F"},
{"TT/F"},
{"Fi"},
{"F(E)"},
};
//根据当前输入符号确定action表列号
int number_action(char c)
{
int n;
switch(c)
{
case '+':n=0;break;
case '-':n=1;break;
case '*':n=2;break;
case '/':n=3;break;
case '(':n=4;break;
case ')':n=5;break;
case 'i':n=6;break;
case '#':n=7;break;
default:n=-1;break;
}
return n;
}
//根据规约后的栈顶符号确定go表列号
int number_go(char c)
{
int n;
switch(c)
{
case 'E':n=0;break;
case 'T':n=1;break;
case 'F':n=2;break;
default:n=-1;break;
}
return n;
}
//生成四元式的函数
void GenQT(char w)
{
Tri[tr][0]=w;
Tri[tr][1]=sem[sem1-2];
Tri[tr][2]=sem[sem1-1];
Tri[tr][3]=t;
//if(tr==0) printf("\t(%c,%c,%c,%c)\n",Tri[tr][0],Tri[tr][1],Tri[tr][2],Tri[tr][3]);
//else printf("\t(%c,%c,%c,%c)\n",Tri[tr][0],Tri[tr][1],Tri[tr][2],Tri[tr][3]);
tr++;
sem[sem1-2]=t;
sem1--;
t++;
}
//四元式语义子程序
void four(int f)
{
switch(f)
{
case 0: break; //E'->E
case 1: break; //E->T
case 2: GenQT('+'); break; //E->E+T
case 3: GenQT('-'); break; //E->E-T
case 4: break; //T->F
case 5: GenQT('*'); break; //T->T*F
case 6: GenQT('/'); break; //T->T/F
case 7: sem[sem1++]=id; break; //F->i
case 8: break; //F->(E)
}
}
//输出分析过程
void print(int step,int state[],int s,char fuhao[],int f,char input[],int in)
{
int i=0;
printf("%3d\t",step); //步骤号
while(i<=s) //状态栈
{
if(state[i]>9) printf(" ");
printf("%d",state[i++]);
}
printf("\t\t");
i=0;
while(i<=f) //符号栈
{
printf("%c",fuhao[i++]);
}
printf("\t\t");
i=in;
while(input[i]!='\0')
{
printf("%c",input[i++]);
}
printf("\t");
}
void SLR1()
{
int m,n; //m->action、goto表行号 n->action、goto表列号
int step=1;
printf("\n\n\t\t\tSLR(1)分析");
printf("\n步骤 状态栈 符号栈 剩余串 action goto\n");
while(1)
{
m=states1[s1]; /**state为整型数组**/
//n=number_action(input1[in1]);
//将输入中除'终结符'及'非终结符'以外的符号换位'i'
if(input1[in1]!='+' && input1[in1]!='-' && input1[in1]!='*' &&
input1[in1]!='/' && input1[in1]!='(' && input1[in1]!=')' &&
input1[in1]!='i' && input1[in1]!='#' && input1[in1]!='E' &&
input1[in1]!='T' && input1[in1]!='F') { n=number_action('i'); }
else n=number_action(input1[in1]);
flag=action1[m][n];
/**当前操作数 op(四元式**/
if(n==6) id=input1[in1]; //6为'i'的列号,说明当前输入符号为操作数
if(('0'<=flag && flag<='9') || flag==':' || flag==';' || flag=='<'
|| flag=='=' || flag=='>' || flag=='?') //移进
{
print(step,states1,s1,fuhao1,f1,input1,in1);
//
if('0'<=flag && flag<='9') printf("\tS%c\n",flag);
if(flag==':') printf("\tS10\n");
if(flag==';') printf("\tS11\n");
if(flag=='<') printf("\tS12\n");
if(flag=='=') printf("\tS13\n");
if(flag=='>') printf("\tS14\n");
if(flag=='?') printf("\tS15\n");
states1[++s1]=flag-'0'; /**state为整型数组**/
fuhao1[++f1]=input1[in1++];
step++;
}
else if('a'<=flag && flag<='z') //规约
{
print(step,states1,s1,fuhao1,f1,input1,in1);
int f=flag-'a'+1; //产生式编号
printf("\tr%d",f);
//从状态栈和符号栈中弹出产生式右部
int len=strlen(G[f])-1; //-1是因为G[][0]记录产生式左部
f1=f1-len;
s1=s1-len;
fuhao1[++f1]=G[f][0];
m=states1[s1]; //goto表的行号
n=number_go(fuhao1[f1]); //goto表的列号
flag=go[m][n];
//
if('0'<=flag && flag<='9') printf("\t%c\n",flag);
if(flag==':') printf("\t10\n");
if(flag==';') printf("\t11\n");
if(flag=='<') printf("\t12\n");
if(flag=='=') printf("\t13\n");
if(flag=='>') printf("\t14\n");
if(flag=='?') printf("\t15\n");
/**四元式语义子程序**/
four(f);
states1[++s1]=flag-'0';
step++;
}
else if(flag=='*') //规约成功,接受
{
print(step,states1,s1,fuhao1,f1,input1,in1);
printf("\t接受!\n");
return;
}
else //查action表为空
{
print(step,states1,s1,fuhao1,f1,input1,in1);
printf("\t出错");
return;
}
}
}
int main()
{
printf("请输入:\n");
gets(input1);
SLR1();
printf("四元式序列:\n");
for(int i=0;i<(t-'0'-1);i++) //t是从'1'开始
{
if(i==0) printf("\t%d.(%c,%c,%c,%c)\n",i+1,Tri[i][0],Tri[i][1],Tri[i][2],Tri[i][3]);
else printf("\t%d.(%c,%c,%c,%c)\n",i+1,Tri[i][0],Tri[i][1],Tri[i][2],Tri[i][3]);
}
}
//a+b-c/d#
//A*(B+C*(A-B))#
//A*(B+C)#