fork 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(); // Remove "E + E" (3 pops)
  41.         push("E"); // Push "E" onto the stack
  42.         return 1; // Indicate that a reduction occurred
  43.     }
  44.  
  45.     // Rule 2: E → E * E (Added for multiplication)
  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(); // Remove "E * E" (3 pops)
  52.         push("E"); // Push "E" onto the stack
  53.         return 1;
  54.     }
  55.  
  56.     // Rule 3: E → (E) (Added for parentheses)
  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(); // Remove "( E )" (3 pops)
  63.         push("E"); // Push "E" onto the stack
  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(); // Remove "id" (1 pop)
  71.         push("E"); // Push "E" onto the stack
  72.         return 1;
  73.     }
  74.  
  75.     return 0; // No reduction matched
  76. }
  77.  
  78. int main()
  79. {
  80.     // Read input string allowing spaces until newline
  81.     scanf("%[^\n]", input); 
  82.  
  83.     // Main parsing loop: continue until input ends and no more reductions are possible
  84.     while (input[i])
  85.     {
  86.         // Ignore whitespaces (spaces, tabs, etc.)
  87.         if (isspace(input[i])) {
  88.             i++;
  89.             continue;
  90.         }
  91.  
  92.         // SHIFT step: if input is not yet fully consumed
  93.         char temp[2] = {input[i], '\0'}; // turn character into string
  94.         push(temp); // push actual character (like 'x', '+', '*', '(')
  95.         i++; // Move input pointer ahead by 1
  96.  
  97.         // Print stack after shift
  98.         printf("Shift: ");
  99.         printStack();
  100.  
  101.         // REDUCE step: apply all possible reductions after shift
  102.         while (reduce())
  103.         {
  104.             printf("Reduce: ");
  105.             printStack();
  106.         }
  107.     }
  108.  
  109.     // Final check: input is accepted if the stack has a single symbol "E"
  110.     if (top == 0 && strcmp(stack[0], "E")==0)
  111.         printf("String Accepted\n");
  112.     else
  113.         printf("String Rejected\n");
  114.  
  115.     return 0;
  116. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
String Rejected
https://ideone.com/4MHsyK
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!