1.
Design and implement a lexical analyzer for a 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>
enum { IDENTIFIER, KEYWORD, NUMBER, OPERATOR };
char *keywords[] = {"if", "else", "while", "int", "return"};
int isKeyword(char *word) {
for (int i = 0; i < 5; i++) {
if (strcmp(word, keywords[i]) == 0) return 1;
return 0;
void lexicalAnalyzer(FILE *file) {
char ch, buffer[100];
int j = 0;
while ((ch = fgetc(file)) != EOF) {
if (isspace(ch)) continue; // Skip whitespace
if (isalpha(ch)) { // Identifier or keyword
buffer[j++] = ch;
while (isalnum(ch = fgetc(file))) buffer[j++] = ch;
ungetc(ch, file);
buffer[j] = '\0';
printf(isKeyword(buffer) ? "<KEYWORD, %s>\n" : "<IDENTIFIER, %s>\n", buffer);
j = 0;
} else if (isdigit(ch)) { // Number
buffer[j++] = ch;
while (isdigit(ch = fgetc(file))) buffer[j++] = ch;
ungetc(ch, file);
buffer[j] = '\0';
printf("<NUMBER, %s>\n", buffer);
j = 0;
} else { // Operator
printf("<OPERATOR, %c>\n", ch);
int main() {
FILE *file = fopen("input.c", "r");
lexicalAnalyzer(file);
fclose(file);
return 0;
Example Source Code:
if (x > 10) {
return x + 1;
} else {
return 0;
Sample Output:
Lexical Analysis Results:
<Keyword, if>
<Operator/Punctuation, (>
<Identifier, x>
<Operator/Punctuation, >
<Number, 10>
<Operator/Punctuation, )>
<Operator/Punctuation, {>
<Keyword, return>
<Identifier, x>
<Operator/Punctuation, +>
<Number, 1>
<Operator/Punctuation, ;>
<Operator/Punctuation, }>
<Keyword, else>
<Operator/Punctuation, {>
<Keyword, return>
<Number, 0>
<Operator/Punctuation, ;>
<Operator/Punctuation, }>
2.Implementation of Lexical Analyzer using Lex Tool.
Prerequisites
You must have Lex (or Flex) and a C compiler (like GCC) installed on your system.
Lex Program (lexer.l)
%{
#include <stdio.h>
#include <string.h>
int line_num = 1;
%}
DIGIT [0-9]
ID [a-zA-Z_][a-zA-Z0-9_]*
KEYWORD if|else|while|return|int|float|char|void
OP \+|\-|\*|\/|==|!=|<=|>=|<|>
%%
{DIGIT}+ { printf("NUMBER: %s\n", yytext); }
{KEYWORD} { printf("KEYWORD: %s\n", yytext); }
{ID} { printf("IDENTIFIER: %s\n", yytext); }
{OP} { printf("OPERATOR: %s\n", yytext); }
"=" { printf("ASSIGNMENT: %s\n", yytext); }
";" { printf("SEMICOLON\n"); }
"{" { printf("LEFT BRACE\n"); }
"}" { printf("RIGHT BRACE\n"); }
"(" { printf("LEFT PARENTHESIS\n"); }
")" { printf("RIGHT PARENTHESIS\n"); }
[\n] { line_num++; }
[ \t] ; // Skip whitespace
. { printf("UNKNOWN CHARACTER: %s\n", yytext); }
%%
int main(int argc, char **argv) {
yylex();
return 0;
int yywrap() {
return 1;
Example Input:
int main() {
int x = 10;
if (x > 5) {
x = x + 1;
return x;
Example Output:
KEYWORD: int
IDENTIFIER: main
LEFT PARENTHESIS
RIGHT PARENTHESIS
LEFT BRACE
KEYWORD: int
IDENTIFIER: x
ASSIGNMENT: =
NUMBER: 10
SEMICOLON
KEYWORD: if
LEFT PARENTHESIS
IDENTIFIER: x
OPERATOR: >
NUMBER: 5
RIGHT PARENTHESIS
LEFT BRACE
IDENTIFIER: x
ASSIGNMENT: =
IDENTIFIER: x
OPERATOR: +
NUMBER: 1
SEMICOLON
RIGHT BRACE
KEYWORD: return
IDENTIFIER: x
SEMICOLON
RIGHT BRACE
3.Generate YACC specification for a few syntactic categories:
a) Program to recognize a valid arithmetic expression that uses operators +, -, *, and /.
%{
#include <stdio.h>
%}
%token NUMBER
%left '+' '-'
%left '*' '/'
%%
expr: expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | NUMBER ;
%%
yyerror(char *s) { printf("Error: %s\n", s); }
main() { yyparse(); }
b) Program to recognize a valid variable which starts with a letter followed by any number of
letters or digits.
%%
[a-zA-Z][a-zA-Z0-9]* { printf("VALID VARIABLE: %s\n", yytext); }
. { printf("INVALID\n"); }
%%
c) Implementation of a Calculator using LEX and YACC.
%{
#include "y.tab.h"
%}
%%
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
[+\-*/] { return yytext[0]; }
\n { return 0; }
. { /* Ignore */ }
%%
d) Convert the BNF rules into YACC form and write code to generate an abstract syntax tree.
%{
typedef struct ASTNode {
char op;
int value;
struct ASTNode *left, *right;
} ASTNode;
ASTNode *makeNode(char op, ASTNode *l, ASTNode *r) { /* ... */ }
%}
%%
expr: expr '+' expr { $$ = makeNode('+', $1, $3); }
| NUMBER { $$ = makeNode('n', $1, NULL); }
%%
4.Write a program to find the ε-closure of all states of any given NFA with ε-transitions.
#include <iostream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
int num_states;
vector<vector<int>> epsilon_transitions;
set<int> epsilonClosure(int state) {
stack<int> stk;
set<int> closure;
stk.push(state);
closure.insert(state);
while (!stk.empty()) {
int current = stk.top();
stk.pop();
for (int next : epsilon_transitions[current]) {
if (closure.find(next) == closure.end()) {
closure.insert(next);
stk.push(next);
}
}
return closure;
int main() {
cout << "Enter number of states: ";
cin >> num_states;
epsilon_transitions.resize(num_states);
int num_transitions;
cout << "Enter number of ε-transitions: ";
cin >> num_transitions;
cout << "Enter ε-transitions (from to):\n";
for (int i = 0; i < num_transitions; i++) {
int from, to;
cin >> from >> to;
epsilon_transitions[from].push_back(to);
cout << "\nEpsilon closures:\n";
for (int i = 0; i < num_states; i++) {
set<int> closure = epsilonClosure(i);
cout << "ε-closure(" << i << ") = { ";
for (int state : closure) {
cout << state << " ";
}
cout << "}\n";
return 0;
Sample Input:
Enter number of states: 4
Enter number of ε-transitions: 4
Enter ε-transitions (from to):
01
12
23
31
Sample Output:
ε-closure(0) = { 0 1 2 3 }
ε-closure(1) = { 1 2 3 }
ε-closure(2) = { 2 3 1 }
ε-closure(3) = { 3 1 2 }
5.Write a program to convert an NFA with ε-transitions to an NFA without ε-transitions.
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <string>
using namespace std;
int num_states, num_symbols;
vector<char> alphabet; // excludes ε
map<int, map<char, set<int>>> transitions; // original transitions (may include ε)
map<int, map<char, set<int>>> new_transitions; // ε-free transitions
vector<set<int>> epsilon_closures;
set<int> computeEpsilonClosure(int state) {
set<int> closure;
stack<int> stk;
stk.push(state);
closure.insert(state);
while (!stk.empty()) {
int s = stk.top();
stk.pop();
for (int t : transitions[s]['e']) {
if (closure.find(t) == closure.end()) {
closure.insert(t);
stk.push(t);
return closure;
void computeAllEpsilonClosures() {
epsilon_closures.resize(num_states);
for (int i = 0; i < num_states; ++i) {
epsilon_closures[i] = computeEpsilonClosure(i);
void convertToNFAWithoutEpsilon() {
for (int state = 0; state < num_states; ++state) {
for (char symbol : alphabet) {
set<int> result_set;
for (int e_state : epsilon_closures[state]) {
for (int t : transitions[e_state][symbol]) {
result_set.insert(epsilon_closures[t].begin(), epsilon_closures[t].end());
if (!result_set.empty())
new_transitions[state][symbol] = result_set;
}
void printNewNFA() {
cout << "\nTransitions of NFA without ε-transitions:\n";
for (int state = 0; state < num_states; ++state) {
for (char symbol : alphabet) {
if (new_transitions[state].count(symbol)) {
cout << "From state " << state << " on '" << symbol << "' -> { ";
for (int dest : new_transitions[state][symbol]) {
cout << dest << " ";
cout << "}\n";
int main() {
cout << "Enter number of states: ";
cin >> num_states;
cout << "Enter number of input symbols (excluding ε): ";
cin >> num_symbols;
cout << "Enter the input symbols: ";
for (int i = 0; i < num_symbols; ++i) {
char ch;
cin >> ch;
alphabet.push_back(ch);
}
int num_transitions;
cout << "Enter number of transitions (including ε, represented by 'e'): ";
cin >> num_transitions;
cout << "Enter transitions (from symbol to):\n";
for (int i = 0; i < num_transitions; ++i) {
int from, to;
char symbol;
cin >> from >> symbol >> to;
transitions[from][symbol].insert(to);
computeAllEpsilonClosures();
convertToNFAWithoutEpsilon();
printNewNFA();
return 0;
Sample Input:
Enter number of states: 3
Enter number of input symbols (excluding ε): 2
Enter the input symbols: a b
Enter number of transitions (including ε, represented by 'e'): 5
Enter transitions (from symbol to):
0e1
1e2
2a2
1b1
0a0
Sample Output:
Transitions of NFA without ε-transitions:
From state 0 on 'a' -> { 0 2 }
From state 0 on 'b' -> { 1 }
From state 1 on 'a' -> { 2 }
From state 1 on 'b' -> { 1 }
From state 2 on 'a' -> { 2 }
6.Write a program to perform loop unrolling.
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
int main() {
int start, end, unroll_factor;
string body_line;
cout << "Enter loop start (e.g., 0): ";
cin >> start;
cout << "Enter loop end (exclusive, e.g., 10): ";
cin >> end;
cin.ignore();
cout << "Enter loop body using variable i (e.g., cout << i << endl;):\n";
getline(cin, body_line);
cout << "Enter unroll factor: ";
cin >> unroll_factor;
cout << "\n--- Unrolled Loop ---\n";
int i = start;
// Print unrolled loop in chunks
cout << "for (int i = " << start << "; i <= " << (end - unroll_factor) << "; i += " <<
unroll_factor << ") {\n";
for (int j = 0; j < unroll_factor; ++j) {
cout << " ";
string line = body_line;
// Replace 'i' with (i + j)
size_t pos;
while ((pos = line.find("i")) != string::npos) {
line.replace(pos, 1, "(i + " + to_string(j) + ")");
cout << line << '\n';
cout << "}\n";
// Handle the remainder
int remainder = (end - start) % unroll_factor;
if (remainder > 0) {
cout << "for (int i = " << (end - remainder) << "; i < " << end << "; i++) {\n";
cout << " " << body_line << '\n';
cout << "}\n";
return 0;
Sample Input:
Enter loop start (e.g., 0): 0
Enter loop end (exclusive, e.g., 10): 10
Enter loop body using variable i (e.g., cout << i << endl;):
cout << i << endl;
Enter unroll factor: 4
Output:
for (int i = 0; i <= 6; i += 4) {
cout << (i + 0) << endl;
cout << (i + 1) << endl;
cout << (i + 2) << endl;
cout << (i + 3) << endl;
for (int i = 8; i < 10; i++) {
cout << i << endl;
}
7.Write a program to convert an NFA to a DFA.
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
int num_states, num_symbols;
vector<char> alphabet;
map<int, map<char, set<int>>> nfa;
map<set<int>, map<char, set<int>>> dfa;
vector<set<int>> dfa_states;
set<int> final_states;
set<set<int>> dfa_final_states;
bool isFinalState(set<int> s) {
for (int f : final_states) {
if (s.count(f)) return true;
return false;
void printSet(const set<int>& s) {
cout << "{ ";
for (int x : s) cout << x << " ";
cout << "}";
void nfaToDfa(int start_state) {
queue<set<int>> q;
set<int> start = { start_state };
q.push(start);
dfa_states.push_back(start);
while (!q.empty()) {
set<int> current = q.front(); q.pop();
if (dfa.count(current)) continue; // already processed
for (char symbol : alphabet) {
set<int> move_result;
for (int state : current) {
if (nfa[state].count(symbol)) {
move_result.insert(nfa[state][symbol].begin(), nfa[state][symbol].end());
if (!move_result.empty()) {
dfa[current][symbol] = move_result;
// Add new DFA state
if (find(dfa_states.begin(), dfa_states.end(), move_result) == dfa_states.end()) {
dfa_states.push_back(move_result);
q.push(move_result);
int main() {
cout << "Enter number of NFA states: ";
cin >> num_states;
cout << "Enter number of input symbols: ";
cin >> num_symbols;
cout << "Enter the symbols (e.g., a b): ";
for (int i = 0; i < num_symbols; ++i) {
char c; cin >> c;
alphabet.push_back(c);
int num_transitions;
cout << "Enter number of NFA transitions: ";
cin >> num_transitions;
cout << "Enter transitions (from symbol to):\n";
for (int i = 0; i < num_transitions; ++i) {
int from, to;
char sym;
cin >> from >> sym >> to;
nfa[from][sym].insert(to);
int start_state;
cout << "Enter start state: ";
cin >> start_state;
int num_final;
cout << "Enter number of final states: ";
cin >> num_final;
cout << "Enter final states: ";
for (int i = 0; i < num_final; ++i) {
int f;
cin >> f;
final_states.insert(f);
nfaToDfa(start_state);
// Identify final DFA states
for (const auto& s : dfa_states) {
if (isFinalState(s)) {
dfa_final_states.insert(s);
cout << "\nDFA Transitions:\n";
for (const auto& [from, trans_map] : dfa) {
for (char sym : alphabet) {
if (trans_map.count(sym)) {
printSet(from);
cout << " --" << sym << "--> ";
printSet(trans_map.at(sym));
cout << "\n";
cout << "\nDFA Start State: ";
printSet({start_state});
cout << "\nDFA Final States:\n";
for (const auto& f : dfa_final_states) {
printSet(f);
cout << "\n";
return 0;
Sample Input:
Enter number of NFA states: 3
Enter number of input symbols: 2
Enter the symbols (e.g., a b): a b
Enter number of NFA transitions: 4
Enter transitions (from symbol to):
0a0
0a1
1b2
2b2
Enter start state: 0
Enter number of final states: 1
Enter final states: 2
Output:
DFA Transitions:
{ 0 } --a--> { 0 1 }
{ 0 1 } --a--> { 0 1 }
{ 0 1 } --b--> { 2 }
{ 2 } --b--> { 2 }
DFA Start State: { 0 }
DFA Final States:
{2}
8.Write a program to minimize any given DFA.
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
using namespace std;
int num_states, num_symbols;
vector<char> alphabet;
vector<vector<int>> dfa_transition;
set<int> final_states;
int start_state;
bool is_final(int s) {
return final_states.find(s) != final_states.end();
void minimizeDFA() {
// Step 1: Create a table of distinguishability
vector<vector<bool>> distinguishable(num_states, vector<bool>(num_states, false));
// Step 2: Mark pairs where one is final and the other is not
for (int i = 0; i < num_states; ++i) {
for (int j = 0; j < i; ++j) {
if (is_final(i) != is_final(j))
distinguishable[i][j] = true;
// Step 3: Iteratively mark distinguishable pairs
bool changed;
do {
changed = false;
for (int i = 0; i < num_states; ++i) {
for (int j = 0; j < i; ++j) {
if (distinguishable[i][j]) continue;
for (int k = 0; k < num_symbols; ++k) {
int si = dfa_transition[i][k];
int sj = dfa_transition[j][k];
if (si == sj) continue;
int a = max(si, sj), b = min(si, sj);
if (distinguishable[a][b]) {
distinguishable[i][j] = true;
changed = true;
break;
} while (changed);
// Step 4: Group indistinguishable states
vector<int> state_group(num_states);
for (int i = 0; i < num_states; ++i) state_group[i] = i;
for (int i = 0; i < num_states; ++i) {
for (int j = 0; j < i; ++j) {
if (!distinguishable[i][j]) {
state_group[i] = state_group[j]; // Merge
break;
// Map old group IDs to new minimized state numbers
map<int, int> group_to_state;
int new_state_id = 0;
for (int i = 0; i < num_states; ++i) {
int grp = state_group[i];
if (group_to_state.find(grp) == group_to_state.end()) {
group_to_state[grp] = new_state_id++;
// Build minimized DFA
int min_states = group_to_state.size();
vector<vector<int>> minimized_dfa(min_states, vector<int>(num_symbols));
set<int> minimized_final_states;
int minimized_start_state = group_to_state[state_group[start_state]];
for (int i = 0; i < num_states; ++i) {
int new_state = group_to_state[state_group[i]];
if (is_final(i)) minimized_final_states.insert(new_state);
for (int k = 0; k < num_symbols; ++k) {
int to = dfa_transition[i][k];
int new_to = group_to_state[state_group[to]];
minimized_dfa[new_state][k] = new_to;
// Output
cout << "\nMinimized DFA:\n";
cout << "Number of states: " << min_states << "\n";
cout << "Start state: " << minimized_start_state << "\n";
cout << "Final states: ";
for (int f : minimized_final_states) cout << f << " ";
cout << "\nTransitions:\n";
for (int i = 0; i < min_states; ++i) {
for (int k = 0; k < num_symbols; ++k) {
cout << i << " --" << alphabet[k] << "--> " << minimized_dfa[i][k] << "\n";
int main() {
cout << "Enter number of states: ";
cin >> num_states;
cout << "Enter number of input symbols: ";
cin >> num_symbols;
cout << "Enter the symbols (e.g., a b): ";
alphabet.resize(num_symbols);
for (int i = 0; i < num_symbols; ++i) {
cin >> alphabet[i];
dfa_transition.resize(num_states, vector<int>(num_symbols));
cout << "Enter transitions in format: from symbol to\n";
for (int i = 0; i < num_states * num_symbols; ++i) {
int from, to;
char sym;
cin >> from >> sym >> to;
for (int k = 0; k < num_symbols; ++k) {
if (alphabet[k] == sym) {
dfa_transition[from][k] = to;
break;
cout << "Enter start state: ";
cin >> start_state;
int f;
cout << "Enter number of final states: ";
cin >> f;
cout << "Enter final states: ";
for (int i = 0; i < f; ++i) {
int x;
cin >> x;
final_states.insert(x);
minimizeDFA();
return 0;
Sample Input:
Enter number of states: 4
Enter number of input symbols: 2
Enter the symbols (e.g., a b): 0 1
Enter transitions in format: from symbol to
001
012
100
113
203
210
302
311
Enter start state: 0
Enter number of final states: 1
Enter final states: 3
Sample Output:
Minimized DFA:
Number of states: 2
Start state: 0
Final states: 1
Transitions:
0 --0--> 0
0 --1--> 1
1 --0--> 1
1 --1--> 0
9.Develop an operator precedence parser for a given language.
#include <iostream>
#include <map>
#include <stack>
#include <string>
using namespace std;
map<char, int> precedence_index;
char precedence_table[6][6]; // For a small number of terminals
string terminals = "+-*/i#"; // 'i' = identifier, '#' = end marker
// Function to get precedence relation
char get_precedence(char top, char input) {
int row = precedence_index[top];
int col = precedence_index[input];
return precedence_table[row][col];
// Function to check if character is terminal
bool is_terminal(char ch) {
return terminals.find(ch) != string::npos;
// Parsing function
void operator_precedence_parse(string input) {
input += "#"; // Ensure input ends with '#'
stack<char> parse_stack;
parse_stack.push('#');
size_t i = 0;
cout << "Stack\tInput\tAction\n";
while (true) {
// Display current stack and input
string stack_content;
stack<char> temp_stack = parse_stack;
while (!temp_stack.empty()) {
stack_content = temp_stack.top() + stack_content;
temp_stack.pop();
cout << stack_content << "\t" << input.substr(i) << "\t";
char a = input[i];
char top = parse_stack.top();
// Find top-most terminal in stack
stack<char> temp = parse_stack;
while (!is_terminal(temp.top())) temp.pop();
top = temp.top();
char relation = get_precedence(top, a);
if (relation == '<' || relation == '=') {
// Shift
cout << "Shift\n";
parse_stack.push(a);
i++;
} else if (relation == '>') {
// Reduce
cout << "Reduce\n";
// Just pop one symbol for simplicity
parse_stack.pop();
} else if (relation == ' ') {
// Invalid relation
cout << "Error: No precedence relation between " << top << " and " << a << "\n";
return;
if (parse_stack.top() == '#' && input[i] == '#') {
cout << "#\t#\tAccept\n";
break;
int main() {
// Map symbols to index
for (int i = 0; i < terminals.length(); ++i)
precedence_index[terminals[i]] = i;
// Precedence table
// Row = top of stack, Column = current input
// + - * / i #
string rows[] = {
// + - * / i #
{ '>', '>', '<', '<', '<', '>' }, // +
{ '>', '>', '<', '<', '<', '>' }, // -
{ '>', '>', '>', '>', '<', '>' }, // *
{ '>', '>', '>', '>', '<', '>' }, // /
{ '>', '>', '>', '>', ' ', '>' }, // i
{ '<', '<', '<', '<', '<', 'A' } // #
};
// Copy rows to table
for (int i = 0; i < 6; ++i)
for (int j = 0; j < 6; ++j)
precedence_table[i][j] = rows[i][j];
string input;
cout << "Enter the input expression (use 'i' for id, end with #): ";
cin >> input;
operator_precedence_parse(input);
return 0;
Sample Input:
Enter the input expression (use 'i' for id, end with #): i+i*i
Output:
Stack Input Action
# i+i*I # Shift
#i +i*I # Reduce
#+ i*I # Shift
#+i *I # Reduce
#+* I # Shift
#+*i # Reduce
#+ # Reduce
# # Accept
10.Write a program to simulate First and Follow of any given grammar.
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;
map<char, set<char>> first, follow;
map<char, vector<string>> productions;
set<char> non_terminals;
set<char> terminals;
char start_symbol;
bool isTerminal(char c) {
return !isupper(c) && c != '#'; // # is epsilon
// Compute FIRST of a symbol
set<char> computeFirst(char symbol) {
if (first[symbol].size()) return first[symbol];
if (isTerminal(symbol)) {
return first[symbol] = { symbol };
}
for (string prod : productions[symbol]) {
for (size_t i = 0; i < prod.size(); ++i) {
char ch = prod[i];
set<char> subFirst = computeFirst(ch);
first[symbol].insert(subFirst.begin(), subFirst.end());
if (subFirst.find('#') == subFirst.end()) break; // no epsilon
if (i == prod.size() - 1) first[symbol].insert('#');
return first[symbol];
// Compute FOLLOW sets
void computeFollow() {
follow[start_symbol].insert('$'); // $ is end of input
bool changed;
do {
changed = false;
for (auto& [nt, prods] : productions) {
for (string prod : prods) {
for (size_t i = 0; i < prod.size(); ++i) {
char B = prod[i];
if (!isupper(B)) continue;
bool eps = true;
for (size_t j = i + 1; j < prod.size(); ++j) {
eps = false;
char beta = prod[j];
set<char> firstBeta = computeFirst(beta);
size_t before = follow[B].size();
for (char c : firstBeta) {
if (c != '#') follow[B].insert(c);
if (firstBeta.find('#') != firstBeta.end()) eps = true;
if (!eps) break;
if (eps || i == prod.size() - 1) {
size_t before = follow[B].size();
follow[B].insert(follow[nt].begin(), follow[nt].end());
if (follow[B].size() > before) changed = true;
} while (changed);
void displaySets(const map<char, set<char>>& sets, string title) {
cout << "\n" << title << " sets:\n";
for (auto& [symbol, s] : sets) {
if (!isupper(symbol)) continue;
cout << symbol << " : { ";
for (char c : s) cout << c << " ";
cout << "}\n";
int main() {
int n;
cout << "Enter number of productions: ";
cin >> n;
cout << "Enter productions (e.g., E=TR):\n";
for (int i = 0; i < n; ++i) {
string prod;
cin >> prod;
char lhs = prod[0];
if (i == 0) start_symbol = lhs;
non_terminals.insert(lhs);
string rhs = prod.substr(2); // skip '='
productions[lhs].push_back(rhs);
for (char c : rhs) {
if (!isupper(c) && c != '#') terminals.insert(c);
// Compute FIRST sets
for (char nt : non_terminals) computeFirst(nt);
// Compute FOLLOW sets
computeFollow();
displaySets(first, "FIRST");
displaySets(follow, "FOLLOW");
return 0;
Sample Input:
Enter number of productions: 4
Enter productions (e.g., E=TR):
E=TR
R=+TR
R=#
T=F
Output:
FIRST sets:
E:{(i}
R:{+#}
T:{(i}
FOLLOW sets:
E:{$)}
R:{$)}
T:{+$)}
