The following is a grammar for regular expressions over symbols $a$ and $b$ only, using $+$ in place of $\mid$ for union, to avoid conflict with the use of vertical bar as a metasymbol in grammars:
- $rexpr\rightarrow rexpr+rterm\mid rterm$
- $rterm\rightarrow rterm\:rfactor\mid rfactor$
- $rfactor\rightarrow rfactor \:\ast\mid rprimary$
- $rprimary\rightarrow a\mid b$
- Left factor this grammar.
- Does left factoring make the grammar suitable for top-down parsing?
- In addition to left factoring, eliminate left recursion from the original grammar.
- Is the resulting grammar suitable for top-down parsing?