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.     

Reusing metamodels and notation with Diagram Definition

It is increasingly common for language specifications to describe visual forms (concrete syntax) separately from underlying concepts (abstract syntax). This is typically to enable interchange of visual information between graphical modeling tools, such as positions of nodes and routings of lines. Often overlooked is that separation of visual forms and abstract concepts enables languages to define multiple visual forms for the same underlying concepts and for the same visual form to be used for similar underlying concepts in different languages (many-to-many relationships between concrete and abstract syntax). Visual forms can be adapted to communities using different notations for the same concepts and can be used to integrate communities using the same notation for similar concepts. Models of concrete syntax have been available for some time, but are rarely used to capture these many-to-many relationships with abstract syntax. This paper shows how to model these relationships using concrete graphical syntax expressed in the Diagram Definition standard, examining cases drawn from the Unified Modeling Language and the Business Process Model and Notation. This gives definers of graphical languages a way to specify visual forms for multiple communities.     

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.     

Bridging concrete and abstract syntaxes in model‐driven engineering: a case of rule languages

The paper covers the problem of bridging the gap between abstract and textual concrete syntaxes of software languages in the model‐driven engineering (MDE) context. This problem has been well studied in the context of programming languages, but due to the obvious difference in the definitions of abstract syntax, MDE requires a new set of engineering principles. We first explore different approaches to defining abstract and concrete syntaxes in the MDE context. Next, we investigate the current state of languages and techniques used for bridging between textual concrete and abstract syntaxes in the context of MDE. Finally, we report on lessons learned in experimenting with the current technologies. In order to provide a comprehensive coverage of the problem under study, we have selected a case of Web rule languages. Web rule languages leverage various types of syntax specification languages; and they are complex in nature and large in terms of the language elements. Thus, they provide us with a realistic analysis framework based on which we can draw general conclusions. Based on the series of experiments that we conducted with the analyzed languages, we propose a method for approaching such problems and report on the empirical results obtained from the data collected during our experiments. Copyright © 2009 John Wiley & Sons, Ltd.     

Synchronization of abstract and concrete syntax in domain-specific modeling languages

Modern domain-specific modeling (DSM) frameworks provide refined techniques for developing new languages based on the clear separation of conceptual elements of the language (called abstract syntax) and their graphical visual representation (called concrete syntax). This separation is usually achieved by recording traceability information between the abstract and concrete syntax using mapping models. However, state-of-the-art DSM frameworks impose severe restrictions on traceability links between elements of the abstract syntax and the concrete syntax. In the current paper, we propose a mapping model which allows to define arbitrarily complex mappings between elements of the abstract and concrete syntax. Moreover, we demonstrate how live model transformations can complement mapping models in providing bidirectional synchronization and implicit traceability between models of the abstract and the concrete syntax. In addition, we introduce a novel architecture for DSM environments which enables these concepts, and provide an overview of the tool support.     

MontiCore: a framework for compositional development of domain specific languages

Domain specific languages (DSLs) are increasingly used today. Coping with complex language definitions, evolving them in a structured way, and ensuring their error freeness are the main challenges of DSL design and implementation. The use of modular language definitions and composition operators are therefore inevitable in the independent development of language components. In this article, we discuss these arising issues by describing a framework for the compositional development of textual DSLs and their supporting tools. We use a redundance-free definition of a readable concrete syntax and a comprehensible abstract syntax as both representations significantly overlap in their structure. For enhancing the usability of the abstract syntax, we added concepts like associations and inheritance to a grammar-based definition in order to build up arbitrary graphs (as known from metamodeling). Two modularity concepts, grammar inheritance and embedding, are discussed. They permit compositional language definition and thus simplify the extension of languages based on already existing ones. We demonstrate that compositional engineering of new languages is a useful concept when project-individual DSLs with appropriate tool support are defined.     

A Representation of Fω in LF

We study how the type theory F_ω can be adequately represented in the meta-logical framework Twelf [16]. This development puts special emphasis on the way how terms, types, and kinds are represented in that it uses higher-order abstract syntax to model variable binding and dependent types to model typing constraints. Furthermore our design ensures that only well-typed terms and well-kinded types can be constructed. A possible application of this work lies in the development of safe intermediate languages for compilation.     

Dynamic aspects of visual modelling languages

A large class of diagrammatic languages falls under the broad definition of “executable graphics”, meaning that some transformational semantics can be devised for them. On the other hand, the definition of static aspects of visual languages often relies on some form of parsing or constructive process. We propose here an approach to the definition of visual languages syntax and semantics based on a notion of transition as production/consumption of resources. Transitions can be represented in forms which are intrinsic to the diagrams or external to them. A collection of abstract metamodels is presented to discuss the approach.     

一种面向图形化建模语言表示法的元模型

对于图形化的建模语言,为定义其表示法一般需要解决3个问题:如何定义每个建模元素的图形符号,如何定义图形符号之间的位置关系以及如何将表示法映射到抽象语法.为了方便进行模型转换和代码生成,还需要使用模型化的方式描述建模语言的表示法.通过对UML及其语言家族中的表示法进行总结、分析和归纳,提出了一种表示法定义元模型(notation definition metamodel,简称NDM).针对定义表示法所面临的3个问题,NDM被分成基本图元及其布局、基本位置关系和抽象语法桥三部分.使用NDM定义好的表示法模型还可以通过代码生成技术生成可使用的源代码.将NDM与其他几种定义表示法的方法进行了比较,结果表明,NDM与其他方法相比具有优势.NDM已经在元建模工具PKU MetaModeler中实现.介绍了NDM在实际应用中的几个案例.     

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.     

