fork download
copy 
  1. // Simple Shift Reduce parsing for E → E + E | id
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <ctype.h>
  5. // Stack to hold tokens and non-terminals during parsing
  6. char stack[100][10];
  7. int top = -1;      // Points to the top of the stack
  8. int index = 0;        // Input pointer/index
  9. char input[100];   // Holds the input string (e.g., "a+b+c")
  10.  
  11.  
  12. void removeSpaces(char *str)
  13. {
  14.     int i = 0, j = 0;
  15.  
  16.     while (str[i] != '\0')
  17.     {
  18.         if (!isspace(str[i]))   // keep only NON-whitespace
  19.         {
  20.             str[j] = str[i];
  21.             j++;
  22.         }
  23.         i++;
  24.     }
  25.     str[j] = '\0'; // terminate new string
  26. }
  27.  
  28. // Push a symbol (token or non-terminal) onto the stack
  29. void push(const char *s)
  30. {
  31.     strcpy(stack[++top], s);
  32. }
  33. // Pop the top of the stack
  34. void pop()
  35. {
  36.     top--;
  37. }
  38. // Print current stack contents
  39. void printStack()
  40. {
  41.     for (int i = 0; i <= top; i++) printf("%s", stack[i]);
  42.     printf("\n");
  43. }
  44.  
  45.  
  46. // Try to apply a reduction rule to the  top of the stack
  47. int reduce()
  48. {
  49.     // Rule 1: E → E + E
  50.     if (top >= 2 &&
  51.             strcmp(stack[top-2], "E")==0 &&
  52.             strcmp(stack[top-1], "+")==0 &&
  53.             strcmp(stack[top], "E")==0)
  54.     {
  55.         pop();
  56.         pop();
  57.         pop();   // Remove "E + E" (3 pops)
  58.         push("E");           // Push "E" onto the stack
  59.         return 1;               // Indicate that a reduction occurred
  60.     }
  61.  
  62.     // Rule 2: E → E * E
  63.     if (top >= 2 &&
  64.             strcmp(stack[top-2], "E")==0 &&
  65.             strcmp(stack[top-1], "*")==0 &&
  66.             strcmp(stack[top], "E")==0)
  67.     {
  68.         pop();
  69.         pop();
  70.         pop();   // Remove "E + E" (3 pops)
  71.         push("E");           // Push "E" onto the stack
  72.         return 1;               // Indicate that a reduction occurred
  73.     }
  74.  
  75.     // Rule 3: E → (E)
  76.     if (top >= 2 &&
  77.             strcmp(stack[top-2], "(")==0 &&
  78.             strcmp(stack[top-1], "E")==0 &&
  79.             strcmp(stack[top], ")")==0)
  80.     {
  81.         pop();
  82.         pop();
  83.         pop();   // Remove "E + E" (3 pops)
  84.         push("E");           // Push "E" onto the stack
  85.         return 1;               // Indicate that a reduction occurred
  86.     }
  87.  
  88.     // Rule 4: E → id
  89.     if (top!=-1 && stack[top][0]>='a'&&stack[top][0]<='z')
  90.     {
  91.         pop();  // Remove "id" (1 pop)
  92.         push("E");  // Push "E" onto the stack
  93.         return 1;
  94.     }
  95.  
  96.     return 0; // No reduction matched
  97. }
  98.  
  99. int main()
  100. {
  101.     // Read input string (e.g., a+b+c)
  102.     fgets(input, sizeof(input), stdin);
  103.     input[strcspn(input, "\n")] = '\0';
  104.     removeSpaces(input);
  105.  
  106.     //E+a
  107.     // Main parsing loop: continue until input ends and no more reductions are possible
  108.     while (input[index])
  109.     {
  110.         // SHIFT step: if input is not yet fully consumed
  111.         // Check for "id" token
  112.         char temp[2] = {input[index], '\0'};  // turn character into string
  113.         push(temp);                           // push actual character (like 'x')
  114.         index ++;        // Move input pointer ahead by 1
  115.  
  116.         // Print stack after shift
  117.         printf("Shift: ");
  118.         printStack();
  119.  
  120.  
  121.         // REDUCE step: apply all possible reductions after shift
  122.         while (reduce())
  123.         {
  124.             printf("Reduce: ");
  125.             printStack();
  126.  
  127.         }
  128.     }
  129.  
  130.     // Final check: input is accepted if the stack has a single symbol "E"
  131.     if (top == 0 && strcmp(stack[0], "E")==0)
  132.         printf("String Accepted\n");
  133.     else
  134.         printf("String Rejected\n");
  135.  
  136.     return 0;
  137. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
a + b * (c)
stdout
copy 
Shift: a
Reduce: E
Shift: E+
Shift: E+b
Reduce: E+E
Reduce: E
Shift: E*
Shift: E*(
Shift: E*(c
Reduce: E*(E
Shift: E*(E)
Reduce: E*E
Reduce: E
String Accepted
https://ideone.com/TScrED
language:
C (gcc 8.3)
created:
7 hours 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!