# Regular Expression to Context-Free Grammar

Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?

-

## migrated from cstheory.stackexchange.comJan 20 '13 at 9:01

This question came from our site for theoretical computer scientists and researchers in related fields.

Do you want the CFG that generates the valid regular expression strings like "a*(a|b)", or do you want the CFG that generates strings like "aaaaab" given the regular expression "a*(a|b)"? –  Alex ten Brink Jan 20 '13 at 10:14

I assume you want to get a grammar that generates the same language as the given regular expression.

You can achieve that by the following steps:

1. Translate the regular expression into an NFA.
2. Translate the NFA into a (right-)regular grammar.

Both translations are standard and covered in basic textbooks on formal languages and automata. Note that any regular grammar is also context-free.

-
Yes, better than my answer. –  Hendrik Jan Jan 21 '13 at 0:39

Yes. I give the high-level answer, without many details.

First you have to parse the expressions. That can be done using a simple recursive decent parser. Several examples on the web.

Then you should add "semantic" rules to the parser, when returning from the recursion. Those are standard in any formal language theory course. If $S_1$ and $S_2$ are non-terminals that generate expressions $E_1$ and $E_2$ then we can generate $E_1+E_2$ by $S$ and the rules $S\to S_1$, $S\to S_2$. We can generate concatenation $E_1 E_2$ by $S$ and the rule $S\to S_1 S_2$. $E_1*$ by $S$ and the rules $S\to S_1 S$, $S\to \lambda$. Assuming we choose fresh nonterminals each time.

-