上下文相关图文法的表达能力分析

上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.     

On the Expressiveness of Context-Sensitive Graph Grammars

上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.     

一种有效的结点标号上下文无关图文法分析算法

本文讨论了上下文无关图文法的性质，并证明了图文法推导具有独立性．本文还给出了一种有效的上下文无关图文法分析算法，它具有多项式时间复杂性，并给出了算法的正确性证明．该算法已经用Ｃ语言实现．     

EGG图文法语法分析算法的研究

EGG是一种基于边的上下文相关图文法形式化框架,其语法分析(归约操作)算法是该文法重要的组成部分。在简要介绍EGG的基础上,给出了EGG语法分析算法的设计,其中包括子图匹配算法、子图替换算法和算法计算复杂性的分析。为了展示如何用EGG来定义图语言,特别是如何用所设计的归约算法来分析图,文中以程序流程图为例,给出了相关的EGG形式定义以及对一个具体流程图的归约过程,并探讨了可能降低分析算法复杂性的一些途径。     

图文法综述

形式语言理论对计算机科学的发展起了重大的作用,作为对传统字符文法扩展的图文法的形式化研究,其重要意义是不言而喻的.本文在概述图文法的产生、发展和现状的基础上,着重介绍了从一维字符文法扩展到二维图文法所出现的新问题,以及在形式化处理上引出的新方法,其中最主要的是嵌入问题的解决、文法类型的划分和成员问题的判定.文中以目前较为流行的图文法为例,特别是一些典型的上下文无关和上下文相关的图文法,对上述的问题进行了深入的讨论,指出了现有方法中的一些不足之处,并展望了图文法今后值得研究的问题和方向.     

一种基于边的上下文相关图文法形式化框架

围绕解决图文法中的主要问题——嵌入问题,提出了一种基于边的上下文相关图文法形式化框架,并对由此定义的文法的一些性质及相应的归约算法进行了讨论.对所提出的图文法与已有的文法进行了比较.同时,展望了今后值得进一步研究的一些问题和方向.     

并行性挖掘的图文法方法

并行性分析技术一般通过对程序的控制与数据流图或相关依赖图的分析来实现,因而需要从程序中抽取出相应依赖图的算法的支持.本文基于上下文相关图文法RGG形式框架,定义了一种任务级的并行编程图语言GPPL来直接描述顺序或并行程序的控制与数据流图,而且设计了相应的并行性分析算法以挖掘GPPL图程序的并行性特征.GPPL图语言可视为并行程序设计与程序代码生成之间的协同语言,从而使并行性挖掘避免了从程序中抽取出相应依赖图的过程.与已有的描述顺序或并行程序的图语言及其分析算法相比,GPPL图程序形式更为简洁和直观,易于设计,描述能力也更强;基于GPPL图的并行性分析算法的分析能力更强,而且具有可扩展性.     

可视化语言技术在软件开发中的应用

可视化语言技术比一维文本语言在描述软件组成方面具有优越性.由于图表和图形概念在系统建模中的广泛使用,可视化语言可以应用于需求分析、设计、测试和维护等软件开发的各个阶段.除了具有直观易见的特点之外,图文法在计算机上的精确建模和验证能力,为设计可视化语言提供了一个坚实的理论基础.讨论了可视化语言的形式理论基础,回顾了相关的可视化图形编程环境.特别提出了一种空间图文法,并且用该图文法定义了统一建模语言的行为语义.基于空间图文法,开发了一种基于模式驱动的框架,以帮助软件架构与设计.     

文法推断研究的历史和现状

文法推断属于形式语言的归纳学习问题,它研究如何从语言的有限信息出发,通过归纳推断得到语言的语法定义.文章综述文法推断研究的历史和现状.首先阐述文法推断的理论模型,接着罗列上下文无关文法类及其非平凡子类、隐马尔可夫模型以及随机上下文无关文法的推断方法,最后简介文法推断的应用,并展望其发展趋势.     

面向层次化数据的变分圆形树图

圆形树图(circular treemap)是面向层次化数据的一种信息可视化方法.提出一种圆形树图构造方法,将圆形树图的布局问题与组合优化中的圆排列(disk packing)问题相结合,以一种基于变分连续优化的算法求解多个半径不同圆的优化布局,由此提高圆形树图的空间利用率,并支持层次下行、层次上行与焦点+上下文等自然交互方式.实验结果表明了该方法的有效性.     

The parsing problem for affix grammars

Summary Affix grammars are an extension of context-free grammars which retain most of their advantages and eliminate most of their limitations with respect to the definition of programming languages and the specification of their translators. The extension allows definition of context-sensitive syntax features, and also allows semantics to be linked to syntax. In this paper, the parsing problem for affix grammars is explored and shown to be closely related to the parsing problem for context-free grammars. This enables a standard context-free parser constructor to be generalised to a constructor for affix grammars, essentially by addition of a preprocessor. The resulting constructors are compared with previously implemented or proposed constructors.     

