fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <ctype.h>
  4.  
  5. // =====================================================================
  6. //  Shift-Reduce Parser
  7. //  Grammar:
  8. //    E -> E + E
  9. //    E -> E * E
  10. //    E -> id
  11. //    E -> (E)
  12. // =====================================================================
  13.  
  14. #define MAX 100
  15.  
  16. char stack[MAX][20]; // The parser stack (each cell = a symbol like "E", "+", "id", etc.)
  17. int top = -1;        // Stack pointer
  18.  
  19. // ---------- Stack helpers ----------
  20.  
  21. void push(const char *sym)
  22. {
  23.     top++;
  24.     strcpy(stack[top], sym);
  25. }
  26.  
  27. void pop()
  28. {
  29.     if (top >= 0) top--;
  30. }
  31.  
  32. // Print current stack state
  33. void printStack(const char *action)
  34. {
  35.     printf("%s: ", action);
  36.     for (int i = 0; i <= top; i++)
  37.         printf("%s ", stack[i]);
  38.     printf("\n");
  39. }
  40.  
  41. // ---------- Reduce rules ----------
  42. // Try to reduce the top of the stack using grammar rules.
  43. // Returns 1 if a reduction was made, 0 otherwise.
  44.  
  45. int tryReduce()
  46. {
  47.     // Rule: E -> (E)
  48.     // Stack top-2 = "(", top-1 = "E", top = ")"
  49.     if (top >= 2 &&
  50.         strcmp(stack[top - 2], "(") == 0 &&
  51.         strcmp(stack[top - 1], "E") == 0 &&
  52.         strcmp(stack[top],     ")") == 0)
  53.     {
  54.         pop(); pop(); pop();          // remove ), E, (
  55.         push("E");                    // push E
  56.         printStack("Reduce");
  57.         return 1;
  58.     }
  59.  
  60.     // Rule: E -> E * E
  61.     // Stack top-2 = "E", top-1 = "*", top = "E"
  62.     if (top >= 2 &&
  63.         strcmp(stack[top - 2], "E") == 0 &&
  64.         strcmp(stack[top - 1], "*") == 0 &&
  65.         strcmp(stack[top],     "E") == 0)
  66.     {
  67.         pop(); pop(); pop();
  68.         push("E");
  69.         printStack("Reduce");
  70.         return 1;
  71.     }
  72.  
  73.     // Rule: E -> E + E
  74.     // Stack top-2 = "E", top-1 = "+", top = "E"
  75.     if (top >= 2 &&
  76.         strcmp(stack[top - 2], "E") == 0 &&
  77.         strcmp(stack[top - 1], "+") == 0 &&
  78.         strcmp(stack[top],     "E") == 0)
  79.     {
  80.         pop(); pop(); pop();
  81.         push("E");
  82.         printStack("Reduce");
  83.         return 1;
  84.     }
  85.  
  86.     // Rule: E -> id
  87.     // Top is an identifier (not a special symbol)
  88.     if (top >= 0 &&
  89.         strcmp(stack[top], "E") != 0 &&
  90.         strcmp(stack[top], "+") != 0 &&
  91.         strcmp(stack[top], "*") != 0 &&
  92.         strcmp(stack[top], "(") != 0 &&
  93.         strcmp(stack[top], ")") != 0)
  94.     {
  95.         pop();
  96.         push("E");
  97.         printStack("Reduce");
  98.         return 1;
  99.     }
  100.  
  101.     return 0; // No reduction possible
  102. }
  103.  
  104. // ---------- Tokenizer (get next token, skip whitespace) ----------
  105. // Returns the next token from input starting at position *pos.
  106. // Tokens: "(", ")", "+", "*", or an identifier string.
  107. // Returns 0 if no more tokens, 1 if a token was written into `out`.
  108.  
  109. int nextToken(const char *input, int *pos, char *out)
  110. {
  111.     int len = strlen(input);
  112.  
  113.     // Skip whitespace
  114.     while (*pos < len && isspace((unsigned char)input[*pos]))
  115.         (*pos)++;
  116.  
  117.     if (*pos >= len) return 0; // No more tokens
  118.  
  119.     char ch = input[*pos];
  120.  
  121.     // Single-character tokens: operators and parentheses
  122.     if (ch == '+' || ch == '*' || ch == '(' || ch == ')')
  123.     {
  124.         out[0] = ch;
  125.         out[1] = '\0';
  126.         (*pos)++;
  127.         return 1;
  128.     }
  129.  
  130.     // Identifier: letters and digits
  131.     if (isalpha((unsigned char)ch) || ch == '_')
  132.     {
  133.         int start = *pos;
  134.         while (*pos < len && (isalnum((unsigned char)input[*pos]) || input[*pos] == '_'))
  135.             (*pos)++;
  136.         int tlen = *pos - start;
  137.         strncpy(out, input + start, tlen);
  138.         out[tlen] = '\0';
  139.         return 1;
  140.     }
  141.  
  142.     // Unknown character — skip it
  143.     (*pos)++;
  144.     return 0;
  145. }
  146.  
  147. // ---------- Main parser ----------
  148.  
  149. void shiftReduceParse(const char *input)
  150. {
  151.     top = -1; // Reset stack
  152.  
  153.     int pos = 0;
  154.     char token[50];
  155.  
  156.     while (nextToken(input, &pos, token))
  157.     {
  158.         // SHIFT: push the current token onto the stack
  159.         push(token);
  160.         printStack("Shift");
  161.  
  162.         // After each shift, try to reduce as many times as possible
  163.         while (tryReduce());
  164.     }
  165.  
  166.     // After all input consumed, try one final round of reductions
  167.     while (tryReduce());
  168.  
  169.     // Check if parse succeeded (stack should contain exactly one "E")
  170.     if (top == 0 && strcmp(stack[0], "E") == 0)
  171.         printf("String Accepted\n");
  172.     else
  173.         printf("String Rejected\n");
  174. }
  175.  
  176. int main()
  177. {
  178.     char input[200];
  179.     printf("Enter an Expression:\n");
  180.     fgets(input, 200, stdin);
  181.  
  182.     // Remove newline if present
  183.     int len = strlen(input);
  184.     if (len > 0 && input[len - 1] == '\n')
  185.         input[len - 1] = '\0';
  186.  
  187.     shiftReduceParse(input);
  188.  
  189.     return 0;
  190. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
(a + (b*a))
stdout
copy 
Enter an Expression:
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/tG3KcL
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!