fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // LL(1) Parsing Table: {Non-terminal, Terminal} -> {Production Symbols}
  5. // Ekhane map use kore table-er value gulo set kora hoyeche
  6. map<pair<string, string>, vector<string>> table = {
  7.     {{"E", "id"}, {"T", "E'"}}, {{"E", "("}, {"T", "E'"}},
  8.     {{"E'", "+"}, {"+", "T", "E'"}}, {{"E'", ")"}, {"eps"}}, {{"E'", "$"}, {"eps"}},
  9.     {{"T", "id"}, {"F", "T'"}}, {{"T", "("}, {"F", "T'"}},
  10.     {{"T'", "+"}, {"eps"}}, {{"T'", "*"}, {"*", "F", "T'"}}, {{"T'", ")"}, {"eps"}}, {{"T'", "$"}, {"eps"}},
  11.     {{"F", "id"}, {"id"}}, {{"F", "("}, {"(", "E", ")"}}
  12. };
  13.  
  14. void predictiveParse(string input) {
  15.     stack<string> st;
  16.     st.push("$"); // Stack-er niche end marker '$' push kora hoyeche
  17.     st.push("E"); // Start symbol 'E' stack-e push kora holo
  18.  
  19.     // Input string ke alada kora (jemon 'id' thakle sheta ke ekta token dhora)
  20.     vector<string> tokens;
  21.     for (int i = 0; i < input.size(); ) {
  22.         if (isspace(input[i])) { i++; continue; }
  23.         if (input.substr(i, 2) == "id") { tokens.push_back("id"); i += 2; }
  24.         else { tokens.push_back(string(1, input[i])); i++; }
  25.     }
  26.     tokens.push_back("$"); // Input string-er sheshe '$' add kora holo
  27.  
  28.     int ptr = 0; // Input pointer manage korar jonno
  29.     cout << left << setw(20) << "STACK" << setw(20) << "INPUT" << "ACTION" << endl;
  30.  
  31.  
  32.  
  33.     while (!st.empty()) {
  34.         string top = st.top();
  35.         string curr = tokens[ptr];
  36.  
  37.         // Current Stack state print korar jonno logic
  38.         stack<string> temp = st;
  39.         string sStack = "";
  40.         vector<string> v;
  41.         while(!temp.empty()){ v.push_back(temp.top()); temp.pop(); }
  42.         reverse(v.begin(), v.end());
  43.         for(string x : v) sStack += x;
  44.  
  45.         // Current Input state print korar jonno logic
  46.         string sInput = "";
  47.         for(int i=ptr; i<tokens.size(); i++) sInput += tokens[i];
  48.  
  49.         cout << left << setw(20) << sStack << setw(20) << sInput;
  50.  
  51.         // MATCH: Stack top ebong Input symbol mile gele pop ebong pointer move hobe
  52.         if (top == curr) {
  53.             if (top == "$") { cout << "ACCEPT" << endl; return; }
  54.             cout << "match " << curr << endl;
  55.             st.pop();
  56.             ptr++;
  57.         }
  58.         // PRODUCTION: Table-e jodi oi (top, current) cell-e kono rule thake
  59.         else if (table.count({top, curr})) {
  60.             vector<string> prod = table[{top, curr}];
  61.             cout << top << " -> ";
  62.             for(string p : prod) cout << p;
  63.             cout << endl;
  64.  
  65.             st.pop(); // Current non-terminal-ke stack theke ber kora holo
  66.             if (prod[0] != "eps") { // Rule-ti jodi epsilon na hoy, tobe reverse-e stack-e push hobe
  67.                 for (int i = (int)prod.size() - 1; i >= 0; i--) st.push(prod[i]);
  68.             }
  69.         }
  70.         // ERROR: Table-e kono rule na thakle parsing error dekhabe
  71.         else {
  72.             cout << "ERROR" << endl;
  73.             return;
  74.         }
  75.     }
  76. }
  77.  
  78. int main() {
  79.     string input;
  80.     cout << "Enter input (e.g., id+id*id): ";
  81.     cin >> input; // Udahoron hisebe 'id+id*id' dewa jete pare
  82.     predictiveParse(input);
  83.     return 0;
  84. }
  85.  
  86. //Enter input (e.g., id+id*id): id+id*id
  87. //STACK               INPUT               ACTION
  88. //$E                  id+id*id$           E -> TE'
  89. //$E'T                id+id*id$           T -> FT'
  90. //$E'T'F              id+id*id$           F -> id
  91. //$E'T'id             id+id*id$           match id
  92. //$E'T'               +id*id$             T' -> eps
  93. //$E'                 +id*id$             E' -> +TE'
  94. //$E'T+               +id*id$             match +
  95. //$E'T                id*id$              T -> FT'
  96. //$E'T'F              id*id$              F -> id
  97. //$E'T'id             id*id$              match id
  98. //$E'T'               *id$                T' -> *FT'
  99. //$E'T'F*             *id$                match *
  100. //$E'T'F              id$                 F -> id
  101. //$E'T'id             id$                 match id
  102. //$E'T'               $                   T' -> eps
  103. //$E'                 $                   E' -> eps
  104. //$                   $                   ACCEPT
  105.  
  106.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter input (e.g., id+id*id): STACK               INPUT               ACTION
$E                  $                   ERROR
https://ideone.com/8erUMP
language:
C++ (gcc 8.3)
created:
6 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!