fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <ctype.h>
  4. #define MAX 100
  5.  
  6. char stack[MAX][20]; 
  7. int top = -1;      
  8.  
  9.  
  10. void push(const char *sym)
  11. {
  12.     top++;
  13.     strcpy(stack[top], sym);
  14. }
  15.  
  16. void pop()
  17. {
  18.     if (top >= 0) top--;
  19. }
  20.  
  21. // Print current stack state
  22. void printStack(const char *action)
  23. {
  24.     printf("%s: ", action);
  25.     for (int i = 0; i <= top; i++)
  26.         printf("%s ", stack[i]);
  27.     printf("\n");
  28. }
  29.  
  30. int tryReduce()
  31. {
  32.     if (top >= 2 &&
  33.         strcmp(stack[top - 2], "(") == 0 &&
  34.         strcmp(stack[top - 1], "E") == 0 &&
  35.         strcmp(stack[top],     ")") == 0)
  36.     {
  37.         pop(); pop(); pop();        
  38.         push("E");                    
  39.         printStack("Reduce");
  40.         return 1;
  41.     }
  42.  
  43.     if (top >= 2 &&
  44.         strcmp(stack[top - 2], "E") == 0 &&
  45.         strcmp(stack[top - 1], "*") == 0 &&
  46.         strcmp(stack[top],     "E") == 0)
  47.     {
  48.         pop(); pop(); pop();
  49.         push("E");
  50.         printStack("Reduce");
  51.         return 1;
  52.     }
  53.  
  54.     if (top >= 2 &&
  55.         strcmp(stack[top - 2], "E") == 0 &&
  56.         strcmp(stack[top - 1], "+") == 0 &&
  57.         strcmp(stack[top],     "E") == 0)
  58.     {
  59.         pop(); pop(); pop();
  60.         push("E");
  61.         printStack("Reduce");
  62.         return 1;
  63.     }
  64.  
  65.     // Rule: E -> id
  66.     // Top is an identifier (not a special symbol)
  67.     if (top >= 0 &&
  68.         strcmp(stack[top], "E") != 0 &&
  69.         strcmp(stack[top], "+") != 0 &&
  70.         strcmp(stack[top], "*") != 0 &&
  71.         strcmp(stack[top], "(") != 0 &&
  72.         strcmp(stack[top], ")") != 0)
  73.     {
  74.         pop();
  75.         push("E");
  76.         printStack("Reduce");
  77.         return 1;
  78.     }
  79.  
  80.     return 0; // No reduction possible
  81. }
  82.  
  83. int nextToken(const char *input, int *pos, char *out)
  84. {
  85.     int len = strlen(input);
  86.  
  87.     // Skip whitespace
  88.     while (*pos < len && isspace((unsigned char)input[*pos]))
  89.         (*pos)++;
  90.  
  91.     if (*pos >= len) return 0; // No more tokens
  92.  
  93.     char ch = input[*pos];
  94.  
  95.     // Single-character tokens: operators and parentheses
  96.     if (ch == '+' || ch == '*' || ch == '(' || ch == ')')
  97.     {
  98.         out[0] = ch;
  99.         out[1] = '\0';
  100.         (*pos)++;
  101.         return 1;
  102.     }
  103.  
  104.     if (isalpha((unsigned char)ch) || ch == '_')
  105.     {
  106.         int start = *pos;
  107.         while (*pos < len && (isalnum((unsigned char)input[*pos]) || input[*pos] == '_'))
  108.             (*pos)++;
  109.         int tlen = *pos - start;
  110.         strncpy(out, input + start, tlen);
  111.         out[tlen] = '\0';
  112.         return 1;
  113.     }
  114.  
  115.     (*pos)++;
  116.     return 0;
  117. }
  118.  
  119. void shiftReduceParse(const char *input)
  120. {
  121.     top = -1; 
  122.  
  123.     int pos = 0;
  124.     char token[50];
  125.  
  126.     while (nextToken(input, &pos, token))
  127.     {
  128.         push(token);
  129.         printStack("Shift");
  130.  
  131.         while (tryReduce());
  132.     }
  133.  
  134.     while (tryReduce());
  135.  
  136.     if (top == 0 && strcmp(stack[0], "E") == 0)
  137.         printf("String Accepted\n");
  138.     else
  139.         printf("String Rejected\n");
  140. }
  141.  
  142. int main()
  143. {
  144.     char input[200];
  145.     printf("Enter an Expression:\n");
  146.     fgets(input, 200, stdin);
  147.  
  148.     int len = strlen(input);
  149.     if (len > 0 && input[len - 1] == '\n')
  150.         input[len - 1] = '\0';
  151.  
  152.     shiftReduceParse(input);
  153.  
  154.     return 0;
  155. }
Success #stdin #stdout 0s 5292KB
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/JQ173C
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!