| This dissertation provides a formal foundation, i.e. the spatial graph grammar (SGG), for specifying and interpreting well-formed visual languages. The spatial graph grammar is different from other graph grammar formalisms by introducing spatial notions to the abstract syntax. The direct representation of spatial information in the abstract syntax reduces the gap between the concrete representation of graphical models and the specification of grammatical rules, and thus makes grammatical rules easier to design and understand. By taking advantage of the spatial information, the parser of the SGG performs in polynomial time with an improved parsing complexity over its non-spatial predecessor, i.e. the reserved graph grammar. The expressiveness of the spatial graph grammar is demonstrated by its application to online adaptive layout and model driven development.;With the facility for spatial specifications, the SGG is used to analyze Web pages and derive a hierarchical structure about the composition of multimedia objects in a Web page. Based on the extracted structure, the original Web page is partitioned to fit both spatially and semantically for displaying on mobile devices. The SGG also serves as a foundation for a grammatical approach to authoring and presenting adaptive structure-directed layouts, emphasizing on the style adaptation.;Based on the spatial graph grammar, this dissertation specifies the behavioral semantics of UML models based on the SGG. In order to interpret state transitions of simple and composite states, a graph grammar automatically produced from a state machine is used to validate, recognize and generate state configurations. The automation mechanism for generating graph grammars and their validation and recognition capability would populate the automated design of model-driven architectures. An integrated behavioral semantics of UML object and state diagrams is given by an event driven graph transformation and grammar system. This dissertation also provides a style-driven framework for specifying software architectures by drawing graphs. The structural integrity of user specified architecture is validated by the SGG parser. |
