1 #include <cstdio>View Code
2 #include <cstring>
3 #include <iostream>
4 #include <stack>
5 #include <queue>
6 #include <map>
7 #include <algorithm>
8 #include <vector>
9
10 using namespace std;
11
12 char A[20];/*分析栈*/
13 char B[20];/*剩余串*/
14 char v1[20]= {'i','+','*','(',')','#'}; /*终结符 */
15 char v2[20]= {'E','G','T','S','F'}; /*非终结符 */
16
17 int j=0,b=0,top=0,l;/*L为输入串长度 */
18 char x,ch;
19 int k=1;
20 int m,n;
21 int flag=0,finish=0;
22
23 typedef struct type/*产生式类型定义 */
24 {
25 char origin;/*大写字符 */
26 char array[5];/*产生式右边字符 */
27 int length;/*字符个数 */
28 } type;
29
30 type e,t,g,g1,s,s1,f,f1,cha;/*结构体变量 */
31 type C[10][10];/*预测分析表 */
32
33 void init()
34 {
35 e.origin='E';
36 strcpy(e.array,"TG");
37 t.origin='T';
38 strcpy(t.array,"FS");
39 g.origin='G';
40 strcpy(g.array,"+TG");
41 g1.origin='G';
42 g1.array[0]='^';
43 s.origin='S';
44 strcpy(s.array,"*FS");
45 s1.origin='S';
46 s1.array[0]='^';
47 f.origin='F';
48 strcpy(f.array,"(E)");
49 f1.origin='F';
50 f1.array[0]='i';
51
52 for(int m=0; m<=4; m++) /*初始化分析表*/
53 for(int n=0; n<=5; n++)
54 C[m][n].origin='N';/*全部赋为空*/
55 /*填充分析表*/
56 C[0][0]=e;
57 C[0][3]=e;
58 C[1][1]=g;
59 C[1][4]=g1;
60 C[1][5]=g1;
61 C[2][0]=t;
62 C[2][3]=t;
63 C[3][1]=s1;
64 C[3][2]=s;
65 C[3][4]=C[3][5]=s1;
66 C[4][0]=f1;
67 C[4][3]=f;
68 }
69
70 void print()/*输出分析栈 */
71 {
72 int a;/*指针*/
73 for(a=0; a<=top+1; a++)
74 printf("%c",A[a]);
75 printf("\t\t");
76 }
77
78 void print1()/*输出剩余串*/
79 {
80 int j;
81 for(j=0; j<b; j++) /*输出对齐符*/
82 printf(" ");
83 for(j=b; j<=l; j++)
84 printf("%c",B[j]);
85 printf("\t\t\t");
86 }
87 int main()
88 {
89 init();
90 //测试样例反例
91 //i+i(i+i)#
92 //i()#
93 //正确样例
94 //i+i*i#
95
96
97 do/*读入分析串*/
98 {
99 scanf("%c",&ch);
100 if ((ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#'))
101 {
102 printf("输入串中有非法字符\n");
103 exit(1);
104 }
105 B[j]=ch;
106 j++;
107 }while(ch!='#');
108 l=j;/*分析串长度*/
109 ch=B[0];/*当前分析字符*/
110 A[top]='#';
111 A[++top]='E';/*'#','E'进栈*/
112 printf("步骤\t\t分析栈 \t\t剩余字符 \t\t所用产生式 \n");
113
114 do{
115 flag = 0;
116 if(finish) break;
117 x=A[top--];/*x为当前栈顶字符*/
118 printf("%d",k++);
119 printf("\t\t");
120
121
122
123
124 for( j=0; j<=5; j++) /*判断是否为终结符*/
125 {
126 if(x==v1[j])
127 {
128 flag=1;
129 break;
130 }
131 }
132 if(flag==1)/*如果是终结符*/
133 {
134 if(x=='#')
135 {
136 finish=1;/*结束标记*/
137 printf("acc!\n");/*接受 */
138 getchar();
139 getchar();
140 exit(1);
141 }
142 if(x==ch)
143 {
144 print();
145 print1();
146 printf("%c匹配\n",ch);
147 ch=B[++b];/*下一个输入字符*/
148 flag=0;/*恢复标记*/
149 }
150 /*else //出错处理
151 {
152 print();
153 print1();
154 printf("%c出错\n",ch);//输出出错终结符
155 exit(1);
156 }*/
157 }
158 else/*非终结符处理*/
159 {
160 for(j=0; j<=4; j++)
161 if(x==v2[j])
162 {
163 m=j;/*行号*/
164 break;
165 }
166 for(j=0; j<=5; j++)
167 if(ch==v1[j])
168 {
169 n=j;/*列号*/
170 break;
171 }
172 cha=C[m][n];
173 if(cha.origin!='N')/*判断是否为空*/
174 {
175 print();
176 print1();
177 printf("%c->",cha.origin);/*输出产生式*/
178 int len = strlen(cha.array); //长度是array的长度
179 for(j=0; j<len; j++)
180 printf("%c",cha.array[j]);
181 printf("\n");
182 for(j=(len-1); j>=0; j--) /*产生式逆序入栈*/
183 A[++top]=cha.array[j];
184 if(A[top]=='^')/*为空则不进栈*/
185 top--;
186 }
187 else //出错处理 调整顺序
188 {
189 print();
190 print1();
191 printf("%c出错\n",ch);//输出出错终结符
192 exit(1);
193 }
194
195 }
196
197 }while(top!=-1); //当分析栈不为空
198
199 return 0;
200 }
送人玫瑰手留余香。。。。
