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
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.