I have a problem with this exercise:
Let G be the following ambiguous grammar for the λ-calculus:
E → v | λv.E | EE | (E)
where E is the single non-terminal symbol, λv.E represents abstraction w.r.t. the variable v in E, and EE represents application.
- Define an LL(1) grammar G′ such that L(G′) = L(G) and the ambiguity of G is resolved by imposing the following usual conventions:
- abstraction is right associative;
- application is left associative;
- application has higher priority than abstraction.
- Show the LL(1) parsing table for G′ and the parse tree obtained when parsing the string
λv1. λv2. v1v2v1.
I eliminated ambiguity setting precedence and association, obtaining this grammar:
E -> EF | F F -> λv.G | G G -> (E) | v
which is not LL(1), since the production
E -> EF is left recursive.
However, eliminating left recursion from that production I obtain:
E -> FE¹ E¹-> FE¹ | ɛ F -> λv.G | G G -> (E) | v
that does not comply with requirement 1.2.
I looked for a solution on the Internet, but it seems like it is not possible to eliminate left-recursion preserving left associativity.
However, this exercise appeared on the compilers exam some years ago, so there must be a correct answer.
Thank you for your help.