SRM UNIVERSITY DELHI-NCR, SONEPAT, HARYANA

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

Bachelor of Technology(B.Tech)

Compiler Design Lab

(21CS3117)

NAME : SAURAV KUMAR

REGISTER NO : 10322210041

SEMESTER : 5th

YEAR : 3rd

SRM University Delhi-NCR, Sonepat, Haryana, Rajiv Gandhi Education City, Delhi-NCR, Sonepat-131029,
Haryana (India)
 SRM UNIVERSITY DELHI-NCR, SONEPAT, HARYANA

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

BONAFIDE CERTIFICATE

This is to certify that is a bonafide work done by Mr. Saurav Kumar For
the 2 1 CS 3 1 1 7 Compiler Design L AB as a part of the B.Tech (Core), course
in SRM University Delhi-NCR, Sonepat, Haryana during the year of 2023-24.
The record was found to be completed and satisfactory.

HOD/Coordinator Subject In-Charge

Submitted for the Practical Examination held on

Internal Examiner External Examiner

1.Write a program to implement a one-pass and two-pass
assembler.

i)One-Pass Assembler

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LINES 100

#define MAX_LABELS 50

typedef struct {
char label[20];
int address;
} Symbol;

Symbol symbol_table[MAX_LABELS];
int symbol_count = 0;

void add_to_symbol_table(char *label, int address) {

strcpy(symbol_table[symbol_count].label, label);
symbol_table[symbol_count].address = address;
symbol_count++;
}

int get_symbol_address(char *label) {

for (int i = 0; i < symbol_count; i++) {
if (strcmp(symbol_table[i].label, label) == 0) {
return symbol_table[i].address;
}
}
return -1; // Symbol not found
}
Machine Code:
0: START
1: LOAD A
2: ADD B
3: STORE C
4: END

Symbol Table:
START -> 0
void one_pass_assembler(char *assembly_code[], int line_count) {
int location_counter = 0;

printf("Machine Code:\n");
for (int i = 0; i < line_count; i++) {
char line[100];
strcpy(line, assembly_code[i]);
char *token = strtok(line, " ");

if (token[strlen(token) - 1] == ':') {
// Label definition
token[strlen(token) - 1] = '\0'; // Remove colon
add_to_symbol_table(token, location_counter);
token = strtok(NULL, " ");
}

printf("%d: %s\n", location_counter, token ? token : "");

location_counter++;
}
printf("\nSymbol Table:\n");
for (int i = 0; i < symbol_count; i++) {
printf("%s -> %d\n", symbol_table[i].label, symbol_table[i].address);
}
}
int main() {
char *assembly_code[] = {
"START:",
"LOAD A",
"ADD B",
"STORE C",
"END:"
};
int line_count = sizeof(assembly_code) / sizeof(assembly_code[0]);
one_pass_assembler(assembly_code, line_count);
return 0;
}
ii)Two-Pass Assembler

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LINES 100

#define MAX_LABELS 50

typedef struct {
char label[20];
int address;
} Symbol;

Symbol symbol_table[MAX_LABELS];
int symbol_count = 0;

void add_to_symbol_table(char *label, int address) {

strcpy(symbol_table[symbol_count].label, label);
symbol_table[symbol_count].address = address;
symbol_count++;
}

int get_symbol_address(char *label) {

for (int i = 0; i < symbol_count; i++) {
if (strcmp(symbol_table[i].label, label) == 0) {
return symbol_table[i].address;
}
}
return -1; // Symbol not found
}

void two_pass_assembler(char *assembly_code[], int line_count) {

int location_counter = 0;
Machine Code:
0: LOAD A
1: ADD B
2: STORE C
3: END

Symbol Table:
START -> 0
 // First Pass: Build Symbol Table
for (int i = 0; i < line_count; i++) {
char line[100];
strcpy(line, assembly_code[i]);
char *token = strtok(line, " ");

if (token[strlen(token) - 1] == ':') {
// Label definition
token[strlen(token) - 1] = '\0'; // Remove colon
add_to_symbol_table(token, location_counter);
}
location_counter++;
}

// Second Pass: Generate Machine Code

location_counter = 0;
printf("Machine Code:\n");
for (int i = 0; i < line_count; i++) {
char line[100];
strcpy(line, assembly_code[i]);
char *token = strtok(line, " ");

if (token[strlen(token) - 1] == ':') {
token = strtok(NULL, " "); // Skip label
}

printf("%d: %s\n", location_counter, token ? token : "");

location_counter++;
}

printf("\nSymbol Table:\n");
for (int i = 0; i < symbol_count; i++) {
printf("%s -> %d\n", symbol_table[i].label, symbol_table[i].address);
}
}
int main() {
char *assembly_code[] = {
"START:",
"LOAD A",
"ADD B",
"STORE C",
"END:"
};
int line_count = sizeof(assembly_code) / sizeof(assembly_code[0]);

two_pass_assembler(assembly_code, line_count);

return 0;
}
2. Write a program to implement a symbol table.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SYMBOLS 100

#define MAX_NAME_LENGTH 50

typedef struct {
char name[MAX_NAME_LENGTH];
char type[20]; // e.g., "int", "float", "char"
int address;
} Symbol;

Symbol symbol_table[MAX_SYMBOLS];
int symbol_count = 0;

// Function to add a symbol to the table

