fork(1) 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!=-1 && strcmp(stack[top],")")==0
  58.     && strcmp(stack[top-1],"E")==0
  59.     && strcmp(stack[top-2],"(")==0 )
  60.     {
  61.         pop();
  62.         pop();
  63.         pop();
  64.         push("E");
  65.         return 1;
  66.     }
  67.  
  68.     // Rule 2: E → id
  69.     if (top!=-1 && stack[top][0]>='a'&&stack[top][0]<='z')
  70.     {
  71.         pop();  // Remove "id" (1 pop)
  72.         push("E");  // Push "E" onto the stack
  73.         return 1;
  74.     }
  75.  
  76.     return 0; // No reduction matched
  77. }
  78.  
  79. int main()
  80. {
  81.  
  82.     fgets(input,100,stdin); 
  83.     input[strcspn(input,"\n")]=0;
  84.  
  85.     while (input[indx])
  86.     {
  87.  
  88.         if(input[indx]==' ')
  89.         {
  90.             indx++;
  91.             continue ;
  92.  
  93.         }
  94.         char temp[2] = {input[indx], '\0'};  // turn character into string
  95.  
  96.         push(temp);                           // push actual character (like 'x')
  97.         indx ++;        // Move input pointer ahead by 1
  98.  
  99.         // Print stack after shift
  100.         printf("Shift: ");
  101.         printStack();
  102.  
  103.  
  104.         // REDUCE step: apply all possible reductions after shift
  105.         while (reduce())
  106.         {
  107.             printf("Reduce: ");
  108.             printStack();
  109.  
  110.         }
  111.     }
  112.  
  113.     // Final check: input is accepted if the stack has a single symbol "E"
  114.     if (top == 0 && strcmp(stack[0], "E")==0)
  115.         printf("String Accepted\n");
  116.     else
  117.         printf("String Rejected\n");
  118.  
  119.     return 0;
  120. }
Success #stdin #stdout 0s 5284KB
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/YZ2kqP
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!