Diagrams such as flowcharts can represent programs. Programming languages
can be represented by context free grammars. But it is not obvious if diagrams
can be generated from formal languages. This sections outlines the formal
methods used to describe diagrams.
H-graphs are graphs whose nodes can be other graphs. This construction
implicitly underlies most visual programming languages. H-graphs are discussed
in Pratt (1971b, 1973).
The components of an H-graph are atoms, nodes, and graphs. We use A
and N to signify the universe of possible atoms and nodes.
An extended directed graph (or graph) G over N and A is a triple
G=(M, E, s) where
Nodeset M 
N,
Edgeset E: M 
A 
M,
Initial Node s, 
M.
E is partial, finite, and M is finite, nonempty.
E(m, b) = n means there is an edge from node m to node n
labeled b.
An H-graph is a pair H = (M, V) where Nodeset M 
N,
and is finite, nonempty.
Value function V: M
A
{G | G is a graph over
M and A}
In other words, the value of a node is an atom or another graph. This
allows for a hierarchy of graphs.
Pratt also defines sub and rooted H-graphs, and defines a selector and
arc traversal function. Rooted H-graphs are used to model arrays, records,
sets, simple variables, lists, etc. Nodes represent storage locations,
and the root is the point of access to the whole structure. The value function
is the accessing mechanism. Atoms represent primitive values such as numbers
and characters.
Pratt (1971a) outlines a method for converting programs back and forth
into flowcharts:
Figure 2.33. Flow chart and language equivalence. From Pratt (1971a).
He points out that compilers and programming language semantics both
rely on building a representation more structured than strings. He notes
the similarity between H-graphs and Web Grammars (Pfaltz 1969).
Pratt accomplishes the conversion between programs and flowcharts by
manipulating graph languages. A graph language is a set of directed graphs
with labeled nodes and arcs. A graph grammar generates a language of terminal
graphs from a single non-terminal node. Each rewriting rule specifies a
way of rewriting a node with a nonterminal value. A node can be replaced
by a graph. This is done by replacing the incoming edge with an edge leading
to the replacing graph, and replacing the outgoing edge of the node with
the outgoing edge of the graph. This restricts the grammar rule to having
a single input and output node. Stotts (1988) has extended the H-graph
model to a visual parallel programming language.
Golin (1989) points out that programs are usually developed free-form
in text editors. He recommends that visual programs should be developed
free form in graphics editors. In order to do this, we need visual language
grammars and compilers. He calls the grammars picture layout grammars.
Golin bases his structure on a grammar model of his own invention he calls
an attributed multiset grammar. The right side of a multiset grammar
is seen as being an unordered collection rather than a sequence. Each grammar
symbol has associated with it a rectangular extent or two endpoints. Production
operators include
over, left_of, tiling, contains, group_of, adjacent_to, touches,
points_to, labels, follow, join, fork, parallel.
A parser, given a picture created with a graphic editor, can recover
the underlying structure of the picture using the picture layout grammar.
Syntactic pattern recognition is a field of study that tries to recognize
patterns in images by using formal language techniques. In most cases,
these techniques are meant to be applied to data from scanned images, rather
than to the already computer-generated images of visual programming. However,
the work is often cited in the visual programming literature, and is useful
in discussing the difference between textual and visual representation.
Context-free grammars can be used to generate images if some terminals
are assumed to be line segments, and operators are assumed to be ways of
joining the line segments. Then a string such as ((a + b) * c) can define
three segments joined in a certain way, say into a triangle. This is the
technique used in Shaw's picture description language (1969).
Figure 2.34. Circuit diagram from a grammar. In Gonzalez (1978).
The above figure can be generated from the string aab, if an a generates a capacitor and a b generates a resistor.
Figure 2.35. Chromosome from a grammar. In Gonzalez (1978).
A string can be used to generate curvilinear figures, as in the above chromosome, from the string babcbabdacad. But the generation of a real graph is much more difficult with this method:
Figure 2.36. Complete 4 node graph. In Gonzalez (1978).
This provokes the thought that textual representation works well with trees, but badly with graphs. We will return to this question in chapter 7.
All of the above grammars are described in Gonzalez (1978); web grammars were first defined in Pfaltz (1970). The work of Fu and his students has dealt with many different ways of representing images, including the grammars described above (Fu 1984).