| 摘要: |
| 图语法将字符串上的形式文法扩充为图上的形式文法,提供一种能够使用精确的数学方法来模拟图变换的机制.提出了几种新的基于一致图语法的方法来表示控制流图、数据流图、控制数据流图、二分图和超图,并说明如何通过图重写来自动生成依赖图并挖掘并行性,从而协助并行编译器和并行语言的设计和实现. |
| 关键词: 框架图语法 图重写 依赖图 超图 编译 |
| DOI： |
| 分类号: |
| 基金项目: |
|
| Dependency Graphs Embedding Confluent Graph Grammars |
|
LI Guo-Dong,ZHANG De-Fu
|
| Abstract: |
| Graph grammars have been 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. In this paper, 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. |
| Key words: graph grammar graph rewriting dependency graph hypergraph compiling |
