Generation of strings from a grammar

Balanced strings of left and right parentheses may be generated using the grammar For instance, there are 5 strings with 3 pairs of parentheses: ((())), (())(), ()(()), (()()), ()()(). The procedure below, by Don Taylor, generates balanced strings from the grammar. The probability of (S)S being chosen rather than eps has been set to 0.3.

> produce := procedure();
>     seq := ["S"];
>     rhs := ["(", "S", ")", "S"];
>     i := 1;
>     repeat
>         if Random(1, 10) gt 7 then
>             Insert(~seq, i, i, rhs);
>         else
>             Remove(~seq, i);
>         end if;
>         print #seq gt 0 select &*seq else "eps";
>         i := Position(seq, "S");
>     until i eq 0;
>     print "Length:", #seq;
> end procedure;
>
> produce();
(S)S
()S
()(S)S
()((S)S)S
()(()S)S
()(())S
()(())(S)S
()(())()S
()(())()
Length: 8
> produce();
eps
Length: 0
> produce();
(S)S
((S)S)S
(()S)S
(())S
(())
Length: 4

Previous Group: Partitions of a set