void add_symbol(char *name, char *type, int address) {
// Check if the symbol already exists
for (int i = 0; i < symbol_count; i++) {
if (strcmp(symbol_table[i].name, name) == 0) {
printf("Error: Symbol '%s' already exists in the table.\n", name);
return;
}
}

// Add new symbol

strcpy(symbol_table[symbol_count].name, name);
strcpy(symbol_table[symbol_count].type, type);
symbol_table[symbol_count].address = address;
symbol_count++;
printf("Symbol '%s' added successfully.\n", name);
}
Symbol Table Menu:
1. Add Symbol
2. Search Symbol
3. Display Symbol Table
4. Exit
Enter your choice: 1
Enter symbol name: x
Enter symbol type: int
Enter symbol address: 100
Symbol 'x' added successfully.

Symbol Table Menu:

1. Add Symbol
2. Search Symbol
3. Display Symbol Table
4. Exit
Enter your choice: 3

Symbol Table:
--------------------------------------------------
| Name | Type | Address |
--------------------------------------------------
|x | int | 100 |
--------------------------------------------------

Symbol Table Menu:

1. Add Symbol
2. Search Symbol
3. Display Symbol Table
4. Exit
Enter your choice: 2
Enter symbol name to search: x
Symbol found: Name = x, Type = int, Address = 100

Symbol Table Menu:

1. Add Symbol
2. Search Symbol
3. Display Symbol Table
4. Exit
Enter your choice: 4
Exiting...
// Function to search for a symbol by name
int search_symbol(char *name) {
for (int i = 0; i < symbol_count; i++) {
if (strcmp(symbol_table[i].name, name) == 0) {
return i; // Return index of the symbol
}
}
return -1; // Symbol not found
}

// Function to display the symbol table

void display_symbol_table() {
printf("\nSymbol Table:\n");
printf("--------------------------------------------------\n");
printf("| %-20s | %-10s | %-10s |\n", "Name", "Type", "Address");
printf("--------------------------------------------------\n");
for (int i = 0; i < symbol_count; i++) {
printf("| %-20s | %-10s | %-10d |\n",
symbol_table[i].name,
symbol_table[i].type,
symbol_table[i].address);
}
printf("--------------------------------------------------\n");
}

int main() {
int choice;
char name[MAX_NAME_LENGTH], type[20];
int address;

do {
printf("\nSymbol Table Menu:\n");
printf("1. Add Symbol\n");
printf("2. Search Symbol\n");
printf("3. Display Symbol Table\n");
printf("4. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter symbol name: ");
scanf("%s", name);
printf("Enter symbol type: ");
scanf("%s", type);
printf("Enter symbol address: ");
scanf("%d", &address);
add_symbol(name, type, address);
break;

case 2:
printf("Enter symbol name to search: ");
scanf("%s", name);
int index = search_symbol(name);
if (index != -1) {
printf("Symbol found: Name = %s, Type = %s, Address = %d\n",
symbol_table[index].name,
symbol_table[index].type,
symbol_table[index].address);
} else
{
printf("Symbol '%s' not found in the table.\n", name);
}
break;

case 3:
display_symbol_table();
break;

case 4:
 printf("Exiting...\n");
break;

default:
printf("Invalid choice. Please try again.\n");
}
} while (choice != 4);

return 0;
}
3. Develop a lexical analyzer to recognize a few patterns in C. (Ex.
identifiers, constants, comments, operators etc.)

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

#define MAX 100

// List of keywords
const char *keywords[] = {
"int", "float", "if", "else", "while", "return", "void", "char", "for", "do", "break"
};
const int num_keywords = sizeof(keywords) / sizeof(keywords[0]);

// Function to check if a string is a keyword

