Ultimately, the recognition process of both textual and graphical languages starts with raw data, which consists of a set of pixels: say, a bitmap. Normally, this phase is not included in a discussion about deriving abstract form from concrete form. I include it to be complete and to indicate that what is considered normal is directed by the tools that most people are used to. We are very much used to character-based entry using a keyboard, but what if we were all used to handwriting-recognition tools?

In the textual case, optical character recognition (OCR) is used to derive a sequence of characters. Note that the OCR phase needs knowledge about the type of characters to be recognized. For instance, Chinese characters are quite different from the ones in the Western alphabet. Font and typeface are also important.

In the graphical case, optical recognition is not very well known, yet there are accounts of tools that are able to scan the proverbial table napkin that has been used to record an important discussion [Lank et al. 2001, Hammond and Davis 2002]. As in the textual case, the graphical optical recognition needs to have knowledge of some form of alphabet, the set of glyphs as it is called in this field. This alphabet determines the answers to such questions as, “Does this set of pixels represent a rectangle or four (touching) lines?

The result of this phase is a set of symbols that include some form of knowledge about their position within the set, called the set of positioned symbols, or posyms. This information may be relative to a fixed point (my location is x = 30, y = 28) or relative to each other (my location is above element X, left of element Y). In the community that studies graphical languages, it is considered folklore that a character stream can also be regarded as a set of posyms. Each character can have a maximum of two relative positions: before and after another character.

Background on Compiler Technology

The area of compiler technology is well established. As early as 1972, Aho and Ullman produced a definitive textbook on the subject, which has been revised in 1985 [Aho 1985]—the so-called dragon book because of the dragon on the front cover)—and again in 2007 [Aho 2007]. The figure shown here, from the 2007 edition, explains some basic facts about compiler technology.

A compiler has seven distinguishable phases: lexical analysis (scanning), syntax analysis (parsing), (static) semantic analysis, intermediate code generation, machine-independent code optimization, code generation, and machine-dependent code optimization. In all these phases, a symbol table is available to store and retrieve information about the text being processed. Here, we address only the first three phases: the process from raw input to an in-memory model. Code generation can be regarded as another type of model transformation.

The first phase, scanning, is associated with a regular grammar, which defines the way the characters are bound together to form tokens. The second phase, parsing, is associated with a context-free grammar, which sometimes takes the form of an attributed grammar. An attributed grammar is a context-free grammar in which the nonterminals can hold context-sensitive information in the form of attribute values. The result of this phase is a parse tree, in which the nodes represent the application of the grammar rules.

The third phase, static semantic analysis, is not associated with a specific formalism. In other words, the implementer of the compiler is completely free to process the input and to produce as a result an abstract syntax tree.

According to common understanding, the nodes in the abstract syntax tree represent language concepts rather than grammar rule applications.

The most difficult part of building these three phases is implementing the parsing phase. Several parsing theories have been developed, mostly during the 1960s and 1970s.

1. LL parsing means scanning the input from left to right while building the leftmost derivation, which means that the leftmost nonterminal in the grammar rule is the first to be replaced.

2. LR parsing means scanning the input from left to right, while building the rightmost derivation, which means that the rightmost nonterminal in the rule is the first to be replaced.

3. LALR parsing stands for Look-Ahead Leftmost Reduction. It is an extension of LR parsing that produces more efficient parsers.

Because building a parser by hand is difficult, many tools have been developed that generate parsers. These tools are called parser generators. The most famous example is Yacc [Johnson 1974], other examples are JavaCC [JavaCC 2008], Antlr [Antlr 2008], and SableCC [SableCC 2009]. They take as input a context-free grammar. However, the allowed grammar rules depend on the type of parser produced (LL, LR, or LALR), and the input format is different for all of the parser generators.

In the last two decades advances of compiler construction have been in code generation, particularly with respect to optimization and paralleltarget machines.

The next phase in a compiler is the lexical analysis, or scanning phase, whereby groups of characters are combined to form words. This phase and the next—syntactical analysis, or parsing—are very similar. They are different in the techniques used to implement them and because doing scanning before parsing makes parsing more simple. Examples of generators for scanners and parsers for textual languages are Yacc [Johnson 1974] and Lex [Lesk and Schmidt 1975], Antlr [Antlr 2008] and JavaCC [JavaCC 2008].

For the textual case, the result of this phase is a parse tree. To extend this for graphical languages, the result should be a parse graph. Most nodes in a parse graph are posyms, but some represent larger, compound concepts. All nodes are connected based on either position or on syntactical grouping. For example, in English, book is a noun, a posym, whereas the best-selling, world-famous red book is syntactical grouping called a noun phrase. The syntactical group connects the posyms and other syntactical groups that are part of it. The subgraph that holds only posyms with their positioning information is also known as a spatial relationship graph [Bardohl et al. 1999].

Parse graphs still include nodes that represent purely syntactical elements. In the textual case, keywords and special characters, such as brackets, are present as posyms in the parse graph. In the graphical case, arrows, rectangles, and so on, are present in the parse graph. The first action of the analysis phase is therefore to abstract away from all purely syntactical elements in order to form the abstract syntax graph. In the textual case, the resulting graph is generally known as an abstract syntax tree.

Together with binding and checking, this phase is known as the static semantic analysis, even though this phase has nothing to do with the actual, dynamic semantics of the language, as is nicely explained by Harel and Rumpe [2004].

The abstract syntax graph is not yet the result that is required for further processing, such as code generation or model transformation. The abstract syntax graph may still contain unbound elements, that each represent a reference to another element in the graph but which is not (yet) connected to this other element. These references may refer to parts that might not exist, perhaps owing to a user error or an incomplete specification.

