嵌入一致图语法的依赖图(英文)  

Dependency Graphs Embedding Confluent Graph Grammars

作　　者：李国东[1] 张德富[1] 

机构地区：[1]南京大学计算机软件新技术国家重点实验室,江苏南京210093

出　　处：《软件学报》2004年第7期956-968,共13页Journal of Software

摘　　要：图语法将字符串上的形式文法扩充为图上的形式文法,提供一种能够使用精确的数学方法来模拟图变换的机制.提出了几种新的基于一致图语法的方法来表示控制流图、数据流图、控制数据流图、二分图和超图,并说明如何通过图重写来自动生成依赖图并挖掘并行性,从而协助并行编译器和并行语言的设计和实现.Graph grammars are developed as an extension of the formal grammars on strings to grammars on graphs, and provide a mechanism in which transformations on graphs can be modeled in a mathematically precise way. Based on confluent graph grammars, the authors present a novel representation for data-flow graphs, control-flow graphs, combined control-data-graphs, bipartite graphs and hyperedge graphs. How to extract parallelism is specified automatically at different levels by graph rewriting, thus facilitating the design and implementation of parallel compilers and parallel languages.

关 键 词：框架图语法 图重写 依赖图 超图 编译 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]