fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <ctype.h>
  4.  
  5. char stack[100];
  6. int top = -1;
  7.  
  8. // Function to push a character onto the stack
  9. void push(char c) {
  10.     stack[++top] = c;
  11. }
  12.  
  13. // Function to print the current contents of the stack
  14. void printStack() {
  15.     for (int i = 0; i <= top; i++)
  16.         printf("%c", stack[i]);
  17. }
  18.  
  19. // Function to apply rules (Shift-Reduce Parsing)
  20. void reduce() {
  21.  
  22.     // Rule 1: id -> E
  23.     // If top of stack is 'a' or 'b', treat it as identifier (id)
  24.     if (top >= 0 && (stack[top] == 'a' || stack[top] == 'b')) {
  25.         printf("Reduce: id -> E\n");
  26.         stack[top] = 'E';  // Replace with non-terminal E
  27.     }
  28.  
  29.     // Rule 2: (E) -> E
  30.     // If pattern "(E)" is found on top of stack
  31.     if (top >= 2 && stack[top] == ')' && stack[top-1] == 'E' && stack[top-2] == '(') {
  32.         printf("Reduce: (E) -> E\n");
  33.         top -= 2;          // Remove '(' and ')'
  34.         stack[top] = 'E';  // Replace with E
  35.     }
  36.  
  37.     // Rule 3: E * E -> E
  38.     // Handle multiplication
  39.     if (top >= 2 && stack[top] == 'E' && stack[top-1] == '*' && stack[top-2] == 'E') {
  40.         printf("Reduce: E * E -> E\n");
  41.         top -= 2;          // Reduce 3 symbols into 1
  42.         stack[top] = 'E';
  43.     }
  44.  
  45.     // Rule 4: E + E -> E
  46.     // Handle addition
  47.     if (top >= 2 && stack[top] == 'E' && stack[top-1] == '+' && stack[top-2] == 'E') {
  48.         printf("Reduce: E + E -> E\n");
  49.         top -= 2;          // Reduce 3 symbols into 1
  50.         stack[top] = 'E';
  51.     }
  52. }
  53.  
  54. int main() {
  55.     char input[100];
  56.     int i = 0;
  57.  
  58.     printf("Enter an Expression: ");
  59.     fgets(input, sizeof(input), stdin);
  60.  
  61.     // Remove newline character from input
  62.     input[strcspn(input, "\n")] = '\0';
  63.  
  64.     printf("\nParsing Steps:\n");
  65.  
  66.     while (input[i] != '\0') {
  67.  
  68.         // Skip whitespace
  69.         if (isspace(input[i])) {
  70.             i++;
  71.             continue;
  72.         }
  73.  
  74.         // SHIFT operation: push character to stack
  75.         printf("Shift: %c\n", input[i]);
  76.         push(input[i]);
  77.  
  78.         // Print current stack after shift
  79.         printStack();
  80.         printf("\n");
  81.  
  82.         // Try to REDUCE after shift
  83.         reduce();
  84.  
  85.         i++;
  86.     }
  87.  
  88.     // After input ends, try to reduce remaining stack
  89.     while (top > 0) {
  90.         reduce();
  91.     }
  92.  
  93.     // Final check: if stack contains only 'E', input is accepted
  94.     if (top == 0 && stack[top] == 'E') {
  95.         printf("String Accepted\n");
  96.     } else {
  97.         printf("String Rejected\n");
  98.     }
  99.  
  100.     return 0;
  101. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
(a+    b)
stdout
copy 
Enter an Expression: 
Parsing Steps:
Shift: (
(
Shift: a
(a
Reduce: id -> E
Shift: +
(E+
Shift: b
(E+b
Reduce: id -> E
Reduce: E + E -> E
Shift: )
(E)
Reduce: (E) -> E
String Accepted
https://ideone.com/XGne20
language:
C (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!