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 | FF -> v.G | GG -> (E) | vwhich is not LL(1), since the production E -> EF is left recursive.However, eliminating left recursion from that production I obtain:E -> FEE-> FE | F -> v.G | GG -> (E) | vthat 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.
Removing left-recursion in grammar while maintaining left-association of operator
context free;formal grammars;compilers;parsers
Compatibility of left associativity and LL(1) parsingYou just hit one of the major inconsistencies in the use ofcontext-free (CF) syntax. People want to choose grammars so that theparse-tree will reflect the intended structure of the sentence,  close to its semantics, especially in the caseof non associative operators, such as application. This was pretty much the original intent of CF grammars in linguistics. But at the sametime they are constraining themselves to parsing technology that willtolerate only some types of grammars.Indeed, if the parse-tree is to reflect the left associativity of anoperator, then the grammar is necessarily left-recursive, since thetop application node in the parse-tree is necessarily adding therightmost term of non-parethesized successive applications.. So LLparsing is out of the question. You are right.There are two ways out of this. One is not to rely on the parser togive the rigth parse-tree to be used for later stages of processing(such as reducing the lambda expression, here). This lead to theconcept of Abstract Syntax Trees (AST) that can be built from theparse-tree, but with a different structure.The other solution is to use more general parsing Techniques that willaccept any CF grammar, and parse in accordance with it. General CFparsers is a well developed technology  (and I do not cease to wonderwhy LL remains so popular).I have no idea what could be considered a proper answer to thesecontradicting requirements.What I would do is show they are contradicting requirements. Give afirst grammar that meets the associativity and priority constraints,then transform the grammar into and LL(1) grammar for the parsing.The fact that something appeared in a journal or on an exam is not atotal garantee that it is correct.  And I might be wrong too ... but Idid some checking, in addition to my own knowledge of the issue.About this specific exampleThis being said, the first grammar you are suggesting does not seemquite correct. It does not have a way of producing u.v.v .One trick to know is to start with operators (here abstraction orapplication) with the lowest priority (abstraction). It is the same for arithmeticexpressions.