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 indx = 0;        // Input pointer/index
  9. char input[100];   // Holds the input string (e.g., "a+b+c")
  10.  
  11. // Push a symbol (token or non-terminal) onto the stack
  12. void push(const char *s)
  13. {
  14.     strcpy(stack[++top], s);
  15. }
  16. // Pop the top of the stack
  17. void pop()
  18. {
  19.     top--;
  20. }
  21. // Print current stack contents
  22. void printStack()
  23. {
  24.     for (int i = 0; i <= top; i++) printf("%s", stack[i]);
  25.     printf("\n");
  26. }
  27.  
  28.  
  29. // Try to apply a reduction rule to the  top of the stack
  30. int reduce()
  31. {
  32.     // Rule 1: E → E + E
  33.     if (top >= 2 &&
  34.             strcmp(stack[top-2], "E")==0 &&
  35.             strcmp(stack[top-1], "+")==0 &&
  36.             strcmp(stack[top], "E")==0)
  37.     {
  38.         pop();
  39.         pop();
  40.         pop();   // Remove "E + E" (3 pops)
  41.         push("E");           // Push "E" onto the stack
  42.         return 1;               // Indicate that a reduction occurred
  43.     }
  44.  
  45.     if (top >= 2 &&
  46.             strcmp(stack[top-2], "E")==0 &&
  47.             strcmp(stack[top-1], "*")==0 &&
  48.             strcmp(stack[top], "E")==0)
  49.     {
  50.         pop();
  51.         pop();
  52.         pop();
  53.         push("E");
  54.         return 1;
  55.     } 
  56.  
  57.     if (top>=2
  58.     && strcmp(stack[top],")")==0
  59.     && strcmp(stack[top-1],"E")==0
  60.     && strcmp(stack[top-2],"(")==0 )
  61.     {
  62.         pop();
  63.         pop();
  64.         pop();
  65.         push("E");
  66.         return 1;
  67.     }
  68.  
  69.     // Rule 2: E → id
  70.     if (top!=-1 && stack[top][0]>='a'&&stack[top][0]<='z')
  71.     {
  72.         pop();  // Remove "id" (1 pop)
  73.         push("E");  // Push "E" onto the stack
  74.         return 1;
  75.     }
  76.  
  77.     return 0; // No reduction matched
  78. }
  79.  
  80. int main()
  81. {
  82.  
  83.     fgets(input,100,stdin); 
  84.     input[strcspn(input,"\n")]=0;
  85.  
  86.     while (input[indx])
  87.     {
  88.  
  89.         if(input[indx]==' ')
  90.         {
  91.             indx++;
  92.             continue ;
  93.  
  94.         }
  95.         char temp[2] = {input[indx], '\0'};  // turn character into string
  96.  
  97.         push(temp);                           // push actual character (like 'x')
  98.         indx ++;        // Move input pointer ahead by 1
  99.  
  100.         // Print stack after shift
  101.         printf("Shift: ");
  102.         printStack();
  103.  
  104.  
  105.         // REDUCE step: apply all possible reductions after shift
  106.         while (reduce())
  107.         {
  108.             printf("Reduce: ");
  109.             printStack();
  110.  
  111.         }
  112.     }
  113.  
  114.     // Final check: input is accepted if the stack has a single symbol "E"
  115.     if (top == 0 && strcmp(stack[0], "E")==0)
  116.         printf("String Accepted\n");
  117.     else
  118.         printf("String Rejected\n");
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
(a+ (b*a))
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/GLEjVs
language:
C (gcc 8.3)
created:
15 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!