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