Context-free grammar describing regular expressions?

Question

I'm trying to write a regular expression engine. I'd like to write a recursive descent parser by hand. What would a context-free grammar without left recursion for the language of regular expressions (not the languages that can be described by regular expressions) look like? Would it be easiest to re-factor out the syntactic sugar, i.e. change a+ to aa* ? Thanks in advance!

Answer 1

The wikipedia article on Left Recursion gives pretty good info on how to pull this off.

Answer 2

Left recursion:

Expression = Expression '|' Sequence
           | Sequence
           ;

Sequence = Sequence Repetition
         | <empty>
         ;

Right recursion:

Expression = Sequence '|' Expression
           | Sequence
           ;

Sequence = Repetition Sequence
         | <empty>
         ;

Ambiguous form:

Expression = Expression '|' Expression
           | Sequence
           ;

Sequence = Sequence Sequence
         | Repetition
         | <empty>
         ;