int is_keyword(const char *word) {
for (int i = 0; i < num_keywords; i++) {
if (strcmp(word, keywords[i]) == 0) {
return 1;
}
}
return 0;
}
// Function to recognize operators
int is_operator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '=' ||
ch == '<' || ch == '>' || ch == '&' || ch == '|' || ch == '%';
}
// Function to recognize delimiters
int is_delimiter(char ch) {
return ch == ' ' || ch == ',' || ch == ';' || ch == '(' || ch == ')' ||
ch == '{' || ch == '}' || ch == '[' || ch == ']';
}
// Function to recognize digits
Input Code:
int main() {
int x = 10; // This is a comment
float y = 20.5;
if (x < y) {
x = x + y;
}
/* Multi-line comment
Example */

Lexical Analysis:
-------------------------------
| Token | Type |
-------------------------------
| int | Keyword |
| main | Identifier |
|( | Delimiter |
|) | Delimiter |
|{ | Delimiter |
| int | Keyword |
|x | Identifier |
|= | Operator |
| 10 | Constant |
|; | Delimiter |
| //... | Comment |
| float | Keyword |
|y | Identifier |
|= | Operator |
| 20 | Constant |
|. | Unknown |
|5 | Constant |
|; | Delimiter |
| if | Keyword |
|( | Delimiter |
|x | Identifier |
|< | Operator |
|y | Identifier |
|) | Delimiter |
|{ | Delimiter |
|x | Identifier |
|= | Operator |
|x | Identifier |
|+ | Operator |
|y | Identifier |
|; | Delimiter |
|} | Delimiter |
| /*...*/ | Comment |
|} | Delimiter |
-------------------------------
int is_constant(char *word) {
for (int i = 0; word[i] != '\0'; i++) {
if (!isdigit(word[i])) {
return 0;
}
}
return 1;
}

// Function to analyze the input

void lexical_analyzer(const char *code) {
int i = 0;
char buffer[MAX];
printf("Lexical Analysis:\n");
printf("-------------------------------\n");
printf("| Token | Type |\n");
printf("-------------------------------\n");

while (code[i] != '\0') {

// Skip whitespace
if (isspace(code[i])) {
i++;
continue;
}

// Handle comments
if (code[i] == '/' && code[i + 1] == '/') {
printf("| %-12s | %-14s |\n", "//...", "Comment");
while (code[i] != '\0' && code[i] != '\n') {
i++;
}
continue;
}

// Handle multi-line comments

if (code[i] == '/' && code[i + 1] == '*') {
 printf("| %-12s | %-14s |\n", "/*...*/", "Comment");
i += 2;
while (code[i] != '\0' && !(code[i] == '*' && code[i + 1] == '/')) {
i++;
}
i += 2; // Skip "*/"
continue;
}

// Handle identifiers and keywords

if (isalpha(code[i])) {
int j = 0;
while (isalnum(code[i]) || code[i] == '_') {
buffer[j++] = code[i++];
}
buffer[j] = '\0';

if (is_keyword(buffer)) {
printf("| %-12s | %-14s |\n", buffer, "Keyword");
} else {
printf("| %-12s | %-14s |\n", buffer, "Identifier");
}
continue;
}

// Handle constants
if (isdigit(code[i])) {
int j = 0;
while (isdigit(code[i])) {
buffer[j++] = code[i++];
}
buffer[j] = '\0';

printf("| %-12s | %-14s |\n", buffer, "Constant");

continue;
}
 // Handle operators
if (is_operator(code[i])) {
printf("| %-12c | %-14s |\n", code[i], "Operator");
i++;
continue;
}

// Handle delimiters
if (is_delimiter(code[i])) {
printf("| %-12c | %-14s |\n", code[i], "Delimiter");
i++;
continue;
}

// Unknown token
printf("| %-12c | %-14s |\n", code[i], "Unknown");
i++;
}

printf("-------------------------------\n");
}

int main() {
const char *code = "int main() {\n"
" int x = 10; // This is a comment\n"
" float y = 20.5;\n"
" if (x < y) {\n"
" x = x + y;\n"
" }\n"
" /* Multi-line comment\n"
" Example */\n"
"}";
printf("Input Code:\n%s\n\n", code);
lexical_analyzer(code);
return 0;
}
4.Write a program to implement a lexical analyzer using Lex
Tool.

%{
#include <stdio.h>
%}

%%

"int"|"float"|"char"|"if"|"else"|"while"|"for"|"return" { printf("Keyword: %s\n",

yytext); }
[a-zA-Z_][a-zA-Z0-9_]* { printf("Identifier: %s\n", yytext); }
[0-9]+ { printf("Constant: %s\n", yytext); }
"//".* { printf("Single-line Comment: %s\n", yytext); }
"/*"([^*]|[\r\n]|"*"[^/])*"*/" { printf("Multi-line Comment: %s\n",
yytext); }
"+"|"-"|"*"|"/"|"="|"<"|">" { printf("Operator: %s\n", yytext); }
"(" | ")" | "{" | "}" | ";" | "," | "[" | "]" { printf("Delimiter: %s\n", yytext); }
[ \t\n]+ { /* Ignore whitespace */ }
. { printf("Unknown Token: %s\n", yytext); }

%%

int main() {
yylex();
return 0;
}

int yywrap() {
return 1;
}
Keyword: int
Identifier: main
Delimiter: (
Delimiter: )
Delimiter: {
Keyword: int
Identifier: a
Operator: =
Constant: 10
Delimiter: ;
Single-line Comment: // This is a single-line comment
Keyword: float
Identifier: b
Operator: =
Constant: 20
Operator: .
Constant: 5
Delimiter: ;
Keyword: char
Identifier: c
Operator: =
Unknown Token: '
Identifier: z
Unknown Token: '
Delimiter: ;
Keyword: if
Delimiter: (
Identifier: a
Operator: <
Identifier: b
Delimiter: )
Delimiter: {
Identifier: a
Operator: =
Identifier: a
Operator: +
Identifier: b
Delimiter: ;
Delimiter: }
Multi-line Comment: /* Multi-line comment
Example */
Keyword: return
Constant: 0
Delimiter: ;
Delimiter: }
Input C file:
int main() {
int a = 10; // This is a single-line comment
float b = 20.5;
char c = 'z';
if (a < b) {
a = a + b;
}
/* Multi-line comment
Example */
return 0;
}
5.Write a program to design a lexical analyzer for a given
language, and the lexical analyzer should ignore redundant
spaces, tabs, and newlines.

%{
#include <stdio.h>
%}

%%

"int"|"float"|"char"|"if"|"else"|"while"|"for"|"return" { printf("Keyword: %s\n",

yytext); }
[a-zA-Z_][a-zA-Z0-9_]* { printf("Identifier: %s\n", yytext); }
[0-9]+ { printf("Constant: %s\n", yytext); }
"//".* { printf("Single-line Comment: %s\n", yytext); }
"/*"([^*]|[\r\n]|"*"[^/])*"*/" { printf("Multi-line Comment: %s\n",
yytext); }
"+"|"-"|"*"|"/"|"="|"<"|">" { printf("Operator: %s\n", yytext); }
"(" | ")" | "{" | "}" | ";" | "," | "[" | "]" { printf("Delimiter: %s\n", yytext); }
[ \t\n]+ { /* Ignore whitespace */ }
. { printf("Unknown Token: %s\n", yytext); }

%%

int main() {
printf("Lexical Analysis:\n");
printf("-------------------------------\n");
yylex();
return 0;
}

int yywrap() {
return 1;
}
Lexical Analysis:
-------------------------------
Keyword: int
Identifier: main
Delimiter: (
Delimiter: )
Delimiter: {
Keyword: int
Identifier: a
Operator: =
Constant: 10
Delimiter: ;
Single-line Comment: // This is a comment
Keyword: float
Identifier: b
Operator: =
Constant: 20
Operator: .
Constant: 5
Delimiter: ;
Keyword: char
Identifier: c
Operator: =
Unknown Token: '
Identifier: z
Unknown Token: '
Delimiter: ;
Keyword: if
Delimiter: (
Identifier: a
Operator: <
Identifier: b
Delimiter: )
Delimiter: {
Identifier: a
Operator: =
Identifier: a
Operator: +
Identifier: b
Delimiter: ;
Delimiter: }

Keyword: return
Constant: 0
Delimiter: ;
Delimiter: }
Input File:

int main() {
int a = 10; // This is a comment
float b = 20.5;
char c = 'z';

if (a < b) {
a = a + b;
}

/* Multi-line comment
example */
return 0;
}
6. Write a program to implement the First and Follow of the
following Grammar:
E→ T E’
E’ → +T E’| Є
T → F T’
T’ → *FT’| Є
F → (E)|id
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 10

// Define grammar rules

char productions[MAX][MAX] = {
"E->TE'",
"E'->+TE'|ε",
"T->FT'",
"T'->*FT'|ε",
"F->(E)|id"
};

char first[MAX][MAX], follow[MAX][MAX];

int prodCount = 5;

// Function to check if a symbol is a non-terminal

int isNonTerminal(char symbol) {
return (symbol >= 'A' && symbol <= 'Z');
}

// Function to compute FIRST of a symbol

void computeFirst(char symbol, int index) {
for (int i = 0; i < prodCount; i++) {
Non-Terminal FIRST FOLLOW
E (id $
E' +ε $
T (id +$
T' *ε +$
F (id *+$
 if (productions[i][0] == symbol) {
char *body = strchr(productions[i], '>') + 1;
for (int j = 0; body[j] != '\0'; j++) {
if (!isNonTerminal(body[j])) {
strncat(first[index], &body[j], 1); // Add terminal
break;
} else {
computeFirst(body[j], body[j] - 'A');
strcat(first[index], first[body[j] - 'A']); // Add FIRST of non-terminal
if (!strchr(first[body[j] - 'A'], 'ε')) break;
}
}
}
}
}

// Function to compute FOLLOW of a symbol

void computeFollow(char symbol, int index) {
if (index == 0) strcat(follow[index], "$"); // Add $ for the start symbol

for (int i = 0; i < prodCount; i++) {

char *body = strchr(productions[i], '>') + 1;
for (int j = 0; body[j] != '\0'; j++) {
if (body[j] == symbol) {
if (body[j + 1] == '\0') {
// Add FOLLOW of LHS
strcat(follow[index], follow[productions[i][0] - 'A']);
} else if (!isNonTerminal(body[j + 1])) {
// Add terminal in FOLLOW
strncat(follow[index], &body[j + 1], 1);
} else {
// Add FIRST of next symbol
strcat(follow[index], first[body[j + 1] - 'A']);
if (strchr(first[body[j + 1] - 'A'], 'ε')) {
strcat(follow[index], follow[productions[i][0] - 'A']);
}
 }
}
}
}
}

// Function to remove duplicates in FIRST or FOLLOW sets

void removeDuplicates(char *set) {
int len = strlen(set);
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; ) {
if (set[i] == set[j]) {
memmove(&set[j], &set[j + 1], len - j);
len--;
} else {
j++;
}
}
}
}

int main() {
// Initialize FIRST and FOLLOW arrays
for (int i = 0; i < MAX; i++) {
first[i][0] = '\0';
follow[i][0] = '\0';
}

// Compute FIRST for all non-terminals

for (int i = 0; i < prodCount; i++) {
computeFirst(productions[i][0], productions[i][0] - 'A');
}

// Compute FOLLOW for all non-terminals

for (int i = 0; i < prodCount; i++) {
computeFollow(productions[i][0], productions[i][0] - 'A');
 }

// Remove duplicates in FIRST and FOLLOW sets

for (int i = 0; i < prodCount; i++) {
removeDuplicates(first[productions[i][0] - 'A']);
removeDuplicates(follow[productions[i][0] - 'A']);
}

// Display results
printf("Non-Terminal\tFIRST\tFOLLOW\n");
for (int i = 0; i < prodCount; i++) {
printf("%c\t\t%s\t%s\n", productions[i][0], first[productions[i][0] - 'A'],
follow[productions[i][0] - 'A']);
}

return 0;
}
7.Write a program to Develop an operator precedence parser
for a given language.

#include <stdio.h>
#include <string.h>

#define MAX 10
#define EMPTY ' '

char operators[] = {'+', '*', '(', ')', 'i', '$'}; // Operator set including terminals
char precedenceTable[MAX][MAX];
char stack[MAX];
int top = -1;

// Function to return precedence table index

int getIndex(char symbol) {
for (int i = 0; i < sizeof(operators); i++) {
if (operators[i] == symbol) return i;
}
return -1; // Not found
}

// Function to initialize precedence table

void initializePrecedenceTable() {
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
precedenceTable[i][j] = EMPTY;
}
}

// Fill precedence table manually based on the grammar

precedenceTable[getIndex('+')][getIndex('+')] = '>';
precedenceTable[getIndex('+')][getIndex('*')] = '<';
precedenceTable[getIndex('+')][getIndex('(')] = '<';
precedenceTable[getIndex('+')][getIndex(')')] = '>';
Enter input string ending with $: i+i*i$

Operator Precedence Table:

+ * ( ) i $
+ > < < > < >
* > > < > < >
( < < < = <
) > > > >
i > > > >
$ < < < < =

Stack Input Action

$ i+i*i$ Shift i
$i +i*i$ Reduce
$ +i*i$ Shift +
$+ i*i$ Shift i
$+i *i$ Reduce
$+ *i$ Shift *
$+* i$ Shift i
$+*i $ Reduce
$+* $ Reduce
$+ $ Reduce
$ $ Accept

The string is accepted by the grammar.

precedenceTable[getIndex('+')][getIndex('i')] = '<';
precedenceTable[getIndex('+')][getIndex('$')] = '>';

precedenceTable[getIndex('*')][getIndex('+')] = '>';
precedenceTable[getIndex('*')][getIndex('*')] = '>';
precedenceTable[getIndex('*')][getIndex('(')] = '<';
precedenceTable[getIndex('*')][getIndex(')')] = '>';
precedenceTable[getIndex('*')][getIndex('i')] = '<';
precedenceTable[getIndex('*')][getIndex('$')] = '>';

precedenceTable[getIndex('(')][getIndex('+')] = '<';
precedenceTable[getIndex('(')][getIndex('*')] = '<';
precedenceTable[getIndex('(')][getIndex('(')] = '<';
precedenceTable[getIndex('(')][getIndex(')')] = '=';
precedenceTable[getIndex('(')][getIndex('i')] = '<';

precedenceTable[getIndex(')')][getIndex('+')] = '>';
precedenceTable[getIndex(')')][getIndex('*')] = '>';
precedenceTable[getIndex(')')][getIndex(')')] = '>';
precedenceTable[getIndex(')')][getIndex('$')] = '>';

precedenceTable[getIndex('i')][getIndex('+')] = '>';
precedenceTable[getIndex('i')][getIndex('*')] = '>';
precedenceTable[getIndex('i')][getIndex(')')] = '>';
precedenceTable[getIndex('i')][getIndex('$')] = '>';

precedenceTable[getIndex('$')][getIndex('+')] = '<';
precedenceTable[getIndex('$')][getIndex('*')] = '<';
precedenceTable[getIndex('$')][getIndex('(')] = '<';
precedenceTable[getIndex('$')][getIndex('i')] = '<';
precedenceTable[getIndex('$')][getIndex('$')] = '=';
}

