Extended Positional Grammars: A Formalism for Describing and Parsing Visual Languages

Abstract

Much recent research is focusing on formal methods for the definition and implementation of visual programming environments. Extended positional grammars naturally extend context-free grammars for string languages to grammars for visual languages by considering new relations in addition to string concatenation. Thanks to this analogy, most results from LR parsing can be extended to extended positional grammars while preserving their well-known efficiency. XPGs include mechanisms for handling contextual information enabling us to model a broader class of visual languages, which includes the diagrammatic notations used in software engineering. Moreover, the XPG grammar formalism can be effectively used for modeling both visual and textual notations in a seamless way. The XPG model is the underlying formalism of the VLDesk system for the automatic generation of visual programming environments. VLDesk inherits and extends to the visual field, concepts and techniques of compiler generation tools like YACC.