fork download 
  1. %{
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. enum ActionType { SHIFT, REDUCE, ACCEPT, ERROR };
  6.  
  7. typedef struct {
  8.     enum ActionType type;
  9.     int value;
  10. } TableEntry;
  11.  
  12. // Columns: i=0, + =1, * =2, ( =3, )=4, $=5, E=6, T=7, F=8
  13. TableEntry parsingTable[12][9] = {
  14.     // i         +         *         (         )         $         E         T         F
  15.     {{SHIFT,5}, {ERROR,0}, {ERROR,0}, {SHIFT,4}, {ERROR,0}, {ERROR,0}, {SHIFT,1}, {SHIFT,2}, {SHIFT,3}}, // 0
  16.     {{ERROR,0}, {SHIFT,6}, {ERROR,0}, {ERROR,0}, {ERROR,0}, {ACCEPT,0}, {ERROR,0}, {ERROR,0}, {ERROR,0}}, // 1
  17.     {{ERROR,0}, {REDUCE,2}, {SHIFT,7}, {ERROR,0}, {REDUCE,2}, {REDUCE,2}, {ERROR,0}, {ERROR,0}, {ERROR,0}}, // 2
  18.     {{ERROR,0}, {REDUCE,4}, {REDUCE,4}, {ERROR,0}, {REDUCE,4}, {REDUCE,4}, {ERROR,0}, {ERROR,0}, {ERROR,0}}, // 3
  19.     {{SHIFT,5}, {ERROR,0}, {ERROR,0}, {SHIFT,4}, {ERROR,0}, {ERROR,0}, {SHIFT,8}, {SHIFT,2}, {SHIFT,3}}, // 4
  20.     {{ERROR,0}, {REDUCE,6}, {REDUCE,6}, {ERROR,0}, {REDUCE,6}, {REDUCE,6}, {ERROR,0}, {ERROR,0}, {ERROR,0}}, // 5
  21.     {{SHIFT,5}, {ERROR,0}, {ERROR,0}, {SHIFT,4}, {ERROR,0}, {ERROR,0}, {ERROR,0}, {SHIFT,9}, {SHIFT,3}}, // 6
  22.     {{SHIFT,5}, {ERROR,0}, {ERROR,0}, {SHIFT,4}, {ERROR,0}, {ERROR,0}, {ERROR,0}, {ERROR,0}, {SHIFT,10}}, // 7
  23.     {{ERROR,0}, {SHIFT,6}, {ERROR,0}, {ERROR,0}, {SHIFT,11}, {ERROR,0}, {ERROR,0}, {ERROR,0}, {ERROR,0}}, // 8
  24.     {{ERROR,0}, {REDUCE,1}, {SHIFT,7}, {ERROR,0}, {REDUCE,1}, {REDUCE,1}, {ERROR,0}, {ERROR,0}, {ERROR,0}}, // 9
  25.     {{ERROR,0}, {REDUCE,3}, {REDUCE,3}, {ERROR,0}, {REDUCE,3}, {REDUCE,3}, {ERROR,0}, {ERROR,0}, {ERROR,0}}, //10
  26.     {{ERROR,0}, {REDUCE,5}, {REDUCE,5}, {ERROR,0}, {REDUCE,5}, {REDUCE,5}, {ERROR,0}, {ERROR,0}, {ERROR,0}}  //11
  27. };
  28.  
  29. // Productions:
  30. // 1. E -> E + T
  31. // 2. E -> T
  32. // 3. T -> T * F
  33. // 4. T -> F
  34. // 5. F -> (E)
  35. // 6. F -> id
  36.  
  37. char* productions[] = {
  38.     "E -> E + T", //1
  39.     "E -> T",     //2
  40.     "T -> T * F", //3
  41.     "T -> F",     //4
  42.     "F -> ( E )", //5
  43.     "F -> id"     //6
  44. };
  45. int productionLengths[] = {3, 1, 3, 1, 3, 1};
  46. int productionLHS[] = {6, 6, 7, 7, 8, 8}; // E=6, T=7, F=8
  47.  
  48. int stack[100];
  49. int top = -1;
  50.  
  51. void push(int state) {
  52.     stack[++top] = state;
  53. }
  54.  
  55. int pop() {
  56.     return stack[top--];
  57. }
  58.  
  59. void printGrammar() {
  60.     printf("Given Grammar is:\n");
  61.     printf("E -> E + T | T\n");
  62.     printf("T -> T * F | F\n");
  63.     printf("F -> (E) | id\n\n");
  64. }
  65. %}
  66.  
  67. %option noyywrap
  68.  
  69. %%
  70.  
  71. . ;
  72.  
  73. %%
  74.  
  75. int main() {
  76.     printGrammar();
  77.  
  78.     char input[100];
  79.     printf("Enter input string (e.g., i+i*i$): ");
  80.     scanf("%s", input);
  81.  
  82.     int inputPtr = 0;
  83.     push(0);
  84.  
  85.     printf("\nStack\t\tInput\t\tAction\n");
  86.  
  87.     while (1) {
  88.         int currentState = stack[top];
  89.         char currentInputSymbol = input[inputPtr];
  90.  
  91.         int col = -1;
  92.         switch (currentInputSymbol) {
  93.             case 'i': col = 0; break;
  94.             case '+': col = 1; break;
  95.             case '*': col = 2; break;
  96.             case '(': col = 3; break;
  97.             case ')': col = 4; break;
  98.             case '$': col = 5; break;
  99.             default:
  100.                 printf("Error: Invalid symbol '%c'\n", currentInputSymbol);
  101.                 return 1;
  102.         }
  103.  
  104.         TableEntry action = parsingTable[currentState][col];
  105.  
  106.         // Print stack
  107.         printf("State ");
  108.         for (int i = 0; i <= top; i++) {
  109.             printf("%d ", stack[i]);
  110.         }
  111.  
  112.         // Print input
  113.         printf("\t%s\t", &input[inputPtr]);
  114.  
  115.         // Take action
  116.         switch (action.type) {
  117.             case SHIFT:
  118.                 printf("\tSHIFT %d\n", action.value);
  119.                 push(action.value);
  120.                 inputPtr++;
  121.                 break;
  122.  
  123.             case REDUCE: {
  124.                 int prodNum = action.value;
  125.                 printf("\tREDUCE by %s\n", productions[prodNum - 1]);
  126.                 for (int i = 0; i < productionLengths[prodNum - 1]; i++) {
  127.                     pop();
  128.                 }
  129.                 int stateAfterPop = stack[top];
  130.                 int gotoCol = productionLHS[prodNum - 1];
  131.                 TableEntry gotoEntry = parsingTable[stateAfterPop][gotoCol];
  132.                 if (gotoEntry.type != SHIFT) {
  133.                     printf("ERROR: Invalid goto after reduction\n");
  134.                     return 1;
  135.                 }
  136.                 push(gotoEntry.value);
  137.                 break;
  138.             }
  139.  
  140.             case ACCEPT:
  141.                 printf("\tACCEPT\n");
  142.                 return 0;
  143.  
  144.             case ERROR:
  145.                 printf("\tERROR\n");
  146.                 return 1;
  147.         }
  148.     }
  149.  
  150.     return 0;
  151. }
  152.  
