Experiment Date

Name- SHWETANK SHUKLA Roll No:2201320100064

PROGRAM NO:-1
OBJECT: Design and implement a lexical analyzer for given language using C
and the lexical analyzer should ignore redundant spaces, tabs, and new lines.

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

#define MAX_KEYWORDS 10

// List of keywords
char *keywords[MAX_KEYWORDS] = {
"if", "else", "while", "do", "int", "float", "return", "char", "for", "break"
};

// Function to check if a string is a

keyword int isKeyword(char *str) {
for (int i = 0; i < MAX_KEYWORDS; i++)
{ if (strcmp(keywords[i], str) == 0) return
1;
}
return 0;
}

// Function to check if a character is a delimiter

int isDelimiter(char ch) {
return (ch == ' ' || ch == '+' || ch == '-' || ch == '*'
|| ch == '/' || ch == ',' || ch == ';' || ch == '>' ||
ch == '<' || ch == '=' || ch == '(' || ch == ')' ||
ch == '[' || ch == ']' || ch == '{' || ch == '}' || ch == '\n' || ch == '\t');
}
// Function to check if character is an operator
int isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '=' || ch == '>' || ch == '<');
}

FacultyName:- [Link]
Experiment Date

// Function to check if a string is a number

int isNumber(char *str) {
for (int i = 0; str[i]; i++) {
if (!isdigit(str[i])) return 0;

FacultyName:- [Link]
Experiment Date

Name- Divya Roll No:2201320100064

}
return 1;
}

// Function to extract and classify tokens

void lexicalAnalyzer(char *input) {
int left = 0, right = 0;
int length = strlen(input);

while (right <= length) {

if (!isDelimiter(input[right])) { right+
+;
} else {
if (left != right) {
char *subStr = (char *)malloc(right - left + 1);
strncpy(subStr, input + left, right - left);
subStr[right - left] = '\0';

if (isKeyword(subStr))
printf("'%s' : Keyword\n", subStr);
else if (isNumber(subStr))
printf("'%s' : Number\n", subStr);
else
printf("'%s' : Identifier\n", subStr);

free(subStr);
}

if (isOperator(input[right]))
printf("'%c' : Operator\n", input[right]);
else if (input[right] != ' ' && input[right] != '\n' && input[right] != '\
t') printf("'%c' : Delimiter\n", input[right]);

right++;
left =
right;
}
}
}
FacultyName:- [Link]
Experiment Date
int main() {
char input[1000];

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

printf("Enter the source code (end input with EOF - Ctrl+D on Linux/Mac or Ctrl+Z on
Windows):\n");
fgets(input, sizeof(input), stdin);
lexicalAnalyzer(input);
return 0;
}

Input:-

int a = 10; if (a > 5) a = a +

1; Output:-

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

PROGRAM N0:02
Object: Implementation of Lexical Analyzer using Lex Tool.

%{
#include <stdio.h>
#include <stdlib.h>
%}

// Define regular expressions for

patterns DIGIT [0-9]
LETTER [a-zA-Z]
ID {LETTER}({LETTER}|
{DIGIT})* NUMBER {DIGIT}+

%%

"int" { printf("KEYWORD: int\n"); }

"float" { printf("KEYWORD: float\
n"); } "char"
{ printf("KEYWORD: char\n"); }
"if" { printf("KEYWORD: if\n"); }
"else" { printf("KEYWORD: else\n"); }
"while" { printf("KEYWORD: while\
n"); }

{ID} { printf("IDENTIFIER: %s\n", yytext); }

{NUMBER} { printf("NUMBER: %s\n", yytext); }

"+" { printf("OPERATOR: +\n"); }

"-" { printf("OPERATOR: -\n"); }
"*" { printf("OPERATOR: *\n"); }
"/" { printf("OPERATOR: /\n"); }
"=" { printf("OPERATOR: =\n"); }

