Online Parsing of Visual Languages Using Adjacency Grammars

Joaquim A. P. Jorge,  Ephraim P. Glinert  

 About the Authors

Adjacency Grammars   Incremental Parsing   Formal Visual Languages  


Visual computing environments continue to grow in importance, yet fast, general parsing algorithms for visual languages remain elusive. In this paper we present an incremental parsing algorithm for a broad class of visual languages which do not contain overlapping elements. Our algorithm is based on the concept of adjacency grammars, where adjacencies are defined so as to encompass both spatial and logical constraints. Our approach combines bottom up and top down methods to support incremental parsing of visual input, allowing for measurably efficient online parsing of diagram-like visual languages, with observed linear run times for large visual sentences.

 Document in PostScript (compressed, 73346 bytes)

Object-Oriented Dataflow Programming Agents with Visual Rules Index of Talks Proceedings - 11th Intl. Symposium on Visual Languages