Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

migrated from cstheory.stackexchange.com Jan 20 '13 at 9:01

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

3  
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
add comment

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
Yes, better than my answer. –  Hendrik Jan Jan 21 '13 at 0:39
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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