Let us learn how to find first and follow of a grammar in C programming. There are two different C programs to find first and follow of non-terminals in a given grammar.
The first of a grammar can be written using structures as well. Here, we have used array data structure to calculate first and follow in C programming.
Must Read: Difference Between Compiler and Interpreter
What is First and Follow?
The first and follow sets are used in compiler designing process. The first set is used in LL parsers which are top – down parsers that read or interpret from left to right.
The follow set is used in LR parsers which are bottom-up parsers that read or interpret from right to left.
The LL parsers use leftmost derivations whereas the LR parsers use rightmost derivations. A predictive parser is constructed using first and follow sets that are associated with Grammar G.
Must Read: C Program For Recursive Descent Parsing
Note: This C program to find First and Follow sets of a Grammar using Array is compiled with GNU GCC compiler and developed using gEdit Editor in Linux Ubuntu operating system.
C Program To Find First of a Given Grammar using Array
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include<stdio.h> #include<ctype.h> void Find_First(char[], char); void Array_Manipulation(char[], char); int limit; char production[25][25]; int main() { char option; char ch; char array[25]; int count; printf("\nEnter Total Number of Productions:\t"); scanf("%d", &limit); for(count = 0; count < limit; count++) { printf("\nValue of Production Number [%d]:\t", count + 1); scanf("%s", production[count]); } do { printf("\nEnter a Value to Find First:\t"); scanf(" %c", &ch); Find_First(array, ch); printf("\nFirst Value of %c:\t{ ", ch); for(count = 0; array[count] != '\0'; count++) { printf(" %c ", array[count]); } printf("}\n"); printf("To Continue, Press Y:\t"); scanf(" %c", &option); }while(option == 'y' || option == 'Y'); return 0; } void Find_First(char* array, char ch) { int count, j, k; char temporary_result[20]; int x; temporary_result[0] = '\0'; array[0] = '\0'; if(!(isupper(ch))) { Array_Manipulation(array, ch); return ; } for(count = 0; count < limit; count++) { if(production[count][0] == ch) { if(production[count][2] == '$') { Array_Manipulation(array, '$'); } else { j = 2; while(production[count][j] != '\0') { x = 0; Find_First(temporary_result, production[count][j]); for(k = 0; temporary_result[k] != '\0'; k++) { Array_Manipulation(array,temporary_result[k]); } for(k = 0; temporary_result[k] != '\0'; k++) { if(temporary_result[k] == '$') { x = 1; break; } } if(!x) { break; } j++; } } } } return; } void Array_Manipulation(char array[], char value) { int temp; for(temp = 0; array[temp] != '\0'; temp++) { if(array[temp] == value) { return; } } array[temp] = value; array[temp + 1] = '\0'; } |
Output
Must Read: Lexical Analyser in C Programming
C Program To Find Follow of a Grammar using Array
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | #include<stdio.h> #include<ctype.h> #include<string.h> int limit, x = 0; char production[10][10], array[10]; void find_first(char ch); void find_follow(char ch); void Array_Manipulation(char ch); int main() { int count; char option, ch; printf("\nEnter Total Number of Productions:\t"); scanf("%d", &limit); for(count = 0; count < limit; count++) { printf("\nValue of Production Number [%d]:\t", count + 1); scanf("%s", production[count]); } do { x = 0; printf("\nEnter production Value to Find Follow:\t"); scanf(" %c", &ch); find_follow(ch); printf("\nFollow Value of %c:\t{ ", ch); for(count = 0; count < x; count++) { printf("%c ", array[count]); } printf("}\n"); printf("To Continue, Press Y:\t"); scanf(" %c", &option); }while(option == 'y' || option == 'Y'); return 0; } void find_follow(char ch) { int i, j; int length = strlen(production[i]); if(production[0][0] == ch) { Array_Manipulation('$'); } for(i = 0; i < limit; i++) { for(j = 2; j < length; j++) { if(production[i][j] == ch) { if(production[i][j + 1] != '\0') { find_first(production[i][j + 1]); } if(production[i][j + 1] == '\0' && ch != production[i][0]) { find_follow(production[i][0]); } } } } } void find_first(char ch) { int i, k; if(!(isupper(ch))) { Array_Manipulation(ch); } for(k = 0; k < limit; k++) { if(production[k][0] == ch) { if(production[k][2] == '$') { find_follow(production[i][0]); } else if(islower(production[k][2])) { Array_Manipulation(production[k][2]); } else { find_first(production[k][2]); } } } } void Array_Manipulation(char ch) { int count; for(count = 0; count <= x; count++) { if(array[count] == ch) { return; } } array[x++] = ch; } |
Output
If you have any compilation error or doubts in this first and follow of a grammar program in C language, let us know about it in the comment section below.
Bottom-Up and To-Down Parsers uses follow and first functions to make a parsing tree from a given grammar G.
This code finally works for computation of follow and first for designing my compiler.
great to know
A switch case or a while loop would be much easier to understand. Do while confuses a lot.
plz help me……………, i could not understand any code,plz forgive me,plz help me…………plz
,,,,,,,,,,,,help
syed you need to see the program from left corner or right corner .then u can know about it
You can also use Extended Backus Naur Form to automatically calculate Follow and First of a Grammar.
This program for follow is not working . It gives segmentation fault . Please Help. My code is similar to you . Input is
8
E=TA
A=+TA
A=$
T=FB
B=*FB
B=$
F=a
F=(E)
First I give E as input to find follow and then A it gives correct output for E but gives segementaton fault for A
This is one of the best explanations of parsing with first and follow set program in c programming language. Thank you so much CodingAlpha team.
If we use the following for loop for(count = 1; count <= limit; count++) in this first of grammar c program, will it make any difference?
Is the first and follow concept used in compiler designing?
For learning compiler designing, you must read Compiler Design – K. Muneeswaran. Its a very good book available on Amazon.
does this program works for epsilon symbol ?? if so how can i specify them
i got a problem while running the follow program, the program was stopped when the find_follow function was calling.i can’t find that what issue is there.
How to enter epsilon in production?
Thanks for such a intuitive code and well indented .
Excellent job