A Grammar-based Approach to Specify and Implement Visual Languages

This thesis work presents a methodology for modeling and implementing visual languages. The approach relies on the syntactic framework of eXtended Positional Grammars (XPG, for short). This is a formalism to model the basic elements (visual symbols) of the visual notation, their syntactic properties, the relations between them, and a set of syntactic rules to formally define the feasible visual sentences. We present a powerful LR-based (XpLR) methodology for parsing visual languages described by XPGs. The result is the possibility of describing and compiling a broad class of visual languages yet keeping most of LR parsing efficiency. We describe this new algo-rithm, named XpLR(0) parser, and provide heuristics able to solve a number of conflicts usually arising in the previous applications of LR methodology to visual languages. The expressive power of the formalism has been highlighted by modeling UML state diagram languages, which represent one of the most complex visual modeling languages used in the software engineering field. An interesting feature of the XpLR methodology is the possibility of using standar