First and Follow programs in C
First and follow functions are not only fixed to the C programming language they can also use in other languages in parsing algorithms. Specifically in the creation of predictive parsers for context-free grammar.
These are related to the compiler design, parsing is the process of analyzing the structure of a program written in any programming language and checking whether it contains any error, checking whether the program is following the grammar rules or not. In this type of parsing algorithm, the program is broken down into smaller parts like statements, conditions, declarations, and operations and uses functions like first and follow and others to check the syntax and structure of the program written in any language.
Terminology related to this concept:
Terminal symbols:
Terminal symbols are tokens in the language. We can simply call it basic units or lexical elements of a programming language. These are the ending symbols in the grammar, operators keywords, identifiers, or punction marks are usually the terminal symbols.
Example: In the expression "v + 8", the terminal symbols are "v", "+", and "8".
Non-Terminal Symbols:
These non-terminal symbols are the syntactic symbols elements in grammar, they are again expanded into by using the first and following elements in the grammar. These are not at the end of the grammar, non-terminal symbols are used to determine the first and following sets.
Example: In a simple arithmetic expression grammar, a non-terminal symbol could be "expression", which can be further expanded into "term + expression" or "term – expression".
Production rules:
Production rules define the valid expansions and these are used to manipulate the non-terminal symbols in the grammar. Production rules are the building blocks of grammar. These are used to determine the possible first and follow programs.
Example: In a grammar for arithmetic expressions, a production rule could be "expression -> term + expression" which means an expression can be composed of a term followed by a plus(+) operator and another expression
First Set:
The "first" set of a non-terminal symbol in grammar tells us the possible first symbols that can appear when using that symbol. It represents the valid starting symbols for a particular construct.
Example: If we have a rule A -> BCD, the first set of A would include the first symbols of B, C, and D, and these are the symbols that can start a string derived from A.
Follow Set:
The "follow" set of a non-terminal symbol in grammar tells us the possible symbols that can come immediately after occurrences of that symbol. It represents the valid symbols that can follow a particular construct.
Example: If we have a rule A -> XYZ, the following set of A would include the symbols that can come right after A in any string derived from the grammar. These symbols can appear immediately after occurrences of A.
First program explanations with an example:
In the context of a C compiler, the "first" set is not a built-in function, but it is a concept used during the lexical analysis and parsing phases of the compilation process. The compiler analyses the source code written in C and breaks it down into tokens (lexical analysis) and then builds a parse tree or abstract syntax tree (parsing) based on the grammar rules of the C language.
The "first" set of a symbol in grammar tells us what possible starting symbols that can appear when we use that symbol in our program. Let's consider an example to make it clearer.
S -> if (condition) then statement
This rule says that an "if" statement in our language starts with the keyword "if", followed by an opening parenthesis "(", then a condition, a closing parenthesis ")", the keyword "then", and finally a statement.
Now, if we want to find the "first" of the non-terminal symbol "S", which represents the "if" statement, we need to figure out what can be the first symbol of any valid "if" statement in our language.
In this case, the first symbol is the keyword "if" because every "if" statement must start with "if". Therefore, the "first" of "S" is {if}.
The "first" program helps us understand what symbols we should expect at the beginning of a specific construct in our language. It helps us build a parser that can analyze and interpret programs correctly.
Example for first sets:
S -> A B
A -> a b | ε
B -> c d | ε
First Set for S:
The production rule for S is S -> A B. To find the first set of S, we need to look at the first set of A and B. The first set of A includes "a" and ε (empty string), and the first set of B includes "c" and ε. Therefore, the first set of S is { a, c, ε }.
First Set for A:
The production rule for A is A -> a b | ε. The first set of A includes "a" and ε. Therefore, the first set of A is { a, ε }.
First Set for B:
The production rule for B is B -> c d | ε. The first set of B includes "c" and ε. Therefore, the first set of B is { c, ε }.
According to this grammar, the first set of S is { a, c, ε }, the first set of A is { a, ε }, and the first set of B is { c, ε }.
The "first" sets help us understand the possible starting symbols for each non-terminal in the grammar. They are essential in parsing techniques for building parsers that can correctly analyze and interpret programs based on grammar rules.
Example for follow set:
E → T + E
E → T
T → F * T
T → F
F → (E)
F → id
In this grammar, E, T, and F are non-terminal symbols, while +, *, (, ), and id are terminal symbols representing addition, multiplication, parentheses, and identifiers respectively.
Now, let's focus on the non-terminal symbol E. To determine its "follow" set, we look at the grammar rules and identify where E appears on the right-hand side. In this case, E appears on the right-hand side of rule 1. We know that after the non-terminal E, we can expect either the + symbol or the end of the expression ($ symbol) because E → T + E is a valid production. Therefore, the "follow" set for E would include the terminals + and $.
Program 1:
Code to calculate first set:
#include <ctype.h>
#include <stdio.h>
#include <string.h>
void first_set_function(char, int, int);
int count, n = 0;
// Stores the final result
// of the First Sets
char first_set_arr[10][100];
int m = 0;
// Stores the production_rules_arr rules
char production_rules_arr[10][10];
char f[10], first[10];
int k;
char ck;
int e;
int main(int argc, char** argv)
{
int jm = 0;
int km = 0;
int i, choice;
char c, ch;
count = 8;
// The Input grammar
strcpy(production_rules_arr[0], "A=BxC");
strcpy(production_rules_arr[1], "A=Dy");
strcpy(production_rules_arr[2], "B=q");
strcpy(production_rules_arr[3], "B=#");
strcpy(production_rules_arr[4], "C=p");
strcpy(production_rules_arr[5], "C=#");
strcpy(production_rules_arr[6], "D=oy");
strcpy(production_rules_arr[7], "D=CB");
int kay;
char done[count];
int ptr = -1;
// Initializing the first_set_arr array
for (k = 0; k < count; k++) {
for (kay = 0; kay < 100; kay++) {
first_set_arr[k][kay] = '!';
}
}
int point1 = 0, point2, xxx;
for (k = 0; k < count; k++) {
c = production_rules_arr[k][0];
point2 = 0;
xxx = 0;
// Checking if First of c has
// already been calculated
for (kay = 0; kay <= ptr; kay++)
if (c == done[kay])
xxx = 1;
if (xxx == 1)
continue;
// Function call
first_set_function(c, 0, 0);
ptr += 1;
// Adding c to the calculated list
done[ptr] = c;
printf("\n First(%c) = { ", c);
first_set_arr[point1][point2++] = c;
// Printing the First Sets of the grammar
for (i = 0 + jm; i < n; i++) {
int lark = 0, chk = 0;
for (lark = 0; lark < point2; lark++) {
if (first[i] == first_set_arr[point1][lark]) {
chk = 1;
break;
}
}
if (chk == 0) {
printf("%c, ", first[i]);
first_set_arr[point1][point2++] = first[i];
}
}
printf("}\n");
jm = n;
point1++;
}
}
void first_set_function(char c, int q1, int q2)
{
int j;
// The case where we
// encounter a Terminal
if (!(isupper(c))) {
first[n++] = c;
}
for (j = 0; j < count; j++) {
if (production_rules_arr[j][0] == c) {
if (production_rules_arr[j][2] == '#') {
if (production_rules_arr[q1][q2] == '\0')
first[n++] = '#';
else if (production_rules_arr[q1][q2] != '\0'
&& (q1 != 0 || q2 != 0)) {
// Recursion to calculate First of New
// Non-Terminal we encounter after
// epsilon
first_set_function(production_rules_arr[q1][q2], q1,
(q2 + 1));
}
else
first[n++] = '#';
}
else if (!isupper(production_rules_arr[j][2])) {
first[n++] = production_rules_arr[j][2];
}
else {
// Recursion to calculate First of
// New Non-Terminal we encounter
// at the beginning
first_set_function(production_rules_arr[j][2], j, 3);
}
}
}
}
Output:
First(A) = { q, x, o, p, #, }
First(B) = { q, #, }
First(C) = { p, #, }
First(D) = { o, p, q, #, }
Now, we add the code to the beginning code for getting both the first set and follow set in one code. For this, we have to add some functions to the above code which are used to calculate the following setin compiler design when you are given the production rules.
Program 2:
// C program to calculate the First and
// Follow sets of a given grammar
#include <ctype.h>
#include <stdio.h>
#include <string.h>
// Functions to calculate Follow
void follow_first_function(char, int, int);
void follow(char c);
// Function to calculate First
void findfirst(char, int, int);
int count, n = 0;
// Stores the final result
// of the First Sets
char first_set_Arr[10][100];
// Stores the final result
// of the Follow Sets
char follow_set_Arr[10][100];
int m = 0;
// Stores the production_rules_arr rules
char production_rules_arr[10][10];
char f[10], first[10];
int k;
char ck;
int e;
int main(int argc, char** argv)
{
int jm = 0;
int km = 0;
int i, choice;
char c, ch;
count = 8;
// The Input grammar
strcpy(production_rules_arr[0], "A=BxC");
strcpy(production_rules_arr[1], "A=Dy");
strcpy(production_rules_arr[2], "B=q");
strcpy(production_rules_arr[3], "B=#");
strcpy(production_rules_arr[4], "C=p");
strcpy(production_rules_arr[5], "C=#");
strcpy(production_rules_arr[6], "D=oy");
strcpy(production_rules_arr[7], "D=CB");
int kay;
char done[count];
int ptr = -1;
// Initializing the first_set_Arr array
for (k = 0; k < count; k++) {
for (kay = 0; kay < 100; kay++) {
first_set_Arr[k][kay] = '!';
}
}
int point1 = 0, point2, xxx;
for (k = 0; k < count; k++) {
c = production_rules_arr[k][0];
point2 = 0;
xxx = 0;
// Checking if First of c has
// already been calculated
for (kay = 0; kay <= ptr; kay++)
if (c == done[kay])
xxx = 1;
if (xxx == 1)
continue;
// Function call
findfirst(c, 0, 0);
ptr += 1;
// Adding c to the calculated list
done[ptr] = c;
first_set_Arr[point1][point2++] = c;
// Printing the First Sets of the grammar
for (i = 0 + jm; i < n; i++) {
int lark = 0, chk = 0;
for (lark = 0; lark < point2; lark++) {
if (first[i] == first_set_Arr[point1][lark]) {
chk = 1;
break;
}
}
if (chk == 0) {
first_set_Arr[point1][point2++] = first[i];
}
}
jm = n;
point1++;
}
char donee[count];
ptr = -1;
// Initializing the follow_set_Arr array
for (k = 0; k < count; k++) {
for (kay = 0; kay < 100; kay++) {
follow_set_Arr[k][kay] = '!';
}
}
point1 = 0;
int land = 0;
for (e = 0; e < count; e++) {
ck = production_rules_arr[e][0];
point2 = 0;
xxx = 0;
// Checking if Follow of ck
// has already been calculated
for (kay = 0; kay <= ptr; kay++)
if (ck == donee[kay])
xxx = 1;
if (xxx == 1)
continue;
land += 1;
// Function call
follow(ck);
ptr += 1;
// Adding ck to the calculated list
donee[ptr] = ck;
printf(" Follow(%c) = { ", ck);
follow_set_Arr[point1][point2++] = ck;
// Printing the Follow Sets of the grammar
for (i = 0 + km; i < m; i++) {
int lark = 0, chk = 0;
for (lark = 0; lark < point2; lark++) {
if (f[i] == follow_set_Arr[point1][lark]) {
chk = 1;
break;
}
}
if (chk == 0) {
printf("%c, ", f[i]);
follow_set_Arr[point1][point2++] = f[i];
}
}
printf(" }\n\n");
km = m;
point1++;
}
}
void follow(char c)
{
int i, j;
// Adding "$" to the follow
// set of the start symbol
if (production_rules_arr[0][0] == c) {
f[m++] = '$';
}
for (i = 0; i < 10; i++) {
for (j = 2; j < 10; j++) {
if (production_rules_arr[i][j] == c) {
if (production_rules_arr[i][j + 1] != '\0') {
// Calculate the first of the next
// Non-Terminal in the production_rules_arr
follow_first_function(production_rules_arr[i][j + 1], i,
(j + 2));
}
if (production_rules_arr[i][j + 1] == '\0'
&& c != production_rules_arr[i][0]) {
// Calculate the follow of the
// Non-Terminal in the L.H.S. of the
// production_rules_arr
follow(production_rules_arr[i][0]);
}
}
}
}
}
void findfirst(char c, int q1, int q2)
{
int j;
// The case where we
// encounter a Terminal
if (!(isupper(c))) {
first[n++] = c;
}
for (j = 0; j < count; j++) {
if (production_rules_arr[j][0] == c) {
if (production_rules_arr[j][2] == '#') {
if (production_rules_arr[q1][q2] == '\0')
first[n++] = '#';
else if (production_rules_arr[q1][q2] != '\0'
&& (q1 != 0 || q2 != 0)) {
// Recursion to calculate First of New
// Non-Terminal we encounter after
// epsilon
findfirst(production_rules_arr[q1][q2], q1,
(q2 + 1));
}
else
first[n++] = '#';
}
else if (!isupper(production_rules_arr[j][2])) {
first[n++] = production_rules_arr[j][2];
}
else {
// Recursion to calculate First of
// New Non-Terminal we encounter
// at the beginning
findfirst(production_rules_arr[j][2], j, 3);
}
}
}
}
void follow_first_function(char c, int c1, int c2)
{
int k;
// The case where we encounter
// a Terminal
if (!(isupper(c)))
f[m++] = c;
else {
int i = 0, j = 1;
for (i = 0; i < count; i++) {
if (first_set_Arr[i][0] == c)
break;
}
// Including the First set of the
// Non-Terminal in the Follow of
// the original query
while (first_set_Arr[i][j] != '!') {
if (first_set_Arr[i][j] != '#') {
f[m++] = first_set_Arr[i][j];
}
else {
if (production_rules_arr[c1][c2] == '\0') {
// Case where we reach the
// end of a production_rules_arr
follow(production_rules_arr[c1][0]);
}
else {
// Recursion to the next symbol
// in case we encounter a "#"
follow_first_function(production_rules_arr[c1][c2], c1,
c2 + 1);
}
}
j++;
}
}
}
Output:
![First and Follow programs in C](https://static.tutorialandexample.com/c/first-and-follow-programs-in-c1.png)