1. Program in c to implement lexical analysis phase tokinization process.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
// Function to check if a character is an operator
int isOperator(char ch) {
char operators[] = "+-*/%=<>!&|^";
for (int i = 0; i < strlen(operators); i++) {
if (ch == operators[i]) {
return 1;
}
}
return 0;
}
// Function to check if a character is a special symbol
int isSpecialSymbol(char ch) {
char symbols[] = "(),;{}[]";
for (int i = 0; i < strlen(symbols); i++) {
if (ch == symbols[i]) {
return 1;
}
}
return 0;
}
// Function to perform lexical analysis
void lexicalAnalysis(char *input) {
int i = 0;
while (i < strlen(input)) {
// Skip whitespace
if (isspace(input[i])) {
i++;
continue;
}
// Check for identifiers or keywords
if (isalpha(input[i])) {
char token[100];
int j = 0;
while (isalnum(input[i])) {
token[j++] = input[i++];
}
token[j] = '\0';
printf("Identifier/Keyword: %s\n", token);
continue;
}
// Check for numbers
if (isdigit(input[i])) {
char token[100];
int j = 0;
while (isdigit(input[i])) {
token[j++] = input[i++];
}
token[j] = '\0';
printf("Number: %s\n", token);
continue;
}
// Check for operators
if (isOperator(input[i])) {
char token[100];
int j = 0;
while (isOperator(input[i])) {
token[j++] = input[i++];
}
token[j] = '\0';
printf("Operator: %s\n", token);
continue;
}
// Check for special symbols
if (isSpecialSymbol(input[i])) {
printf("Special Symbol: %c\n", input[i]);
i++;
continue;
}
// If none of the above, it's an unknown character
printf("Unknown Character: %c\n", input[i]);
i++;
}
}
int main() {
char input[1000];
printf("Enter a string for lexical analysis: ");
fgets(input, sizeof(input), stdin);
// Remove newline character if present
input[strcspn(input, "\n")] = '\0';
lexicalAnalysis(input);
return 0;
}
2. Program to convert NFA to DFA in c Program
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STATES 10
#define MAX_SYMBOLS 2
// Structure to represent a state in the NFA
typedef struct {
int transitions[MAX_SYMBOLS][MAX_STATES]; // Transition table
int num_transitions[MAX_SYMBOLS]; // Number of transitions for each symbol
int is_final; // 1 if the state is final, 0 otherwise
} NFA_State;
// Structure to represent a state in the DFA
typedef struct {
int states[MAX_STATES]; // Set of NFA states represented by this DFA state
int num_states; // Number of NFA states in this DFA state
int is_final; // 1 if the DFA state is final, 0 otherwise
} DFA_State;
// Global variables
NFA_State nfa[MAX_STATES];
DFA_State dfa[MAX_STATES * MAX_STATES]; // DFA can have up to 2^N states
int num_nfa_states, num_dfa_states;
int symbols[MAX_SYMBOLS] = {0, 1}; // Example symbols: 0 and 1
// Function to compute the epsilon closure of a set of NFA states
void epsilon_closure(int *states, int num_states, int *closure, int *num_closure) {
int stack[MAX_STATES];
int top = -1;
// Initialize closure with the input states
for (int i = 0; i < num_states; i++) {
closure[i] = states[i];
stack[++top] = states[i];
}
*num_closure = num_states;
// Perform DFS to find all reachable states via epsilon transitions
while (top >= 0) {
int current_state = stack[top--];
for (int i = 0; i < nfa[current_state].num_transitions[0]; i++) {
int next_state = nfa[current_state].transitions[0][i];
int found = 0;
for (int j = 0; j < *num_closure; j++) {
if (closure[j] == next_state) {
found = 1;
break;
}
}
if (!found) {
closure[(*num_closure)++] = next_state;
stack[++top] = next_state;
}
}
}
}
// Function to compute the move for a set of states and a symbol
void move(int *states, int num_states, int symbol, int *result, int *num_result) {
*num_result = 0;
for (int i = 0; i < num_states; i++) {
for (int j = 0; j < nfa[states[i]].num_transitions[symbol]; j++) {
result[(*num_result)++] = nfa[states[i]].transitions[symbol][j];
}
}
}
// Function to check if a DFA state already exists
int is_dfa_state_exist(int *states, int num_states) {
for (int i = 0; i < num_dfa_states; i++) {
if (dfa[i].num_states == num_states) {
int match = 1;
for (int j = 0; j < num_states; j++) {
if (dfa[i].states[j] != states[j]) {
match = 0;
break;
}
}
if (match) {
return i;
}
}
}
return -1;
}
// Function to convert NFA to DFA
void convert_nfa_to_dfa() {
int start_closure[MAX_STATES];
int num_start_closure;
epsilon_closure(&0, 1, start_closure, &num_start_closure);
// Initialize the first DFA state
dfa[0].num_states = num_start_closure;
for (int i = 0; i < num_start_closure; i++) {
dfa[0].states[i] = start_closure[i];
if (nfa[start_closure[i]].is_final) {
dfa[0].is_final = 1;
}
}
num_dfa_states = 1;
// Process each DFA state
for (int i = 0; i < num_dfa_states; i++) {
for (int s = 0; s < MAX_SYMBOLS; s++) {
int move_result[MAX_STATES];
int num_move_result;
move(dfa[i].states, dfa[i].num_states, s, move_result, &num_move_result);
int closure_result[MAX_STATES];
int num_closure_result;
epsilon_closure(move_result, num_move_result, closure_result, &num_closure_result);
int dfa_state_index = is_dfa_state_exist(closure_result, num_closure_result);
if (dfa_state_index == -1) {
dfa_state_index = num_dfa_states;
dfa[dfa_state_index].num_states = num_closure_result;
for (int j = 0; j < num_closure_result; j++) {
dfa[dfa_state_index].states[j] = closure_result[j];
if (nfa[closure_result[j]].is_final) {
dfa[dfa_state_index].is_final = 1;
}
}
num_dfa_states++;
}
// Print the transition
printf("DFA State %d on symbol %d goes to DFA State %d\n", i, s, dfa_state_index);
}
}
}
int main() {
// Example NFA
num_nfa_states = 3;
nfa[0].num_transitions[0] = 1; nfa[0].transitions[0][0] = 1; // State 0 -> State 1 on 0
nfa[0].num_transitions[1] = 1; nfa[0].transitions[1][0] = 0; // State 0 -> State 0 on 1
nfa[1].num_transitions[0] = 1; nfa[1].transitions[0][0] = 2; // State 1 -> State 2 on 0
nfa[1].num_transitions[1] = 1; nfa[1].transitions[1][0] = 1; // State 1 -> State 1 on 1
nfa[2].num_transitions[0] = 0; // State 2 has no transitions on 0
nfa[2].num_transitions[1] = 0; // State 2 has no transitions on 1
nfa[2].is_final = 1; // State 2 is a final state
// Convert NFA to DFA
convert_nfa_to_dfa();
return 0;
}
