XML graphs in program analysis

XML graphs have shown to be a simple and effective formalism for representing sets of XML documents in program analysis. It has evolved through a six year period with variants tailored for a range of applications. We present a unified definition, outline the key properties including validation of XML graphs against different XML schema languages, and provide a software package that enables others to make use of these ideas. We also survey the use of XML graphs for program analysis with four very different languages: Xact (XML in Java), Java Servlets (Web application programming), XSugar (transformations between XML and non-XML data), and XSLT (stylesheets for transforming XML documents).     

A visual programming language for XML manipulation

XML data flow has reached beyond the world of computer science and has spread to other areas such as data communication, e-commerce and instant messaging. Therefore, manipulating this data by non-expert programmers is becoming imperative and has emerged two alternatives. On one hand, Mashups have emerged a few years ago, providing users with visual tools for web data manipulation but not necessarily XML specific. Mashups have been leaning towards functional composition but no formal definitions have yet been defined. On the other hand, visual languages for XML have been emerging since the standardization of XML, and mostly relying on querying XML data for extraction or structure transformations. These languages are mainly based on existing textual XML languages, they have limited expressiveness and do not provide non-expert programmers with means to manipulate XML data. In this paper, we define a generic visual language called XCDL based on Colored Petri Nets allowing non-expert programmers to compose manipulation operations. The XML manipulations range from simple data selection/projection to data modification (insertion, removal, obfuscation, etc.). The language is oriented to deal with XML data (XML documents and fragments), providing users with means to compose XML oriented operations. The language core syntax is presented here along with an implemented prototype based on it.     

XML-based Specification of Diagram Editors

This paper describes a graphical specification tool for Dia Gen, a diagram editor generator based on hypergraph grammars and hypergraph transformation. The specification tool greatly simplifies the process of specifying and generating diagram editors. It uses an XML-based specification language, and it is an extension of a generic XML editor which offers syntax-directed editing based on the DTD, i.e, syntax specification, of the underlying XML-based language.     

Defining the abstract syntax of visual languages with advanced graph grammars—A case study based on behavior trees

Diagrammatic visual languages can increase the ability of engineers to model and understand complex systems. However, to effectively use visual models, the syntax and semantics of these languages should be defined precisely. Since most diagrammatic visual models that are currently used to specify systems can be described as (directed) typed graphs, graph grammars have been identified as a suitable formalism to describe the abstract syntax of visual modeling languages. In this article, we investigate how advanced graph-transformation techniques, such as conditional, structure-generic and type-generic graph-transformation rules, can help to improve and simplify the specification of the abstract syntax of a visual modeling language. To demonstrate the practicability of an approach that unifies these advanced graph-transformation techniques, we define the abstract syntax of behavior trees (BTs), a graphical specification language for functional requirements. Additionally, we provide a translational semantics of BTs by formalizing a translation scheme to the input language of the SAL model checking tool for each of the graph-transformation rules.     

基于XML和ECA规则的工作流建模及执行

长期以来,工作流产品互操作性的缺乏、尤其是工作流建模语言互操作性缺乏,已成为阻碍工作流技术进一步发展的重要因素,XML作为万维网组织规定的结构化的标记语言,它可以用作描述过程模型的共同语法格式,有望解决工作流描述语言的互操作性问题。文章介绍了采用基于XML的工作流描述语言XFL及其工作流管理系统XFMS。由于XFL本身并不是可执行模型,XFMS系统在低层采用了基于规则的工作流执行系统。并给出了从XFL语言到ECA规则的映射方式,所采用的方法综合了面向规则系统的灵活性以及基于XML模型的可交换性和易学性。     

Grammar-based model transformations: Definition,execution, and quality properties

Model transformation is a key concept in model-driven software engineering. The definition of model transformations is usually based on meta-models describing the abstract syntax of languages. While meta-models are thereby able to abstract from superfluous details of concrete syntax, they often loose structural information inherent in languages, like information on model elements always occurring together in particular shapes. As a consequence, model transformations cannot naturally re-use language structures, thus leading to unnecessary complexity in their development as well as in quality assurance.In this paper, we propose a new approach to model transformation development which allows to simplify the developed transformations and improve their quality via the exploitation of the languages׳ structures. The approach is based on context-free graph grammars and transformations defined by pairing productions of source and target grammars. We show that such transformations have important properties: they terminate and are sound, complete, and deterministic.     

基于XML的UML模型向AADL模型的自动转换

UML已经成为复杂系统建模的工业标准,并可借助代码自动生成工具实现从分析到编码的开发过程自动化;AADL具有精确的语义和严格的语法规范,可用于描述嵌入式实时系统的软、硬件体系结构,并能分析系统的功能及非功能属性。 UML和AADL模型的基本元对象有相互对应关系,并且两种模型的表示都能够采用标准的XML的交换格式。为充分发挥两种语言的优势,文中研究了UML模型向AADL模型的自动转换,以XML为媒介实现两种模型的元对象的对应转换,最终达到两种模型的转换,使用户在设计阶段能够结合运用AADL、UML工具的优点对系统进行分析。     

The Specification of Assemblers

The problem of applying formal techniques of program specification and verification to large complex programs is considered. It is argued that a practical solution requires a variety of techniques, including both procedural and nonprocedural specifications, hierarchical program organization, and the use of program transformations. In particular, a case is made for flexible problem-oriented choice of specification techniques and languages. These ideas are expanded by specifying a load-and-go assembler in three parts: a transduction grammar describing the correspondence between concrete and abstract syntax for assembly language programs; a set of transformations of the abstract form; and a nonconstructive axiomatic specification of the result of core assembly and loading of transformed abstract programs.     

