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