Build regular grammar from regular expression

Is there an algorithm for creating a regular grammar directly from a regular expression? All the discussions and notes I found so far go through an intermediary step of creating an FA for the reg ex and then the regular grammar from the FA. E.g., for a reg ex $a(b|c)*d$, what's the algorithm for figuring out the rewriting rules without first building the FA? I already built the grammar, but did so intuitively, I'd really like to see a generic algorithm that can be applied on any reg ex to build the grammar's productions.

Thanks

• Nvm, found it in a notebook. And my productions seem ok based on this alg :). – user3013202 Nov 20 '13 at 14:23

You can do it by combining grammars.

Notation:

$A,B,C,...$ will be non-terminals

$a,b,c,...$ will be terminals

$\alpha,\beta, ...$ will be "whatever can be here"

$x$ and $y$ will be regular expressions

The grammar corresponding to a regular expression $x$ will be denoted $f(x)=(N_x,\Sigma,P_x,S_x)$

$f(a)=(\{S\},\Sigma, \{S\to a\}, S)$

$f(x\mid y)=(N, \Sigma, P, S)$

$N=N_x\cup N_y \cup \{S\}$

$P=P_x\cup P_y\cup\{S\to \alpha \mid S_x\to \alpha\in P_x\}\cup\{S\to \alpha \mid S_y\to \alpha\in P_y\}$

The idea is that you want to be able to go one way or the other but if you add $S\to S_a$ and $S\to S_b$, then your grammar isn't regular anymore.

You could want to replace both $S_x$ and $S_y$ and their associated rules but if you do that, if the grammars use $S_x$ or $S_y$ somewhere on the right hand side, it might fail. For example if they represent $a^*$ and $b^*$ in such a way, then instead of $a^*\mid b^*$, your grammar would represent $(a\mid b)^*$ which isn't the same thing.

Here's the grammar for $a^*$:

$S\to \varepsilon$

$S\to aS$

$f(x\cdot y)=(N, \Sigma, P, S_x)$

$N=N_x\cup N_y$

$P=\{A\to bC\mid A\to bC\in P_x\} \cup \{A\to bS_y \mid A\to b \in P_x\}\cup \{A\to S_y \mid A\to \varepsilon \in P_x\} \cup P_y$

The idea is that since your grammar is regular, you'll always have a unique non-terminal until you finish your word with a rule not producing a non-terminal so you simply replace those rules in the first grammar by rules saying to continue on the second grammar.

$f(a*)=(N_a,\Sigma, P_a\cup \{A\to bS_a\mid A\to b\in P_a\}\cup \{A\to S_a\mid A\to \varepsilon\in P_a\}\cup \{S_a\to \varepsilon\}, S_a)$

$f(x^*)=(N_x,\Sigma, P, S_x)$

$P=P_x \cup \{A\to bS_x \mid A\to b \in P_x\}\cup \{A\to S_x \mid A\to \varepsilon \in P_x\}\cup \{S_x\to \varepsilon\}$

Same thing as above but you also take the rules giving simply the non-terminal or $\varepsilon$ to allow to end right away.

• Very good explanation. But for $f(a*)$, won't this break the definition of the regular grammar? I.e., a right lin grammar where, if $S \rightarrow \epsilon \in P$, then $S$ cannot appear in the right hand side of any production? – user3013202 Nov 20 '13 at 20:16
• $f(a*)=(N_a,\Sigma, P_a\cup \{A\to bS_a\mid A\to b\in P_a\}\cup \{A\to S_a\mid A\to \varepsilon\in P_a\}\cup \{S\to \varepsilon\}\cup \{S\to S_a\}, S)$ – xavierm02 Nov 20 '13 at 22:43
• And if $a$ and $b$ are primitive regexps, for $f(a+b)$ can't one also safely remove $N_a$ and $N_b$ from $N$? And in general, can't unneeded elements be removed from $N$, $P$ as the grammar definition advances from the primitive regexps to the complete regular expression? – user3013202 Nov 20 '13 at 22:47
• I don't think disallowing $A\to\varespilon$ when you have $B\to cA$ is useful. Since your grammar is regular, you'll always have at most one non-terminal... It's not like in general grammars where having $A\to\varespilon$ could make it really hard to "execute" because you could generate a lot of non-terminals for nothing. – xavierm02 Nov 21 '13 at 11:30
• I updated about $x\mid y$ and no, you can't remove them. – xavierm02 Nov 21 '13 at 11:31