In this tutorial,you'll learn to program the algorithm to find the First of Dynamic Grammar. However, you can also build your own code for static grammar.
What is First of a Grammar ?
Consider, ('$' is for NULL)
E=E+T
E=T
T=T-E
T=F
T=id
F=lex
F=$
E=$
So, first of any grammar is defined by where a non terminal is heading to get a terminal.
In above case,
For E,
E goes to '$' and 'T', which can be included in First{E}={'$' and First{T}}
For T,
T heads to 'id' and 'F', which can be included in First{t}={'id' and First{F}}
For F,
F heads to 'lex' and '$', which can be included in First{t}={'$','lex'}
so,
First{F}={'$','lex'}
First{T}={'$','lex','id'}
First{E}={'$','lex','id'}
Program :
Output :
The Code for Follow is also added, but it's something fishy. Go figure it out, find the bug and get a chance to get featured with one program on C#ODE STUDIO and CS-BEANS.
So, get open up your IDE and start debugging.
What is First of a Grammar ?
Consider, ('$' is for NULL)
E=E+T
E=T
T=T-E
T=F
T=id
F=lex
F=$
E=$
So, first of any grammar is defined by where a non terminal is heading to get a terminal.
In above case,
For E,
E goes to '$' and 'T', which can be included in First{E}={'$' and First{T}}
For T,
T heads to 'id' and 'F', which can be included in First{t}={'id' and First{F}}
For F,
F heads to 'lex' and '$', which can be included in First{t}={'$','lex'}
so,
First{F}={'$','lex'}
First{T}={'$','lex','id'}
First{E}={'$','lex','id'}
Program :
1: #include"ctype.h"
2: #include"string.h"
3: #include"stdio.h"
4: char gram[10][10],vFirst[5];
5: int elem[10],size,fPt,k=0;
6: int getGram(){
7: char ch; int i,j,k;
8: printf("\nEnter Number of Rule : ");
9: scanf("%d",&size);
10: printf("\nEnter Grammar as E=E+B \n");
11: for(i=0;i<size;i++){
12: scanf("%s%c",gram[i],&ch);
13: elem[i]=strlen(gram[i]);
14: }
15: printf("\nGrammar is :\n");
16: for(i=0;i<size;i++)
17: printf("\n%s",gram[i]);
18: }
19: int funcFirst(char victim){
20: int j,i;
21: if(!(isupper(victim)))
22: vFirst[k++]=victim;
23: else
24: for(j=0;j<size;j++){
25: if(gram[j][0]==victim){
26: if(gram[j][2]=='$')
27: vFirst[k++]='$';
28: else if(islower(gram[j][2]))
29: vFirst[k++]=gram[j][2];
30: else
31: funcFirst(gram[j][2]);
32: }
33: }
34: }
35: int main(){
36: int i,j,k;
37: getGram();
38: printf("\nEnter the Non Terminal : ");
39: char nt;
40: scanf("%c",&nt);
41: funcFirst(nt);
42: printf("\n{ ");
43: for(i=0;i<strlen(vFirst);i++)
44: printf(" %c",vFirst[i]);
45: printf(" }\n");
46: }
Output :
The Code for Follow is also added, but it's something fishy. Go figure it out, find the bug and get a chance to get featured with one program on C#ODE STUDIO and CS-BEANS.
1: #include"stdio.h"
2: #include"string.h"
3: #include"ctype.h"
4: int n=0,m=0,i=0,j=0,k=0;
5: char vGram[10][10], vFirst[5], vFollow[10];
6: int funcFirst(char);
7: int funcFirst_F(char);
8: int funcFollow(char);
9: int funcFirst(char victim){
10: int j,i;
11: if(!(isupper(victim)))
12: vFirst[k++]=victim;
13: for(j=0;j<n;j++){
14: if(vGram[j][0]==victim){
15: if(vGram[j][2]=='$')
16: vFirst[k++]='$';
17: else if(islower(vGram[j][2]))
18: vFirst[k++]=vGram[j][2];
19: else
20: funcFirst(vGram[j][2]);
21: }
22: }
23: printf("\n{ ");
24: for(i=0;i<strlen(vFirst);i++)
25: printf(" %c",vFirst[i]);
26: printf(" }\n");
27: }
28: int funcFirst_F(char victim){
29: int j;
30: if(!(isupper(victim)))
31: vFollow[k++]=victim;
32: for(j=0;j<n;j++){
33: if(vGram[j][0]==victim){
34: if(vGram[j][2]=='$')
35: funcFollow(vGram[j][0]);
36: else if(islower(vGram[j][2]))
37: vFollow[k++]=vGram[j][2];
38: else
39: funcFirst_F(vGram[j][2]);
40: }
41: }
42: }
43: int funcFollow(char victim){
44: int i=0,g=0;
45: if(vGram[0][0]==victim)
46: vFollow[m++]='$';
47: for(i=0;i<n;i++){
48: for(j=2;j<strlen(vGram[i]); j++){
49: if(vGram[i][j]==victim){
50: if(vGram[i][j+1]!='\0')
51: funcFirst_F(vGram[i][j+1]);
52: if(vGram[i][j+1]=='\0' && victim!=vGram[1][0])
53: funcFollow(vGram[i][0]);
54: }
55: }
56: }
57: printf("\n{ ");
58: for(g=0;g<strlen(vFollow);g++)
59: printf(" %c",vFollow[g]);
60: printf(" }\n");
61: }
62: int main(){
63: printf("\nProgram contains bug in Follow Module. ");
64: printf("\nVisit http://www.csbeans.com/ to submit resolved one.\n\n");
65: int i,z,choice,cont=1;
66: char ch, c;
67: printf("Enter the number of production : ");
68: scanf("%d",&n);
69: printf("Enter production as 'E=AB' and '$' for null\n");
70: for(i=0;i<n;i++)
71: scanf("%s%c",vGram[i],&ch);
72: while(cont==1){
73: printf("Enter Victim Character : ");
74: scanf("%c",&c);
75: printf("Enter Choice : 1:First 2:Follow : ");
76: scanf("%d",&choice);
77: switch(choice){
78: case 1: funcFirst(c);
79: break;
80: case 2: funcFollow(c);
81: break;
82: }
83: printf("\n 1:continue");
84: scanf("%d%c",&cont,&ch);
85: }
86: printf("\n\n\t------PROGRAMMED AT C#ODE STUDIO------");
87: } So, get open up your IDE and start debugging.
0 comments:
Post a Comment