Question

what roles do fist/follow sets have in constructing a table driven parser

Answer 1

Answer:-

first set and follow set to check your grammar is not ambiguous, or at least to discover where it is so that you can correct (by making a little hack). The rue is that when a symbol can have more than one follower, those followers must have sdifferents start smbols.

For example, the construct  if a then if b then s else s2 because it can means if a then (if b then s else s2) or if a then (if b then s) else s2. This is because the constructs (if-then) and (if-then-else) are both followers of then and have the same first set (the single symbol {if}). So the compiler does not know how to interpret it, and you have to find a way to change your parser so that it picks the longest construct.

They are also used for error recovery. As you want a compiler to find the maximum of errors in your program, when it finds an error, it skip the symbols until it finds one which is in the possible follower. It will not correct the program, but the compiler will resume checking syntax as soon as possible.

FIRST(S), where S is any string of grammar symbols is the set of terminals that begin strings derived from a. If S =>* a, then a will be added among FIRST (S).

Define FOLLOW(S) for nonterminal S, to be the set of terminals a that can appear immediately to the right of A in some sentential form; that is, the set of terminals a such that there exists a derivation of the form S =>* aAa. There may have been symbols between S and a, at some time during the derivation, but if so, they derive ɛ and disappeared. A can als be the rightmost symbol in some sentential form, then $ is in FOLLOW(A), where $ is a special "endmarker" symbol that is not to be a symbol of any grammar.

You do a first and follow set if you are trying to write an LL parser by hand. However, unless you are doing this for a compiler course and need to understand the principles, you are much better off letting a parser generator do it for you.

By the way a compiler doesn't generate a first and follow set. A compiler compiler aka a parser generator (for LL, but not LR) does. A first and follow set are used to create the right set of condionals to use to pick the appropriate rule to parse with while building an LL parser. Once you have built those conditionals, you throw those sets away, they have done their job.

I suppose if you are doing table driven LL parsing, you might keep the sets around rather than translating them into conditionals. However, most LL parser generators generate recursive descent code rather than tables and the recursive descent code uses the conditionals