Compiler Design Lecture | Examples on how to find first and follow in LL(1)

• Report rights infringement
• published: 15 Apr 2015
• views: 2785

First and Follow Set solved examples, First Follow solved examples Part 2 Video lecture for gate exam preparation CS IT MCA, The productions are: If X is terminal, FIRST(X) = {X}. If X → ε is a production, then add ε to FIRST(X). If X is a non-terminal, and X → Y1 Y2 … Yk is a production, and ε is in all of FIRST(Y1), …, FIRST(Yk), then add ε to FIRST(X). If X is a non-terminal, and X → Y1 Y2 … Yk is a production, then add a to FIRST(X) if for some i, a is in FIRST(Yi), and ε is in all of FIRST(T) = { (, id } FIRST(F) = { (, id } E → T implies that we should add FIRST(T) to FIRST(E), giving: FIRST(E) = { (, id } FIRST(T) = { (, id } FIRST(F) = { (, id } Finally, going through every production reveals that no more nonterminals can be added to any of the sets. So we've found the FIRST sets. Computing FOLLOW sets is similar. Assuming that the start symbol is E, and calling the end marker $, we initialise: FOLLOW(E) = { $ } FOLLOW(T) = { } FOLLOW(F) = { } E→E+T implies that + should be added to FOLLOW(E) and that everything in FOLLOW(E) should be added to FOLLOW(T): FOLLOW(E) = { $, + } FOLLOW(T) = { $, + } FOLLOW(F) = { } T→T*F implies that * should be added to FOLLOW(T) and that everything in FOLLOW(T) should be added to FOLLOW(F): FOLLOW(E) = { $, + } FOLLOW(T) = { $, +, * } FOLLOW(F) = { $, +, * } F→(E) implies that ) should be added to FOLLOW(E): FOLLOW(E) = { $, +, ) } FOLLOW(T) = { $, +, * } FOLLOW(F) = { $, +, * } E→T implies that everything in FOLLOW(E) should be added to FOLLOW(T): FOLLOW(E) = { $, +, ) } FOLLOW(T) = { $, +, *, ) } FOLLOW(F) = { $, +, * } T→F implies that everything in FOLLOW(T) should be added to FOLLOW(F): FOLLOW(E) = { $, +, ) } FOLLOW(T) = { $, +, *, ) } FOLLOW(F) = { $, +, *, ) } ...and no further applications of the rules add anything to any of the FOLLOW sets. There are some problems for which it's easier to analyse the grammar if left recursion has been removed FIRST(X) for all grammar symbols X Apply following rules: Applying rules 1 and 2 is obvious. Applying rules 3 and 4 for FIRST(Y1 Y2 … Yk) can be done as follows: Add all the non-ε symbols of FIRST(Y1) to FIRST(Y1 Y2 … Yk). If ε ∈ FIRST(Y1), add all the non-ε symbols of FIRST(Y2). If ε ∈ FIRST(Y1) and ε ∈ FIRST(Y2), add all the non-ε symbols of FIRST(Y3), and so on. Finally, add ε to FIRST(Y1 Y2 … Yk) if ε ∈ FIRST(Yi), for all 1 ≤ i ≤ k. Example: Consider the following grammar. E → E + T | T T → T * F | F F → (E) | idGrammar after removing left recursion: E → TX X → +TX | ε T → FY Y → *FY | ε F → (E) | id For the above grammar, following the above rules, the FIRST sets could be computed as follows: FIRST(E) = FIRST(T) = FIRST(F) = {(, id} FIRST(X) = {+, ε} FIRST(Y) = {*, ε} FOLLOW(A) for all non-terminals A Apply the following rules: If $ is the input end-marker, and S is the start symbol, $ ∈ FOLLOW(S). If there is a production, A → αBβ, then (FIRST(β) – ε) ⊆ FOLLOW(B). If there is a production, A → αB, or a production A → αBβ, where ε ∈ FIRST(β), then FOLLOW(A) ⊆ FOLLOW(B). Note that unlike the computation of FIRST sets for non-terminals, where the focus is on what a non-terminal generates, the computation of FOLLOW sets depends upon where the non-terminal appears on the RHS of a production. Example: For the above grammar, the FOLLOW sets can be computed by applying the above rules as follows. FOLLOW(E) = {$, )} FOLLOW(E) ⊆ FOLLOW(X) [in other words, FOLLOW(X)contains FOLLOW(E)] Since there is no other rule applicable to FOLLOW(X), FOLLOW(X) = {$, )} FOLLOW(T) ⊆ FOLLOW(Y) …. (1) (FIRST(X) – ε) ⊆ FOLLOW(T) i.e., {+} ⊆ FOLLOW(T) …. (2) Also, since ε ∈ FIRST(X), FOLLOW(E) ⊆ FOLLOW(T) i.e., {$, )} ⊆ FOLLOW(T) …. (3) Putting (2) and (3) together, we get: FOLLOW(T) = {$, ), +} Since, there is no other rule applying to FOLLOW(Y), from (1), we get:FOLLOW(Y) = {$, ), +} Since ε ∈ FIRST(Y), FOLLOW(T) ⊆ FOLLOW(F) and FOLLOW(Y) ⊆ FOLLOW(F). Also, (FIRST(Y) – ε) ⊆ FOLLOW(F). Putting all these together: FOLLOW(F) = FOLLOW(T) ∪ FOLLOW(Y) ∪ (FIRST(Y) – ε) = {$, ), +, *} first and follow examples first and follow in compiler design first and follow program in c first and follow ppt first and follow in compiler design ppt first and follow algorithm first and follow examples in compiler design pdf first and follow parsing first and follow examples in compiler design compute first and follow for the grammar first set follow set examples first and follow sets