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