How to find first set?

Question

I am trying to list the First set of a given grammar with this function:

Note:
char c - the character to find the first set;
first_set - store elements of the corresponding first set;
q1, q2 - the previous position;
rule- store all the grammar rule line by line listed below;
for the first time the parameters are ('S', 0, 0).

void findfirst(char c, int q1, int q2){
    if(!(isupper(c)) || c=='$'){
         first_set[n++] = c;
    }
    for(int j=0;j<rule_number;j++){
        if(rule[j][0]==c){
            if(rule[j][2]==';'){
                if(rule[q1][q2]=='\0')
                    first_set[n++] = ';';
                else if(rule[q1][q2]!='\0' &&(q1!=0||q2!=0))
                    findfirst(rule[q1][q2], q1, (q2+1));
                else
                    first_set[n++] = ';';
            }
            else if(!isupper(rule[j][2]) || rule[j][2]=='$')
                first_set[n++] = rule[j][2];
            else
                findfirst(rule[j][2],j,3);
        }
    }
}

But found that if the given grammar looks like this:

S AC$
C c
C ;
A aBCd
A BQ
B bB
B ;
Q q
Q ;

(which the left hand side or any capital letters in the right hand side are non-terminal, and any small case letters are terminal) the function couldn't correctly output the first set for S, since it will stop at finding the first set of Q and store ';' to the first set and won't go on to find C's first set.

Does anyone have a clue? Thanks in advance.

Answer 1

It is extremely inefficient to compute FIRST sets one at a time, since they are interdependent. For example, in order to compute the FIRST set of A , you need to also compute the FIRST set of B, and then because B can derive the emoty string, you need the FIRST set of Q.

Most algorithms compute all of them in parallel, using some variation of a transitive closure algorithm. You can do this with a depth-first search, which seems to be what you are attempting, but it might be easier to implement the least fixed point algorithm described in the Dragon book (and Wikipedia.

Either way, you will probably find it easier to first compute NULLABLE (that is, which non-terminals derive the empty set). There is a simple linear-time algorithm for that (linear in the size of the grammar), which again is easy to find.

If you are doing this work as part of a class, you'll probably find the relevant algorithms in your course materials. Alternatively, you can look for a copy of the Dragon book or other similar text books.