// Function to print precedence table

void printPrecedenceTable() {
printf("Operator Precedence Table:\n");
 printf(" ");
for (int i = 0; i < sizeof(operators); i++) {
printf(" %c", operators[i]);
}
printf("\n");
for (int i = 0; i < sizeof(operators); i++) {
printf(" %c ", operators[i]);
for (int j = 0; j < sizeof(operators); j++) {
printf(" %c", precedenceTable[i][j]);
}
printf("\n");
}
}

// Function to push onto stack

void push(char symbol) {
stack[++top] = symbol;
}

// Function to pop from stack

char pop() {
return stack[top--];
}

// Function to peek at the top of the stack

char peek() {
return stack[top];
}

// Function to parse the input string

int parseInput(char *input) {
char *ptr = input;
push('$'); // Push initial symbol onto the stack

printf("\nStack\t\tInput\t\tAction\n");
while (*ptr != '\0') {
char topSymbol = peek();
int topIndex = getIndex(topSymbol);
int inputIndex = getIndex(*ptr);

if (topIndex == -1 || inputIndex == -1) {

printf("Invalid symbol in input.\n");
return 0;
}

printf("%s\t\t%s\t\t", stack, ptr);

char precedence = precedenceTable[topIndex][inputIndex];

if (precedence == '<' || precedence == '=') {
printf("Shift %c\n", *ptr);
push(*ptr);
ptr++;
} else if (precedence == '>') {
printf("Reduce\n");
while (precedenceTable[getIndex(peek())][inputIndex] == '>') {
pop();
}
} else {
printf("Error: Invalid precedence.\n");
return 0;
}
}

while (peek() != '$') {

char topSymbol = peek();
char precedence = precedenceTable[getIndex(topSymbol)][getIndex('$')];
printf("%s\t\t%s\t\t", stack, ptr);

if (precedence == '>') {
printf("Reduce\n");
pop();
 } else {
printf("Error: Invalid precedence.\n");
return 0;
}
}

printf("Accept\n");
return 1;
}

