Regular Expression to Context-Free Grammar

Question

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

Answer 1

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.

Answer 2

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.