Topological composition systems: specifications for lexical elements of visual languages

The paper explains the role of lexical analysis in a visual programming environment. The authors classify the visual lexical elements based on the geometric properties of their composition operators. They explore the class of topologically composed lexical elements and provide a method of specifying them. They refer to these specifications as topological composition systems. The core of such a system is a set of composition rules that define the topological compositions to be performed and the conditions when the rules can be fired. They also describe the design of a lexical analyzer for topological composition systems. The design uses efficient computational geometry algorithms to achieve a time complexity of O(|R| N log N) for an input size of N primitive picture elements, where |R| is the number of rules in the system. A lexical analysis phase, preceding parsing, can reduce the input size to the parser by 30%-50%. Early experiments also show that using topological lexical analysis can enhance the overall picture recognition process performance by a factor of 10