Computations of LEADING sets:
Algorithm:
1. Check the first non-terminal's productions one by one for terminals. If a terminal is found, print it. Then look at the next production.
2. If not found, recursively call the procedure for the single non-terminal present before the | or '\0' and include it's results (leading set's contents) in the result of this non-terminal.
Source:
Computation of TRAILING sets:
Algorithm:
1. Consider the first non-terminal's productions.
2. Scanning from right, if a non-terminal is found in a production, print it, skip the rest of this production's content and look for either '|' or '='. If '|' is found, this means that we are ready to consider the next production for this non-terminal. If '=' is found, it means that no production for this non-terminal is left to consider. We can look at the next non-terminal now.
3. If after scanning from right to left, we encounter '|' or '=' and non-terminal has not yet been found in between, we apply this recursive procedure to include the result of the singe non-terminal that must be present after the '|' separator and include it's result in the result for this non-terminal.
Source:
Algorithm:
1. Check the first non-terminal's productions one by one for terminals. If a terminal is found, print it. Then look at the next production.
2. If not found, recursively call the procedure for the single non-terminal present before the | or '\0' and include it's results (leading set's contents) in the result of this non-terminal.
Source:
#include <iostream> using namespace std;
bool checkTerminal(char c) { if (!isupper(c) && c != '\0' && c != '|') return true; else return false; } int findProduction(char NT, char **strings, int currentProduction, int nProductions){ for (int i = 0; i < nProductions; ++i){ if (i == currentProduction)continue; if (strings[i][0] == NT)return i; } } void checkNTString(char *string, char** strings, int currentProduction, int nProductions) { int i = 2; for (; i < 50; ++i){ if (checkTerminal(string[i])){ cout << string[i] << " "; while (string[i] != '|' && string[i] != '\0') i++; } else if (string[i] == '|' || string[i] == '\0'){ int productionNo = findProduction(string[i - 1], strings, currentProduction, nProductions); checkNTString(strings[productionNo], strings, productionNo, nProductions); } if (string[i] == '\0')break; } } int main() { cout << "Enter the number of non-terminals: "; int nProductions = 0; cin >> nProductions; cout << "Enter the productions: \n"; char **strings = new char*[nProductions]; for (int i = 0; i < nProductions; ++i){ strings[i] = new char[50]; cin >> strings[i]; } for (int i = 0; i < nProductions; ++i){ cout << "{ "; checkNTString(strings[i], strings, i, nProductions); cout << "}\n"; } return 0; }
/*
Input: E=E+T|T T=T*E|F F=(E)|q Input: E=T|E+T T=F|T*E F=q|(E) Input: S=(L)|a L=L,S|S */
Computation of TRAILING sets:
Algorithm:
1. Consider the first non-terminal's productions.
2. Scanning from right, if a non-terminal is found in a production, print it, skip the rest of this production's content and look for either '|' or '='. If '|' is found, this means that we are ready to consider the next production for this non-terminal. If '=' is found, it means that no production for this non-terminal is left to consider. We can look at the next non-terminal now.
3. If after scanning from right to left, we encounter '|' or '=' and non-terminal has not yet been found in between, we apply this recursive procedure to include the result of the singe non-terminal that must be present after the '|' separator and include it's result in the result for this non-terminal.
Source:
#include <iostream> using namespace std;
bool checkTerminal(char c) { if (!isupper(c) && c != '|' && c != '=') return true; else return false; } int findProduction(char NT, char **strings, int currentProduction, int nProductions){ for (int i = 0; i < nProductions; ++i){ if (i == currentProduction)continue; if (strings[i][0] == NT) return i; } } void checkNTString(char *string, char** strings, int currentProduction, int nProductions) { int i = 49; while (string[i] != '\0')i--; i = i - 1; for (; i >= 1;--i){ if (checkTerminal(string[i])){ cout << string[i] << " "; while (string[i] != '|' && string[i] != '=') i--; } else if (string[i] == '|' || string[i] == '='){ int productionNo = findProduction(string[i + 1], strings, currentProduction, nProductions); checkNTString(strings[productionNo], strings, productionNo, nProductions); } if (string[i] == '=')break; } } int main() { cout << "Enter the number of non-terminals: "; int nProductions = 0; cin >> nProductions; cout << "Enter the productions: \n"; char **strings = new char*[nProductions]; for (int i = 0; i < nProductions; ++i){ strings[i] = new char[50]; cin >> strings[i]; } for (int i = 0; i < nProductions; ++i){ cout << "{ "; checkNTString(strings[i], strings, i, nProductions); cout << "}\n"; } return 0; }/*Input: E=E+T|T T=T*E|F F=(E)|q Input: E=T|E+T T=F|T*E F=q|(E) Input: S=(L)|a L=L,S|S*/
No comments:
Post a Comment