28 views

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$
1. Left factor this grammar.
2. Does left factoring make the grammar suitable for top-down parsing?
3. In addition to left factoring, eliminate left recursion from the original grammar.
4. Is the resulting grammar suitable for top-down parsing?
| 28 views