Download LPFG user`s manual - Algorithmic Botany

Transcript
4 Appendix: How productions are matched
When rewriting the string it is necessary to determine which production must be
applied to each module in the string. The process of determining the applicable
production is called production matching. For every module in the string, productions are
checked for matching. The productions are checked in the order in which they are
specified in the L-system.
For a production to match, all three components of the predecessor (left context, strict
predecessor and right context) must match. The rules for matching each of these
components are different. This is because the L-system string is a means of representing
branching structures and symmetric operations on the string do not (in general)
correspond to symmetric operations on the branching structure.
This section contains a detailed explanation of rules that control the process of
production matching. The notation used here utilizes symbols [ and ] to denote beginning
of branch and end of branch (modules SB and EB in lpfg).
When the strict predecessor is compared with the contents of the string in the current
position in order for it to match the modules in the strict predecessor have to match
exactly the modules in the string.
When matching the right context and a module in the context is not the same as
module in the string the following rules apply:
•
If a module in the string is [ and the module expected is not [ then the branch is
skipped. This rule reflects the fact that modules may be topologically adjacent,
even though in the string representation of the structure the two modules may be
separated by modules representing the lateral branch B (see Figure 2).
•
When a branch in the right context ends (with a right bracket) then the rest of the
branch in the string is ignored by skipping to the first unmatched ]. This rule also
reflects the topology of the branching structure, not its string representation. For
example in Figure 3, module C is closer to A than D.
•
If multiple lateral branches start at a given branching point, then the predecessor
in Figure 3 would check the first branch (see Figure 4). To skip a branch it is
necessary to specify explicitly which branch at the branching point should be
40