PRACTICAL - NO : 8
AIM: Write a C program for constructing of LL (1) parsing.
INTRODUCTION : An LL(1) parser is a type of top-down parser for context-free
grammars that reads input from left to right, performing a leftmost derivation of the input and
using one token of lookahead to make parsing decisions. The "LL" stands for "left-to-right,
leftmost derivation," and the "(1)" indicates that the parser uses one token of lookahead.
Here's a breakdown of what each part of "LL(1)" means:
Left-to-right: The parser processes the input from left to right.
Leftmost derivation: At each step, the parser chooses the leftmost non-terminal in
the current production to expand.
(1): The number of tokens of lookahead the parser uses. This means that the parser
looks at the next token in the input stream to decide which production to apply.
PROGRAM:
#include <stdio.h>
#include <string.h>
#define MAX_PRODUCTIONS 10
#define MAX_STRING_LENGTH 10
void main() {
char pro[MAX_PRODUCTIONS][MAX_STRING_LENGTH];
char first[MAX_PRODUCTIONS][MAX_STRING_LENGTH];
char follow[MAX_PRODUCTIONS][MAX_STRING_LENGTH];
char nt[MAX_PRODUCTIONS], ter[MAX_PRODUCTIONS];
char res[MAX_PRODUCTIONS][MAX_PRODUCTIONS][MAX_STRING_LENGTH];
int count[MAX_PRODUCTIONS][MAX_PRODUCTIONS];
int npro, noter = 0, nont = 0, i, j, k, flag, row, col, m, n, index;
printf("Enter the no of productions: ");
scanf("%d", &npro);
printf("Enter the productions: ");
for (i = 0; i < npro; i++) {
scanf("%s", pro[i]);
// Initialize arrays
memset(count, 0, sizeof(count));
memset(res, '\0', sizeof(res));
// Extract non-terminals and terminals
for (i = 0; i < npro; i++) {
flag = 0;
for (j = 0; j < nont; j++) {
if (nt[j] == pro[i][0]) {
flag = 1;
break;
if (!flag) {
nt[nont] = pro[i][0];
nont++;
// Extract first and follow sets
printf("\nEnter the first values:\n");
for (i = 0; i < nont; i++) {
printf("First value(%c): ", nt[i]);
scanf("%s", first[i]);
}
printf("\nEnter the follow values:\n");
for (i = 0; i < nont; i++) {
printf("Follow value(%c): ", nt[i]);
scanf("%s", follow[i]);
// Extract terminals
for (i = 0; i < nont; i++) {
for (j = 0; j < strlen(first[i]); j++) {
flag = 0;
for (k = 0; k < noter; k++) {
if (ter[k] == first[i][j]) {
flag = 1;
break;
if (!flag && first[i][j] != '#') {
ter[noter++] = first[i][j];
for (j = 0; j < strlen(follow[i]); j++) {
flag = 0;
for (k = 0; k < noter; k++) {
if (ter[k] == follow[i][j]) {
flag = 1;
break;
if (!flag) {
ter[noter++] = follow[i][j];
// Construct LL(1) parsing table
for (i = 0; i < nont; i++) {
for (j = 0; j < strlen(first[i]); j++) {
flag = 0;
if (first[i][j] == '#') {
col = i;
for (m = 0; m < strlen(follow[col]); m++) {
for (n = 0; n < noter; n++) {
if (ter[n] == follow[col][m]) {
row = n;
break;
sprintf(res[col][row], "%c->#", nt[col]);
count[col][row]++;
} else {
for (n = 0; n < noter; n++) {
if (ter[n] == first[i][j]) {
row = n;
break;
for (k = 0; k < npro; k++) {
if (nt[i] == pro[k][0]) {
col = i;
if ((pro[k][3] == first[i][j]) && (pro[k][0] == nt[col])) {
sprintf(res[col][row], "%s", pro[k]);
count[col][row]++;
} else {
if ((isupper(pro[k][3])) && (pro[k][0] == nt[col])) {
flag = 0;
for (m = 0; m < nont; m++) {
if (nt[m] == pro[k][3]) {
index = m;
flag = 1;
break;
if (flag) {
for (m = 0; m < strlen(first[index]); m++) {
if (first[i][j] == first[index][m]) {
sprintf(res[col][row], "%s", pro[k]);
count[col][row]++;
break;
// Print LL(1) parsing table
printf("LL1 Table\n\n");
printf("\t");
for (i = 0; i < noter; i++) {
printf("%c\t", ter[i]);
for (j = 0; j < nont; j++) {
printf("\n\n%c", nt[j]);
for (k = 0; k < noter; k++) {
printf("\t%s", res[j][k]);
}
}
// Check for LL(1) grammar
flag = 0;
for (i = 0; i < nont; i++) {
for (j = 0; j < noter; j++) {
if (count[i][j] > 1) {
flag = 1;
break;
if (flag) {
printf("\nThe given grammar is not LL1\n");
} else {
printf("\nThe given grammar is LL1\n");
}
OUTPUT :
