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:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
Experiment Date
int main() {
char input[1000];

FacultyName:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
Experiment Date

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

FacultyName:- Sign.WithDate
 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 lex.yy.c -o lexer
./lexer

3. Enter code to analyze, for example:

int main()
{ int a =
5;

FacultyName:- Sign.WithDate
Experiment Date

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

FacultyName:- Sign.WithDate
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 "y.tab.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:- Sign.WithDate
Experiment Date

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

FacultyName:- Sign.WithDate
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:- Sign.WithDate
Experiment Date

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

FacultyName:- Sign.WithDate
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 lex.yy.c -o id && ./id.

Command:-

Input:-

Output:-

◆ c) Calculator using LEX &

YACC calc.l (LEX file)
%{
#include "y.tab.h"
FacultyName:- Sign.WithDate
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:- Sign.WithDate
Experiment Date

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

FacultyName:- Sign.WithDate
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:- Sign.WithDate
Experiment Date

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

FacultyName:- Sign.WithDate
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:- Sign.WithDate
Experiment Date

Name-Divya RollNo:2201320100064

#include "lex.yy.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 "y.tab.h"
#include <stdlib.h>
#include
<string.h>
%}

%%

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

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

%%

Input:-

Output:-

FacultyName:- Sign.WithDate
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:- Sign.WithDate
Experiment Date

Name-Divya RollNo:2201320100064
}

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

FacultyName:- Sign.WithDate
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:- Sign.WithDate
Experiment Date

Name-Divya RollNo:2201320100064

Compilation:-

FacultyName:- Sign.WithDate
Experiment Date

Name-Divya RollNo:2201320100064

Input:-

Output:-

FacultyName:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
Experiment Date

Name-Divya RollNo:2201320100064
}
return 0;
}

FacultyName:- Sign.WithDate
Experiment Date

Name-Divya RollNo:2201320100064

Input :-

Output :-

FacultyName:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
Experiment Date

Name-Divya RollNo:2201320100064

FacultyName:- Sign.WithDate
Experiment Date

Name-Divya RollNo:2201320100064

Output:-

FacultyName:- Sign.WithDate
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:- Sign.WithDate
Experiment Date

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

FacultyName:- Sign.WithDate
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:- Sign.WithDate
Experiment Date

Name-Divya RollNo:2201320100064

}
printf("\n");
}

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

Output:-

FacultyName:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate
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:- Sign.WithDate