標題: 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
顯示於類別:期刊論文


文件中的檔案:

  1. 000087521000002.pdf