Content area
Visual programming languages use pictures formed from graphical elements as programs rather than strings of text. A visual program is a diagram specifying a computation. Examples of visual programming languages include many types of diagrams traditionally used within computer science, such as data flow diagrams, finite state diagrams and flowcharts; as well as graphical methodologies developed for software engineering; and new languages such as StateCharts developed to exploit the visual paradigm.
One problem that has hampered research in visual programming languages is the lack of a syntax definition mechanism. The specification of syntax and parsing of programs is well understood for textual programming languages. Both formal methods for syntax specification (e.g. context-free grammars) and practical tools (such as yacc) have proven valuable to language developers. Visual language syntax is more complicated because of the two-dimensional nature of the languages. Previous visual programming environments largely used ad-hoc specifications and special purpose structure editors to handle visual language syntax.
The attributed multiset grammar is a formal model for generating languages which are collections of objects. Picture layout grammars are a specification mechanism for visual language syntax based on attributed multiset grammars. Using picture layout grammars, a language designer can define both the syntactic structure and the two-dimensional layout of a visual language. A spatial parser is an algorithm to recover the syntactic structure of a visual program from an unstructured picture representation. This dissertation develops the attributed multiset grammar model and gives a spatial parsing algorithm for picture layout grammars. It also describes the GREEN environment, which combines an object-oriented graphics editor with the spatial parser to form a grammar-based visual programming environment.