0 votes 0 votes S->AaAb|Bb A->ε B->ε how can this grammar be left factored grammar? Compiler Design compiler-design parsing left-recursion descriptive + – Sanket_ asked Nov 17, 2016 retagged Jun 23, 2022 by Lakshman Bhaiya Sanket_ 3.2k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments papesh commented Nov 17, 2016 reply Follow Share Easy way do find is : First (AaAb) $\bigcap$ First(Bb) = phi than it is left factored... 2 votes 2 votes Sanket_ commented Nov 17, 2016 reply Follow Share @Gabbar Can you explain your formula with the statement i said and why my approach is wrong. 0 votes 0 votes Shiva Sagar Rao commented Feb 3, 2021 reply Follow Share Left Factoring: If two rules for a non-terminal have right-hand sides that begin with the same symbol, we can’t predict which one to use. Solution: Factor the common prefix into a separate production. Example: Original grammar: ifStmt ::= if ( expr ) stmt | if ( expr ) stmt else stmt Factored grammar: ifStmt ::= if ( expr ) stmt ifTail ifTail ::= else stmt | $\epsilon$ Source: https://courses.cs.washington.edu/courses/cse413/08au/lectures/llparsing.pdf#page=23 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes left factoring is use to remove non determinism....means for a given input string if we cant decide on seeing a symbol which production to use... A non deterministic grammar is of the form A->aB/abC(example)...here on seeing 'a' we cant decide whether to use aB or abC now coming to the question...it is already left factored....we dont have to make any decision on seeing an input symbol... final conclusion:-NO need to do any left factoring....given grammar is already non deterministic.... sudsho answered Nov 18, 2016 edited Dec 11, 2016 by sudsho sudsho comment Share Follow See all 3 Comments See all 3 3 Comments reply Sanket_ commented Nov 18, 2016 reply Follow Share it is not ambiguous for ambiguity more than 1 parse tree is required here only 1 parse tree will be created 0 votes 0 votes sudsho commented Nov 18, 2016 reply Follow Share yea i just wanted to differentiate between both 0 votes 0 votes meghna commented Sep 19, 2018 reply Follow Share so can i say non determinism implies unambiguity? What if its bi-implication? 0 votes 0 votes Please log in or register to add a comment.