Snippets, SPCC

Implementation of Bottom-Up (Shift-Reduce) Parsing in C++

2 Comments

Bottom-up parsing is a strategy used by compilers to analyse source code by building the parse tree from the leaves (terminal symbols) up to the root (start symbol). The most common bottom-up technique is shift-reduce parsing, which uses a stack and a set of production rules. At each step the parser either shifts the next input symbol onto the stack, or reduces the top of the stack by replacing a substring that matches the right-hand side of a production rule with the corresponding left-hand side symbol.

This C++ program implements a simple shift-reduce parser. It reads a set of production rules and an input string from the user, then processes the string step by step, displaying the stack contents, remaining input, and the action taken (Shifted or Reduced) at every stage.

C++ Code

#include <conio.h>
#include <iostream.h>
#include <string.h>

/* Structure to hold one grammar production rule */
struct grammer {
    char p[20];     /* LHS: left-hand side non-terminal (e.g. "E") */
    char prod[20];  /* RHS: right-hand side string     (e.g. "E+E") */
} g[10];            /* up to 10 production rules */

void main() {
    int i, stpos, j, k, l, m, o, p, f, r;
    int np, tspos, cr;

    /* --- Step 1: Read production rules --- */
    cout << "\nEnter Number of productions:";
    cin >> np;

    char sc, ts[10];

    cout << "\nEnter productions:\n";
    for (i = 0; i < np; i++) {
        cin >> ts;              /* e.g. "E->E+E" */
        strncpy(g[i].p, ts, 1); /* first character is the LHS non-terminal */
        strcpy(g[i].prod, &ts[3]); /* skip "X->" prefix to get the RHS */
    }

    /* --- Step 2: Read the input string to be parsed --- */
    char ip[10];
    cout << "\nEnter Input:";
    cin >> ip;

    int lip = strlen(ip);   /* length of input string */
    char stack[10];

    stpos = 0;
    i     = 0;

    /* Shift first input symbol onto the stack to start */
    sc           = ip[i];
    stack[stpos] = sc;
    i++; stpos++;

    /* --- Step 3: Print the parsing table header --- */
    cout << "\n\nStack\tInput\tAction";

    /* --- Step 4: Main parse loop --- */
    do {
        r = 1;  /* r=1 means we just shifted; r=2 means we just reduced */

        /* Inner loop: keep reducing while a reduction is possible */
        while (r != 0) {
            cout << "\n";

            /* Print current stack contents */
            for (p = 0; p < stpos; p++) {
                cout << stack[p];
            }
            cout << "\t";

            /* Print remaining input (from current position to end) */
            for (p = i; p < lip; p++) {
                cout << ip[p];
            }

            /* Print the action performed in the PREVIOUS iteration */
            cout << (r == 2 ? "\tReduced" : "\tShifted");
            r = 0;

            getch();   /* pause for step-by-step viewing */

            /* Try to reduce: check every substring of the stack against all rules */
            for (k = 0; k < stpos; k++) {
                f = 0;

                /* Clear temporary buffer */
                for (l = 0; l < 10; l++) ts[l] = '';

                /* Extract stack substring starting at position k */
                tspos = 0;
                for (l = k; l < stpos; l++) {
                    ts[tspos] = stack[l];
                    tspos++;
                }

                /* Compare extracted substring against each production RHS */
                for (m = 0; m < np; m++) {
                    cr = strcmp(ts, g[m].prod);

                    if (cr == 0) {
                        /* Match found: reduce by removing the matched symbols
                           from the stack and pushing the LHS non-terminal */
                        for (l = k; l < 10; l++) {
                            stack[l] = '';
                            stpos--;
                        }
                        stpos = k;
                        strcat(stack, g[m].p);  /* push LHS onto stack */
                        stpos++;
                        r = 2;  /* flag: a reduction was performed */
                    }
                }
            }
        }

        /* No more reductions possible: shift next input symbol */
        sc           = ip[i];
        stack[stpos] = sc;
        i++; stpos++;

    } while (strlen(stack) != 1 && stpos != lip);

    /* --- Step 5: Accept or reject the input --- */
    if (strlen(stack) == 1) {
        cout << "\n String Accepted";
    }

    getch();
}

How the Code Works

  1. Grammar input: Each production is entered in the form LHS->RHS (e.g. E->E+E). The program splits this at the -> separator: the LHS character is stored in g[i].p and the RHS string in g[i].prod.
  2. Initial shift: Before entering the main loop, the first character of the input is pushed onto the stack to ensure the loop has something to work with.
  3. Reduce phase: The inner while(r != 0) loop repeatedly tries every possible substring of the stack against all RHS patterns. When a match is found (strcmp == 0), the matched portion is removed from the stack and the LHS symbol is pushed in its place. This continues until no more reductions are possible (r stays 0).
  4. Shift phase: After all reductions are exhausted, the next input character is shifted onto the stack and the outer do-while loop repeats.
  5. Accept condition: The parse succeeds if the stack is reduced to a single symbol (the grammar start symbol) after all input has been consumed.

Sample Input / Output

Enter Number of productions:4

Enter productions:
E->E+E
E->E*E
E->(E)
E->a

Enter Input:(a+a)*a


Stack   Input   Action
(       a+a)*a  Shifted
(a      +a)*a   Shifted
(E      +a)*a   Reduced
(E+     a)*a    Shifted
(E+a    )*a     Shifted
(E+E    )*a     Reduced
(E      )*a     Reduced
(E)     *a      Shifted
E       *a      Reduced
E*      a       Shifted
E*a             Shifted
E*E             Reduced
E               Reduced
 String Accepted

Output Explanation

  1. ( Shifted: The opening parenthesis is pushed onto the stack; remaining input is a+a)*a.
  2. (a Shifted: The terminal a is shifted. Stack is now (a.
  3. (E Reduced: The top of the stack matches the RHS of E->a, so a is replaced by E.
  4. (E+ Shifted, (E+a Shifted, (E+E Reduced: + is shifted, then a is shifted and immediately reduced to E via E->a.
  5. (E Reduced: The three-symbol substring E+E matches E->E+E, reducing it to a single E. Stack becomes (E.
  6. E Reduced: After ) is shifted ((E) on the stack), the rule E->(E) fires, collapsing all three symbols to E.
  7. Multiplication: * and a are shifted; a reduces to E; then E*E reduces via E->E*E.
  8. Acceptance: The stack contains a single E (the start symbol) and all input is consumed — the string is accepted.

See Also

Conclusion

This shift-reduce parser illustrates the fundamental mechanism behind LALR(1) parsers — the engine that powers tools like yacc and Bison. The core insight is that every parse is a sequence of shift and reduce decisions driven by the current stack top and the lookahead symbol. In a production parser these decisions are encoded in a pre-computed parse table; here they are computed by brute-force substring matching, which keeps the code readable and easy to trace. Pairing this parser with the lexical analyser gives you a complete front-end that can be connected to the code generator to form a minimal compiler pipeline.

2 thoughts on “Implementation of Bottom-Up (Shift-Reduce) Parsing in C++”

  2. hi, i’m really newbie at this and i just wanna ask, did you use table parsing to create this program?

    Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.