int main() {
char input[MAX];

// Initialize operator precedence table

initializePrecedenceTable();

// Print precedence table

printPrecedenceTable();

// Input string
printf("\nEnter input string ending with $: ");
scanf("%s", input);

// Parse input string

if (!parseInput(input)) {
printf("\nThe string is not accepted by the grammar.\n");
} else {
printf("\nThe string is accepted by the grammar.\n");
}

return 0;
}
8.Write a program to construct a recursive descent parser for
an expression: E –> E + T | T
T –> T * F | F
F –> ( E ) | id
#include <stdio.h>
#include <string.h>
#include <ctype.h>

// Global variables
char input[100];
int position = 0;

// Function prototypes
int E();
int T();
int F();

// Function to match and consume a token

int match(char expected) {
if (input[position] == expected) {
position++;
return 1;
}
return 0;
}

// Recursive function for E -> E + T | T

int E() {
printf("Entering E\n");
if (T()) {
if (input[position] == '+') {
match('+'); // Consume '+'
if (E()) return 1;
return 0; // Invalid after '+'
Enter the input expression: id+id*id

Entering E
Entering T
Entering F
Entering T
Entering F
Entering E
Entering T
Entering F

The input expression is valid.

 }
return 1; // Valid if it matches T
}
return 0; // Invalid if T fails
}

