fork download
copy 
  1. // Shift Reduce Parser Improved
  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 pos = 0;       // Input pointer
  10. char input[100];   // Holds input string
  11.  
  12. // Push a symbol onto stack
  13. void push(const char *s)
  14. {
  15.     strcpy(stack[++top], s);
  16. }
  17.  
  18. // Pop top element
  19. void pop()
  20. {
  21.     top--;
  22. }
  23.  
  24. // Print stack contents
  25. void printStack()
  26. {
  27.     for (int i = 0; i <= top; i++)
  28.         printf("%s", stack[i]);
  29.     printf("\n");
  30. }
  31.  
  32. // Apply reduce rules
  33. int reduce()
  34. {
  35.     // Rule 1: E -> E + E
  36.     if (top >= 2 &&
  37.         strcmp(stack[top-2], "E") == 0 &&
  38.         strcmp(stack[top-1], "+") == 0 &&
  39.         strcmp(stack[top], "E") == 0)
  40.     {
  41.         pop();
  42.         pop();
  43.         pop();
  44.         push("E");
  45.         return 1;
  46.     }
  47.  
  48.     // Rule 2: E -> E * E
  49.     if (top >= 2 &&
  50.         strcmp(stack[top-2], "E") == 0 &&
  51.         strcmp(stack[top-1], "*") == 0 &&
  52.         strcmp(stack[top], "E") == 0)
  53.     {
  54.         pop();
  55.         pop();
  56.         pop();
  57.         push("E");
  58.         return 1;
  59.     }
  60.  
  61.     // Rule 3: E -> (E)
  62.     if (top >= 2 &&
  63.         strcmp(stack[top-2], "(") == 0 &&
  64.         strcmp(stack[top-1], "E") == 0 &&
  65.         strcmp(stack[top], ")") == 0)
  66.     {
  67.         pop();
  68.         pop();
  69.         pop();
  70.         push("E");
  71.         return 1;
  72.     }
  73.  
  74.     // Rule 4: E -> id
  75.     if (top != -1 &&
  76.         stack[top][0] >= 'a' &&
  77.         stack[top][0] <= 'z')
  78.     {
  79.         pop();
  80.         push("E");
  81.         return 1;
  82.     }
  83.  
  84.     return 0;
  85. }
  86.  
  87. int main()
  88. {
  89.     printf("Enter an Expression:\n");
  90.     fgets(input, 100, stdin);
  91.  
  92.     while (input[pos])
  93.     {
  94.         // Ignore spaces
  95.         if (isspace(input[pos]))
  96.         {
  97.             pos++;
  98.             continue;
  99.         }
  100.  
  101.         char temp[2] = {input[pos], '\0'};
  102.         push(temp);
  103.         pos++;
  104.  
  105.         printf("Shift: ");
  106.         printStack();
  107.  
  108.         while (reduce())
  109.         {
  110.             printf("Reduce: ");
  111.             printStack();
  112.         }
  113.     }
  114.  
  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 5312KB
comments (?)
stdin
copy 
(a + b*a)
stdout
copy 
Enter an Expression:
Shift: (
Shift: (a
Reduce: (E
Shift: (E+
Shift: (E+b
Reduce: (E+E
Reduce: (E
Shift: (E*
Shift: (E*a
Reduce: (E*E
Reduce: (E
Shift: (E)
Reduce: E
String Accepted
https://ideone.com/0v6HIl
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!