11. Programmed
grammars
When
a generative grammar is used to derive a string, rule order is intrinsically
predetermined by the availability of variables in the string under derivation.
This process is generally non-deterministic because there may be several
candidate rules. The idea of a
programmed
grammar,
as suggested by Laske (1973a:365), is to impose an extrinsic ordering of rules
reflecting a certain manner in which the generation process is envisaged by the
composer. Alternate methods involve
production
procedures
(see reference manual §8.1).
11.1 Using
flags
Programmed
grammars in BP2 use
flags
taking integer values. Suppose we need to generate random variations of length
6 containing 'a' and 'b', yet with exactly four occurrences of 'a' and two of
'b'. We may write (see "-gr.tryflags"):
RND
GRAM#1[1]
S
--> X
X X X X X /flag1 = 4/ /flag2 = 2/
GRAM#1[2]
/flag1 -1/ X
--> a
GRAM#1[3]
/flag2 -1/ X
--> b
The
first rule generates "X X X X X X" and six flags. More precisely, "flag1" is
set to integer value 4 whereas "flag2" is set to 2.
These
are used as conditions for the application of rules [2] and [3]: a rule may be
applied only if the values of all its condition flags
are
strictly
positive
.
In addition, each time rule [2] (or [3]) is applied, "flag1" (or "flag2") is
decremented by one unit.
Productions
look like:
a
a a a b b, b a a a b a, b a a a b a, a a b a b a, a b a b a a, b a b a a a, a b
a a a b...
Another
example: generate a string of length 10 on alphabet {a,b,c} in which 'b' and
'c' have equal numbers of occurrences (±1). The following grammar
("-gr.tryflags2")
will do it:
[1]
S --> X
X X X X X X X X X /make_b = 1/
[2]
/make_b -1/ X
--> b
/make_c +1/
[3]
/make_c -1/ X
--> c
/make_b +1/
[4]
X --> a
This
grammar produces:
c
a b b b c c a a a, a b a a b a a c c b, b a b c a b b c c a, c a b a a a b a a
c...
We
recommend reading about
production
procedures
(reference manual §8.1) that solve equivalent problems.
11.2 New
flag syntax
From
version 2.5 onward it is possible to write flag conditions as per the following
examples:
/flag1
- 3/ X
--> a [means
that /flag1/ is to be decremented by three units]
/flag1
+ 4/ X
--> a [means
that /flag1/ is to be incremented by four units]
The
second rule is therefore increasing flags values. It could be equivalently
written:
/flag1/
X
--> a /flag1
+ 4/
Many
other new features on flags have been implemented in version 2.5. Here is a
brief survey of
flag
conditions
taken from the on-line help under "Flags":
/myflag
= 3/ X --> a checks that 'myflag' is equal to 3, and if so, makes the rule
candidate.
/myflag
≠ 3/ X --> a checks that 'myflag' is unequal to 3, and if so, makes
the rule candidate.
/myflag
< 3/ X --> a checks that 'myflag' is smaller than 3, and if so, makes
the rule candidate.
/myflag
> 3/ X --> a checks that 'myflag' is greater than 3, and if so, makes
the rule candidate.
/myflag
≤ 3/ X --> a checks that 'myflag' is smaller or equal to 3, and if
so, makes the rule candidate.
/myflag
≥ 3/ X --> a checks that 'myflag' is greater or equal to 3, and if
so, makes the rule candidate.
Be
careful that '=' is the
assignment
operator
if found in the right argument of a rule, and a
comparison
operator otherwise. To get '≤' (inferior or equal) on a US keyboard,
type option comma, and to get '≥' (superior or equal) type option period.
A
rule may now contain several flag conditions, e.g.:
/myflag
≥ 3/ /myflag < 20/ /otherflag = 4/ X --> a
In
assignments and comparisons, numbers may be replaced with other flags or
control parameters K1, K2, etc., e.g.:
X
--> a
/flag1 = K1/ /flag2 = flag1/
/flag1
> K19/ X
--> b
/flag2
≠ flag3/ X
--> c
Be
careful that all flags are set to zero when computation starts, unless the
project is running in "Improvize" mode and "Reset rule flags" is
not
checked on dialog "Settings". In the latter case, flags keep the values they
have acquired during the preceding computation.
11.3 Classical
problems solved with flags
We
now take an example showing that the new flag syntax provides elegant and
comprehensive solutions to problems often encountered when dealing with formal
grammars: (1) how do I control the global length of strings produced by a
self-imbedding grammar?
(2) how do I manage to place particular symbols at specific locations in all
strings the grammar produces?
The
example is project "-gr.tryflags3"
and deserves comments.
// This grammar produces all strings of length 8 containing a's and b's, and
c's in positions 4 and 6. Every string contains at least two a's.
RND
[1]
S
-->
X /pos = 1/ /done = 0/
[2]
X
-->
a X /pos +1/ /done +1/
[3]
X
-->
b X /pos +1/
[4]
<∞> /pos > 8/ X
-->
lambda [Infinite weight]
[5]
<∞> /pos ≥ 7/ /done < 2/ X
-->
a X /pos +1/ /done +1/ [Infinite weight]
[6]
<∞> /pos = 4/ X
-->
c X /pos +1/ [Infinite weight]
[7]
<∞> /pos = 6/ X
-->
c X /pos +1/ [Infinite weight]
Rules
[2],[3],[5],[6],[7] are
self-imbedding,
i.e. their left arguments are substrings of their right arguments.
Consequently, should these rules remain candidate forever, the length of the
work string would grow infinitely. So far, the only techniques to limitate the
growth of the work string were dynamic weights (see §4.6 of reference
manual) or limited buffer size (§4.7). The inconvenient of dynamic
weights is that they make it difficult to control the probabilities of each
candidate rule. Flags provide an independent (and numerical) control of
derivations.
In
the above example, flag 'pos' measures the length of the work string, which may
not exceed 8 units. Rule [4] becomes compulsory (its weight being infinite) as
soon as the flag condition pos > 8 is fulfilled.
Flag
'done' controls the number of occurrences of 'a', which must be minimum 2 in
the final item. Rule [5] takes care of that condition: if less than 2 a's have
been produced when the length is greater than 6, then this rule becomes
compulsory and produces the missing terminals.
Rules
[6] and [7] take care of the compulsion to place occurrences of 'c' in
positions 4 and 6.