"(" { printf("PUNCTUATION: (\n"); }

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
")" { printf("PUNCTUATION: )\n"); }
"{" { printf("PUNCTUATION: {\n"); }
"}" { printf("PUNCTUATION: }\n"); }
";" { printf("PUNCTUATION: ;\n"); }

FacultyName:- [Link]
 Experiment Date

Name-Divya RollNo:2201320100064
[ \t\n]+ { /* Ignore whitespace */ }

. { printf("UNKNOWN CHARACTER: %s\n", yytext); }

%%

int main(int argc, char **argv)

{ printf("Enter input code:\
n"); yylex();
return 0;
}
(
)
}
{
Output: r
int e
y t
y u
w r
r n
a
p 1
;

Steps to Compile and Run

1. Save the file as lexer.l.
2. Open terminal and run:

bash
CopyEdit
lex lexer.l
gcc [Link].c -o lexer
./lexer

3. Enter code to analyze, for example:

int main()
{ int a =
5;

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
float b = 10.5;
if (a < b) {
a = a + 1;
}
}

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
PROGRAM N0: 03

Generate YACC specification for a few syntactic categories.

a) Program to recognize a valid arithmetic expression that uses
operator +, –, * and /.
b) Program to recognize a valid variable which starts with a letter
followed by any number of letters or digits.
c) Implementation of Calculator using LEX and YACC
d) Convert the BNF rules into YACC form and write code to generate
abstract syntax tree

◆ a) Recognize a Valid Arithmetic Expression (+, –,

*, /) expr.l (LEX file)
%{
#include "[Link].h"
%}

digit [0-9]

%%

{digit}+ { yylval = atoi(yytext); return

NUMBER; } [+*/-] { return yytext[0]; }
[\n] { return 0; }
[ \t] ; // skip whitespace

. { return yytext[0]; }

%%
expr.y (YACC file)
%{
#include <stdio.h>
#include <stdlib.h>
%}

%token NUMBER

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
%left '+' '-'
%left '*' '/'

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

%%
input: expression '\n' { printf("Valid Expression\n"); return 0; }
;

expression:
expression '+' expression
| expression '-' expression
| expression '*' expression
| expression '/' expression
| NUMBER
;

%%

int main() {
printf("Enter arithmetic expression:
"); yyparse();
return 0;
}

int yyerror(char *msg)

{ printf("Invalid Expression\
n"); return 0;
}

Sample Input:-

Output:-

◆ b) Recognize Valid Identifier (Starts with a Letter, Then

Letters/Digits) identifier.l
FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
%{
#include <stdio.h>

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

%}
letter [a-zA-Z]
digit [0-9]

%%

{letter}({letter}|{digit})* { printf("Valid Identifier: %s\n", yytext); }

.|\n ;

