Compilers Octob er 8, 2007FIRST and FOLLOW sets – a necessary preliminary to constructingthe LL(1) parsing tableRemember: A predictive parser can only be built for an LL( 1) grammar. A grammar is notLL(1) if it is:1. Left recursive, or2. Not left factored.However, grammars that are not left recursive and are left factored may still not be LL(1).To see if a grammar is LL(1), try to build the parse table for the predictive parser by themethod we are about t o desc ribe. If any element in the table co nta ins more than onegrammar rule right-hand side, then the grammar is not LL( 1).To build the table, we must must compute FIRST and FOLLOW sets for the grammar.1Compilers Octob er 8, 2007FIRST SetsUltimately, we want to define FIRST sets for the right-hand sides of each of the grammar’sproductions. The idea is t hat for a sequence α of symbols, FIRST(α) is the set of terminalsthat beg in the strings derivable from α, and also, if α can derive ǫ, then ǫ is in FIRST(α).By allowing ǫ to be in FIRST(α), we can avoid defining the notion of “nullable” as Appeldoe s in the book. More formally:F IRST (α) = {t | (t is a terminal and α ⇒∗ tβ) or (t = ǫ and α ⇒∗ ǫ)}To define F IRST (α) for arbitrary α, we start by defining F IRST (X), for a singlesymbol X (a terminal, a nonterminal, or ǫ):• X is a terminal: F IRST (X) = X• X is ǫ: F IRST (X) = ǫ2Compilers Octob er 8, 2007• X is a nonterminal. In this case, we must look at all g rammar productions with X onthe left, i.e., productions of the form:X → Y1Y2Y3. . . Ykwhere each Ykis a single terminal or nonterminal (or there is just one Y, and it is ǫ).For each such production, we perform the following actions:– Put F IRST (Y1) − {ǫ} into F IRST (X).– If ǫ is in F IRST (Y1), the n put F IRST (Y2) − {ǫ} into F IRST (X).– If ǫ is in F IRST (Y2), the n put F IRST (Y3) − {ǫ} into F IRST (X).– . . .– If ǫ is in F IRST (Yi) for 1  i  k (all production right- hand sides) then put ǫinto F IRST (X).For example, compute the FIRST sets of each of the non-terminals in the followinggrammar:exp → term exp′3Compilers Octob er 8, 2007exp′→ − term exp′| ǫterm → factor term′term′→ / factor term′| ǫfactor → INT LIT ERAL | ( exp )Once we have computed FIRST(X) for each terminal and nonterminal X, we can computeFIRST(α) for every production’s right-hand-side α. In general, alpha will be o f the form:X1X2. . . Xnwhere each X is a single terminal or nonterminal, or there is just one X1and it is ǫ. Therules for computing FIRST(α) are essentially the sa me as the rules for computing the firstset of a nonterminal.• Put F IRST (X1) − {ǫ} into F IRST (α)• If ǫ is in F IRST (X1) putF IRST (X2) − {ǫ} into F IRST (α).4Compilers Octob er 8, 2007• . . .• If ǫ is in the FIRST set for every Xk, put ǫ into F IRST (α).For the example grammar above, compute the FIRS T sets for each production’s right-handside.Why do we care about the FIRST (α) sets? During parsing, suppose the top-of- stacksymbol is nonterminal A , that there are two productions A → α and A → β, and thatthe current token is a. Well, if FIRS T(α) includes a . . .5Compilers Octob er 8, 2007FOLLOW setsFOLLOW sets are only defined for single no nterminals. The definition is as follows:For a nonterminal A, FOLLOW(A) is the set of terminals that can appear immediately tothe right of A in so m e partial derivation; i.e., terminal t is in FOL LOW(A) if:S ⇒+ . . . A t . . .where t is a terminalFurthermore , if A can be the rightmost symbol in a derivation, then EOF is in FOLLOW(A).It is worth not ing that epsilon is never in a FO LLOW set.Notationally:6Compilers Octob er 8, 2007F OLLOW (A) = {t | (t is a terminal a nd S ⇒+ α A t β) or (t is EOF and S ⇒∗ αA)}Some conditions under which symbols a, c, and EOF are in the FOLLOW set of nonterminalA:S S S/ \ / \ / \/ \ / \ / \/ \ / X Y\ / \/ /\ \ / / | \ / \A \ /\ | (A)/\ A B /\ |/ \ / / \ |(a)b c epsilon / \ /| /______\ EOF is in FOLLOW(A)| (c)d e fa is in FOLLOW(A) ||\c is in FOLLOW(A)7Compilers Octob er 8, 2007How to compute FOLLOW(A) for each nonterminal A:• If A is the start nonterminal, put EO F in FOLLOW(A)Find the product ions with A on the right-hand-side:• For each production X → αAβ, put F IRST (β) − {ǫ} in FOLLOW(A)• If ǫ is in F IRST (β) then put F OLLOW (X) into F OLLOW (A)• For each production X → αA, put FOLLOW(X) into FOLLOW(A)Note that• To compute FIRST(A) you must look for A o n a production’s left-hand side.• To compute FO LLOW(A) you must look for A o n a production’s right-hand side.• FIRST and FOLLOW sets are always sets of terminals (plus, perhaps, ǫ for FIRST sets,and E OF for follow sets). Nonterminals are never in a F I RST or a FOLLOW set.8Compilers Octob er 8, 2007Example: Compute FOLL OW sets of the non-terminals in the following language:S → B c | D BB → a b | c SD → d | ǫWhy do we care about FOLLOW sets? Suppose during parsing we have X on top of thestack and a is the current token. What if X has two productions X → α and X → βbut a is not in the FIRST set of either α or β?9Compilers Octob er 8, 2007How to build parse tables – and tell if a grammar is LL(1)To build the table, we fill in the rows one at a time f or e ach no nterminal X as follows:• for each production X → α– for each t erminal t in First(α): put α in Table[X,t]– if ǫ is in First(α) t hen:∗ for each terminal t in Follow(X): put α in Table[X,t]The grammar is not LL(1) if and only if the re is more than one entry for any c e ll in thetable. Try building a parse table for the following grammar:S → B c | D BB → a b | c SD → d |