The complexity of graph languages generated by hyperedge replacement

Summary Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.Parts of the results of this paper were presented at 15^th ICALP, [La88b]     

A class of linearly parsable graph grammars

Summary Specializing an existing graph grammar model we look in detail at node context-free graph grammars. With a slight generalization the parse trees for context-free Chomsky grammars can be used to describe derivations of these graph grammars.As shown already in former works the precedence graph grammars are defined as a subclass of context-free graph grammars by certain algebraic restrictions on the form of the rules. Then we can prove that every precedence grammar is unambiguous and additionally the reduction process in such a grammar read as replacement system is finite.The most important aim in defining the predence relations was a simple parsing method. This is realized because it is shown that the syntactic analysis for precedence graph grammars can be done in a time which linearly depends on the size of the input graph.The whole method has been implemented and a documentation is available.     

A parsing methodology for the implementation of visual systems

The Visual Language Compiler-Compiler (VLCC) is a grammar-based graphical system for the automatic generation of visual programming environments. In this paper the theoretical and algorithmic issues of VLCC are discussed in detail. The parsing methodology we present is based on the “positional grammar” model. Positional grammars naturally extend context-free grammars by considering new relations in addition to string concatenation. Thanks to this, most of the results from LR parsing can be extended to the positional grammars inheriting the well known LR technique efficiency. In particular, we provide algorithms to implement a YACC-like tool embedded in the VLCC system for automatic compiler generation of visual languages described by positional grammars     

An LR parsing technique for extended context-free grammars

Extended context-free grammars allow regular expressions to appear in productions right hand sides, and are a clear and natural way to describe the syntax of programming languages.In this paper an LR parsing technique for extended context-free grammars is presented, which is based on an underlying transformation of the grammar into an equivalent context-free one.The technique is suitable for inclusion in one-pass compilers: the implementation requires little extensions to the algorithms working for normal LR grammars. Besides describing the parsing method, the paper shows also the algorithms for deriving the parsing tables; tables optimization is also discussed. Finally, this technique is compared with other proposals appeared in the literature.     

Specifications and an implementation of the type-ambiguity problem in pascal

Certain ambiguities in the definition of Pascal imperil the portability of Pascal programs. Specifications and an implementation of alternative interpretations are presented. Context-free grammars augmented with guarded commands are demonstrated as a notation for specifying the static context-sensitive constraints of programming languages. Most of the advantages of context-free grammars are preserved and yet the potential range of the syntactic definition component has been extended to encompass all static constraints. Context-sensitive syntax typically tends to either clutter the semantic definition component or (as with type equivalence in Pascal) result in undesirable implementor-dependent decisions. An implementation of a CFG-based parser that automatically checks for the defined context-sensitive constraints is also described. In addition stepwise abstraction is introduced as a practical technique for communicating formal programming language definitions.     

一种特殊的上下文无关文法及其语法分析

SAQ系统是一个进行软件规约获取、检验和复用的实验系统，其中以上下文无关文法表示的概念是规约的一部分.SAQ要求将概念的词法和句法定义结合在一个上下文无关文法中.如果用常规的上下文无关文法描述诸如程序设计语言和自然语言等一些复杂概念的语法，则需要把诸如空格和回车等没有实质意义的分隔符包含到语法中去(这种描述方法称为朴素表示法),使得语法描述很累赘.为此，作者设计了一种特殊的上下文无关文法,它把通常上下文无关文法定义中的非终极符集合和终极符集合进行细化.用这种文法可以相对简洁地描述程序语言和自然语言等复杂概     

Parsing nonlinear languages

The diagrammatic approach to user interfaces for computer-aided software development toolkits, visual query systems, and visual programming environments, is based on the use of diagrams and charts traditionally drawn on paper. In particular, the VLG system (Visual Language Generator) has been proposed to generate icon-oriented visual languages customized for given applications. The syntactical model underlying the interpretation of a visual language in VLG has been designed to describe icon-oriented visual languages. In order to enable the VLG system to apply to any kind of graphical languages, like diagrammatic ones, it is necessary to find a more general syntactical model able to support both their generation and interpretation. This paper addresses the comprehension of the features that a grammatical formalism for nonlinear languages must have to match any requirement for an efficient parsing. To this aim, relation grammars support an easy implementation of a general parsing algorithm for multidimensional languages, parametric with respect to the rewriting rules of the grammar. We compare the expressive power of relation grammars to grammatical formalisms for graph grammars