Subject : Compiler Design Lab (BCS-652) Dept.
of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
EXPERIMENT - 01
AIM - Designing and implementing a lexical analyzer for given language
using C and the lexical analyzer should ignore redundant spaces, tabs and
new lines.
-> #include <stdio.h>
#include <ctype.h>
#include <string.h>
char keywords[6][10] = {"int", "float", "if", "else", "while", "return"};
int isKeyword(char str[]) {
for (int i = 0; i < 6; i++) {
if (strcmp(keywords[i], str) == 0)
return 1;
return 0;
int main() {
char ch, buffer[20];
int i = 0;
FILE *fp;
fp = fopen("[Link]", "r");
if (fp == NULL) {
printf("Cannot open file\n");
return 0;
while ((ch = fgetc(fp)) != EOF) {
/* Ignore all whitespace (space, tab, newline) */
if (isspace(ch))
1
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
continue;
/* Identifier or Keyword */
if (isalpha(ch)) {
buffer[i++] = ch;
while (isalnum(ch = fgetc(fp))) {
buffer[i++] = ch;
buffer[i] = '\0';
i = 0;
fseek(fp, -1, SEEK_CUR);
if (isKeyword(buffer))
printf("Keyword: %s\n", buffer);
else
printf("Identifier: %s\n", buffer);
/* Number */
else if (isdigit(ch)) {
buffer[i++] = ch;
while (isdigit(ch = fgetc(fp))) {
buffer[i++] = ch;
buffer[i] = '\0';
i = 0;
fseek(fp, -1, SEEK_CUR);
printf("Number: %s\n", buffer);
/* Operators */
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '=') {
2
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
printf("Operator: %c\n", ch);
/* Delimiters */
else if (ch == ';' || ch == ',' || ch == '(' || ch == ')' ||
ch == '{' || ch == '}') {
printf("Delimiter: %c\n", ch);
/* Invalid characters */
else {
printf("Invalid character: %c\n", ch);
fclose(fp);
return 0;
[Link]
int a = 10;
float b = 20;
if(a < b)
a = a + b;
3
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
OUTPUT:-
4
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
EXPERIMENT - 02
AIM - Implementing a Lexical Analyzer using the Lex tool to identify tokens
such as keywords, identifiers, numbers, operators, and special symbols in a
given input program.
-> Theory
A Lexical Analyzer is the first phase of a compiler. It reads the source code character by
character and converts it into [Link] are the smallest meaningful units of a program
such as: Keywords, Identifiers, Constants, Operators, Special symbols .The Lex tool is used
to generate lexical analyzers automatically. It uses regular expressions to define token
patterns and produces a C program for scanning [Link] program consists of three
sections:
1. Definition Section
2. Rules Section
3. User Subroutines Section
Structure:
%{
C declarations
%}
%%
pattern
%%
action
user functions
Algorithm
1. Start the program.
2. Define token patterns using regular expressions.
3. Read the input program.
4. Match the input with defined patterns.
5. Identify tokens such as keywords, identifiers, numbers, operators, and symbols.
5
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
6. Display the token type.
7. Repeat until the end of input.
8. Stop.
Program
%{
#include<stdio.h>
#include<stdlib.h>
%}
%%
int|float|char|double|if|else|while|return
{ printf("Keyword : %s\n", yytext); }
[0-9]+
{ printf("Number : %s\n", yytext); }
[a-zA-Z][a-zA-Z0-9]*
{ printf("Identifier : %s\n", yytext); }
"+"|"-"|"*"|"/"
{ printf("Arithmetic Operator : %s\n", yytext); }
"="
{ printf("Assignment Operator : %s\n", yytext); }
";"
{ printf("Special Symbol : %s\n", yytext); }
[ \t\n]
{ } { printf("Invalid Token : %s\n", yytext); }
%%
int main()
printf("Enter the input program:\n");
yylex();
6
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
return 0;
int yywrap()
return 1;
Commands Used
Step 1: Create lex file
vi lexical.l
Step 2: Run Lex
lex lexical.l
Step 3: Compile program
gcc [Link].c -o lexical
Step 4: Execute
./lexical
OUTPUT:-
7
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
EXPERIMENT - 03
AIM - Generating YACC Specifications for Different Syntactic Categories.
• Recognizing a valid arithmetic expression using operators +, -, *, /
• Recognizing a valid variable name starting with a letter followed by letters
or digits
• Implementation of a calculator using LEX and YAC
-> Introduction to YACC:
YACC (Yet Another Compiler Compiler) is a tool used to generate a parser for a
programming language. It works together with Lex, where Lex performs lexical analysis
(token generation) and YACC performs syntax analysis (checking grammar rules). YACC
reads a grammar specification and produces a C program that parses input according to the
given grammar rules.
Structure of a YACC Program :
A YACC program consists of three sections separated by %%.
%{
C Declarations
%}
%%
Grammar Rules
%%
User Functions
I. Definition Section: This section contains header files, token declarations, and variable
definitions.
[Link] Section: This section contains grammar rules and the syntax structure of the
language.
[Link] Subroutines: This section contains functions such as main() and yyerror().
3. Working of LEX and YACC Together
Input Program
8
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
Lex (Scanner)
Tokens
YACC (Parser)
Syntax Checking / Evaluation
Output
Part (a) : Program to Recognize a Valid Arithmetic Expression
YACC Program :
%{
#include<stdio.h>
#include<stdlib.h>
%}
%token NUMBER
%%
E:E'+'E
| E'+'E
|E'-'E
| E'*'E
|E'/'E
NUMBER
%%
int main()
printf("Enter Arithmetic Expression:\n");
yyparse();
9
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
return 0;
int yyerror()
printf("Invalid Expression\n");
return 0;
Lex Program:
%{
#include "[Link].h"
%}
%%
[0-9]+ { return NUMBER; }
[+-*/] { return yytext[0]; }
\n { return 0; } [ \t] ;
%%
int yywrap()
return 1;
Example Input:
5+3*2
Output:
Valid Expression
Part (b): Program to Recognize a Valid Variable
Rule: A valid variable
• Must start with a letter.
• Must be followed by letters or digits
10
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
Lex Program :
%{
#include<stdio.h>
%}
%%
[a-zA-Z][a-zA-Z0-9]* { printf("Valid Variable\n"); }
. { printf("Invalid Variable\n"); }
%%
int main() {
printf("Enter Variable:\n");
yylex();
int yywrap() {
return 1;
Example Input:
0 var123
Output :
Valid Variable
Part (c): Calculator Implementation using LEX and YACC YACC Program:
%{
#include<stdio.h>
#include<stdlib.h>
%}
%token NUMBER
%%
E: E'+'E { printf("Result = %d\n", $1+$3); }
| E'-'E { printf("Result = %d\n", $1-$3); }
11
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
| E'*'E { printf("Result = %d\n", $1*$3); }
| E'/'E { printf("Result = %d\n", $1/$3); }
| NUMBER { $$=$1; }
%%
int main() {
printf("Enter Expression:\n");
yyparse();
return 0;
int yyerror() {
printf("Error in expression\n");
return 0;
Lex Program :
%{
#include "[Link].h"
%}
%%
[0-9]+ { yylval=atoi(yytext); return NUMBER; }
[+\-*/] { return yytext[0]; }
\n { return 0; }
[ \t] ;
%%
int yywrap() {
return 1;
Example Input: 8+2 , Output : Result = 10
12
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
EXPERIMENT - 04
AIM - Writing a program to find ε-closure of all states of a given NFA with
ε-transitions.
-> CODE (C Program)
#include <stdio.h>
#define MAX 10
int n;
int e[MAX][MAX];
void epsilonClosure(int state, int visited[]) {
printf("%d ", state);
visited[state] = 1;
for (int i = 0; i < n; i++) {
if (e[state][i] == 1 && !visited[i]) {
epsilonClosure(i, visited);
}}}
int main() {
printf("Enter number of states: ");
scanf("%d", &n);
printf("Enter epsilon transition matrix:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &e[i][j]);
}}
for (int i = 0; i < n; i++) {
int visited[MAX] = {0};
printf("Epsilon-closure of state %d: { ", i);
epsilonClosure(i, visited);
13
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
printf("}\n");
} return 0;
SAMPLE INPUT
Enter number of states: 3
Enter epsilon transition matrix: 0 1 0 , 0 0 1 , 0 0 0
SAMPLE OUTPUT
Epsilon-closure of state 0: { 0 1 2 }, Epsilon-closure of state 1: { 1 2 }, Epsilon-closure of
state 2: { 2 }
14
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
EXPERIMENT - 05
AIM - Writing a program to convert an NFA with ε-transitions into an NFA
without ε-transitions.
-> CODE (C Program)
#include <stdio.h>
#define MAX 10
int n, m; // n = states, m = input symbols
void epsilonClosure(int state, int visited[], int index) {
for (int i = 0; i < n; i++) { if (e[state][i] == 1 && !visited[i]) {
epsilonClosure(i, visited, index);} } }
int main() {
printf("Enter number of states: ");
scanf("%d", &n);
printf("Enter number of input symbols: ");
scanf("%d", &m);
printf("Enter epsilon transition matrix:\n");
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) {
scanf("%d", &e[i][j]); } }
printf("Enter transition table (for each symbol):\n");
for (int k = 0; k < m; k++) {
printf("For symbol %d:\n", k);
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) {
scanf("%d", &trans[i][k][j]); } } }
printf("\nEpsilon Closures:\n");
for (int i = 0; i < n; i++) {
printf("Closure(%d): ", i);
for (int j = 0; j < n && closure[i][j] != 0; j++) {
15
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
printf("%d ", closure[i][j]); }
printf("\n"); }
printf("\nNew Transition Table (without epsilon):\n");
for (int i = 0; i < n; i++) { for (int k = 0; k < m; k++) {
printf("From state %d on symbol %d: ", i, k);
for (int j = 0; j < n; j++) {
if (closure[i][j]) {
for (int x = 0; x < n; x++) {
if (trans[j][k][x]) {
printf("%d ", x); } } } }
printf("\n"); } }
return 0; }
SAMPLE INPUT
Enter number of states: 2
Enter number of input symbols: 1
Epsilon matrix:
01
00
SAMPLE OUTPUT
Epsilon Closures:
Closure(0): 0 1
Closure(1): 1
New Transition Table (without epsilon):
From state 0 on symbol 0: 1
From state 1 on symbol 0: 1
16
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
EXPERIMENT - 06
AIM - Writing a program to convert a Non-deterministic Finite Automaton
(NFA) into an equivalent Deterministic Finite Automaton (DFA).
-> CODE (C Program)
#include <stdio.h>
#include <string.h>
#define MAX 10
int n, m; int nfa[MAX][MAX][MAX]; int dfa[MAX][MAX]; int visited[MAX]; int
dfa_states[MAX][MAX];
int dfa_count = 0; int addState(int state[]) {
for (int i = 0; i < dfa_count; i++) {
if (isEqual(dfa_states[i], state))
return i; }
for (int i = 0; i < n; i++)
dfa_states[dfa_count][i] = state[i];
return dfa_count++; }
int main() {
printf("Enter number of states: ");
scanf("%d", &n);
printf("Enter number of input symbols: ");
scanf("%d", &m);
printf("Enter NFA transition table:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
printf("Number of transitions from state %d on symbol %d: ", i, j);
int count;
scanf("%d", &count);
17
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
for (int i = 0; i < dfa_count; i++) {
for (int j = 0; j < m; j++) {
int newState[MAX] = {0};
for (int k = 0; k < n; k++) {
if (dfa_states[i][k]) {
for (int x = 0; x < n; x++) {
if (nfa[k][j][x])
newState[x] = 1; } } }
printf("\nDFA Transition Table:\n");
for (int i = 0; i < dfa_count; i++) {
printf("State %d: ", i);
for (int j = 0; j < m; j++) {
printf("%d ", dfa[i][j]); }
printf("\n"); }
return 0; }
SAMPLE INPUT
Enter number of states: 2
Enter number of input symbols: 2
State 0:
Symbol 0 → 1 state → 0
Symbol 1 → 1 state → 0
State 1:
Symbol 0 → 1 state → 1
Symbol 1 → 1 state → 1
SAMPLE OUTPUT
DFA Transition Table:
State 0: 0 0
State 1: 1 1
18
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
EXPERIMENT - 07
AIM - Writing a program to minimize a given Deterministic Finite Automaton
(DFA)
-> CODE (C Program)
#include <stdio.h>
#define MAX 10
int n, m; int dfa[MAX][MAX]; int final[MAX]; int table[MAX][MAX];
int main() {
printf("Enter number of states: ");
printf("Enter number of input symbols: ");
scanf("%d", &m&n);
printf("Enter DFA transition table:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &dfa[i][j]); } }
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (final[i] != final[j])
table[i][j] = 1;
else
table[i][j] = 0; } }
int changed;
do {
changed = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
19
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
if (table[i][j] == 0) {
for (int k = 0; k < m; k++) {
int p = dfa[i][k]; int q = dfa[j][k];
if (p != q) {
if (table[p][q] == 1 || table[q][p] == 1) {
table[i][j] = 1;
changed = 1;
break; } } } } } }
} while (changed);
printf("\nEquivalent States:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (table[i][j] == 0) {
printf("(%d, %d)\n", i, j); } } }
return 0; }
SAMPLE INPUT
Enter number of states: 3
Enter number of input symbols: 2
Transition table:
01
02
01
Final states:
011
SAMPLE OUTPUT
Equivalent States:
(2, 1)
20
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
EXPERIMENT - 08
AIM - Constructing a Recursive Descent Parser for arithmetic expressions.
-> CODE (Python)
import re
TOKEN_SPEC = [
('NUMBER', r'\d+'), ('PLUS', r'\+'), ('MINUS', r'-'), ('MUL', r'\*'), ('DIV', r'/'), ('LPAREN', r'\('),
('RPAREN', r'\)'),
('SKIP', r'[ \t]+'), ]
TOKEN_REGEX = '|'.join(f'(?P<{name}>{pattern})' for name, pattern in TOKEN_SPEC)
class Token:
def __init__(self, type_, value):
[Link] = type_
[Link] = value
def tokenize(text):
tokens = []
for match in [Link](TOKEN_REGEX, text):
if [Link] != 'SKIP':
[Link](Token([Link], [Link]()))
return tokens
class Parser:
def __init__(self, tokens):
[Link] = tokens
[Link] = 0
def current(self):
if [Link] < len([Link]):
return [Link][[Link]]
21
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
return None
def eat(self, token_type):
token = [Link]()
if token and [Link] == token_type:
[Link] += 1
else:
raise SyntaxError("Invalid Expression")
def E(self):
self.T()
while [Link]() and [Link]().type in ('PLUS', 'MINUS'):
[Link]([Link]().type)
self.T()
def T(self):
self.F()
while [Link]() and [Link]().type in ('MUL', 'DIV'):
[Link]([Link]().type)
self.F()
def F(self):
token = [Link]()
if [Link] == 'NUMBER':
[Link]('NUMBER')
elif [Link] == 'LPAREN':
[Link]('LPAREN')
self.E()
[Link]('RPAREN')
else:
raise SyntaxError("Invalid Expression")
expr = input("Enter expression: ")
22
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
tokens = tokenize(expr)
parser = Parser(tokens)
try:
parser.E()
if [Link]() is None:
print("Valid Expression")
else:
print("Invalid Expression")
except:
print("Invalid Expression")
SAMPLE INPUT
3 + 5 * (2 - 4)
OUTPUT
Valid Expression
23
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
EXPERIMENT - 09
AIM - Constructing a Shift Reduce Parser for a given language.
-> CODE (Python)
stack = []
input_string = input("Enter the input string (use 'id' for identifiers): ") + "$"
productions = { "E+E": "E", "E*E": "E", "(E)": "E", "id": "E" }
i=0
print("\nStack\tInput\tAction")
while True:
[Link](input_string[i])
i += 1
print("".join(stack), "\t", input_string[i:], "\tShift")
while True:
reduced = False
for rhs in productions:
if "".join(stack).endswith(rhs):
# Perform reduction
stack = list("".join(stack)[:-len(rhs)] + productions[rhs])
print("".join(stack), "\t", input_string[i:], f"Reduce {rhs}→E")
reduced = True
break
if not reduced:
break
if "".join(stack) == "E" and input_string[i] == "$":
print("E\t$\tAccept")
break
24
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
if i >= len(input_string):
print("Error")
break
SAMPLE INPUT
id+id*id
OUTPUT
Stack Input Action
i d+id*id$ Shift
id +id*id$ Shift
E +id*id$ Reduce id→E
E+ id*id$ Shift
E+i d*id$ Shift
E+id *id$ Shift
E+E *id$ Reduce id→E
E *id$ Reduce E+E→E
E* id$ Shift
E*i d$ Shift
E*id $ Shift
E*E $ Reduce id→E
E $ Reduce E*E→E
E $ Accept
25
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
EXPERIMENT - 10
AIM - Writing a program to compute FIRST and FOLLOW sets of a given
grammar.
-> CODE (Python)
grammar = {}
n = int(input("Enter number of productions: "))
for _ in range(n):
prod = input("Enter production (A->α): ")
lhs, rhs = [Link]("->")
grammar[lhs] = [Link]('|')
first = {}
follow = {}
for non_terminal in grammar:
first[non_terminal] = set()
follow[non_terminal] = set()
start_symbol = list([Link]())[0]
follow[start_symbol].add('$')
def find_first(symbol):
if symbol not in grammar:
return {symbol}
result = set()
for production in grammar[symbol]:
if production == 'ε':
[Link]('ε')
else:
for char in production:
temp = find_first(char)
26
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
[Link](temp - {'ε'})
if 'ε' not in temp:
break
else:
[Link]('ε')
return result
def find_follow(symbol):
result = follow[symbol]
for lhs in grammar:
for production in grammar[lhs]:
for i in range(len(production)):
if production[i] == symbol:
# Case 1: A → αBβ
if i + 1 < len(production):
next_symbol = production[i + 1]
first_next = find_first(next_symbol)
[Link](first_next - {'ε'})
if 'ε' in first_next:
[Link](find_follow(lhs))
else:
# Case 2: A → αB
if lhs != symbol:
[Link](find_follow(lhs))
return result
for non_terminal in grammar:
first[non_terminal] = find_first(non_terminal)
for non_terminal in grammar:
follow[non_terminal] = find_follow(non_terminal)
27
Subject : Compiler Design Lab (BCS-652) Dept. of CSE
Name : Roll No. :
---------------------------------------------------------------------------------------------------------------------------
print("\nFIRST sets:")
for nt in first:
print(f"FIRST({nt}) = {first[nt]}")
print("\nFOLLOW sets:")
for nt in follow:
print(f"FOLLOW({nt}) = {follow[nt]}")
SAMPLE INPUT
Enter number of productions: 3
E->TR
R->+TR|ε
T->i
OUTPUT
FIRST sets:
FIRST(E) = {'i'}
FIRST(R) = {'+', 'ε'}
FIRST(T) = {'i'}
FOLLOW sets:
FOLLOW(E) = {'$'}
FOLLOW(R) = {'$'}
FOLLOW(T) = {'+', '$'}
28