Deterministic and nondeterministic flowchart interpretations

Programming languages are studied in the abstract. Algebraic theories supply the syntax for programming languages. Semantics is provided by coproduct preserving functors from the algebraic theory to some semantic category with finite coproducts. Deterministic programming languages are provided when the semantic domain is the category of pointed sets and point preserving functions. Nondeterministic programming languages occur when the semantic domain is the category of Abelian monoids. The class of all nondeterministic programming languages with a fixed syntax is shown to be a variety of algebras. All classes of deterministic programming languages that allow branching are shown to be nonvarietal. Other properties of classes of programming languages are studied using category theory.     

An institution theory of formal meta-modelling in graphically extended BNF

Meta-modelling plays an important role in model driven software development.In this paper,a graphic extension of BNF (GEBNF) is proposed to define the abstract syntax of graphic modelling languages.Fro...     

基于模型驱动的实时嵌入式系统

随着实时嵌入式系统的功能越来越复杂,现有的软硬件分离、软硬件协调等实时系统设计方法已经无法满足其系统实现的要求.本文根据模型驱动开发架构MDA和模型集成开发MIC的核心思想,将时间语义结合服务体/执行流（Servant/Exe-Flow Model,简称SEFM）模型,提出了一种基于模型驱动的实时系统设计方法.首先,本文给出了SEFM模型的元模型表达系统的抽象语义,同时使用XML语言和框图语言来描述SEFM模型的具体语法.结合XML解析技术,根据同一抽象语法的不同具体语法能够相互转化,实现了框图语言的代码生成,最后以实时跟车系统设计方案表明该系统实现方法的可行性和正确性.     

基于JavaCC的抽象语法树生成错误处理技术研究

随着C++语言标准的不断演进,词法语法解析工具如JavaCC等对于很多扩充的新特性以及复杂的语法结构不能做到完全支持,这可能会导致抽象语法树生成错误且不完整;针对这一问题,提出一个针对抽象语法树生成错误的处理框架;首先,通过对JavaCC的扩充,实现一套可以解析C++语言的词法语法分析器,生成抽象语法树并记录报错行;其次,根据报错行寻找所在函数区间即不支持或不匹配的语法片段;最后,通过注释函数区间的方式来跳过不支持或不匹配的语法片段进行错误处理并迭代生成抽象语法树;实验结果表明,对抽象语法树生成进行错误处理后可以更全面的分析代码,抽象语法树完成率上升37.8%,分析行数提高3.9倍。     

一种基于语义重构的模型映射方法

通过对模型描述语言的语法结构和语义表达特性的抽象分析，提出了一种基于语义重构的模型映射方法。该方法通过归纳分析建立抽象目标语义模型，基于源模型语义域在目标语义域中的重新构造，以目标语义模型为中介建立源模型到目标模型的映射关系。该方法不仅可为模型转换的具体实现提供理论指导，还可为验证不同抽象层次模型之间映射关系的正确性提供依据。以JSF+EJB为目标平台阐述了该方法的应用。     

Recovering structured data types from a legacy data model with overlays

Legacy systems are often written in programming languages that support arbitrary variable overlays. When migrating to modern languages, the data model must adhere to strict structuring rules, such as those associated with an object oriented data model, supporting classes, class attributes and inter-class relationships.In this paper, we deal with the problem of automatically transforming a data model which lacks structure and relies on the explicit layout of variables in memory as defined by programmers. We introduce an abstract syntax and a set of abstract rewrite rules to describe the proposed approach in a language neutral formalism. Then, we instantiate the approach for the proprietary programming language that was used to develop a large legacy system we are migrating to Java.     

用于漏洞检测的中间语言表示方法

现有Web漏洞检测方法中使用的中间语言针对特定编程语言设计,在对多种编程语言源代码进行漏洞抽象表示时,无法将多语言下的同类型漏洞用统一的中间语言表示,增加了后续漏洞分析处理的难度。针对该问题提出了一种基于污点分析的中间语言表示方法,实现多编程语言下同类型漏洞信息的统一抽象表示。该中间语言设计过程中将漏洞发生过程抽象为三元组表示,将与三元组相关的代码元素抽象为中间语言的关键字,根据三元组间的语义关系设计了该中间语言的语法。在转义时,利用污点分析方法跟踪污染源的执行路径,对路径中的源代码进行转义得到中间语言表示。最后将该中间语言用于漏洞检测模型,实验结果表明该中间语言与对照中间语言相比对编程语言中漏洞信息的抽象表示更具普适性,对漏洞检测具有有效性。     

IA64二进制翻译中过程抽象技术及其实现

过程抽象技术是用机器无关的表达方式对过程中与机器相关的内容进行抽象。然而用传统的Pascal,C或者是C 语言来实现该技术是相当困难的。本文基于IA64二进制翻译框架,提出了一种新的过程抽象技术,并对扩展的过程抽象语言进行了详细介绍。     

A program design language based software maintenance tool

Program design languages are an increasingly important method of expressing the detailed design of a software system. Such languages can be modelled using a data structure known as a semantic net. This paper describes a maintenance tool for program design languages based on such a data structure. The tool allows the user to interrogate a semantic net using an interactive procedural language in order to derive information necessary for software maintenance. The technique upon which this tool is based is applicable to the maintenance of activities throughout the software lifecycle.