Success #stdin #stdout #stderr 0.03s 7020KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
ERROR: /home/m28Udm/prog:2:1: Syntax error: Operator expected
Warning: /home/m28Udm/prog:30:
	Singleton variables: [T]
ERROR: /home/m28Udm/prog:30:
	No permission to modify static procedure `(->)/2'
	Defined at /usr/lib/swi-prolog/boot/init.pl:212
Warning: /home/m28Udm/prog:31:
	Singleton variables: [E,T]
ERROR: /home/m28Udm/prog:31:
	No permission to modify static procedure `(->)/2'
	Defined at /usr/lib/swi-prolog/boot/init.pl:212
Warning: /home/m28Udm/prog:32:
	Singleton variables: [F]
ERROR: /home/m28Udm/prog:32:
	No permission to modify static procedure `(->)/2'
	Defined at /usr/lib/swi-prolog/boot/init.pl:212
Warning: /home/m28Udm/prog:33:
	Singleton variables: [T,F]
ERROR: /home/m28Udm/prog:33:
	No permission to modify static procedure `(->)/2'
	Defined at /usr/lib/swi-prolog/boot/init.pl:212
Warning: /home/m28Udm/prog:34:
	Singleton variables: [F,E]
ERROR: /home/m28Udm/prog:34:
	No permission to modify static procedure `(->)/2'
	Defined at /usr/lib/swi-prolog/boot/init.pl:212
ERROR: /home/m28Udm/prog:36:0: Syntax error: Operator expected
ERROR: /home/m28Udm/prog:151:1: Syntax error: Unexpected end of file
ERROR: '$runtoplevel'/0: Undefined procedure: program/0
   Exception: (3) program ? EOF: exit
https://ideone.com/aiU1mu
language:
Prolog (swi 7.6.4)
created:
9 days 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!