shift reduce parser demo

Sure! Here is an example of a shift-reduce parser in C, along with explanations for each step:

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

#define MAX_STACK_SIZE 100

int stack[MAX_STACK_SIZE];
int top = -1;

void push(int item) {
    if (top >= MAX_STACK_SIZE - 1) {
        printf("Stack Overflow");
        return;
    }
    stack[++top] = item;
}

int pop() {
    if (top < 0) {
        printf("Stack Underflow");
        return -1;
    }
    return stack[top--];
}

int parse(char input[]) {
    int i = 0;
    int length = strlen(input);

    push('$');
    push('E');

    while (i < length) {
        if (input[i] == stack[top]) {
            pop();
            i++;
        } else {
            switch (stack[top]) {
                case 'E':
                    pop();
                    push('T');
                    push('A');
                    break;
                case 'A':
                    pop();
                    push('+');
                    push('T');
                    push('A');
                    break;
                case 'T':
                    pop();
                    push('F');
                    push('B');
                    break;
                case 'B':
                    pop();
                    push('*');
                    push('F');
                    push('B');
                    break;
                case 'F':
                    pop();
                    push(')');
                    push('E');
                    push('(');
                    break;
                case '$':
                    return 1;
                default:
                    return 0;
            }
        }
    }
    return 0;
}

int main() {
    char input[100];
    printf("Enter an expression: ");
    scanf("%s", input);

    if (parse(input)) {
        printf("Parsing successful.\n");
    } else {
        printf("Parsing failed.\n");
    }

    return 0;
}

Explanation:

This program demonstrates a simple shift-reduce parser for a given input expression. Let's go through the steps involved:

The program defines a stack and its maximum size using the MAX_STACK_SIZE constant. It also declares a variable top to keep track of the top element of the stack.
The push function is defined to insert an item into the stack. It checks for stack overflow before pushing the item.
The pop function is defined to remove and return the top item from the stack. It checks for stack underflow before popping the item.
The parse function takes an input expression as a parameter and returns 1 if the parsing is successful, and 0 otherwise.
The function initializes the stack with the end marker $ and the start symbol E.
The function then enters a loop that processes the input expression character by character.
If the current character matches the top of the stack, it is popped from the stack and the loop moves to the next character.
If the current character does not match the top of the stack, a switch statement is used to handle different stack symbols.
For each stack symbol, the corresponding production rule is applied by popping the symbol from the stack and pushing the appropriate symbols onto the stack.
The loop continues until all characters in the input expression have been processed.
At the end of the loop, if the stack is empty and the input expression has been fully parsed, the function returns 1 indicating successful parsing. Otherwise, it returns 0.
In the main function, the user is prompted to enter an expression. The parse function is called with the input expression, and the result is printed accordingly.

Note: This is a simplified example of a shift-reduce parser and may not handle all possible expressions correctly. It serves as a basic demonstration of the shift-reduce parsing technique.