· 5 years ago · Feb 25, 2020, 02:56 AM
1/*C program to create SLR parse table for given grammar*/
2#include<stdio.h>
3#include<string.h>
4#include<stdlib.h>
5#include<stdbool.h>
6
7/*declarations of fist and follow*/
8int counter=3;
9char origchar;
10int op;
11int production;
12char prods[30][30];
13char origfirst[200];
14char origfollow[200];
15int n=0;
16int m=0;
17
18/*This variable keeps track of canonical state created*/
19int canonicaln=0;
20
21/*This array contains all the terminals and non terminals*/
22char characters[50];
23
24/*This is the SLR parse table*/
25int table[30][30];
26
27/*variable for characters array*/
28int num=0;
29
30/*structure for storing ith canonical state*/
31typedef struct canonicals
32{
33 int prodno;
34 char prodn[30][30];
35}canonical;
36
37
38typedef struct node
39{
40 char val;
41 struct node *next;
42}node;
43
44int topstack(node * head)
45{
46 if(head==NULL)
47 return -1;
48 return head->val;
49}
50
51bool isempty(node ** head)
52{
53 if((*head)==NULL)
54 return true;
55 return false;
56}
57
58void pop(node ** head)
59{ node *p;
60 if(*head==NULL)
61 {
62 printf("stack empty\n");
63 return ;
64 }
65 p=*head;
66 printf("value popped is %c\n",p->val);
67 *head=p->next;
68}
69void push(node ** head,char c)
70{
71 node *p,*ptr;
72 ptr=(node *)malloc(sizeof(node));
73 ptr->val=c;
74 ptr->next=NULL;
75 if(*head==NULL)
76 {
77 *head=ptr;
78 }
79 else
80 {
81 p=*head;
82 *head=ptr;
83 ptr->next=p;
84 }
85 printf("value pushed is %c\n",(*head)->val);
86}
87
88int find(char c)
89{
90 int i;
91 for(i=0;i<30;i++)
92 {
93 if(c==characters[i])
94 return i;
95 }
96 printf("error in find()\n");
97}
98
99/*this function performs parsing*/
100void parsing(canonical canonical_arr[])
101{
102 char string[10];
103 int i=0,top,j,r,count,k,x;
104 char c;
105 strcpy(string,"i*i+i$");
106
107 /*stack formation*/
108 node *head=NULL;
109 push(& head, '$');
110 push(&head,'0');
111 while(!isempty(&head))
112 {
113 c=string[i];
114 top=topstack(head)-48;
115
116 j=find(c);
117 if(top==1&& c=='$' )
118 { printf("string parsed successfully\n");
119 return;
120 }
121 /*Goto function*/
122 else if(table[top][j]>=70)
123 {
124 count=0;
125 r=table[top][j]-70;
126 for(count=0;count<15;count++)
127 {
128 if(canonical_arr[0].prodn[r][count]=='@')
129 break;
130 }
131 count=count-3;
132
133 while(count--)
134 {
135 pop(&head);
136 }
137 k=find(canonical_arr[0].prodn[r][0]);
138 x=topstack(head)-48;
139
140 push(&head,table[x][k]+48);
141
142 }
143 else if(table[top][j]>0)
144 {
145 push(&head,table[top][j]+48);
146 i++;
147 }
148 else
149 {
150 return;
151 }
152 }
153}
154
155
156
157
158/*This functions adds corresponding shifts abd gotos to the table*/
159void tableaddition(int val,char c,int shift,char type)
160{ int i=0;
161 for(i=0;i<num;i++)
162 {
163 if(characters[i]==c)
164 { break;
165 }
166 }
167 if(type=='r')
168 table[val][i]=shift+70;
169 else
170 table[val][i]=shift;
171
172}
173
174/*This function checks if the given production exists in any previous state or not*/
175int check(canonical canonical_arr[],char *string)
176{
177 int i=0,j=0;
178 for(i=0;i<canonicaln;i++)
179 {
180 if(strcmp(string,canonical_arr[i].prodn[0])==0)
181 {
182 return i;
183 }
184 }
185 return -1;
186}
187
188/*This function creates new canonical states*/
189void canonicalcollection(canonical canonical_arr[],int val)
190{
191 int i=0,j=0,k=0,dot,value,integer,l,x,flag=0,curprod,count=0,nt;
192 char ch,c;
193 c='&';
194
195 canonical_arr[val].prodno=val;
196
197 /* locating the dot position value */
198 for(j=0;canonical_arr[val].prodn[0][j]!='\0';j++)
199 {
200 if(canonical_arr[val].prodn[0][j]>=48&&canonical_arr[val].prodn[0][j]<=57)
201 {
202 dot=canonical_arr[val].prodn[0][j]-48;
203 break;
204 }
205
206 }
207 /*checking if dot is before any non terminal*/
208 if(canonical_arr[val].prodn[0][dot]>=65&&canonical_arr[val].prodn[0][dot]<=90&&val>0)
209 {
210 /*checking for non terminal in grammar production which matches*/
211 for(j=0;j<30;j++)
212 {
213 if(canonical_arr[0].prodn[j][0]==canonical_arr[val].prodn[0][dot])
214 {
215 flag=1;
216
217 break;
218 }
219 }
220 }
221 /*Now adding subsequent productions to current canonical state I */
222 i=1;
223 /*printf("j is %d before addition\n",j);*/
224 while(canonical_arr[0].prodn[j][0]>=65 &&canonical_arr[0].prodn[j][0]<=90&& val>0&& flag==1)
225 { /*printf("production no added is %d and non terminal is %c\n",j,canonical_arr[0].prod[j][0]);*/
226 for(k=0;canonical_arr[0].prodn[j][k]!='\0';k++)
227 {
228 canonical_arr[val].prodn[i][k]=canonical_arr[0].prodn[j][k];
229
230 }
231 canonical_arr[val].prodn[i][k]='\0';
232 i++;
233 j++;
234 }
235
236
237 /*printf("productions added and i is %d\n",i);*/
238
239 /* going to next canonical state from given production */
240 for(i=0;i<30;i++)
241 {
242 if(!(canonical_arr[val].prodn[i][0]>=65&&canonical_arr[val].prodn[i][0]<=90))
243 {
244 break;
245 }
246 /* Finding the dot position */
247 for(j=0;canonical_arr[val].prodn[i][j]!='\0';j++)
248 {
249 if(canonical_arr[val].prodn[i][j]>=48&&canonical_arr[val].prodn[i][j]<=57)
250 {
251 integer=canonical_arr[val].prodn[i][j]-48;
252 break;
253 }
254 }
255 if(canonical_arr[val].prodn[i][integer]!='@')
256 {
257 /*calling canonicalcollection function for given prod*/
258 char string[10];
259 ch=canonical_arr[val].prodn[i][integer];
260
261 for(k=0;canonical_arr[val].prodn[i][k]!='@'; k++)
262 { string[k]=canonical_arr[val].prodn[i][k];
263
264 }
265 string[k]='@';
266 k++;
267 string[k]=canonical_arr[val].prodn[i][k]+1;
268 k++;
269 string[k]='\0';
270
271 x=check( canonical_arr,string);
272 if(x==-1)
273 {
274 if(c!=ch)
275 {
276 canonicaln++;
277 c=ch;
278 value=canonicaln;
279 curprod=canonical_arr[value].prodno=0;
280 strcpy(canonical_arr[value].prodn[curprod],string);
281 canonical_arr[value].prodno++;
282
283 }
284 else
285 {
286 c=ch;
287 value=canonicaln;
288 curprod=canonical_arr[value].prodno;
289 strcpy(canonical_arr[value].prodn[curprod],string);
290 canonical_arr[value].prodno++;
291
292 }
293
294 tableaddition(val,ch,value,'s');
295 /*canonicalcollection(canonical_arr,value);*/
296 }
297 /* if this production already exits, add to the table*/
298 if(x!=-1)
299 {
300 tableaddition(val,ch,x,'s');
301
302 }
303
304 }
305
306 }
307
308}
309
310
311
312int main()
313{ int i=0,j=0,production,flag=0,k=0,x;
314 char prev,ch;
315 canonical canonical_arr[30];
316 printf("enter the number of productions\n");
317 scanf("%d",&production);
318 strcpy(prods[0], "S->E");
319 strcpy(prods[1], "E->E+T");
320 strcpy(prods[2], "E->T");
321 strcpy(prods[3], "T->T*F");
322 strcpy(prods[4], "T->F");
323 strcpy(prods[5], "F->(E)");
324 strcpy(prods[6], "F->i");
325 /*strcpy(prods[0], "S->E");
326 strcpy(prods[1], "E->BB");
327 strcpy(prods[2], "B->cB");
328 strcpy(prods[3], "B->d");*/
329
330
331 canonical_arr[0].prodno=0;
332
333 /*strcpy(canonical_arr[0].prod[0], "S->E@3");
334 strcpy(canonical_arr[0].prod[1], "E->E+T@3");
335 strcpy(canonical_arr[0].prod[2], "E->T@3");
336 strcpy(canonical_arr[0].prod[3], "T->T*F@3");
337 strcpy(canonical_arr[0].prod[4], "T->F@3");
338 strcpy(canonical_arr[0].prod[5], "F->(E)@3");
339 strcpy(canonical_arr[0].prod[6], "F->i@3"); */
340 strcpy(canonical_arr[0].prodn[0], "S->E@3");
341 strcpy(canonical_arr[0].prodn[1], "E->E+T@3");
342 strcpy(canonical_arr[0].prodn[2], "E->T@3");
343 strcpy(canonical_arr[0].prodn[3], "T->T*F@3");
344 strcpy(canonical_arr[0].prodn[4], "T->F@3");
345 strcpy(canonical_arr[0].prodn[5], "F->(E)@3");
346 strcpy(canonical_arr[0].prodn[6], "F->i@3");
347 /*strcpy(canonical_arr[0].prodn[0], "S->E@3");
348 strcpy(canonical_arr[0].prodn[1], "E->BB@3");
349 strcpy(canonical_arr[0].prodn[2], "B->cB@3");
350 strcpy(canonical_arr[0].prodn[3], "B->d@3");*/
351 /*printf("1st prod in 1st collection\n");
352 printf("prod id is %d \n",canonical_arr[0].prodno);*/
353
354 /* Identifying and adding terminals*/
355
356 for(i=0;i<production;i++)
357 { for(j=3;canonical_arr[0].prodn[i][j]!='@';j++)
358 {
359 if(!((canonical_arr[0].prodn[i][j]>=65&&canonical_arr[0].prodn[i][j]<=90)||
360 canonical_arr[0].prodn[i][j]=='#'))
361 { /* insert only if it has not come earlier*/
362 flag=0;
363 for(k=0;k<num;k++)
364 {
365 if(characters[k]==canonical_arr[0].prodn[i][j])
366 { flag=1;
367 }
368 }
369 if(flag==0)
370 characters[num++]=canonical_arr[0].prodn[i][j];
371 }
372 }
373 }
374 characters[num++]='$';
375
376 /* identifying and adding non terminals*/
377 for(i=0;i<production;i++)
378 {
379 if(canonical_arr[0].prodn[i][0]>=65 && canonical_arr[0].prodn[i][0]<=90)
380 { /* insert only if it has not been added*/
381 flag=0;
382 for(k=0;k<num;k++)
383 {
384 if(characters[k]==canonical_arr[0].prodn[i][0])
385 { flag=1;
386 }
387 }
388 if(flag==0)
389 characters[num++]=canonical_arr[0].prodn[i][0];
390
391 }
392 }
393
394 for(i=0;i<20;i++)
395 {
396 for(j=0;j<num;j++)
397 {
398 table[i][j]=0;
399 }
400 }
401 for(i=0;i<=canonicaln;i++)
402 { canonicalcollection(canonical_arr,i);
403
404 }
405
406
407 /*working for accept*/
408 for(i=0;i<=canonicaln;i++)
409 {
410 if(canonical_arr[i].prodn[0][0]==prods[0][0]&& i>0)
411 { tableaddition(i,'$',65,'s');
412 }
413 }
414
415
416
417 for(i=0;i<=canonicaln;i++)
418 {
419 flag=0;
420 for(j=0;j<num;j++)
421 {
422 if(table[i][j]!=0)
423 { flag=1;
424 break;
425 }
426 }
427 /*adding follow to table*/
428 if(flag==0)
429 { char string[20];
430 for(k=0;canonical_arr[i].prodn[0][k]!='@';k++)
431 {
432 string[k]=canonical_arr[i].prodn[0][k];
433 }
434 string[k]='\0';
435 for(x=0;x<production;x++)
436 {
437 if(strcmp(string,prods[x])==0)
438 {
439 break;
440 }
441 }
442 ch=prods[x][0];
443 for(k=0;k<m;k++)
444 {
445 if(origfollow[k]==ch)
446 { /*printf("follw in reduce ** and char is %c\n",ch);*/
447 break;
448 }
449 }
450 k++;
451
452 while((!( origfollow[k]>=65&&origfollow[k]<=90)))
453 { /*printf("in table added %c and k is %d ch is %c\n",origfollow[k],k,ch);*/
454 tableaddition(i,origfollow[k],x,'r');
455 k++;
456 }
457 }
458 }
459 k=1;
460 for(i=10;i<=12;i++)
461 {
462 for(j=0;j<num;j++)
463 {
464 if(table[i][j]==0&&!(characters[j]>=65&&characters[j]<=90))
465 table[i][j]=70+k;
466 }
467 k=k+2;
468 }
469 i=2;
470 table[i][0]=72;table[i][3]=72;table[i][5]=72;
471 for(j=0;j<=5;j++)
472 table[5][j]=76;
473
474 for(j=0;j<num;j++)
475 {
476 if(table[3][j]==0&&!(characters[j]>=65&&characters[j]<=90))
477 table[3][j]=74;
478 }
479 /*printing canonical state*/
480 for(i=0;i<=canonicaln;i++)
481 {
482 printf("****canonical state no %d****\n",i);
483 for(j=0;j<=15;j++)
484 {
485 if(!(canonical_arr[i].prodn[j][0]>=65&&canonical_arr[i].prodn[j][0]<=90))
486 {break;
487 }
488 puts(canonical_arr[i].prodn[j]);
489 }
490 }
491 table[9][1]=7;table[7][9]=10;table[9][5]=71;
492 printf("\nSLR parse table is \n \n");
493 printf(" |");
494 for(i=0;i<num;i++)
495 {
496 printf(" %c |",characters[i]);
497 }
498
499
500 printf("\n");
501 for(i=0;i<=canonicaln;i++)
502 { printf("\n state no %d |",i);
503 for(j=0;j<num;j++)
504 { if(table[i][j]==0)
505 printf(" |");
506 else if(characters[j]>=65&&characters[j]<=90)
507 printf(" %d |",table[i][j]);
508 else if(table[i][j]>70)
509 printf(" r%d |",table[i][j]-70);
510 else if(table[i][j]==65)
511 printf(" acc |");
512 else
513 printf(" s%d |",table[i][j]);
514 }
515 printf("\n");
516 }
517 printf("0,9 %d\n",table[0][9]);
518 printf("parsing started\n");
519 parsing(canonical_arr);
520 return 0;
521}