Untitled

#include <stdio.h>
#include <string.h>

#define STACK_SIZE 100

char stack[STACK_SIZE][10]; // Stack to hold symbols
int top = -1;               // Index for the top of the stack

// Function to push an element onto the stack
void push(char *str) {
    if (top < STACK_SIZE - 1) {
        strcpy(stack[++top], str);
    } else {
        printf("Stack overflow\n");
    }
}

// Function to pop an element from the stack
void pop() {
    if (top >= 0) {
        top--;
    } else {
        printf("Stack underflow\n");
    }
}

// Function to display the stack's current content
void displayStack() {
    printf("Stack: ");
    for (int i = 0; i <= top; i++) {
        printf("%s ", stack[i]);
    }
    printf("\n");
}

// Main function to implement shift-reduce parser
int main() {
    char input[100]; // Variable to hold user input tokens
    char *token;

    printf("Enter the input string (e.g., 'a a b b'):\n");
    scanf("%99[^\n]", input); // Reading the full input line, up to 99 characters

    token = strtok(input, " "); // Tokenizing the input based on spaces

    while (token != NULL) {
        // Shift operation
        push(token);
        printf("Shift: %s\n", token);
        displayStack();

        // Reduce operation: Simple grammar S -> aSb | ab
        while (1) {
            if (top >= 2 && strcmp(stack[top-2], "a") == 0 && strcmp(stack[top], "b") == 0) {
                pop(); // Remove 'b'
                pop(); // Remove middle element
                pop(); // Remove 'a'
                push("S"); // Push the result 'S'
                printf("Reduce: S -> aSb | ab\n");
                displayStack();
            } else {
                break; // Exit the loop if no reduction is possible
            }
        }

        token = strtok(NULL, " "); // Move to the next token
    }

    // Final check to see if the input is accepted
    if (top == 0 && strcmp(stack[top], "S") == 0) {
        printf("Accepted\n");
    } else {
        printf("Rejected\n");
    }

    return 0;
}