Left recursion elimination

Examined at 8 marks, and the exam’s own expression grammar is the opening preset. Immediate recursion A → Aα | β becomes A → βA′ with A′ → αA′ | ε; indirect recursion is handled by substituting earlier variables out first, one variable per step.

Grammar — one variable per line, alternatives with |, ε for the empty production

Presets:

Symbols split per character (aSb is a, S, b) unless any alternative contains spaces — then tokens are space-separated and id stays one terminal. Variables are whatever appears left of an arrow.

3 variables {E, T, F}, 5 terminals {+, *, (, ), id}, start E — 6 productions.

The order trap

Left recursion elimination introduces ε-productions — every new primed variable gets one. The grammar-simplification pipeline (arriving with Module 4's tools) removes ε-productions, and the two transformations are taught in different modules, so it is easy to run them in the wrong order: ε-removal first would hand this algorithm input it refuses. Eliminate left recursion first, clean up ε afterwards.