COMPILER DESIGN LABORATORY ASSIGNMENT
INTRODUCTION TO FIRST, FOLLOW, LEFT RECURSION, LEFT
FACTORING
➤ 1. FIRST Set
FIRST(X) is the set of terminals that begin the strings derivable from X.
➤ 2. FOLLOW Set
FOLLOW(A) is the set of terminals that can appear immediately to the right of A in some sentential form.
➤ 3. Left Recursion
A grammar has left recursion if a non-terminal refers to itself as the leftmost symbol in one of its productions:
4. Left Factoring
Used when two or more productions for a non-terminal begin with the same symbols:
EXAMPLE
➤ 1. FIRST Se
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id
FIRST(E) = { (, id }
FIRST(E') = { +, ε }
FIRST(T) = { (, id }
FIRST(T') = { *, ε }
FIRST(F) = { (, id }
➤ 2. FOLLOW Set: Consider previous example
FOLLOW(E) = { $ }
FOLLOW(E') = { $ }
FOLLOW(T) = { +, $ }
FOLLOW(T') = { +, $ }
FOLLOW(F) = { *, +, $ }
➤ 3. Left Recursion:
A → Aα | β
Can be converted into:
A → βA'
A' → αA' | ε
4. Left Factoring:
A → αβ1 | αβ2
Can be converted into:
A → αA'
A' → β1 | β2
CODE IMPLEMENTATION IN C:
➤ 1. FIRST Set:
#include <stdio.h>
#include <ctype.h>
#include <string.h>
char prod[10][10];
char first[10];
int n, m = 0;
void findFirst(char c);
int main() {
int i;
char c, ch;
printf("Enter number of productions: ");
scanf("%d", &n);
printf("Enter productions (e.g., E=E+T):\n");
for (i = 0; i < n; i++)
scanf("%s", prod[i]);
printf("Enter symbol to find FIRST: ");
scanf(" %c", &c);
findFirst(c);
printf("FIRST(%c) = { ", c);
for (i = 0; i < m; i++)
printf("%c ", first[i]);
printf("}\n");
return 0;
}
void findFirst(char c) {
int i;
if (!isupper(c)) {
first[m++] = c;
return;
for (i = 0; i < n; i++) {
if (prod[i][0] == c) {
if (!isupper(prod[i][2]))
first[m++] = prod[i][2];
else
findFirst(prod[i][2]);
}
}
}
➤ 2. FOLLOW Set:
#include <stdio.h>
#include <string.h>
#include <ctype.h>
char prods[10][10];
int n;
char follow[10];
int m = 0;
void findFirst(char c, char* result);
void findFollow(char c);
int main() {
int i;
char c;
printf("Enter number of productions: ");
scanf("%d", &n);
printf("Enter productions (e.g., S=AB):\n");
for (i = 0; i < n; i++)
scanf("%s", prods[i]);
printf("Enter symbol to find FOLLOW: ");
scanf(" %c", &c);
findFollow(c);
printf("FOLLOW(%c) = { ", c);
for (i = 0; i < m; i++)
printf("%c ", follow[i]);
printf("}\n");
return 0;
void findFirst(char c, char* result) {
int i, k = 0;
if (!isupper(c)) {
result[k++] = c;
result[k] = '\0';
return;
}
for (i = 0; i < n; i++) {
if (prods[i][0] == c) {
if (!isupper(prods[i][2]))
result[k++] = prods[i][2];
else
findFirst(prods[i][2], result);
}
}
result[k] = '\0';
}
void findFollow(char c) {
int i, j;
char result[10];
if (c == prods[0][0])
follow[m++] = '$';
for (i = 0; i < n; i++) {
for (j = 2; j < strlen(prods[i]); j++) {
if (prods[i][j] == c) {
if (prods[i][j + 1] != '\0') {
findFirst(prods[i][j + 1], result);
for (int k = 0; result[k] != '\0'; k++)
follow[m++] = result[k];
}
if (prods[i][j + 1] == '\0' && c != prods[i][0])
findFollow(prods[i][0]);
}
}
}
}
➤ 3. Left Recursion:
#include <stdio.h>
#include <string.h>
void removeLeftRecursion(char *);
int main() {
char production[100];
printf("Enter production (e.g., A=Aa|b): ");
scanf("%s", production);
removeLeftRecursion(production);
return 0;
}
void removeLeftRecursion(char *prod) {
char nonTerminal = prod[0];
char alpha[10][10], beta[10][10];
int i = 0, j = 0, k = 0, m = 0, n = 0;
i = 2; // Skip A=
while (prod[i] != '\0') {
if (prod[i] == '|') {
if (prod[2] == nonTerminal) // Left recursive
alpha[m++][k] = '\0';
else
beta[n++][j] = '\0';
k = j = 0;
i++;
} else if (prod[2] == nonTerminal && k == 0) {
i++;
} else {
if (prod[2] == nonTerminal) {
alpha[m][k++] = prod[i++];
} else {
beta[n][j++] = prod[i++];
}
}
}
if (prod[2] == nonTerminal)
alpha[m++][k] = '\0';
else
beta[n++][j] = '\0';
if (m == 0) {
printf("No Left Recursion\n");
return;
printf("After removing Left Recursion:\n");
printf("%c -> ", nonTerminal);
for (i = 0; i < n; i++)
printf("%s%c' | ", beta[i], nonTerminal);
printf("\b\b \n");
printf("%c' -> ", nonTerminal);
for (i = 0; i < m; i++)
printf("%s%c' | ", alpha[i], nonTerminal);
printf("ε\n");
}
4. Left Factoring:
#include <stdio.h>
#include <string.h>
void leftFactor(char *prod);
int main() {
char prod[100];
printf("Enter production (e.g., A=abc|abd): ");
scanf("%s", prod);
leftFactor(prod);
return 0;
}
void leftFactor(char *prod) {
char nt = prod[0];
char part1[20], part2[20];
int i = 2, j = 0;
while (prod[i] != '|')
part1[j++] = prod[i++];
part1[j] = '\0';
i++; j = 0;
while (prod[i] != '\0')
part2[j++] = prod[i++];
part2[j] = '\0';
// Find common prefix
char prefix[20];
int len = strlen(part1) < strlen(part2) ? strlen(part1) : strlen(part2);
for (i = 0; i < len; i++) {
if (part1[i] == part2[i])
prefix[i] = part1[i];
else
break;
}
prefix[i] = '\0';
if (strlen(prefix) == 0) {
printf("No common prefix, no left factoring needed.\n");
return;
}
printf("After Left Factoring:\n");
printf("%c -> %s%c'\n", nt, prefix, nt);
printf("%c' -> %s | %s\n", nt, &part1[i], &part2[i]);
}
OBJECTIVE:-
• Write a C program to construct the LL(1) parsing table using computed FIRST and
FOLLOW sets.
• Write a C program to simulate an LL(1) parser using a hardcoded parsing table
and stack simulation
• Write a C program that checks whether a given grammar is LL(1) or not.
