0 votes 0 votes S-> SS | Aa A->Sb | a (a) prove that the grammar is ambiguous. (b) find the follow for the grammar (c) then remove the left recursion from the grammar. Compiler Design left-recursion + – Sara Wageh asked Dec 31, 2021 Sara Wageh 1.1k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply AngshukN commented Dec 31, 2021 reply Follow Share The grammar is ambigous since two different parse trees yield $a^{6}$ S → SS → SSAa → AaAaAa → $a^{6}$ also S → SS → AaSS → AaAaAa → $a^{6}$ . I am not sure if this might remove the ambiguity. Can anyone confirm or reject and if reject can you please explain also. Thanks S → F1F2 F1 → Aa F2 → F1F2 | Aa A → Sb | a 0 votes 0 votes Zack Fair commented Jan 2, 2022 reply Follow Share @AngshukN You removed the sting $aa$ from language. To make grammar unambiguous : Your solution could work though, just a little change in $F_2$, $S → F_1F_2$ $F_1 → Aa$ $F_2 → F_1F_2 |ϵ$ $A → Sb | a$ Also it doesn’t need extra Non Terminals, It would look cleaner that way. $S → AaS |Aa$ $A → Sb | a$ 1 votes 1 votes AngshukN commented Jan 2, 2022 reply Follow Share @Zack Fair Your solution is correct. 0 votes 0 votes Zack Fair commented Jan 2, 2022 reply Follow Share @Sara WagehYou don't need to remove left recursion in order to find the follow. ( We sometimes feel like it would loop forever but ... )whenever we encounter a trivial condition we don't explore it again, like production which says $First(NT)$ should contain $First(NT)$ we don't trace the same path which implied above condition. Because obviously $First(NT)$ $\epsilon$ $First(NT)$ Here is an attempt to explain what I meant :the grammar is :$S \rightarrow SS | Aa$$A \rightarrow Sb | a$ $Follow(S)$ contains $\$$From $2^{nd}$ $S$ in $S\rightarrow SS$ we have $Follow(S)$ contains $Follow(S)$ . . . (trivial)From $1^{st}$ $S$ in $S\rightarrow SS$ we have$Follow(S)$ contains $First(S)$ . . . ($1$)From $S\rightarrow Aa$ we have$First(S)$ contains $First(A)$$\therefore Follow(S)$ contains $First(A)$From $A\rightarrow Sb$ we have $First(A)$ contains $First(S)$$\therefore Follow(S)$ contains $First(S)$ . . . ($2$)Since we already covered condition ($2$) in condition ($1$) now it becomes trivial and we do not explore it further.From $A\rightarrow a$ we have $First(A)$ contains $a$$\therefore Follow(S)$ contains $a$From $A\rightarrow Sb$ we have $Follow(S)$ contains $b$$\therefore Follow(S)=${$\$,a,b$}From $S\rightarrow Aa$ we have $Follow(A)$ contains $a$$\therefore Follow(A)=${$a$}Tip : We do not care about $N\rightarrow N\beta$, ($N$ is any non terminal) while finding $First(N)$ ......Unless $N\rightarrow$ $\epsilon$, in which case we would substitute $\epsilon$ at place of $N$ and find $First(\beta)$ 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes (c) then remove the left recursion from the grammar. After removing the left recursion the grammar is as below :- S→ aaX X→ SX / baX / epsilon Patel Arya answered Jun 19, 2023 Patel Arya comment Share Follow See all 0 reply Please log in or register to add a comment.