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 gramma
r?
(2) how do I manage to place particular symbols at specific locations in all
strings the grammar produces?
The
example is project "-gr.tryflags
3"
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.