1 votes 1 votes Rewrite the following SDT: $A\rightarrow A\{a\}B\mid AB\{b\}\mid 0$ $B\rightarrow B\{c\}A\mid BA\{d\}\mid 1$ so that the underlying grammar becomes non-left-recursive. Here, $a, b, c$, and $d$ are actions, and $0$ and $1$ are terminals. Compiler Design ullman compiler-design syntax-directed-translation grammar descriptive + – admin asked Sep 6, 2019 admin 762 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Let {a} = M1, {b} = M2, {c} = M3 and {d} = M4 A → 0A` A`→ M1 B A` / B M2 A` / ε B → 1B` B` → M3 A B` / A M4 B` / ε M1 → ε {a} M2 → ε {b} M3 → ε {c} M4 → ε {d} This way it has no left recursion and also it is now a postfix SDT Rexus answered May 8, 2020 Rexus comment Share Follow See all 2 Comments See all 2 2 Comments reply Hradesh patel commented May 10, 2020 reply Follow Share Why u including in final statement M1 ,M2,M3,M4 is €. U intinally let {a} = M1 .....so on 0 votes 0 votes Rexus commented May 10, 2020 reply Follow Share That step is to make SDT S-Attributed. You can omit that step to get the desired answer also. Left recursion can still be removed without doing that step. 0 votes 0 votes Please log in or register to add a comment.