0 votes 0 votes Compiler Design compiler-design parsing ace-test-series + – Dheeraj Pant asked Nov 16, 2018 edited Mar 3, 2019 by I_am_winner Dheeraj Pant 2.6k views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Shreya kumari commented Nov 17, 2018 reply Follow Share Is correct answer is b and d. 0 votes 0 votes Dheeraj Pant commented Nov 17, 2018 reply Follow Share ACCORDING TO ACE ANSWER IS D 0 votes 0 votes Shivam Kasat commented Nov 17, 2018 reply Follow Share Left factoring is removing the common left factor that appears in two productions of the same non-terminal. It is done to avoid back-tracing by the parser. Suppose the parser has a look-ahead ,consider this example- A -> qB | qC where A,B,C are non-terminals and q is a sentence. In this case, the parser will be confused as to which of the two productions to choose and it might have to back-trace. After left factoring, the grammar is converted to- A -> qD D -> B | C This is what left factoring. Then how can D be the answer? 0 votes 0 votes Dheeraj Pant commented Nov 17, 2018 reply Follow Share Actually yes you r right. But is { S->A | B A--> aaaac B--> aaaab} left factored ?? 0 votes 0 votes Shivam Kasat commented Nov 17, 2018 reply Follow Share yes this one is left factored! 0 votes 0 votes Dheeraj Pant commented Nov 17, 2018 reply Follow Share But how can u say that there will be no backtracking in this. Say string is aaaab ; now from S we doesn't have any hint whether to go towards A or towards B. Now if we go through A then we will surely need to backtrack. Do you agree?? 0 votes 0 votes Shivam Kasat commented Nov 17, 2018 reply Follow Share yes I agree 0 votes 0 votes Dheeraj Pant commented Nov 17, 2018 reply Follow Share Then how is it left factored , because there is no determinism. 0 votes 0 votes Dheeraj Pant commented Nov 17, 2018 reply Follow Share Actually this is my reasoning , i doesn't know the exact answer so please correct me if i am wrong... 0 votes 0 votes Dheeraj Pant commented Nov 17, 2018 reply Follow Share Left factored version for { S->A | B A--> aaaac B--> aaaab} should be {S->aaaaB B->c|b } 0 votes 0 votes Shivam Kasat commented Nov 17, 2018 reply Follow Share why isn't A left factored? 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes Answer is D. First (AB) ⋂ First(ef) = phi then it is left factored... Aakash_ answered Nov 21, 2018 Aakash_ comment Share Follow See all 2 Comments See all 2 2 Comments reply Dheeraj Pant commented Nov 21, 2018 reply Follow Share @Aakash_ please tell correct answer for below question also : https://gateoverflow.in/262707/compiler-design-doubt#c262791 0 votes 0 votes Ashish Lakhmani commented Jul 22, 2019 reply Follow Share @Aakash_ Why are you using this approach? Intersection of FIRST of productions can also be !=phi when there is Left Recursion. In option B.) S -> Sa / b FIRST(Sa) ⋂ FIRST(b) != phi because of the presence of Left Recursion & I think you are assuming it's because of Non-Determinism. 0 votes 0 votes Please log in or register to add a comment.