Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Context-free grammar describing regular expressions?

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!

like image 715
wkf Avatar asked Jun 10 '09 20:06

wkf


1 Answers

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>
         ;
like image 184
Markus Jarderot Avatar answered Nov 15 '22 08:11

Markus Jarderot