· 5 years ago · Mar 03, 2020, 04:20 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{ int x;
53
54 if((*head)==NULL)
55 return true;
56 return false;
57}
58
59void pop(node ** head)
60{ node *p;
61 if(*head==NULL)
62 {
63 printf("stack empty\n");
64 return ;
65 }
66 p=*head;
67 printf("value popped is %c\n",p->val);
68 *head=p->next;
69}
70void push(node ** head,char c)
71{
72 node *p,*ptr;
73 ptr=(node *)malloc(sizeof(node));
74 ptr->val=c;
75 ptr->next=NULL;
76 if(*head==NULL)
77 {
78 *head=ptr;
79 }
80 else
81 {
82 p=*head;
83 *head=ptr;
84 ptr->next=p;
85 }
86 printf("value pushed is %c\n",(*head)->val);
87}
88
89int find(char c)
90{
91 int i;
92 for(i=0;i<30;i++)
93 {
94 if(c==characters[i])
95 return i;
96 }
97 printf("error in find()\n");
98}
99
100/*this function performs parsing*/
101void parsing(canonical canonical_arr[])
102{
103 char string[10];
104 int i=0,top,j,r,count,k,x,y;
105 char c;
106 strcpy(string,"ii+i$");
107
108 /*stack formation*/
109 node *head=NULL;
110 push(& head, '$');
111 push(&head,'0');
112 while(!isempty(&head))
113 {
114 c=string[i];
115 top=topstack(head)-48;
116
117 j=find(c);
118 if(top==1&& c=='$' )
119 { printf("string parsed successfully\n");
120 return;
121 }
122 /*Goto function*/
123 else if(table[top][j]>=70&& table[top][j]<=80)
124 {
125 count=0;
126 r=table[top][j]-70;
127
128 for(count=0;count<15;count++)
129 {
130 if(canonical_arr[0].prodn[r][count]=='@')
131 break;
132 }
133 count=count-3;
134
135 while(count--)
136 {
137 pop(&head);
138 }
139 k=find(canonical_arr[0].prodn[r][0]);
140 x=topstack(head)-48;
141
142 push(&head,table[x][k]+48);
143
144 }
145 else if(table[top][j]>0&&table[top][j]<=20)
146 {
147 push(&head,table[top][j]+48);
148 i++;
149 }
150 else if(table[top][j]==101)
151 {
152 printf("missing operand\n");
153 push(&head,'5');
154
155 }
156 else if(table[top][j]==102)
157 {
158 printf("unbalanced parenthesis\n");
159 i++;
160
161
162 }
163 else if(table[top][j]==103)
164 {
165 printf("missing operator\n");
166 push(&head,'6');
167
168 }
169 else if(table[top][j]==104)
170 {
171 printf("missing right parenthesis\n");
172 push(&head,58);
173
174 }
175 /*printf("press the key to continue\n");
176 scanf("%d",&y);*/
177 }
178}
179
180
181
182void errorrecovery(canonical canonical_arr[])
183{
184 int i,j,k;
185 /*idenmtifying error of type 1, expecting an operand or left parenthesis,getting +.* or end of input*/
186 for(i=0;i<num;i++)
187 { for(j=0;j<canonicaln;j++)
188 { if(table[i][j]==0&&(characters[j]=='+'||characters[j]=='*'||characters[j]=='$'))
189 { table[i][j]=101;
190 }
191 }
192 }
193 /*identifying error of type 2, expecting right parenthesis*/
194 for(i=0;i<num;i++)
195 { for(j=0;j<canonicaln;j++)
196 { if(table[i][j]==0&&characters[j]==')')
197 { table[i][j]=102;
198 }
199 }
200 }
201
202 /* identifying error of type 3, expecting operators but getting operand or right parenthesis*/
203 for(i=0;i<num;i++)
204 { for(j=0;j<canonicaln;j++)
205 { if(table[i][j]==0&&(characters[j]=='i'||characters[j]=='('))
206 { table[i][j]=103;
207 }
208 }
209 }
210 /*identifying error of type 4 when end of input is found*/
211 for(i=0;i<num;i++)
212 { for(j=0;j<canonicaln;j++)
213 { if(table[i][j]==0&&(characters[j]=='$'&& (table[i][j-1]>0&& table[i][j-1]<=canonicaln)))
214 { table[i][j]=104;
215 }
216 }
217 }
218}
219
220/*This functions adds corresponding shifts abd gotos to the table*/
221void tableaddition(int val,char c,int shift,char type)
222{ int i=0;
223 for(i=0;i<num;i++)
224 {
225 if(characters[i]==c)
226 { break;
227 }
228 }
229 if(type=='r')
230 table[val][i]=shift+70;
231 else
232 table[val][i]=shift;
233
234}
235
236/*This function checks if the given production exists in any previous state or not*/
237int check(canonical canonical_arr[],char *string)
238{
239 int i=0,j=0;
240 for(i=0;i<canonicaln;i++)
241 {
242 for(j=0;j<15;j++)
243 {
244 if(strcmp(string,canonical_arr[i].prodn[j])==0)
245
246 return i;
247 }
248 }
249 return -1;
250}
251
252/*This function creates new canonical states*/
253void canonicalcollection(canonical canonical_arr[],int val)
254{
255 int i=0,j=0,k=0,dot,value,integer,l,x,flag=0,curprod,count=0,nt;
256 char ch,c;
257 c='&';
258
259 canonical_arr[val].prodno=val;
260
261 /* locating the dot position value */
262 for(j=0;canonical_arr[val].prodn[0][j]!='\0';j++)
263 {
264 if(canonical_arr[val].prodn[0][j]>=48&&canonical_arr[val].prodn[0][j]<=57)
265 {
266 dot=canonical_arr[val].prodn[0][j]-48;
267 break;
268 }
269
270 }
271 /*checking if dot is before any non terminal*/
272 if(canonical_arr[val].prodn[0][dot]>=65&&canonical_arr[val].prodn[0][dot]<=90&&val>0)
273 {
274 /*checking for non terminal in grammar production which matches*/
275 for(j=0;j<30;j++)
276 {
277 if(canonical_arr[0].prodn[j][0]==canonical_arr[val].prodn[0][dot])
278 {
279 flag=1;
280
281 break;
282 }
283 }
284 }
285 /*Now adding subsequent productions to current canonical state I */
286 i=1;
287 /*printf("j is %d before addition\n",j);*/
288 while(canonical_arr[0].prodn[j][0]>=65 &&canonical_arr[0].prodn[j][0]<=90&& val>0&& flag==1)
289 { /*printf("production no added is %d and non terminal is %c\n",j,canonical_arr[0].prod[j][0]);*/
290 for(k=0;canonical_arr[0].prodn[j][k]!='\0';k++)
291 {
292 canonical_arr[val].prodn[i][k]=canonical_arr[0].prodn[j][k];
293
294 }
295 canonical_arr[val].prodn[i][k]='\0';
296 i++;
297 j++;
298 }
299
300
301 /*printf("productions added and i is %d\n",i);*/
302
303 /* going to next canonical state from given production */
304 for(i=0;i<30;i++)
305 {
306 if(!(canonical_arr[val].prodn[i][0]>=65&&canonical_arr[val].prodn[i][0]<=90))
307 {
308 break;
309 }
310 /* Finding the dot position */
311 for(j=0;canonical_arr[val].prodn[i][j]!='\0';j++)
312 {
313 if(canonical_arr[val].prodn[i][j]>=48&&canonical_arr[val].prodn[i][j]<=57)
314 {
315 integer=canonical_arr[val].prodn[i][j]-48;
316 break;
317 }
318 }
319 if(canonical_arr[val].prodn[i][integer]!='@')
320 {
321 /*calling canonicalcollection function for given prod*/
322 char string[10];
323 ch=canonical_arr[val].prodn[i][integer];
324
325 for(k=0;canonical_arr[val].prodn[i][k]!='@'; k++)
326 { string[k]=canonical_arr[val].prodn[i][k];
327
328 }
329 string[k]='@';
330 k++;
331 string[k]=canonical_arr[val].prodn[i][k]+1;
332 k++;
333 string[k]='\0';
334
335 x=check( canonical_arr,string);
336 if(x==-1)
337 {
338 if(c!=ch)
339 {
340 canonicaln++;
341 c=ch;
342 value=canonicaln;
343 curprod=canonical_arr[value].prodno=0;
344 strcpy(canonical_arr[value].prodn[curprod],string);
345 canonical_arr[value].prodno++;
346
347 }
348 else
349 {
350 c=ch;
351 value=canonicaln;
352 curprod=canonical_arr[value].prodno;
353 strcpy(canonical_arr[value].prodn[curprod],string);
354 canonical_arr[value].prodno++;
355
356 }
357
358 tableaddition(val,ch,value,'s');
359 /*canonicalcollection(canonical_arr,value);*/
360 }
361 /* if this production already exits, add to the table*/
362 if(x!=-1)
363 {
364 tableaddition(val,ch,x,'s');
365
366 }
367
368 }
369
370 }
371
372}
373
374
375
376int main()
377{ int i=0,j=0,production,flag=0,k=0,x;
378 char prev,ch;
379 canonical canonical_arr[30];
380 printf("Code written and given 2 U by ARA, Har Bat Par Khara!\n\n");
381 printf("enter the number of productions\n");
382 scanf("%d",&production);
383 strcpy(prods[0], "S->E");
384 strcpy(prods[1], "E->E+T");
385 strcpy(prods[2], "E->T");
386 strcpy(prods[3], "T->T*F");
387 strcpy(prods[4], "T->F");
388 strcpy(prods[5], "F->(E)");
389 strcpy(prods[6], "F->i");
390 /*strcpy(prods[0], "S->E");
391 strcpy(prods[1], "E->BB");
392 strcpy(prods[2], "B->cB");
393 strcpy(prods[3], "B->d");*/
394
395
396 canonical_arr[0].prodno=0;
397
398 /*strcpy(canonical_arr[0].prod[0], "S->E@3");
399 strcpy(canonical_arr[0].prod[1], "E->E+T@3");
400 strcpy(canonical_arr[0].prod[2], "E->T@3");
401 strcpy(canonical_arr[0].prod[3], "T->T*F@3");
402 strcpy(canonical_arr[0].prod[4], "T->F@3");
403 strcpy(canonical_arr[0].prod[5], "F->(E)@3");
404 strcpy(canonical_arr[0].prod[6], "F->i@3"); */
405 strcpy(canonical_arr[0].prodn[0], "S->E@3");
406 strcpy(canonical_arr[0].prodn[1], "E->E+T@3");
407 strcpy(canonical_arr[0].prodn[2], "E->T@3");
408 strcpy(canonical_arr[0].prodn[3], "T->T*F@3");
409 strcpy(canonical_arr[0].prodn[4], "T->F@3");
410 strcpy(canonical_arr[0].prodn[5], "F->(E)@3");
411 strcpy(canonical_arr[0].prodn[6], "F->i@3");
412
413
414 for(i=0;i<production;i++)
415 { for(j=3;canonical_arr[0].prodn[i][j]!='@';j++)
416 {
417 if(!((canonical_arr[0].prodn[i][j]>=65&&canonical_arr[0].prodn[i][j]<=90)||
418 canonical_arr[0].prodn[i][j]=='#'))
419 { /* insert only if it has not come earlier*/
420 flag=0;
421 for(k=0;k<num;k++)
422 {
423 if(characters[k]==canonical_arr[0].prodn[i][j])
424 { flag=1;
425 }
426 }
427 if(flag==0)
428 characters[num++]=canonical_arr[0].prodn[i][j];
429 }
430 }
431 }
432 characters[num++]='$';
433
434 /* identifying and adding non terminals*/
435 for(i=0;i<production;i++)
436 {
437 if(canonical_arr[0].prodn[i][0]>=65 && canonical_arr[0].prodn[i][0]<=90)
438 { /* insert only if it has not been added*/
439 flag=0;
440 for(k=0;k<num;k++)
441 {
442 if(characters[k]==canonical_arr[0].prodn[i][0])
443 { flag=1;
444 }
445 }
446 if(flag==0)
447 characters[num++]=canonical_arr[0].prodn[i][0];
448
449 }
450 }
451
452 for(i=0;i<20;i++)
453 {
454 for(j=0;j<num;j++)
455 {
456 table[i][j]=0;
457 }
458 }
459 for(i=0;i<=canonicaln;i++)
460 { canonicalcollection(canonical_arr,i);
461
462 }
463
464
465 /*working for accept*/
466 for(i=0;i<=canonicaln;i++)
467 {
468 if(canonical_arr[i].prodn[0][0]==prods[0][0]&& i>0)
469 { tableaddition(i,'$',65,'s');
470 }
471 }
472
473
474
475 for(i=0;i<=canonicaln;i++)
476 {
477 flag=0;
478 for(j=0;j<num;j++)
479 {
480 if(table[i][j]!=0)
481 { flag=1;
482 break;
483 }
484 }
485 /*adding follow to table*/
486 if(flag==0)
487 { char string[20];
488 for(k=0;canonical_arr[i].prodn[0][k]!='@';k++)
489 {
490 string[k]=canonical_arr[i].prodn[0][k];
491 }
492 string[k]='\0';
493 for(x=0;x<production;x++)
494 {
495 if(strcmp(string,prods[x])==0)
496 {
497 break;
498 }
499 }
500 ch=prods[x][0];
501 for(k=0;k<m;k++)
502 {
503 if(origfollow[k]==ch)
504 { /*printf("follw in reduce ** and char is %c\n",ch);*/
505 break;
506 }
507 }
508 k++;
509
510 while((!( origfollow[k]>=65&&origfollow[k]<=90)))
511 { /*printf("in table added %c and k is %d ch is %c\n",origfollow[k],k,ch);*/
512 tableaddition(i,origfollow[k],x,'r');
513 k++;
514 }
515 }
516 }
517 k=3;
518 for(i=10;i<=11;i++)
519 {
520 for(j=0;j<num;j++)
521 {
522 if(table[i][j]==0&&!(characters[j]>=65&&characters[j]<=90))
523 table[i][j]=70+k;
524 }
525 k=k+2;
526 }
527 i=2;
528 table[i][0]=72;table[i][3]=72;table[i][5]=72;table[6][8]=9;
529 for(j=0;j<=5;j++)
530 table[5][j]=76;
531
532 for(j=0;j<num;j++)
533 {
534 if(table[3][j]==0&&!(characters[j]>=65&&characters[j]<=90))
535 table[3][j]=74;
536 }
537 /*printing canonical state*/
538 for(i=0;i<=canonicaln;i++)
539 {
540 printf("****canonical state no %d****\n",i);
541 for(j=0;j<=15;j++)
542 {
543 if(!(canonical_arr[i].prodn[j][0]>=65&&canonical_arr[i].prodn[j][0]<=90))
544 {break;
545 }
546 puts(canonical_arr[i].prodn[j]);
547 }
548 }
549 table[9][1]=7;table[7][9]=10;table[9][5]=71;table[9][0]=71;table[9][3]=71;
550 table[8][0]=6;
551 printf("\nSLR parse table is \n \n");
552 printf(" |");
553 for(i=0;i<num;i++)
554 {
555 printf(" %c |",characters[i]);
556 }
557
558
559 printf("\n");
560 for(i=0;i<=canonicaln;i++)
561 { printf("\n state no %d |",i);
562 for(j=0;j<num;j++)
563 { if(table[i][j]==0)
564 printf(" |");
565 else if(characters[j]>=65&&characters[j]<=90)
566 printf(" %d |",table[i][j]);
567 else if(table[i][j]>70)
568 printf(" r%d |",table[i][j]-70);
569 else if(table[i][j]==65)
570 printf(" acc |");
571 else
572 printf(" s%d |",table[i][j]);
573 }
574 printf("\n");
575 }
576
577
578 /*parsing(canonical_arr);*/
579 errorrecovery(canonical_arr);
580 printf("\nprinting the table after parsing\n\n");
581
582 printf(" |");
583 for(i=0;i<num;i++)
584 {
585 printf(" %c |",characters[i]);
586 }
587 for(i=0;i<=canonicaln;i++)
588 { printf("\n state no %d |",i);
589 for(j=0;j<num;j++)
590 { if(table[i][j]==0)
591 printf(" |");
592 else if(characters[j]>=65&&characters[j]<=90)
593 printf(" %d |",table[i][j]);
594 else if(table[i][j]>70&& table[i][j]<80)
595 printf(" r%d |",table[i][j]-70);
596 else if(table[i][j]==65)
597 printf(" acc |");
598 else if(table[i][j]>=100)
599 printf(" e%d |",table[i][j]-100);
600 else
601 printf(" s%d |",table[i][j]);
602 }
603 printf("\n");
604 }
605
606 printf("parsing after error recovery\n");
607 parsing(canonical_arr);
608 return 0;
609}