fork(1) download
copy 
  1. // Simple Shift Reduce parsing for E → E + E | E * E | (E) | id
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <ctype.h>
  5.  
  6. // Stack to hold tokens and non-terminals during parsing
  7. char stack[100][10];
  8. int top = -1; // Points to the top of the stack
  9. int i = 0; // Input pointer/index
  10. char input[100]; // Holds the input string (e.g., "a + b * c")
  11.  
  12. // Push a symbol (token or non-terminal) onto the stack
  13. void push(const char *s)
  14. {
  15.     strcpy(stack[++top], s);
  16. }
  17.  
  18. // Pop the top of the stack
  19. void pop()
  20. {
  21.     top--;
  22. }
  23.  
  24. // Print current stack contents
  25. void printStack()
  26. {
  27.     for (int i = 0; i <= top; i++) printf("%s", stack[i]);
  28.     printf("\n");
  29. }
  30.  
  31. // Try to apply a reduction rule to the top of the stack
  32. int reduce()
  33. {
  34.     // Rule 1: E → E + E
  35.     if (top >= 2 &&
  36.             strcmp(stack[top-2], "E")==0 &&
  37.             strcmp(stack[top-1], "+")==0 &&
  38.             strcmp(stack[top], "E")==0)
  39.     {
  40.         pop(); pop(); pop();
  41.         push("E");
  42.         return 1;
  43.     }
  44.  
  45.     // Rule 2: E → E * E
  46.     if (top >= 2 &&
  47.             strcmp(stack[top-2], "E")==0 &&
  48.             strcmp(stack[top-1], "*")==0 &&
  49.             strcmp(stack[top], "E")==0)
  50.     {
  51.         pop(); pop(); pop();
  52.         push("E");
  53.         return 1;
  54.     }
  55.  
  56.     // Rule 3: E → (E)
  57.     if (top >= 2 &&
  58.             strcmp(stack[top-2], "(")==0 &&
  59.             strcmp(stack[top-1], "E")==0 &&
  60.             strcmp(stack[top], ")")==0)
  61.     {
  62.         pop(); pop(); pop();
  63.         push("E");
  64.         return 1;
  65.     }
  66.  
  67.     // Rule 4: E → id
  68.     if (top!=-1 && stack[top][0]>='a'&&stack[top][0]<='z')
  69.     {
  70.         pop();
  71.         push("E");
  72.         return 1;
  73.     }
  74.  
  75.     return 0;
  76. }
  77.  
  78. int main()
  79. {
  80.     strcpy(input, "( a +      (b*a))");
  81.  
  82.     // Main parsing loop
  83.     while (input[i])
  84.     {
  85.         // Ignore whitespaces
  86.         if (isspace(input[i])) {
  87.             i++;
  88.             continue;
  89.         }
  90.  
  91.         // SHIFT step
  92.         char temp[2] = {input[i], '\0'};
  93.         push(temp);
  94.         i++;
  95.  
  96.         printf("Shift: ");
  97.         printStack();
  98.  
  99.         // REDUCE step
  100.         while (reduce())
  101.         {
  102.             printf("Reduce: ");
  103.             printStack();
  104.         }
  105.     }
  106.  
  107.     // Final check
  108.     if (top == 0 && strcmp(stack[0], "E")==0)
  109.         printf("String Accepted\n");
  110.     else
  111.         printf("String Rejected\n");
  112.  
  113.     return 0;
  114. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Shift: (
Shift: (a
Reduce: (E
Shift: (E+
Shift: (E+(
Shift: (E+(b
Reduce: (E+(E
Shift: (E+(E*
Shift: (E+(E*a
Reduce: (E+(E*E
Reduce: (E+(E
Shift: (E+(E)
Reduce: (E+E
Reduce: (E
Shift: (E)
Reduce: E
String Accepted
https://ideone.com/gONEPx
language:
C (gcc 8.3)
created:
2 days 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!