%%
int main()
{ yylex();
return 0;
}
`^ Compile and test this file using lex identifier.l && gcc [Link].c -o id && ./id.

Command:-

Input:-

Output:-

◆ c) Calculator using LEX &

YACC calc.l (LEX file)
%{
#include "[Link].h"
FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

%%

[0-9]+ { yylval = atoi(yytext); return

NUMBER; } [\n] { return 0; }
[+*/()-] { return yytext[0]; }
[ \t] ; // ignore whitespace

%%
calc.y (YACC file)
%{
#include <stdio.h>
#include <stdlib.h>
%}

%token NUMBER
%left '+' '-'
%left '*' '/'
%right UMINUS

%%
input:
| input line
;

line:
'\n'
| expression '\n' { printf("Result = %d\n", $1); }
;

expression:
expression '+' expression { $$ = $1 + $3; }
| expression '-' expression { $$ = $1 - $3; }
| expression '*' expression { $$ = $1 * $3; }
| expression '/' expression { $$ = $1 / $3; }
| '-' expression %prec UMINUS { $$ = -$2; }

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
| '(' expression ')' { $$ = $2; }
| NUMBER
;

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

%%

int main() {
printf("Enter expression:\n");
yyparse();
return 0;
}

int yyerror(char *s)

{ printf("Syntax error: %s\n",
s); return 0;
}
Input:-

Output:-

◆ d) Convert BNF to YACC and Generate Abstract Syntax Tree

(AST) Sample BNF Rule
E→E+T|T
T→T*F|F
F → (E) | id
ast.y (YACC + AST building)
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {

char val[10];
struct node *left, *right;
} Node;

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
Node* create(char *op, Node *l, Node *r) {

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

Node* t = (Node*)
malloc(sizeof(Node)); strcpy(t->val, op);
t->left = l;
t->right =
r; return t;
}

void preorder(Node* t) {
if(t) {
printf("%s ", t-
>val); preorder(t-
>left); preorder(t-
>right);
}
}

%}
%union
{ char* str;
Node* ptr;
}

%token <str> ID
%left '+' '-'
%left '*' '/'
%type <ptr> E T F

%%
S : E { printf("AST (Prefix): "); preorder($1); printf("\n"); return 0; };
E : E '+' T { $$ = create("+", $1, $3); }
| E '-' T { $$ = create("-", $1, $3); }
|T { $$ = $1; };T : T '*' F { $$ = create("*", $1, $3); }
| T '/' F { $$ = create("/", $1, $3); }
|F { $$ = $1; };F : '(' E ')' { $$ = $2; }
| ID { $$ = create($1, NULL, NULL); };

%%

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

#include "[Link].c"
int main() {
printf("Enter expression: ");
yyparse();
return 0;
}

int yyerror(char *s)

{ printf("Syntax Error: %s\n",
s); return 0;
}
ast.l (LEX file)
%{
#include "[Link].h"
#include <stdlib.h>
#include
<string.h>
%}

%%

[a-zA-Z_][a-zA-Z0-9_]* { [Link] = strdup(yytext); return

ID; } [+*/()-] { return yytext[0]; }
[ \t\n] ;
. ;

%%

Input:-

Output:-

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

PROGRAM NO:04

Program to Find ε-Closure of All States in NFA with ε-Transition

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

#define MAX 10

int epsilon[MAX][MAX];
int eclosure[MAX][MAX];
int visited[MAX];
int n;

void findEclosure(int state, int root) {

int i;
for (i = 0; i < n; i++) {
if (epsilon[state][i] && !visited[i])
{ visited[i] = 1;
eclosure[root][i] = 1;
findEclosure(i, root);
}
}
}

int main()
{ int i, j;

printf("Enter the number of states: ");

scanf("%d", &n);

printf("Enter epsilon transitions (Enter 1 if there is ε-transition from state i to state j, else
0):\n");
for (i = 0; i < n; i++)
{ for (j = 0; j < n; j++)
{
scanf("%d", &epsilon[i][j]);
}

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
}

for (i = 0; i < n; i++) {

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

for (j = 0; j < n; j++) visited[j] = 0;

visited[i] = 1;
eclosure[i][i] = 1;
findEclosure(i, i);
}

printf("\nEpsilon Closure of each state:\n");

for (i = 0; i < n; i++) {
printf("ε-closure(q%d) = { ", i);
for (j = 0; j < n; j++) {
if (eclosure[i][j]) printf("q%d ", j);
}
printf("}\n");
}

return 0;
}

eclosure.1(flex file)

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

Compilation:-

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

Input:-

Output:-

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

PROGRAM NO:05

5. Convert NFA with ε to NFA without ε

This program uses the ε-closure computed above to eliminate ε-transitions.
#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int epsilon[MAX][MAX], trans[MAX][MAX][MAX];

int eclosure[MAX][MAX], result[MAX][MAX];
int visited[MAX];
int states, symbols;

void computeEclosure(int state, int root)

{ for (int i = 0; i < states; i++) {
if (epsilon[state][i] && !visited[i])
{ visited[i] = 1;
eclosure[root][i] = 1;
computeEclosure(i, root);
}
}
}

int main()
{ int i, j,
k;

printf("Enter number of states: ");

scanf("%d", &states);
printf("Enter number of symbols (excluding ε): ");
scanf("%d", &symbols);

// Input ε-transitions
printf("Enter epsilon transitions matrix:\n");
for (i = 0; i < states; i++)
for (j = 0; j < states; j++)
scanf("%d", &epsilon[i][j]);

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

// Input normal transitions

for (k = 0; k < symbols; k++) {
printf("Enter transitions for symbol %c (matrix):\n", 'a' + k);
for (i = 0; i < states; i++)
for (j = 0; j < states; j++)
scanf("%d", &trans[i][j][k]);
}
// Compute ε-closure
for (i = 0; i < states; i++) {
for (j = 0; j < states; j++) visited[j] = 0;
visited[i] = 1;
eclosure[i][i] = 1;
computeEclosure(i, i);
}
// Remove ε-transitions
for (i = 0; i < states; i++)
{
for (k = 0; k < symbols; k++)
{ for (j = 0; j < states; j++) {
if (eclosure[i][j]) {
for (int m = 0; m < states; m++) {
if (trans[j][m][k])
result[i][m] = 1;
}
}
}
}
}
printf("\nNFA without ε-transitions (for each symbol):\n"); for (k = 0; k < symbols; k++) {
printf("On symbol %c:\n", 'a' + k);
for (i = 0; i < states; i++) {
printf("From q%d: ", i);
for (j = 0; j < states; j++)
{
if (result[i][j]) printf("q%d ", j);
}
printf("\n");
}
FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
}
return 0;
}

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

Input :-

Output :-

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

PROGRAM NO:06
6. Convert NFA to
DFA #include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 20

int nfa[MAX][MAX], dfa[MAX][MAX];

int n, symbol_count;
int state_map[MAX][MAX], dfa_states[MAX][MAX], dfa_state_count = 0; int compare(int
a[], int b[], int len) {
for (int i = 0; i < len; i++) if (a[i] != b[i]) return 0;
return 1;
}

int exists(int arr[][MAX], int row) {

for (int i = 0; i < dfa_state_count; i++) {
if (compare(arr[i], arr[row], n)) return 1;
}
return 0;
}

void copy(int dest[], int src[]) {

for (int i = 0; i < n; i++) dest[i] = src[i];
}

void add_state(int src[])

{ copy(dfa_states[dfa_state_count++], src);
}

void print_dfa() {
printf("\nDFA Transition Table:\n");
for (int i = 0; i < dfa_state_count; i++)
{
printf("DFA State %d: { ", i);

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
for (int j = 0; j < n; j++) if (dfa_states[i][j]) printf("q%d ", j); printf("}\
n");

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

for (int k = 0; k < symbol_count; k++)

{ printf(" on '%c' -> ", 'a' + k);
for (int j = 0; j < n; j++)
{ if (dfa[i][k] == j) {
printf("DFA State %d\n", j);
break;
}
}
}
}
}

int main()
{ int i, j,
k;
printf("Enter number of NFA states: ");
scanf("%d", &n);
printf("Enter number of symbols: ");
scanf("%d", &symbol_count);
printf("Enter the transition table (for each symbol):\n");
for (k = 0; k < symbol_count; k++) {
printf("On symbol %c:\n", 'a' + k);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &nfa[i * symbol_count + k][j]);
}
}
}

// initial DFA state = {0}

int initial[MAX] = {0};
initial[0] = 1;
add_state(initial);

for (i = 0; i < dfa_state_count; i++)

{ for (k = 0; k < symbol_count; k++)
{
int new_state[MAX] =
{0}; for (j = 0; j < n; j++) {

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
if (dfa_states[i][j]) {
for (int m = 0; m < n; m++) {
if (nfa[j * symbol_count + k][m])

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

new_state[m] = 1;
}
}
}

// Check if new_state already exists

int exists_flag = 0, state_index = -1;
for (int s = 0; s < dfa_state_count; s++) {
if (compare(dfa_states[s], new_state, n))
{ exists_flag = 1;
state_index = s;
break;
}
}

if (!exists_flag) {
state_index = dfa_state_count;
add_state(new_state);
}
dfa[i][k] = state_index;
}
}
print_dfa();
return 0;
}

Input:-

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

Output:-

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

PROGRAM NO:07

PROGRAM 7: Operator Precedence Parser

// This is a simplified operator precedence parser using a hardcoded
precedence table
#include <stdio.h>
#include <string.h>

char stack[50], input[50];

int top = -1, i = 0;

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

void pop()
{ top--;
}

int precedence(char op)

{ switch(op) {
case '+':

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
case '-': return
1; case '*':
case '/': return 2;

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

default: return 0;
}
}
void operatorPrecedenceParser()
{ printf("Enter expression: ");
scanf("%s", input);
push('$');
char c;
c = input[i++];
while (c != '\0') {
if (c == '+' || c == '-' || c == '*' || c == '/') {
while (precedence(stack[top]) >= precedence(c))
{ printf("%c", stack[top]);
pop();

}
push(c);
} else {
printf("%c", c);
}
c = input[i++];
}
while (stack[top] != '$') {
printf("%c", stack[top]);
pop();

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

}
printf("\n");
}

int main2()
{ operatorPrecedenceParser();
return 0;
}
Input:-

Output:-

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

PROGRAM NO:08
// PROGRAM 3: First and Follow Simulation (static example)
// Grammar: E -> TE'
// E' -> +TE' | ε
// T -> FT'
// T' -> *FT' | ε
// F -> (E) | id
// FIRST(E) = FIRST(T) = FIRST(F) = { '(', id }
// FOLLOW(E) = { $, ')' }
// FOLLOW(T) = { +, $, ')' }
// PROGRAM 8: Recursive Descent Parser
#include <stdio.h>
#include <string.h>
char input[10];
int i = 0;
void
E();
void E1();
void T();
void T1();
void F();
void E() { T(); E1(); }
void E1() {
if (input[i] == '+') {
i++; T(); E1();
}
}
void T() { F(); T1(); }
void T1() {
if (input[i] == '*') {
i++; F(); T1();
}
}
void F() {

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064
if (input[i] == '(')
{ i++; E();
if (input[i] == ')') i++;
else printf("Missing closing parenthesis\n");
} else if (isalnum(input[i]))
{ i++;

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

} else {
printf("Invalid character\n");
}
}

int main3() {
printf("Enter expression: ");
scanf("%s", input);
E();
if (input[i] == '\0') printf("Valid expression\n");
else printf("Invalid expression\n");
return 0;
}

Valid Input:-

Invalid input:-

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

// PROGRAM 9:
Loop Unrolling
#include <stdio.h> int main4() {
int i;
printf("Loop Unrolling Example (Original Loop):\n");
for (i = 0; i < 8; i++) printf("i = %d\n", i);

printf("\nUnrolled Loop (2 times):\n");

for (i = 0; i < 8; i += 2) {
printf("i = %d\n", i);
printf("i = %d\n", i + 1);
}
return 0;
}

OUTPUT:

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

// PROGRAM 10: Constant Propagation

#include <stdio.h>
int main5() {
int a = 5;
int b = a +
3; int c = b
* 2;
printf("Result = %d\n", c); // Constant propagation can make b = 8, so c = 16
return 0;
}

OUTPU

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

// PROGRAM 11: Intermediate Code Generation (3-address form)

#include <stdio.h>
int main6() {
char expr[] = "a = b + c * d";
printf("t1 = c * d\n");
printf("t2 = b + t1\n");
printf("a = t2\n");
return 0;
}

Output:

FacultyName:- [Link]
Experiment Date

Name-Divya RollNo:2201320100064

// PROGRAM 12: 8086 Code Generation from Three Address Code.

#include <stdio.h>
int main7() {
printf("MOV C, R1\n");
printf("MUL D\n");
printf("MOV R1, T1\n");
printf("ADD B, T1\n");
printf("MOV T1, A\n");
return 0;
}

Output:

FacultyName:- [Link]