// Recursive function for T -> T * F | F

int T() {
printf("Entering T\n");
if (F()) {
if (input[position] == '*') {
match('*'); // Consume '*'
if (T()) return 1;
return 0; // Invalid after '*'
}
return 1; // Valid if it matches F
}
return 0; // Invalid if F fails
}

// Recursive function for F -> ( E ) | id

int F() {
printf("Entering F\n");
if (input[position] == '(') {
match('('); // Consume '('
if (E()) {
if (match(')')) return 1; // Consume ')'
return 0; // Invalid if ')' is missing
}
return 0; // Invalid if E fails
} else if (isalnum(input[position])) {
match(input[position]); // Consume id (single letter/digit)
return 1;
}
return 0; // Invalid if neither '(' nor id
}
// Main function
int main() {
printf("Enter the input expression: ");
scanf("%s", input);

// Add end marker to the input

strcat(input, "$");

// Start parsing from E and check if input is fully consumed

if (E() && input[position] == '$') {
printf("\nThe input expression is valid.\n");
} else {
printf("\nThe input expression is invalid.\n");
}

return 0;
}
9.Write a program to construct an LL(1) parser for an
expression.
E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | id

#include <stdio.h>
#include <string.h>

#define MAX 10

// Parsing table
char parsingTable[MAX][MAX][MAX] = {
/* id + * ( ) $ */
/* E */ {"TE'", "", "", "TE'", "", ""},
/* E' */ {"", "+TE'", "", "", "ε", "ε"},
/* T */ {"FT'", "", "", "FT'", "", ""},
/* T' */ {"", "ε", "*FT'", "", "ε", "ε"},
/* F */ {"id", "", "", "(E)", "", ""}
};

char stack[MAX];
int top = -1;

// Push onto the stack

void push(char *str) {
for (int i = strlen(str) - 1; i >= 0; i--) {
stack[++top] = str[i];
}
Enter input string ending with $: id+id*id$

Expand: E -> TE'

Expand: T -> FT'
Expand: F -> id
Match: i
Expand: E' -> +TE'
Match: +
Expand: T -> FT'
Expand: F -> id
Match: i
Expand: T' -> *FT'
Match: *
Expand: F -> id
Match: i
Expand: T' -> ε
Expand: E' -> ε
The input string is valid.
}

// Pop from the stack

char pop() {
return (top == -1) ? '\0' : stack[top--];
}

// Peek at the top of the stack

char peek() {
return (top == -1) ? '\0' : stack[top];
}

// Function to return column index for a terminal

int getColumnIndex(char terminal) {
switch (terminal) {
case 'i': return 0; // id
case '+': return 1;
case '*': return 2;
case '(': return 3;
case ')': return 4;
case '$': return 5;
default: return -1;
}
}

// Function to return row index for a non-terminal

int getRowIndex(char nonTerminal) {
switch (nonTerminal) {
case 'E': return 0;
case 'E': return 1;
case 'T': return 2;
case 'T': return 2;
case 'T': return 3;
case 'F': return 4;
 default: return -1;
}
}

// Function to parse input

int parse(char *input) {
stack[++top] = '$'; // Push end marker
stack[++top] = 'E'; // Start symbol

int idx = 0;
char currentInput = input[idx];
while (top != -1) {
char topSymbol = pop();

// Match terminal symbols

if (topSymbol == currentInput) {
printf("Match: %c\n", currentInput);
idx++;
currentInput = input[idx];
} else if (topSymbol >= 'A' && topSymbol <= 'Z') {
// Non-terminal
int row = getRowIndex(topSymbol);
int col = getColumnIndex(currentInput);

if (row == -1 || col == -1 || strcmp(parsingTable[row][col], "") == 0) {

printf("Error: No rule for %c -> %c\n", topSymbol, currentInput);
return 0;
}

printf("Expand: %c -> %s\n", topSymbol, parsingTable[row][col]);

if (strcmp(parsingTable[row][col], "ε") != 0) {
push(parsingTable[row][col]);
}
} else {
 // Error case
printf("Error: Unexpected symbol %c\n", topSymbol);
return 0;
}
}

return (currentInput == '$');

}

// Main function
int main() {
char input[MAX];

printf("Enter input string ending with $: ");

scanf("%s", input);

if (parse(input)) {
printf("The input string is valid.\n");
} else {
printf("The input string is invalid.\n");
}

return 0;
}
10.Write a program to design a predictive parser for the
given language:
E->E+T|T
T->T*F|F
F->(E)|id
#include <stdio.h>
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

