7
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ 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)"? $\endgroup$ – Alex ten Brink Jan 20 '13 at 10:14
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, better than my answer. $\endgroup$ – Hendrik Jan Jan 21 '13 at 0:39
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Like a previous answer, I assume you want to get a grammar that generates the same language as the given regular expression $r$.

A recursive algorithm for constructing a context-free grammar $G$ with $L(G) = L(r)$ goes as follows:

  • if $r = \emptyset$, output a grammar with no production rules (or $S \to S$ if it must have a rule).
  • if $r = \Lambda$, output $S \to \Lambda$.
  • if $r = a$ (the expression is just a single letter), output $S \to a$.
  • if $r = a \cup b$ (union, also notated as + or |): construct disjoint grammars for $a$ and $b$ with start symbols $S_a$ and $S_b$, combine them and add $S \to S_a \mid S_b$.
  • if $r = lr$ (concatenation, also notated as $\cdot$): construct disjoint grammars for $l$ and $r$ with start symbols $S_l$ and $S_r$, combine them and add $S \to S_l S_r$.
  • if $r = x^*$ (Kleene star): construct a grammar for $x$ with start symbol $S_x$ and add $S \to S_x S \mid \Lambda$.

This is essentially equivalent to Hendrik's answer, but with more detail which may be useful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.