標題: | A finest partitioning algorithm for attribute grammars |
作者: | Yang, W 資訊工程學系 Department of Computer Science |
關鍵字: | attribute grammars;partitioning;strictness analysis;parallel evaluation |
公開日期: | 1-十月-1999 |
摘要: | The attribute dependence graph of a syntax tree may be partitioned into disjoint regions. Attribute instances in different regions are independent of one other. The advantages of partitioning the attribute dependence graph include simplifying the attribute grammar conceptually and allowing the possibility of parallel evaluation. We present a static partitioning algorithm for attribute grammars. The algorithm builds the set of all feasible partitions for every production by analyzing the grammar. After the attributed syntax tree is constructed, one of the feasible partitions is chosen for each production instance in the syntax tree. Gluing together the selected partitions for individual production instances results in a partition of the attribute dependence graph of the syntax tree. No further merging or partitioning is needed at evaluation time. In addition to static partitioning, the algorithm always produces the finest partition of every attribute dependence graph. An application of the partitioning technique is the strictness analysis for a simple programming language that contains no higher-order functions. (C) 2000 Elsevier Science Ltd. All rights reserved. |
URI: | http://hdl.handle.net/11536/31074 |
ISSN: | 0096-0551 |
期刊: | COMPUTER LANGUAGES |
Volume: | 25 |
Issue: | 3 |
起始頁: | 145 |
結束頁: | 164 |
顯示於類別: | 期刊論文 |