// Parsing table
char parsingTable[5][6][MAX] = {
// id + * ( ) $
{ "TE'", "", "", "TE'", "", "" }, // E
{ "", "+TE'", "", "", "ε", "ε" }, // E'
{ "FT'", "", "", "FT'", "", "" }, // T
{ "", "ε", "*FT'", "", "ε", "ε" }, // T'
{ "id", "", "", "(E)", "", "" } // F
};

// Function to get row index for non-terminal

int getNonTerminalIndex(char nonTerminal) {
switch (nonTerminal) {
case 'E': return 0;
case 'E': return 1;
case 'T': return 2;
case 'T': return 2;
case 'T': return 3;
case 'F': return 4;
default: return -1;
Enter input string ending with $: id+id*id$

Expand: E -> TE'

Expand: T -> FT'
Expand: F -> id
Match: i
Expand: E' -> +TE'
Match: +
Expand: T -> FT'
Expand: F -> id
Match: i
Expand: T' -> *FT'
Match: *
Expand: F -> id
Match: i
Expand: T' -> ε
Expand: E' -> ε
The input string is valid.
 }
}

// Function to get column index for terminal

int getTerminalIndex(char terminal) {
switch (terminal) {
case 'i': return 0; // id
case '+': return 1;
case '*': return 2;
case '(': return 3;
case ')': return 4;
case '$': return 5;
default: return -1;
}
}

// Function to push a string onto the stack in reverse

void push(char *str) {
for (int i = strlen(str) - 1; i >= 0; i--) {
stack[++top] = str[i];
}
}

// Function to pop the top of the stack

char pop() {
return (top == -1) ? '\0' : stack[top--];
}

// Peek the top of the stack

char peek() {
return (top == -1) ? '\0' : stack[top];
}

// Function to parse the input

int parse(char *input) {
stack[++top] = '$'; // End marker
 stack[++top] = 'E'; // Start symbol

int idx = 0;
char currentInput = input[idx];

while (top != -1) {

char topSymbol = pop();

// Match terminal
if (topSymbol == currentInput) {
printf("Match: %c\n", currentInput);
idx++;
currentInput = input[idx];
} else if (topSymbol >= 'A' && topSymbol <= 'Z') {
// Non-terminal
int row = getNonTerminalIndex(topSymbol);
int col = getTerminalIndex(currentInput);

if (row == -1 || col == -1 || strcmp(parsingTable[row][col], "") == 0) {

printf("Error: No rule for %c -> %c\n", topSymbol, currentInput);
return 0;
}

printf("Expand: %c -> %s\n", topSymbol, parsingTable[row][col]);

if (strcmp(parsingTable[row][col], "ε") != 0) {
push(parsingTable[row][col]);
}
} else {
// Error: unexpected symbol
printf("Error: Unexpected symbol %c\n", currentInput);
return 0;
}
}

return (currentInput == '$');

}
// Main function
int main() {
char input[MAX];

printf("Enter input string ending with $: ");

scanf("%s", input);

if (parse(input)) {
printf("The input string is valid.\n");
} else {
printf("The input string is invalid.\n");
}

return 0;
}
11.Write a program to implement shift- reduce parsing
algorithm for the following grammar:
S→(L)|a
L→ L,S|S
and input string is (a,a).

#include <stdio.h>
#include <string.h>

#define MAX 100

// Grammar rules
char *rules[] = {
"S -> (L)",
"S -> a",
"L -> L,S",
"L -> S"
};

// Function to check if a reduction is possible

