A Systolic Parsing Algorithm for a Visual Programming Language

In this paper we consider a problem of parsing a two-dimensional visual programming language Show and Tell on a two-dimensional array of processors. A program in Show and Tell is a bit-mapped, two-dimensional pattern satisfying a certain set of grammatical rules. The pattern consists of partially ordered set of rectilinear boxes and arrows distributed over the space of nxn pixel area. The corresponding directed graph, the box graph, where boxes are nodes and arrows are directed edges, may not have a cycle in a Show and Tell program. The cycle detection is the most computationally intensive stage of the parsing section of a Show and Tell program. We propose to exploit the concept of systolic array in parsing of Show and Tell programming language. A given bit pattern is mapped onto nxn array of mesh connected processors with one pixel assigned to one processing element. We show an algorithm for cycle detection which runs in time proportional to the size of the box graph. The complexity of any individual processor is independent on n, the parameter describing the size of the array