Correct and Robust Programs

The design of programs which are both correct and robust is investigated. It is argued that the notion of an exception is a valuable tool for structuring the specification, design, verification, and modification of such programs. The syntax and semantics of a language with procedures and exception handling are presented. A deductive system is proposed for proving total correctness and robustness properties of programs written in this language. The system is both sound and complete. It supports proof modularization, in that it allows one to reason separately about fault-free and fault-tolerant system properties. Since the programming languages considered closely resembles CLU or Ada, the presented deductive system is easily adaptable for verifying total correctness and robustness properties of programs written in these, or similar, languages.     

Language design for program manipulation

The design of procedural and object-oriented programming languages is considered with respect to how easily programs written in those languages can be formally manipulated. Current procedural languages such as Pascal, Modula-2 and Ada; generally support such program manipulations, except for some annoying anomalies and special cases. Three main areas of language design are identified as being of concern from a manipulation viewpoint: the interface between concrete and abstract syntax; the relationship between the abstract syntax and static semantics naming, scoping and typing; and the ability to express basic transformations (folding and unfolding). Design principles are suggested so that the problems identified for current languages can be avoided in the future     

Code generators

Code generators, which take a programmer's inputs in the form of some abstraction, design, or direct interaction with the system and write out a source program that implements the details of the application, are reviewed. After a brief overview, four separate presentations cover examples of such systems from four domains. The Tags tools uses abstraction to specify real-time control systems. In this tool, the details of synchronization code are hidden from the designer, but some functionality must still be provided in detail. Microstep is a similar kind of tool for data-processing applications. One can view both Tags and Microstep as high-level specification languages. PSG generates programming environments, i.e. one gives it a nonprocedural specification of a language's syntax and it generates an integrated programming environment for that language. While one must specify the environment in detailed form, the actual code generation is hidden. Escort is a similar system specialized for telecommunications applications. It lets one build, execute, and test specifications for telecommunication systems. Both PSG and Escort illustrate the power of domain-specific tools     

An on-the-fly grammar modification mechanism for composing and defining extensible languages

Adaptable Parsing Expression Grammar (APEG) is a formal method for defining the syntax of programming languages. It provides an on-the-fly mechanism to perform modifications of the syntax of the language during parsing time. The primary goal of this dynamic mechanism is the formal specification and the automatic parser generation for extensible languages. In this paper, we show how APEG can be used for the definition of the extensible languages SugarJ and Fortress, clarifying many aspects of the syntax of these languages. We also show that the mechanism for on-the-fly modification of syntax rules can be useful for defining grammars in a modular way, implementing almost all types of language composition in the context of specification of extensible languages.     

Formatted syntaxes and modula-2

The formatted syntax notation has been developed for the specification of formatted programming languages. This paper describes how a formatted syntax may be constructed for the purpose of prettyprinting an existing free-format language. Those aspects of the system of particular relevance to free-format languages are emphasized and their use explained. Also, a number of deficiencies in the defining metasyntax and formatting symbol repertoire are discussed. Practical enhancements and further areas of research are suggested. The programming language Modula-2 is used for illustration, and a formatted syntax for it is given.     

Transformation of XML data using updates without side effects

One of the key technologies of XML data management is XQuery, the query language for both retrieving and transforming XML data. In the paper, limitations of the XQuery facilities for transforming XML data are discussed. It is shown that, for one important class of queries, XQuery expressions are too cumbersome and computationally inefficient. In the paper, it is suggested to extend the XQuery language by functional update expressions. From the syntax standpoint, such expressions are similar to expressions of XML update languages. However, they can be evaluated without side effects, which makes it possible to integrate them in XQuery in a natural way. The expressiveness of the extended language is demonstrated, and approaches to efficient implementation of the suggested extension are considered. In addition, the problem of arbitrary compositions of XML query and update expressions (the problem of nested update expressions) is discussed. The existing XML update languages are based, as a rule, on the XQuery language; however, the possibility of constructing arbitrary compositions of XQuery expressions and those of the XML update language is not provided. This impedes development of practical XML applications in the XQuery language. In the paper, an approach to solving the composition problem based on the use of functional update expressions is suggested. Possibilities of the implementation of the suggested extension are discussed.     

Graph transformations and software engineering: Success stories and lost chances

Textual as well as visual and diagrammatic notations are essential in software engineering, and are used in many different contexts. Chomsky grammars are the key tool to handle textual notations, and find many applications for textual languages. Visual and diagrammatic languages add spatial dimensions that reduce the applicability of textual grammars and call for new tools.Graph transformation systems have been studied for over 40 years and are a powerful tool to deal with syntax, semantics and transformation of diagrammatic notations. The enormous importance of visual and diagrammatic languages and the strong support that graph transformation provide to the manipulation of diagrammatic notations would suggest a big success of graph transformation in software engineering.Graph transformation systems find their application both as language generating devices and specification means for system evolution, and thus can have many applications in software engineering. In this paper we discuss the main features of graph transformation and how they can help software engineers. We look back to the many attempts to use graph transformations in software engineering in the last 15 years, identify some success stories, and discuss to what extent graph transformation succeeded, when they have not succeeded yet, what are the main causes of failures, and how they can help software engineering in the next 15 years.