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 Show 16 previous comments 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.