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 
*/

Finding FIRST Sets (of terminals) of Productions [Compiler Design][C++]

This program finds the FIRST sets of terminals of the productions supplied to it.

Algorithm:

1. Input the productions from the user.
2. For each production, check the first char after = sign, if it is a terminal, print it if it is not in the already printed record set and record it in memory otherwise just skip it if it is listed as already printed.
3. If it is a non-terminal, find the production starting with the non-terminal and do recursion.
4. Skip all other input until comma ',' or '\0' is found.
5. The first character after ',' is checked again for being a terminal or non-terminal.
6. After the FIRST terminal set for current production has been evaluated, reset the record for already printed non-terminals.

Source:

#include <iostream>

using namespace std;

//This array stores the terminals already printed
char printed[50];
int index=0;

//This resets the printed terminals record for the next production
void resetPrinted()
{
    index=0;
    for(int i=0;i<50;++i) printed[i] = '0';
}

//Checks whether the nonterminal char found has already been printed for this production
bool alreadyPrinted(char c)
{
    for(int i=0;i<50;++i)
        if(printed[i]==c) return true;
    return false;
}

bool checkChar(char c)
{
    if(!isupper(c))
    {
        if(!alreadyPrinted(c))
        {
        cout<<c<<" ";
        printed[index++] = c;
        }
        return true;
    }else
        return false;
}

void printFirst(char **input, int production, int nProductions)
{
    char c;
    int index=0;
    while(c=input[production][index]!='=')index++;
    index++; //We have found '=', we need to skip it now.

    while((c=input[production][index])!='\0')
    {
        //Is terminal
        if(checkChar(c)){}
        //Is not terminal
        else
        {
            for(int i=0;i<nProductions;++i)
            {
                if(i==production) continue;
                if(c==input[i][0]) {printFirst(input, i, nProductions); break;}
            }
        }
        //Skip until next terminal or non-terminal is found
        while((c=input[production][++index])!=','){ if(c=='\0') return;};
        c=input[production][++index]; //We have found a comma, we need to look at the next character now
    }
}

int main()
{
    int nProductions = 0;
    char **input;

    cout<<"Enter the number of productions: ";
    cin>>nProductions;
    cin.ignore();

    input = new char*[nProductions];
    for(int i=0;i<nProductions;++i)
    {
        input[i] = new char[50];
    }

    cout<<"Enter the productions: \n";

    for(int i=0;i<nProductions;++i)
        cin>>input[i];

    for(int i=0;i<nProductions;++i)
    {
        resetPrinted();
        cout<<"{ ";
        printFirst(input, i, nProductions);
        cout<<"}\n";
    }
}

Output:

Enter the number of productions: 4
Enter the productions:
A=aB,Bc,Dd
B=Cb,b
C=Db,cD,d
D=c
{ a c d b }
{ c d b }
{ c d }
{ c }