Flesh out the details of an algorithm to eliminate left recursion and common prefixes in an arbitrary context-free grammar. In some languages an assignment can appear in any context in which an...

Flesh out the details of an algorithm to eliminate left recursion and common

prefixes in an arbitrary context-free grammar.

In some languages an assignment can appear in any context in which an

expression is expected: the value of the expression is the right-hand side

of the assignment, which is placed into the left-hand side as a side effect.

Consider the following grammar fragment for such a language. Explain

why it is not LL(1), and discuss what might be done to make it so.

expr −→ id := expr

−→ term term tail

term tail −→ + term term tail |

term −→ factor factor tail

factor tail −→ * factor factor tail |

factor −→ ( expr ) | id