What is the most simple, elegant way of implementing a rewrite-system defined as:
$$ \begin{aligned} \Sigma &= \{a_1, a_2, a_3, ...\} \\ N &= \{A_1, A_2, A_3, ...\} \\ \{\alpha_1 , \alpha_2, \alpha_3, ...\} &= \Sigma \bigcup N \\ F &= \{f_1, f_2, f_3, ... \} \\ P &= \left\{ \begin{aligned} A &\rightarrow a \\ A &\rightarrow \alpha \\ A &\rightarrow \alpha_1 | \alpha_2| \alpha_3 | ... \\ A &\rightarrow f(\alpha_1, \alpha_2, \alpha_3, ...) \\ \end{aligned} \right\} \end{aligned} $$
That is: given a set of terminal symbols $\Sigma$, a set of nonterminal symbols $N$, a set of functions $F$ and a set of rewrite rules $P$, starting from an arbitrary but well-formed sentence $S$ of the grammar $G = (\Sigma, N, F, P, S)$, the system should apply the rewrite rules until all non-terminals are resolved, producing sentences like:
$$ f_1(a_3, a_1, f_2(a_4, a_1), a_1, f_3(a_2, f_1(a_1), a_4)) $$
UPDATE: Specification
- terminal and nonterminal symbols can be e.g. strings;
only symbols of $\Sigma$ and $N$ are replaced, functions of $F$ are left intact, though symbols inside them are to be replaced. Therefore
g["A"]in the initial sentence below is to be replaced, e.g.:g["A"]--applying-7th-rule-->g["B" ~~ "b"];- some functions should evaluate immediately to result in a (non)terminal symbol (
|= random choice,..= repeate 1 or more times,...= repeate 0 or more times); - all $f_i$ should be held until termination;
- rules should be applied randomly: any that fits could be chosen for a certain replacement.
At present, I am struggling with recursively applying structural replacements in held rules, and it's becoming more and more complex and convoluted. There must be a simpler way, concerning Mathematica is by design a very effective rewrite system. Though I have no idea how to start to exploit e.g. regular expressions.
UPDATE: Example
An example follows (note that I used StringExpression, but it can be replaced with List, or similar):
terminals = {"a", "b", "c", "d", "e", "f", "g", "h"};
nonTerminals = {"A", "B", "C", "D"};
functions = {f, g, h, i};
initSentence = g["A"] ... ~~ "B"; (* ... indicates zero or more g["A"] *)
rules = {
"A" :> "a",
"B" :> "b" | "c" | "d", (* immediately choose any terminal of the rhs *)
"C" :> "e" | "f",
"D" :> "g" | "h",
"A" :> "a" ~~ "b",
"A" :> "A" ~~ "a",
"A" :> "B" ~~ "b",
"A" :> f["e" | "f"] ~~ "a", (* do not evaluate f but choose "e" or "f" *)
"A" :> g@"h" ~~ "C",
"B" :> g@"C", (* do not evaluate g but "C" must be replaced later *)
"B" :> "B" ~~ h@"e",
"C" :> f@"f",
"C" :> "C" ~~ g@"d"
};
Starting from initSentence one possible process with a valid outcome would be:
g["A"] ... ~~ "B" (* initial sentence *)
g["A"] g["A"] ~~ "B" (* g["A"] is repeated randomly *)
g["A" ~~ "a"] g["A"] ~~ "B" (* rule A ":>"A "~~"a " is applied *)
g["A" ~~ "a"] g[g@"C"] ~~ "B" (* rule "B" :> g@"C" is applied *)
g["a" ~~ "a"] g[g@"C"] ~~ "B" (* rule "A" :> "a" is applied *)
g["a" ~~ "a"] g[g@f@"f"] ~~ "B" (* rule "C" :> f@"f" is applied *)
g["a" ~~ "a"] g[g@f@"f"] ~~ "b" | "c" | "d" (* rule "B":>"b"|"c"|"d" is applied *)
g["a" ~~ "a"] g[g@f@"f"] ~~ "d" (* one terminal is randomly chosen *)
(* terminate and evaluate g, f *)
The point is that the grammar is represented as a set of rules that are both probabilistic (e.g. random choices) and are applied in a random way, i.e. for each symbol (at each step), a random fitting rule should be applied.
SymbolicC`in the Mathematica distribution, particularly functionGenerateCode, which generates a string of C code (more or less a sequence of terminal tokens, although they are not separately generated and the joined, but rather joined on the fly), from the Symbolic C representation, which is, in fact, a form of a parse tree for C code. Of course, C grammar is more complex than regular grammars, so this may be an overkill for your purposes. $\endgroup$/.and//.with someRules, but that does not solve the problem completely. Can you give a simple example where/.doesn't do what you need? I guess the key is in "What is of importance here is that the some functions (e.g. |, cf. Alternatives) should evaluate immediately to result in a (non)terminal symbol, while some fi should be held until termination." but I do not completely understand what you mean by that, and I also don't understand where held expressions come in when you useReplace(All)(asHoldAlldoesn't affect replacements) $\endgroup$initSentencestill does not look to be a legal sentence obtained from the grammar, since there is no production to getg["A"]. $\endgroup$