23 votes 23 votes Translate the arithmetic expression $a^\ast -(b+c)$ into syntax tree. A grammar is said to have cycles if it is the case that $A \overset{+}{\Rightarrow} A$ Show that no grammar that has cycles can be $\text{LL(1)}.$ Compiler Design gate1995 compiler-design grammar normal descriptive + – Kathleen asked Oct 8, 2014 • recategorized Apr 25, 2021 by Lakshman Bhaiya Kathleen 6.7k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Shubhm commented Dec 17, 2019 reply Follow Share cycle means infinite loop infinite loop due to left recursion left recursion is not allowed in LL(1) Thus no grammar that has cycle is LL(1) 1 votes 1 votes smsubham commented Dec 25, 2019 i edited by smsubham Dec 25, 2019 reply Follow Share A context-free grammar is cyclic if there exists a non-terminal A and a derivation in one or more steps A⟹+ A. It is left-recursive if there exists a non-terminal A, a mixed sequence of terminals and non-terminals γ, and a derivation in one or more steps A⇒+ Aγ. Hence cyclic implies left-recursive, but the converse does not hold. https://cstheory.stackexchange.com/questions/18609/difference-between-a-cyclic-and-a-left-recursive-context-free-grammar 1 votes 1 votes Please log in or register to add a comment.
15 votes 15 votes A grammer having left recursion generates a cycle. And no left recursive grammer is LL(1) grammer. simran answered Dec 23, 2014 simran comment Share Follow See all 19 Comments See all 19 19 Comments reply Akash Kanase commented Dec 31, 2015 reply Follow Share A=> +A I don't see left recursion here ! 2 votes 2 votes abhilashpanicker29 commented Jan 14, 2016 reply Follow Share the + is misplaced, it should be over the arrow.. for extended transition.. 8 votes 8 votes Tanushree commented Sep 19, 2016 reply Follow Share How will we make syntax tree of a part? 0 votes 0 votes Sachin Mittal 1 commented Jan 9, 2017 reply Follow Share this is $A \stackrel{+}{\Longrightarrow} A$ ? 3 votes 3 votes Ahwan commented May 23, 2017 reply Follow Share "And no left recursive grammer is LL(1) grammer." I guess this line needs editing, it should be "can be" instead of "is". 1 votes 1 votes Tuhin Dutta commented Aug 24, 2017 reply Follow Share "And no left recursive grammer is LL(1) grammer." - i think it means no grammar which is left recursive can be LL grammar which is what you have written. you might have read it not properly and interpreted wrongly 1 votes 1 votes Ayush Upadhyaya commented Oct 14, 2017 reply Follow Share Please verify if this syntax tree is correct. 0 votes 0 votes rahul sharma 5 commented Oct 15, 2017 reply Follow Share Why there is 0 to - operator? Left of - should be * node? 0 votes 0 votes rahul sharma 5 commented Oct 15, 2017 reply Follow Share If i read inorder of your expression tree it does not give me same expression back 0 votes 0 votes Ayush Upadhyaya commented Oct 15, 2017 reply Follow Share how would -(b+c) would be evaluated in that case? 0 votes 0 votes A_i_$_h commented Dec 23, 2017 reply Follow Share from that minus node , the node to the left must be * and again one node to its left will have node a now will it be right 0 votes 0 votes Puja Mishra commented Dec 27, 2017 i edited by Puja Mishra Dec 27, 2017 reply Follow Share This might be the tree .. 28 votes 28 votes rahul sharma 5 commented Jan 23, 2018 reply Follow Share @ Ayush From the questions it seems as * is unary operator applied to a.I will go with @Puja Mishra tree given above assuming that the * is not misplaced in the question. 3 votes 3 votes mehul vaidya commented Sep 18, 2018 reply Follow Share @Rahul I also think puja's answer is correct 0 votes 0 votes Ayush Upadhyaya commented Nov 6, 2018 reply Follow Share Yes pooja's answer is correct. Please ignore my tree. 1 votes 1 votes jatin khachane 1 commented Nov 13, 2018 i reshown by jatin khachane 1 Nov 13, 2018 reply Follow Share Does Cycle => Left recursion always ?? What if Cycle is generating due to Right recursion.. So for such grammar there will be cycle ..still LL(1) ? A->aB B->bA 3 votes 3 votes tusharp commented Nov 24, 2018 reply Follow Share @Ayush Upadhyaya what is the meaning of extended transition?? Does that mean if any non terminal to the RHS of A is replaced by its value then it will be left recursive? I mean A => B b B => Ac which is indirectly A=> Acb 1 votes 1 votes anchitjindal07 commented Dec 19, 2018 reply Follow Share How to draw tree? * is binary operator (multiplication), but only single operand is given. IS this wrong 0 votes 0 votes Surya Pratap Singh S commented Dec 17, 2019 reply Follow Share grammar has cycle means? 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes $a^∗−(b+c)$ We have the infix (inorder) expression. This will be the equivalent postfix: $a^∗(bc+)-$ You have infix, you have postfix, now make the tree. Cycle => Loop => Usage of Left Recursive Grammar. So, can't be LL(1) JashanArora answered Dec 21, 2019 JashanArora comment Share Follow See all 3 Comments See all 3 3 Comments reply neel19 commented Sep 3, 2021 reply Follow Share Why does loop imply Left Recursive Grammar? It could Right recursive too, I guess. 0 votes 0 votes ankit3009 commented Nov 3, 2021 reply Follow Share @neel do let me know if your doubt gets cleared, I am having same doubt. 0 votes 0 votes Pranavpurkar commented Nov 21, 2022 reply Follow Share same doubt! 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes A. Convert $a^∗−(b+c)$ How to check if the syntax tree is correct? Find inorder traversal of the tree it should give above expression. (infix expression) Image source: Answer below. B. A context-free grammar is cyclic if there exists a non-terminal A and a derivation in one or more steps A⟹+ A. It is left-recursive if there exists a non-terminal A, a mixed sequence of terminals and non-terminals γ, and a derivation in one or more steps A⇒+ Aγ. Hence cyclic implies left-recursive, but the converse does not hold. left recusion grammar cannot be LL(1). Ref: https://cstheory.stackexchange.com/questions/18609/difference-between-a-cyclic-and-a-left-recursive-context-free-grammar smsubham answered Dec 25, 2019 smsubham comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes The tree will be * / \ a - / \ b + / \ c ε rajveer43 answered Dec 29, 2023 rajveer43 comment Share Follow See all 0 reply Please log in or register to add a comment.