#include<stdio.
h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
// Function to check if a given word is a C keyword
int iskeyword(char buffer[]) {
// Array containing all C keywords
char keywords[32][10] = {
"auto", "break", "case", "char", "const", "continue", "default", "do", "double", "else",
"enum",
"extern", "float", "for", "goto", "if", "int", "long", "register", "return", "short", "signed",
"sizeof", "static", "struct", "switch", "typedef", "union", "unsigned", "void", "volatile",
"while"
};
int i, flag = 0; // `flag` used to indicate if word is a keyword
// Loop to check if buffer matches any keyword
for(i = 0; i < 32; i++) {
if(strcmp(keywords[i], buffer) == 0) { // If a match is found
flag = 1; // Set flag to 1 (indicating keyword found)
break;
return flag; // Return 1 if keyword, 0 otherwise
int main() {
char ch, buffer[15], operators[] = "+-*/%=", specialch[] = ",;[]{}", num[] = "1234567890",
buf[10];
FILE *fp; // File pointer
int i, j = 0, k = 0; // `j` and `k` used to index buffer arrays
fp = fopen("program.txt", "r"); // Open file for reading
if(fp == NULL) { // Check if file is successfully opened
printf("error while opening file\n"); // Print error if file could not be opened
exit(0); // Exit program if file open fails
// Loop through each character in file until end of file (EOF) is reached
while((ch = fgetc(fp)) != EOF) {
// Check if character is an operator
for(i = 0; i < 6; i++) {
if(ch == operators[i]) { // If character matches an operator
printf("%c\tis operator\n", ch); // Print that character is an operator
if(ch == specialch[i]) { // If character matches a special character
printf("%c\tis special character\n", ch); // Print that character is a special character
if(isalpha(ch)) { // Check if character is an alphabet (part of identifier or keyword)
buffer[j++] = ch; // Add character to buffer
if(isdigit(ch)) { // Check if character is a digit
buf[k++] = ch; // Add digit to buf array
buf[k++] = ','; // Add comma after each digit (delimiter)
// Condition to check if end of a word or identifier is reached
else if((ch == ',' || ch == '\n') && (j != 0)) {
buffer[j] = '\0'; // Null terminate the buffer (end of identifier or keyword)
j = 0; // Reset buffer index for the next word
if(iskeyword(buffer) == 1) // Check if buffer contains a keyword
printf("%s\tis keyword\n", buffer); // Print keyword if buffer is a keyword
else {
printf("%s\tis identifier\n", buffer); // Print identifier if buffer is not a keyword
fclose(fp); // Close file
return 0; // End of program
#include<string.h> // For string manipulation functions
#include<stdlib.h> // For standard library functions
#include<ctype.h> // For character classification functions
#include<stdio.h> // For standard input and output functions
void main() {
FILE *f1; // File pointer to handle the input file
char c, str[10]; // `c` stores each character, `str` stores sequences of letters/numbers for
keywords/identifiers
int lineno = 1, num = 0, i = 0; // `lineno` for line number count, `num` for numeric values,
`i` for indexing in `str`
f1 = fopen("input.txt", "r"); // Open the input file for reading
// Loop through each character in the file until End Of File (EOF) is reached
while((c = getc(f1)) != EOF) {
if(isdigit(c)) { // Check if character is a digit
num = c - 48; // Convert character digit to integer
c = getc(f1); // Get the next character
while(isdigit(c)) { // Loop while the character is a digit
num = num * 10 + (c - 48); // Convert and accumulate the number
c = getc(f1); // Get the next character
printf("\n%d is a number", num); // Print the number found
ungetc(c, f1); // Push last character back to stream for next processing
else if(isalpha(c)) { // Check if character is an alphabet (indicating possible keyword or
identifier)
str[i++] = c; // Add character to `str`
c = getc(f1); // Get the next character
// Loop for alphanumeric characters, underscore, or dollar sign (valid in identifiers)
while(isdigit(c) || isalpha(c) || c == '_' || c == '$') {
str[i++] = c; // Add character to `str`
c = getc(f1); // Get the next character
str[i] = '\0'; // Null terminate `str`
// Check if `str` matches any keyword
if(strcmp("for", str) == 0 || strcmp("while", str) == 0 || strcmp("do", str) == 0 ||
strcmp("int", str) == 0 || strcmp("float", str) == 0 || strcmp("char", str) == 0 ||
strcmp("double", str) == 0 || strcmp("static", str) == 0 || strcmp("switch", str) == 0 ||
strcmp("case", str) == 0) {
printf("\n%s is a keyword", str); // Print as keyword if match found
} else {
printf("\n%s is an identifier", str); // Otherwise, print as identifier
ungetc(c, f1); // Push the last character back to stream for next processing
i = 0; // Reset `i` for the next word
else if(c == ' ' || c == '\t') // Ignore spaces and tabs
printf("\n"); // Just move to a new line
else if(c == '\n') // If newline character is encountered
lineno++; // Increment the line number
else
printf("\n%c is a special symbol", c); // Print special symbols directly
}
printf("\nTotal no of lines are: %d\n", lineno - 1); // Print the total number of lines in the
file
fclose(f1); // Close the file
#include <stdio.h> // For input and output functions
#include <string.h> // For string manipulation functions
#include <stdlib.h> // For standard functions, like `exit`
#include <ctype.h> // For character classification functions
#define MAX 50 // Define the maximum length of the input expression
char ip_sym[MAX], op[MAX], tmp[MAX]; // `ip_sym` stores input, `op` stores production state,
`tmp` is a temporary buffer
int ip_ptr = 0; // Pointer to track position in the input string
void e_prime(); // Function for E' non-terminal
void e(); // Function for E non-terminal
void t_prime(); // Function for T' non-terminal
void t(); // Function for T non-terminal
void f(); // Function for F non-terminal
void advance(); // Function to advance the input pointer
// Parsing function for E non-terminal (E -> T E')
void e() {
strcpy(op, "TE"); // Initialize `op` with "TE" to represent E -> T E'
printf("E=%-25s", op); // Print current state of E
printf("E -> T E'\n"); // Output production rule applied
t(); // Call function for T
e_prime(); // Call function for E'
// Parsing function for E' non-terminal (E' -> + T E' | e)
void e_prime() {
int i, n = 0;
for (i = 0; i <= strlen(op); i++) // Loop to remove 'e' characters from `op`
if (op[i] != 'e') tmp[n++] = op[i];
strcpy(op, tmp); // Copy cleaned `tmp` back to `op`
int len = strlen(op);
for (n = 0; n < len && op[n] != 'E'; n++); // Find E in op
if (ip_sym[ip_ptr] == '+') { // Check if next symbol is '+'
int i = n + 2;
do { op[i + 2] = op[i]; i--; } while (i >= len); // Shift contents to insert "+TE'"
op[n++] = '+'; op[n++] = 'T'; op[n++] = 'E'; op[n++] = 39; // Add "+TE'"
printf("E=%-25s", op); // Print updated `op`
printf("E'-> +TE'\n"); // Print production rule applied
advance(); // Move to next input symbol
t(); // Parse T
e_prime(); // Recursively parse E'
} else {
op[n] = 'e'; // Otherwise, set E' to epsilon (e)
for (i = n+1; i <= strlen(op); i++) op[i] = op[i + 1];
printf("E=%-25s", op); // Print final state of E'
printf("E -> e "); // Print production rule E' -> e
// Parsing function for T non-terminal (T -> F T')
void t() {
int i, n = 0;
for (i = 0; i <= strlen(op); i++) // Loop to remove 'e' from `op`
if (op[i] != 'e') tmp[n++] = op[i];
strcpy(op, tmp); // Copy cleaned `tmp` back to `op`
int len = strlen(op);
for (n = 0; n < len && op[n] != 'T'; n++);
i = n + 1;
do { op[i + 2] = op[i]; i++; } while (i < len); // Shift to make space for "FT'"
op[n++] = 'F'; op[n++] = 'T'; op[n++] = 39; // Add "FT'"
printf("E=%-25s", op); // Print current state of T
printf("T -> F T'\n"); // Output production rule T -> F T'
f(); // Parse F
t_prime(); // Parse T'
// Parsing function for T' non-terminal (T' -> * F T' | e)
void t_prime() {
int i, n = 0;
for (i = 0; i <= strlen(op); i++) // Loop to remove 'e' from `op`
if (op[i] != 'e') tmp[n++] = op[i];
strcpy(op, tmp); // Copy cleaned `tmp` back to `op`
int len = strlen(op);
for (n = 0; n < len && op[n] != 'T'; n++);
if (ip_sym[ip_ptr] == '*') { // Check if current symbol is '*'
int i = n + 2;
do { op[i + 2] = op[i]; i++; } while (i < len); // Shift to insert "*FT'"
op[n++] = '*'; op[n++] = 'F'; op[n++] = 'T'; op[n++] = 39; // Add "*FT'"
printf("E=%-25s", op); // Print current state of T'
printf("T -> *F T\n"); // Output production rule T' -> * F T'
advance(); // Move to next input symbol
f(); // Parse F
t_prime(); // Parse T' again
} else {
op[n] = 'e'; // If `*` not found, set T' -> e
for (i = n + 1; i <= strlen(op); i++) op[i] = op[i + 1];
printf("E=%-25s", op); // Print final state of T'
printf("T -> e\n"); // Output production rule T' -> e
// Parsing function for F non-terminal (F -> ( E ) | i)
void f() {
int i, n = 0, l;
for (i = 0; i <= strlen(op); i++) // Remove 'e' from `op`
if (op[i] != 'e') tmp[n++] = op[i];
strcpy(op, tmp);
l = strlen(op);
for (n = 0; n < l && op[n] != 'F'; n++);
if ((ip_sym[ip_ptr] == 'i') || (ip_sym[ip_ptr] == 'l')) { // If identifier 'i' or 'l'
op[n] = 'i';
printf("E=%-25s", op); // Print current state of F
printf("F -> i\n"); // Output production rule F -> i
advance(); // Move to next input symbol
} else {
if (ip_sym[ip_ptr] == '(') { // Check if current symbol is '('
advance();
e(); // Parse inner E
if (ip_sym[ip_ptr] == ')') { // Ensure closing ')'
advance();
i = n + 2;
do { op[i + 2] = op[i]; i++; } while (i <= l);
op[n++] = '('; op[n++] = 'E'; op[n++] = ')'; // Add "(E)"
printf("E=%-25s", op); // Print final state of F
printf("F -> (E)\n"); // Output production rule F -> (E)
} else {
printf("\n\t syntax error"); // Print syntax error if F is invalid
exit(1); // Exit the program
// Advances the input pointer
void advance() {
ip_ptr++;
}
int main() {
printf("Grammar without left recursion\n");
printf("\tE -> T E'\n");
printf("\tE' -> + T E' | e \n");
printf("\tT -> F T'\n");
printf("\tT' -> * F T' | e \n");
printf("\tF -> ( E ) | i\n");
printf("Enter the input expression: ");
fgets(ip_sym, MAX, stdin); // Read the input expression
ip_sym[strcspn(ip_sym, "\n")] = 0; // Remove trailing newline character
printf("Expression sequence of production rules:\n");
e(); // Start parsing with E
if (ip_sym[ip_ptr] == '\0') { // Check if the entire input was parsed
printf("Input expression is valid\n"); // If valid, print confirmation
} else {
printf("Syntax error: Unexpected input after end of expression\n"); // Otherwise, print
syntax error
return 0; // End of program
#include<stdio.h> // Include the standard input/output library for functions like printf.
#include<stdlib.h> // Include the standard library for general-purpose functions.
#include<string.h> // Include the string manipulation library for functions like strcpy and
strlen.
int z=0,i=0,j=0,c=0; // Declare global integer variables: z, i, j, and c for indexing and control.
char a[16],ac[2],stk[15],act[10]; // Declare character arrays a, ac, stk, and act to store input
string, action, stack, and action description.
void check() // Function to perform reduction of production rules.
strcpy(ac,"REDUCE TO E->"); // Set the reduction action string to "REDUCE TO E->".
for(z=0;z<c;z++) // Loop through each character in the stack (from 0 to c-1).
if(stk[z]=='4') // If the character at the stack position is '4', perform a reduction.
printf("%s4",ac); // Print the reduction rule.
stk[z]='E'; // Replace '4' with 'E' in the stack.
stk[z+1]=' '; // Add a space after 'E'.
printf("\n$%s\t%s$\t",stk,a); // Print the current state of the stack and the remaining
input.
for(z=0;z<c-2;z++) // Loop through the stack to check for the pattern '2E2' (used for the
production E->2E2).
if(stk[z]=='2'&&stk[z+1]=='E'&&stk[z+2]=='2') // If pattern '2E2' is found.
printf("%s2E2",ac); // Print the reduction rule for E->2E2.
stk[z]='E'; // Replace '2E2' with 'E'.
stk[z+1]=' '; // Add space after 'E'.
stk[z+2]=' '; // Add space after 'E'.
printf("\n$%s\t%s$\t",stk,a); // Print the updated stack and the remaining input.
i=i-2; // Adjust the index i to account for the reduction.
for(z=0;z<c-2;z++) // Loop through the stack to check for the pattern '3E3' (used for the
production E->3E3).
if(stk[z]=='3'&&stk[z+1]=='E'&&stk[z+2]=='3') // If pattern '3E3' is found.
printf("%s3E3",ac); // Print the reduction rule for E->3E3.
stk[z]='E'; // Replace '3E3' with 'E'.
stk[z+1]=' '; // Add space after 'E'.
stk[z+2]=' '; // Add space after 'E'.
printf("\n$%s\t%s$\t",stk,a); // Print the updated stack and the remaining input.
i=i-2; // Adjust the index i to account for the reduction.
return; // End the check function.
int main() // Main function.
printf("GRAMMER is \nE->2E2\nE->3E3\nE->4"); // Print the grammar rules.
strcpy(a,"32423"); // Initialize the input string a with "32423".
c=strlen(a); // Get the length of the input string and store it in c.
strcpy(act,"SHIFT"); // Initialize the action string to "SHIFT".
printf("\nstack\tinput\taction"); // Print headers for stack, input, and action.
printf("\n$\t%s$\t",a); // Print the initial state of the input string.
for(i=0;j<c;i++,j++) // Loop through the input string.
{
printf("%s",act); // Print the current action (SHIFT).
stk[i]=a[j]; // Move the current input symbol to the stack.
stk[i+1]=' '; // Add space after the symbol in the stack.
a[j]=' '; // Remove the current input symbol from the input string.
printf("\n$%s\t%s$\t",stk,a); // Print the current stack and remaining input.
check(); // Call the check function to see if any reduction can occur.
check(); // Call check function once more to ensure all reductions are done.
if(stk[0]=='E'&&stk[1]==' ') // If the stack contains 'E' and is empty afterwards.
printf("Accept"); // Print "Accept" to indicate the input string is valid.
else
printf("Reject"); // Otherwise, print "Reject" to indicate an invalid input string.
#include<stdio.h> // Include the standard input/output library for using printf and scanf.
#include<string.h> // Include the string manipulation library for functions like strlen.
#include<math.h> // Include the math library for using pow() to compute powers of numbers.
int ninputs; // Declare a global variable for the number of input symbols.
int dfa[100][2][100] = {0}; // Define a 3D array for DFA transitions, initialized to 0.
int state[10000] = {0}; // Array to keep track of visited states in the DFA.
char ch[10], str[10000]; // Arrays to store characters and input strings.
int go[10000][2] = {0}; // Array to store transitions for each state and input symbol.
int arr[10000] = {0}; // Array to store distinct new states.
int main() {
int st, fin, in; int f[10]; // Declare variables for the number of states, final states, initial state,
and an array for final states.
int i, j = 3, s = 0, final = 0, flag = 0, curr1, curr2, k, I; // Declare counters and state variables.
int c; // Declare a counter variable.
// Prompt the user to follow one-based indexing and input number of states.
printf("\nFollow the one based indexing\n");
printf("\nEnter the number of states::");
scanf("%d", &st); // Read the number of states.
printf("\nGive state numbers from 0 to %d", st - 1); // Ask user to provide state numbers.
for (i = 0; i < st; i++) // Loop over each state.
state[(int)(pow(2, i))] = 1; // Mark states as visited based on binary representation.
// Prompt for and read the number of final states and their values.
printf("\nEnter number of final states\t");
scanf("%d", &fin);
printf("\nEnter final states::");
for (i = 0; i < fin; i++) {
scanf("%d", &f[i]); // Read each final state.
int p, q, r, rel; // Declare variables for transition rules.
// Prompt for the number of transition rules and their input format.
printf("\nEnter the number of rules according to NFA::");
scanf("%d", &rel); // Read the number of transition rules.
printf("\n\nDefine transition rule as \"initial state input symbol final\"");
printf("\n");
for (i = 0; i < rel; i++) { // Loop over each rule.
scanf("%d%d%d", &p, &q, &r); // Read NFA transition rules (initial state, input symbol,
final state).
if (q == 0)
dfa[p][0][r] = 1; // Transition for input symbol '0'.
else
dfa[p][1][r] = 1; // Transition for input symbol '1'.
// Read the initial state and convert it to its binary representation.
printf("\nEnter initial state::");
scanf("%d", &in);
in = pow(2, in); // Convert the initial state to binary representation.
i = 0;
printf("Solving according to DFA\n");
int x = 0;
// Build the DFA transition table based on the NFA transitions.
for (i = 0; i < st; i++) { // Loop over all states.
for (j = 0; j < 2; j++) { // Loop over each input symbol (0 and 1).
int stf = 0; // Initialize a new state variable.
for (k = 0; k < st; k++) { // Loop through each state.
if (dfa[i][j][k] == 1) // If there is a transition from state `i` on input `j` to state `k`.
stf = stf + pow(2, k); // Update the new state based on binary representation.
go[(int)(pow(2, i))][i] = stf; // Store the new state in the transition table.
printf("%d-%d-->%d\n", (int)(pow(2, i)), j, stf); // Print the transition.
if (state[stf] == 0) // If the state hasn't been visited.
arr[x++] = stf; // Add the new state to the `arr[]`.
state[stf] = 1; // Mark the state as visited.
// Process any newly discovered states.
for (i = 0; i < x; i++) {
printf("for %d ---", arr[x]);
for (j = 0; j < 2; j++) { // Loop over each input symbol (0 and 1).
int new = 0; // Initialize a new state.
for (k = 0; k < st; k++) { // Loop through each state.
if (arr[i] & (1 << k)) { // If the state contains state `k`.
int h = pow(2, k);
if (new == 0)
new = go[h][j]; // Set the new state for the input symbol.
new = new | (go[h][j]); // Update the new state.
if (state[new] == 0) { // If the new state hasn't been visited.
arr[x++] = new; // Add it to the `arr[]`.
state[new] = 1; // Mark it as visited.
// Print the total number of distinct states.
printf("\nThe total number of distinct states are:: \n");
printf("STATe 0 1\n");
for (i = 0; i < 10000; i++) {
if (state[i] == 1) { // For each visited state.
int y = 0;
if (i == 0)
printf("q0"); // Print state `q0` for state 0.
else
for (j = 0; j < st; j++) { // For each state.
int x = 1 << j;
if (x & i) {
printf("q%d", j); // Print the state number.
y = y + pow(2, j); // Update `y`.
printf("%d", y); // Print the state value.
printf("%d %d", go[y][0], go[y][1]); // Print the transitions for the state.
printf("\n");
j = 3; // Set the number of strings to test.
while (j--) { // Loop over each string to test.
printf("\nEnter string::");
scanf("%s", str); // Read the input string.
I = strlen(str); // Get the length of the string.
curr1 = in; // Set the current state to the initial state.
flag = 0; // Initialize the acceptance flag.
printf("\nString takes the following path-->\n");
printf("%d-", curr1); // Print the current state.
for (i = 0; i < I; i++) { // Loop over each character in the string.
curr1 = go[curr1][str[i] - '0']; // Update the current state based on input symbol.
printf("%d-", curr1); // Print the updated state.
printf("\nFinal state-%d\n", curr1); // Print the final state after processing the string.
for (i = 0; i < fin; i++) { // Check if the final state is an accepting state.
if (curr1 & (1 << f[i])) { // If the final state is in the set of final states.
flag = 1; // Mark as accepted.
break;
if (flag)
printf("\nString Accepted"); // Print accepted message.
else
printf("\nString Rejected"); // Print rejected message.
return 0; // End the program.
#include<stdio.h> // Include the standard input/output library for using printf and scanf
functions.
#include<string.h> // Include the string manipulation library for functions like strcmp,
strcpy, etc.
#include<stdlib.h> // Include the standard library for functions like atoi (to convert strings
to integers).
#include<ctype.h> // Include the ctype library for functions like isdigit (to check if a
character is a digit).
void input(); // Declare the input function to read user input.
void change(int p, char *res); // Declare the change function to replace variable values in
expressions.
void output(); // Declare the output function to display the final optimized code.
void constant(); // Declare the constant propagation function to evaluate constant
expressions.
struct expr { // Define a structure to represent an expression.
char op[2], op1[5], op2[5], res[5]; // Define fields for the operator and operands.
int flag; // Flag to indicate whether the expression has been evaluated or not.
} arr[10]; // Define an array of structures to store multiple expressions.
int n; // Declare a global variable n to store the number of expressions.
int main() { // Define the main function to control the flow of the program.
input(); // Call the input function to get the list of expressions from the user.
constant(); // Call the constant function to evaluate constant expressions.
output(); // Call the output function to print the optimized code.
return 0; // Return 0 to indicate successful execution of the program.
void input() { // Define the input function to read expressions from the user.
int i; // Declare a loop counter variable.
printf("\n\nEnter the maximum number of expressions: "); // Prompt the user to input the
number of expressions.
scanf("%d", &n); // Read the number of expressions into n.
printf("\nEnter the input: \n"); // Prompt the user to enter the expressions.
for(i = 0; i < n; i++) { // Loop through each expression.
scanf("%s", arr[i].op); // Read the operator of the expression.
scanf("%s", arr[i].op1); // Read the first operand of the expression.
scanf("%s", arr[i].op2); // Read the second operand of the expression.
scanf("%s", arr[i].res); // Read the result variable of the expression.
arr[i].flag = 0; // Set the flag to 0, indicating that the expression hasn't been evaluated
yet.
void constant() { // Define the constant propagation function.
int i; // Declare a loop counter variable.
int op1, op2, res; // Declare variables for the operands and result of the expression.
char op, res1[5]; // Declare a variable for the operator and the result as a string.
for(i = 0; i < n; i++) { // Loop through each expression.
if((isdigit(arr[i].op1[0]) && isdigit(arr[i].op2[0])) || (strcmp(arr[i].op, "=")) == 0) { // Check
if both operands are constants or if the operation is an assignment.
op1 = atoi(arr[i].op1); // Convert the first operand from string to integer.
op2 = atoi(arr[i].op2); // Convert the second operand from string to integer.
op = arr[i].op[0]; // Get the operator (e.g., '+', '-', etc.).
switch(op) { // Perform the corresponding operation based on the operator.
case '+': // If the operator is '+'.
res = op1 + op2; // Add the operands.
break;
case '-': // If the operator is '-'.
res = op1 - op2; // Subtract the operands.
break;
case '*': // If the operator is '*'.
res = op1 * op2; // Multiply the operands.
break;
case '/': // If the operator is '/'.
res = op1 / op2; // Divide the operands.
break;
case '=': // If the operator is '=' (assignment).
res = op1; // The result is just the value of op1.
break;
sprintf(res1, "%d", res); // Convert the result into a string.
arr[i].flag = 1; // Mark the expression as evaluated by setting the flag to 1.
change(i, res1); // Call the change function to update other expressions with the
result.
void output() { // Define the output function to display the optimized code.
int i = 0; // Declare a loop counter variable.
printf("\nOptimized code is: "); // Print the header for optimized code.
for(i = 0; i < n - 1; i++) { // Loop through the expressions (excluding the last one).
if(!arr[i].flag) { // If the expression has not been evaluated.
printf("\n%s %s %s %s", arr[i].op, arr[i].op1, arr[i].op2, arr[i].res); // Print the
expression.
printf("\n"); // Print a newline after displaying all expressions.
}
void change(int p, char *res) { // Define the change function to update the expressions.
int i; // Declare a loop counter variable.
for(i = p + 1; i < n; i++) { // Loop through the expressions after the one being updated.
if(strcmp(arr[p].res, arr[i].op1) == 0) // If the result of the current expression matches
the first operand.
strcpy(arr[i].op1, res); // Replace the first operand with the new result.
else if(strcmp(arr[p].res, arr[i].op2) == 0) // If the result of the current expression
matches the second operand.
strcpy(arr[i].op2, res); // Replace the second operand with the new result.
