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!
7
votes
3 Answers
7
votes
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>
;
2
votes
You could look at the source code for Plan 9 grep. The file grep.y has a yacc (LALR(1) if I recall correctly) grammar for regular expressions. You might be able to start from the yacc grammar, and rewrite it for recursive descent parsing.
0
votes
