时间：2014-6-9 作者：顾博君 /* 0. Z-S 1. S-while(E)S 2. S-E; 3. S-; 4. E-i=E 5. E-T 6. T-T+P 7. T-P 8. P-P*F 9. P-F10. F-i11. F-(E)12. F-num-------------------------------------- | |-------------------------------------- |---------
时间：2014-6-9 作者：顾博君
/*
0. Z->S
1. S->while(E)S
2. S->E;
3. S->;
4. E->i=E
5. E->T
6. T->T+P
7. T->P
8. P->P*F
9. P->F
10. F->i
11. F->(E)
12. F->num
--------------------------------------
| |
--------------------------------------
|
--------------------------------------
*/
#include "stdio.h"
#include "conio.h"
#define MAX 140
typedef struct
{
char left;
int length;
} production;
void create_production(production p[13])
{
p[0].left='Z';//Z->S
p[0].length=1;
p[1].left='S';//S->while(E)S
p[1].length=5;
p[2].left='S';//S->E;
p[2].length=2;
p[3].left='S';//S->;
p[3].length=1;
p[4].left='E';//E->i=E
p[4].length=3;
p[5].left='E';//E->T
p[5].length=1;
p[6].left='T';//T->T+P
p[6].length=3;
p[7].left='T';//T->P
p[7].length=1;
p[8].left='P';//P->P*F
p[8].length=3;
p[9].left='P';//P->F
p[9].length=1;
p[10].left='F';//F->i
p[10].length=1;
p[11].left='F';//F->(E)
p[11].length=3;
p[12].left='F';//F->num
p[12].length=1;
}
//状态栈
typedef struct
{
int data[MAX];
int top;
} state_stack;
//符号栈
typedef struct
{
char data[MAX];
int top;
} char_stack;
void init_state_stack(state_stack *st)
{
st->top=0;
}
void init_char_stack(char_stack *st)
{
st->top=0;
}
void state_push(state_stack *st,int s)
{
if(st->top==MAX-1)
{
printf("\nstate stack is full!");
getch();
exit(0);
}
st->data[st->top]=s;
st->top++;
}
void char_push(char_stack *st,char ch)
{
if(st->top==MAX-1)
{
printf("\nchar stack is full!");
getch();
exit(0);
}
st->data[st->top]=ch;
st->top++;
}
void state_pop(state_stack *st)
{
if(st->top==0)
{
printf("\nstack is empty!");
getch();
exit(0);
}
st->top--;
}
void char_pop(char_stack *st)
{
if(st->top==0)
{
printf("\nstack is empty!");
getch();
exit(0);
}
st->top--;
}
int read_state(state_stack *st)
{
return st->data[st->top-1];
}
char read_char(char_stack *st)
{
return st->data[st->top-1];
}
void error()
{
printf("\nerror!");
getch();
exit(0);
}
int vn_to_int(char ch)
{
switch(ch)
{
case 'S':
return 0;
case 'E':
return 1;
case 'T':
return 2;
case 'P':
return 3;
case 'F':
return 4;
}
}
int vt_to_int2(char ch)
{
switch(ch)
{
case 4://while
return 0;
case 29://[
case 31://(
case 33://{
return 1;
case 30://]
case 32://)
case 34://|
return 2;
case 35://;
return 3;
case 11://标识符
return 4;
case 28://=
return 5;
case 13://'+'
case 14://'-'
return 6;
case 15://'*'
case 16://'/'
return 7;
case 12://num
return 8;
case 38://'#'
return 9;
default:
printf("\ncharacter is false!");
getch();
exit(0);
}
return -1;
}
int vt_to_int(int ch)
{
switch(ch)
{
case 'w'://while
return 0;
case '(':
return 1;
case ')':
return 2;
case ';':
return 3;
case 'i':
return 4;
case '=':
return 5;
case '+':
return 6;
case '*':
return 7;
case '1'://num
return 8;
case '#':
return 9;
default:
printf("\ncharacter is false!");
getch();
exit(0);
}
return -1;
}
void SLR_driver(state_stack *state,char_stack *input,char action1[25][10],
int action2[25][10],int SLR_goto[25][5], production p[13] )
{
int s,k,l,m;
char c,ch;
s=read_state(state);
ch=read_char(input);
printf("s=%d,ch=%c",s,ch);
while(1)
{
k=vt_to_int(ch);
c=action1[s][k];
switch(c)
{
case 's':
state_push(state,action2[s][k]);
char_pop(input);
break;
case 'r':
m=action2[s][k];
for(l=p[m].length; l>0; l--)
state_pop(state);
state_push(state,SLR_goto[read_state(state)][vn_to_int(p[m].left)]);
break;
case 'a':
printf("\naccept!");
getch();
exit(0);
default:
error();
}
s=read_state(state);
ch=read_char(input);
printf("\ns=%d,ch=%c",s,ch);
}
}
void SLR_driver2(state_stack *state,state_stack *input,char action1[25][10],
int action2[25][10],int SLR_goto[25][5], production p[13] )
{
int s,k,l,m,ch;
char c;
s=read_state(state);
ch=read_state(input);
printf("s=%d,ch=%d",s,ch);
while(1)
{
k=vt_to_int2(ch);
c=action1[s][k];
switch(c)
{
case 's':
state_push(state,action2[s][k]);
state_pop(input);
break;
case 'r':
m=action2[s][k];
for(l=p[m].length; l>0; l--)
state_pop(state);
state_push(state,SLR_goto[read_state(state)][vn_to_int(p[m].left)]);
break;
case 'a':
printf("\naccept!");
getch();
exit(0);
default:
error();
}
s=read_state(state);
ch=read_state(input);
printf("\ns=%d,ch=%d",s,ch);
}
}
main()
{
char c,ch[MAX];
int i=0,j;
state_stack state,Input,t;
char_stack input;
char action1[25][10]=
{
{'s','s','0','s','s','0','0','0','s','0'},//0
{'0','0','0','0','0','0','0','0','0','a'},//1
{'0','s','0','0','0','0','0','0','0','0'},//2
{'0','0','0','s','0','0','0','0','0','0'},//3
{'0','0','0','0','0','0','0','0','0','r'},//4
{'0','0','r','r','0','s','r','r','0','0'},//5
{'0','0','r','r','0','0','s','0','0','0'},//6
{'0','0','r','r','0','0','r','s','0','0'},//7
{'0','0','r','r','0','0','r','r','0','0'},//8
{'0','s','0','0','s','0','0','0','s','0'},//9
{'0','0','r','r','0','0','r','r','0','0'},//10
{'0','s','0','0','s','0','0','0','s','0'},//11
{'0','0','0','0','0','0','0','0','0','r'},//12
{'0','s','0','0','s','0','0','0','s','0'},//13
{'0','s','0','0','s','0','0','0','s','0'},//14
{'0','s','0','0','s','0','0','0','s','0'},//15
{'0','0','s','0','0','0','0','0','0','0'},//16
{'0','0','s','0','0','0','0','0','0','0'},//17
{'0','0','r','r','0','0','0','0','0','0'},//18
{'0','0','r','r','0','0','r','s','0','0'},//19
{'0','0','r','r','0','0','r','r','0','0'},//20
{'0','0','r','r','0','0','r','r','0','0'},//21
{'0','0','r','r','0','0','r','r','0','0'},//22
{'s','s','0','s','s','0','0','0','s','0'},//23
{'0','0','0','0','0','0','0','0','0','r'}//24
};
int action2[25][10]=
{
{ 2, 9,-1, 4, 5,-1,-1,-1,10,-1},//0
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},//1
{-1,11,-1,-1,-1,-1,-1,-1,-1,-1},//2
{-1,-1,-1,12,-1,-1,-1,-1,-1,-1},//3
{-1,-1,-1,-1,-1,-1,-1,-1,-1, 3},//4
{-1,-1,10,10,-1,13,10,10,-1,-1},//5
{-1,-1, 5, 5,-1,-1,14,-1,-1,-1},//6
{-1,-1, 7, 7,-1,-1, 7,15,-1,-1},//7
{-1,-1, 9, 9,-1,-1, 9, 9,-1,-1},//8
{-1, 9,-1,-1, 5,-1,-1,-1,10,-1},//9
{-1,-1,12,12,-1,-1,12,12,-1,-1},//10
{-1, 9,-1,-1, 5,-1,-1,-1,10,-1},//11
{-1,-1,-1,-1,-1,-1,-1,-1,-1, 2},//12
{-1, 9,-1,-1, 5,-1,-1,-1,10,-1},//13
{-1, 9,-1,-1,20,-1,-1,-1,10,-1},//14
{-1, 9,-1,-1,20,-1,-1,-1,10,-1},//15
{-1,-1,22,-1,-1,-1,-1,-1,-1,-1},//16
{-1,-1,23,-1,-1,-1,-1,-1,-1,-1},//17
{-1,-1, 4, 4,-1,-1,-1,-1,-1,-1},//18
{-1,-1, 6, 6,-1,-1, 6,15,-1,-1},//19
{-1,-1,10,10,-1,-1,10,10,-1,-1},//20
{-1,-1, 8, 8,-1,-1, 8, 8,-1,-1},//21
{-1,-1,11,11,-1,-1,11,11,-1,-1},//22
{ 2, 9,-1, 4, 5,-1,-1,-1,10,-1},//23
{-1,-1,-1,-1,-1,-1,-1,-1,-1, 1}//24
};
int SLR_goto[25][5]=
{
{ 1, 3, 6, 7, 8},//0
{-1,-1,-1,-1,-1},//1
{-1,-1,-1,-1,-1},//2
{-1,-1,-1,-1,-1},//3
{-1,-1,-1,-1,-1},//4
{-1,-1,-1,-1,-1},//5
{-1,-1,-1,-1,-1},//6
{-1,-1,-1,-1,-1},//7
{-1,-1,-1,-1,-1},//8
{-1,16, 6, 7, 8},//9
{-1,-1,-1,-1,-1},//10
{-1,17, 6, 7, 8},//11
{-1,-1,-1,-1,-1},//12
{-1,18, 6, 7, 8},//13
{-1,-1,-1,19, 8},//14
{-1,-1,-1,-1,21},//15
{-1,-1,-1,-1,-1},//16
{-1,-1,-1,-1,-1},//17
{-1,-1,-1,-1,-1},//18
{-1,-1,-1,-1,-1},//19
{-1,-1,-1,-1,-1},//20
{-1,-1,-1,-1,-1},//21
{-1,-1,-1,-1,-1},//22
{24, 3, 6, 7, 8},//23
{-1,-1,-1,-1,-1}//24
};
production p[13];
create_production(p);
init_char_stack(&input);
init_state_stack(&state);
init_state_stack(&Input);
init_state_stack(&t);
#if 1
FILE *stream;
char str[1000];
int numread,a,b;
if ((stream = fopen("TokenL.txt","r")) != NULL)
{
fscanf(stream,"TokenList:");
while(fscanf(stream,"\n %d 编码:%d \t字符:%s",&a,&b,str)!=EOF){
state_push(&t,b);
//printf("%d\n",read_state(&Input));
}
fclose(stream);
//printf("%s\n***********************\n",str);
state_push(&state,0);
while(t.top){
if(read_state(&t)!=37)//\n
state_push(&Input,read_state(&t));
state_pop(&t);
}
SLR_driver2(&state,&Input,action1,action2,SLR_goto,p);
}
else printf("\n*********Wrong***********\n");
#elif 2
printf("\ninput a string:");
scanf("%c",&c);
while(c!='#')
{
ch[i]=c;
i++;
scanf("%c",&c);
}
ch[i]='#';
for(j=i; j>=0; j--) printf("%c",ch[j]);
printf("\n");
for(j=i; j>=0; j--)
char_push(&input,ch[j]);
state_push(&state,0);
SLR_driver(&state,&input,action1,action2,SLR_goto,p);
#endif
}