Thursday, September 25, 2014

Computation of LEADING and TRAILING sets [Compiler Design][C++]

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:

#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