Wednesday, September 24, 2014

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 }

No comments:

Post a Comment