int reduce(char stack[], int *top) {
// Check for possible reductions
if (*top >= 2 && stack[*top - 2] == '(' && stack[*top] == ')' && stack[*top - 1] ==
'L') {
// Reduce (L) -> S
stack[*top - 2] = 'S';
*top -= 2;
printf("Reduce: S -> (L)\n");
return 1;
}
if (*top >= 0 && stack[*top] == 'a') {
// Reduce a -> S
stack[*top] = 'S';
printf("Reduce: S -> a\n");
Input: (a,a)$
Stack Action
( Shift: (
(a Shift: a
(a Reduce: S -> a
(aS Reduce: L -> S
(aS, Shift: ,
(aS,a Shift: a
(aS,a Reduce: S -> a
(aL Reduce: L -> L,S
S Reduce: S -> (L)
Input string is successfully parsed.
 return 1;
}
if (*top >= 2 && stack[*top - 1] == ',' && stack[*top] == 'S' && stack[*top - 2] ==
'L') {
// Reduce L,S -> L
stack[*top - 2] = 'L';
*top -= 2;
printf("Reduce: L -> L,S\n");
return 1;
}
if (*top >= 0 && stack[*top] == 'S') {
// Reduce S -> L
stack[*top] = 'L';
printf("Reduce: L -> S\n");
return 1;
}
return 0; // No reduction possible
}

// Function to parse the input string

void shiftReduceParse(char input[]) {
char stack[MAX] = {0};
int top = -1;
int idx = 0;
int length = strlen(input);

printf("Input: %s\n", input);

printf("Stack\t\tAction\n");

while (idx < length || top >= 0) {

// Print the stack and input
for (int i = 0; i <= top; i++) {
printf("%c", stack[i]);
}
printf("\t\t");
 if (idx < length) {
// Shift the next input symbol onto the stack
stack[++top] = input[idx++];
printf("Shift: %c\n", stack[top]);
} else {
printf("Reduce\n");
}

// Try to reduce
while (reduce(stack, &top)) {
// Keep reducing until no further reduction is possible
}
}

// Final check
if (top == 0 && stack[top] == 'S') {
printf("Input string is successfully parsed.\n");
} else {
printf("Error: Input string is invalid.\n");
}
}

// Main function
int main() {
char input[] = "(a,a)$";

shiftReduceParse(input);

return 0;
}
12.Write a program to design a LALR bottom-up parser for
the given language:
E→E+T | T
T→T*F | F
F→(E) | id for the input string id+id*id
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 100

typedef struct {
char action[10];
int state;
} ParsingTableEntry;

// Parsing table for the grammar

ParsingTableEntry actionTable[12][6]; // Action table
int gotoTable[12][3]; // Goto table

// Grammar rules
char *rules[] = {
"E -> E+T",
"E -> T",
"T -> T*F",
"T -> F",
"F -> (E)",
"F -> id"
};

// Helper function to initialize the parsing table

void initializeParsingTable() {
// Fill in actionTable
Stack Input Action
0 i+i*i$ s5
5 +i*i$ r6
...
Input string is valid.
 strcpy(actionTable[0][0].action, "s5"); // Shift state 5 on "id"
strcpy(actionTable[0][3].action, "s4"); // Shift state 4 on "("

strcpy(actionTable[1][1].action, "s6"); // Shift state 6 on "+"

strcpy(actionTable[1][5].action, "acc"); // Accept

strcpy(actionTable[2][2].action, "s7"); // Shift state 7 on "*"

strcpy(actionTable[2][1].action, "r2"); // Reduce T -> F
strcpy(actionTable[2][5].action, "r2");

strcpy(actionTable[3][1].action, "r4"); // Reduce F -> (E)

strcpy(actionTable[3][2].action, "r4");
strcpy(actionTable[3][5].action, "r4");

strcpy(actionTable[4][0].action, "s5");
strcpy(actionTable[4][3].action, "s4");

strcpy(actionTable[5][1].action, "r6"); // Reduce F -> id

strcpy(actionTable[5][2].action, "r6");
strcpy(actionTable[5][5].action, "r6");

// Fill in gotoTable
gotoTable[0][0] = 1; // Goto E
gotoTable[0][1] = 2; // Goto T
gotoTable[0][2] = 3; // Goto F

gotoTable[4][0] = 8;
gotoTable[4][1] = 2;
gotoTable[4][2] = 3;
}

// Function to parse input

void parseInput(char *input) {
int stack[MAX];
char symbols[MAX];
int top = 0;
stack[top] = 0; // Start state
int idx = 0;

printf("Stack\t\tInput\t\tAction\n");
while (1) {
int state = stack[top];
char symbol = input[idx];

// Determine the column in the action table

int col = -1;
if (symbol == 'i') col = 0; // "id"
else if (symbol == '+') col = 1; // "+"
else if (symbol == '*') col = 2; // "*"
else if (symbol == '(') col = 3; // "("
else if (symbol == ')') col = 4; // ")"
else if (symbol == '$') col = 5; // End marker

// Get action
ParsingTableEntry action = actionTable[state][col];

printf("%d\t\t%s\t\t%s\n", stack[top], &input[idx], action.action);

if (action.action[0] == 's') { // Shift

stack[++top] = atoi(&action.action[1]); // Push next state
idx++; // Move to the next input symbol
} else if (action.action[0] == 'r') { // Reduce
int rule = atoi(&action.action[1]) - 1;
char *ruleBody = strchr(rules[rule], '>') + 2;
int len = strlen(ruleBody);

// Pop the stack for each symbol in the rule

for (int i = 0; i < len; i++) {
top--;
}
 // Push the LHS of the rule
char lhs = rules[rule][0];
stack[++top] = gotoTable[stack[top - 1]][lhs - 'E'];
} else if (strcmp(action.action, "acc") == 0) { // Accept
printf("Input string is valid.\n");
break;
} else { // Error
printf("Error: Invalid input.\n");
break;
}
}
}

int main() {
initializeParsingTable();

char input[MAX] = "i+i*i$"; // Input string (id = i)

parseInput(input);

return 0;
}
13.Write a program to perform loop unrolling.

#include <stdio.h>

// Function to perform a regular loop

void regularLoop(int *arr, int size) {
for (int i = 0; i < size; i++) {
arr[i] += 1;
}
}

// Function to perform loop unrolling

void unrolledLoop(int *arr, int size, int unrollFactor) {
int i;
for (i = 0; i <= size - unrollFactor; i += unrollFactor) {
// Unrolled loop body
for (int j = 0; j < unrollFactor; j++) {
arr[i + j] += 1;
}
}
// Handle the remainder
for (; i < size; i++) {
arr[i] += 1;
}
}

int main() {
int size = 10;
int unrollFactor = 2; // Factor of unrolling
int arr1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int arr2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

printf("Original Array: ");

Array: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Unroll Factor: 2

Original Array: 0 1 2 3 4 5 6 7 8 9
After Regular Loop: 1 2 3 4 5 6 7 8 9 10
After Unrolled Loop: 1 2 3 4 5 6 7 8 9 10
 for (int i = 0; i < size; i++) {
printf("%d ", arr1[i]);
}
printf("\n");

// Regular loop
regularLoop(arr1, size);
printf("After Regular Loop: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr1[i]);
}
printf("\n");

// Loop unrolling
unrolledLoop(arr2, size, unrollFactor);
printf("After Unrolled Loop: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr2[i]);
}
printf("\n");

return 0;
}