2 votes 2 votes Can we find FIRST and FOLLOW for a left recursive grammar? Compiler Design compiler-design left-recursion first-and-follow + – Vivek Jain asked Aug 19, 2017 Vivek Jain 767 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply stblue commented Aug 20, 2017 reply Follow Share Refer : https://gateoverflow.in/143993/can-anyone-calculate-first-follow-this-question-incorrect#c144045 1 votes 1 votes G Shaheena commented Aug 23, 2017 reply Follow Share We can find first and follow for left recursive grammer Example: E$\rightarrow$E+T/T T$\rightarrow$T*F/F F$\rightarrow$(E)/id initialize first(x) to the empty set for every non-terminal x. for every epsilon production of the form X$\rightarrow$$\epsilon$, add epsilon to first(x) for every non epsilon productions of the form X$\rightarrow$a$\beta$ where a is a terminal. Add a to the first(x) algorithm is; repeat let x$\rightarrow$y1,y2........yk be a non-terminal production for i=1 to k if yi is a terminal then break add every non terminal from first(yi) to first(x) if $\epsilon$not belongs to first(yi) then break end for until no more non terminals can be added to any set for above examle productions are: E$\rightarrow$E+T E$\rightarrow$T T$\rightarrow$T*F T$\rightarrow$F F$\rightarrow$(E) F$\rightarrow$id there are no epsilon productions in this grammer. And there are 2 productions whose R.H.S begins with terminal. so before loop FIRST(E) = {} FIRST(T) = {} FIRST(F) = { (, id } T → F implies that we should add FIRST(F) to FIRST(T) now, FIRST(E) = {} FIRST(T) = { (, id } FIRST(T) = { (, id } FIRST(F) = { (, id } going through every production no more non terminals added to any of these sets 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) = { $, +, *, ) } 1 votes 1 votes Mayank0343 commented Jan 24, 2020 reply Follow Share shouldn't first(E) also contain ( and $ as first of E = first of T 0 votes 0 votes Please log in or register to add a comment.