For instance, suppose that a publisher has created a domain-specific language to record books and their authors, according to the metamodel in Figure 7-2(a). Mograms of the language can use either a textual or a graphical concrete syntax, as shown in Figure 7-2(b) and Figure 7-2(c). Any instance of the class Book in a mogram must include a property named author. In the textual concrete syntax (in Figure 7-2(b)), its value is given by a string following the keyword author. In the binding phase, this string value needs to be replaced by, or otherwise bound to, an instance of class Person. This means that somewhere in the mogram, this instance must be present. In the general case, this may not be true.

Figure 7-2. An example of the problem of binding: (a) metamodel, (b) textual concrete syntax, (c) graphical concrete syntax

In the graphical concrete syntax (in Figure 7-2(c)), the value of the element author is given directly by the spatial relationship between the arrow leading from the book symbol on the left to the person symbol on the right. In this case, the binding for the property can be deduced from the spatial relationship between the symbols. On the other hand, when two or more symbols representing the same linguistic element are allowed in one diagram or when two or more diagrams are used in a single model, binding may still be necessary. For instance, when the same Person instance symbol appears twice in the diagram, both occurrences must be bound to the same Person instance.

Finally, a number of checks can be performed on the abstract syntax graph. Type checking is a well-known form of checking that can be performed only when all elements have been bound. Control flow analysis is also often done in this phase to recognize unreachable code. Note that although both examples are commonly found in textual languages, this does not mean that similar checks are not required in a graphical language. For instance, according to the UML specification [OMG-UML Superstructure 2005], the arrow in Figure 7-3 may be drawn only between an instance of a BehavioredClassifier and an instance of an Interface. Most UML tools will not allow their users to draw such an arrow in any other case, but when the diagram has been optically recognized from a hand-made sketch (the proverbial napkin), this check still needs to be performed. This scenario does not often take place, since current tools are not powerful enough, but I would really love to include this functionality in my tool set.

Figure 7-3. An example of the need for static checking in a graphical language

Figure 7-6 shows an example of an Alan mogram using the graphical syntax, which is more or less the same as the UML syntax. Actually, the mogram is not completely graphical but rather is a mix of graphical and textual representations. For instance, attributes and operations are shown using a structured text of the well-known format name : type-reference = initial expression and name ( parameters ) : type-reference, respectively, although in the example, the type reference has been omitted because it is void.

Figure 7-6. An example Alan mogram

Another textual reference to a type is the text in the overlayed box. A class symbol together with an overlayed box with solid line represents a parameterized class. An overlayed box with a dotted line represents a generic type. The line with the black arrowhead means that the parameterized class uses the generic class as its definition. The text in the solid line box refers to a type variable (X) and to another class (Airplane). Both the type variable and the class must be present elsewhere in the mogram. Binding rules must be given for each of these cases.

However, in this section, I focus on the graphical elements. One such graphical element is the arrow with the little eye on its end, which represents the occurrence of an observe expression.

Figure 7-7 shows some of the elements in Alan’s graphical concrete syntax model (GCSM). As you can see, most elements are simple graphical items: boxes, texts, and lines. You may assume that these graphical items have some way to reveal their spatial relationships, such as the fact that a certain text is within a box and below other text.

Figure 7-7. Part of Alan’s graphical CSM

The graphical items are all part of the alphabet. In this case, there are only two more complex syntactical elements. One is the TextBox; the other is called ClassBox. A TextBox consists of a text and a box, with the restriction that the text must be contained in the box. Using the spatial information on the bounding box of each element in the alphabet together with the surrounds relationship, we can express this by the following constraint:

A ClassBox consists of a box, a name text, and, optionally, an attribute text, an operation text, and/or an overlaying textbox. Similar constraints can be defined on the spatial relationships between these parts. For instance, the attribute text must be contained in the box belonging to the same classbox and must be below the name text; similar constraints hold for operation text.

Together with the metaclasses TextBox and ClassBox, these constraints form the parsing rules in this concrete syntax model. Whether the tooling for this language implements these constraints by allowing only the creation of complete classbox instances or by checking these rules during the parsing phase is not determined or restricted by the way the rules are expressed. Both options are still open.

Similar flexibility is created by the metaclass Line. Because the different line types are represented by attributes (hasEye, etc.), it is possible to create a tool that is able to switch between the different line types. The mapping to the abstract syntax needs to take care of the intended meaning.

In general, there is no direct one-to-one relationship between the elements of a graphical CSM (GCSM) and the elements of the ASM. For instance, a box overlayed by a solid textbox is a representation of an object type, but a box overlayed by a dotted textbox should be mapped to a generic type.

A line with an open arrowhead should be recognized as a supertype relationship between two types. But a line with an eye symbol attached should be mapped to an observer/subject relationship; a line with no attachments should be recognized as a pair of attributes that are each other’s opposite. (I could have used a different GCSM in which these three options were represented by three different classes. In that case, I would have a much simpler job in linking the inheritance symbol, but the other two cases would still be difficult because their recognition involves not one but a pattern of graphical symbols.)

For instance, to map a line representing an association in an instance of the GCSM (the concrete form) to the corresponding elements in an instance of the ASM (the abstract form), we must consider not only the line itself but also the boxes to which the line is attached. These boxes need to have their counterparts in the abstract form before we are able to make a good mapping. Rule 2 in Figure 7-8 specifies this. The rule uses information on the mapping between a classbox and an object type that has been created by the application of rule 1. Both rules are examples of abstraction rules, which indicate the parts of the concrete form that purely concern the visualization, like Line and Box, whereas the contents of a text block cannot be discarded. Note that both rules use a combination of Alan’s GCSM and ASM.

Figure 7-8. Transformation rules from Alan’s graphical CSM to the ASM