/*Aim: Write a C program for implementation of a Shift Reduce Parser using Stack
Data Structure to accept
a given input string of a given grammar. */
/*Description:
A shift-reduce parser is a type of bottom-up parser used in syntax analysis within
compilers. It processes an input string by shifting symbols onto a stack and
reducing sequences of symbols to grammar rules. The parser operates in two main
phases:
Shift: The next input symbol is moved onto the stack.
Reduce: A sequence of symbols on the stack is replaced with a nonterminal symbol
based on a grammar rule.
The goal is to reduce the entire input string to the start symbol of the grammar,
indicating that the string is syntactically correct. If the parser successfully
reduces the input to the start symbol, it accepts the string; otherwise, it reports
a syntax error.
*/
/*Source Code: */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
// Global Variables
int z = 0, i = 0, j = 0, c = 0;
// Modify array size to increase length of string to be parsed
char a[16], ac[20], stk[15], act[10];
// This function will check whether the stack contains a production rule to be
reduced.
// Rules can be E -> 2E2, E -> 3E3, E -> 4
void check() {
// Copying string to be printed as action
strcpy(ac, "REDUCE TO E -> ");
// c = length of input string
for (z = 0; z < c; z++) {
// Checking for producing rule E -> 4
if (stk[z] == '4') {
printf("%s4", ac);
stk[z] = 'E';
stk[z + 1] = '\0';
// Printing action
printf("\n$%s\t%s$\t", stk, a);
}
}
for (z = 0; z < c - 2; z++) {
// Checking for another production
if (stk[z] == '2' && stk[z + 1] == 'E' && stk[z + 2] == '2') {
printf("%s2E2", ac);
stk[z] = 'E';
stk[z + 1] = '\0';
stk[z + 2] = '\0';
printf("\n$%s\t%s$\t", stk, a);
i = i - 2;
}
}
for (z = 0; z < c - 2; z++) {
// Checking for E -> 3E3
if (stk[z] == '3' && stk[z + 1] == 'E' && stk[z + 2] == '3') {
printf("%s3E3", ac);
stk[z] = 'E';
stk[z + 1] = '\0';
stk[z + 2] = '\0';
printf("\n$%s\t%s$\t", stk, a);
i = i - 2;
}
}
return; // Return to main
}
// Driver Function
int main() {
printf("GRAMMAR is -\nE -> 2E2 \nE -> 3E3 \nE -> 4\n");
// a is input string
strcpy(a, "32423");
// strlen(a) will return the length of a to c
c = strlen(a);
// "SHIFT" is copied to act to be printed
strcpy(act, "SHIFT");
// This will print Labels (column name)
printf("\nstack \t input \t action");
// This will print the initial values of stack and input
printf("\n$\t%s$\t", a);
// This will run up to the length of the input string
for (i = 0; j < c; i++, j++) {
// Printing action
printf("%s", act);
// Pushing into stack
stk[i] = a[j];
stk[i + 1] = '\0';
// Moving the pointer
a[j] = ' ';
// Printing action
printf("\n$%s\t%s$\t", stk, a);
// Call check function which will check the stack whether it contains any
production or not
check();
}
// Rechecking last time if it contains any valid production then it will
replace, otherwise invalid
check();
// If the top of the stack is E (starting symbol), then it will accept the
input
if (stk[0] == 'E' && stk[1] == '\0') {
printf("Accept\n");
} else { // Else reject
printf("Reject\n");
}
return 0;
}
/*Output:
GRAMMAR is -
E -> 2E2
E -> 3E3
E -> 4
stack input action
$ 32423$ SHIFT
$3 2423$ SHIFT
$32 423$ SHIFT
$324 23$ REDUCE TO E -> 4
$32E 23$ SHIFT
$32E2 3$ REDUCE TO E -> 2E2
$3E 3$ SHIFT
$3E3 $ REDUCE TO E -> 3E3
$E $ Accept
*/
