In what sense is a CFDG grammar a context free grammar?
CFDG is described as a language for context free grammars which can generate images. It allows rules to have parameters, but places restrictions on them to ensure the grammar is context free rather than an indexed grammar.
In what sense can a CFDG grammar be interpreted as a context-free grammar, and how would this fail with unrestricted parameters?
For completeness, I will describe the relevant parts of CFDG. A CFDG grammar designates a starting shape name and provides a list of rules, each mapping a shape name to some number of children; each child has a shape name and a transform. Each referenced shape name must be a primitive shape (eg SQAURE, CIRCLE) or have at least one rule.
The rules for a shape name may also include parameters to be specified each time the shape name is referenced in a child. 373
The parameters of a rule can appear in expressions in the transform or parameters passed to children. However there are restrictions as noted above; the parameter expressions passed to children must be one of: * an integer expression constructed using only integer operations, * a real number parameter forwarded directly from the encompassing rule, or * a real number expression without any reference to the parameters of the encompassing rule.
For example, the following should generate zero or more primitive shapes in a row with period 2, each rotated by 60 degrees: ``` startshape main shape main rule { zero_or_more(2) [] } shape zero_or_more(number dx) rule { primitive [rotate by 60] zero_or_more(dx) [translate by dx] } rule {}
shape primitive rule { SQUARE [] } rule { CIRCLE [] } ```
Without parameters, I could interpret this as a context free grammar whose terminal symbols are the primitive shapes and every possible transformation. To generate an image, we could expand the start shape to terminal symbols and then process them sequentially, maintaining the current transformation. Each primitive shape would be drawn using the current transformation, and each transformation symbol would be applied to the current transformation. Thus the rules shape squares rule { SQUARE [rotate by 60] squares(dx) [translate by 1] } rule {} would become production rules squares -> [rotate by 60] SQUARE [rotate by -60] [translate by 1] squares [translate by -1] squares -> ε I guess a rule with a parameter would produce a production rule for each possible parameter value, and the restriction somehow ensures a finite number of production rules? 904