Context-attributed graph grammar framework for specifying visual languages  

一个描述可视化语言上下文属性化的图文法框架(英文)

作　　者：邹阳[1] 曾晓勤[1] 韩秀清[1] 张康[2] 

机构地区：[1]河海大学计算机及信息工程学院,南京210098 [2]德克萨斯大学达拉斯分校计算机科学系,美国德克萨斯750803021

出　　处：《Journal of Southeast University(English Edition)》2008年第4期455-461,共7页东南大学学报（英文版）

基　　金：The National Natural Science Foundation of China(No.60571048,60673186,60736015);the National High Technology Researchand Development Program of China(863Program)(No.2007AA01Z178)

摘　　要：Since the specifications of most of the existing context-sensitive graph grammars tend to be either too intricate or not intuitive, a novel context-sensitive graph grammar formalism, called context-attributed graph grammar（CAGG）, is proposed. In order to resolve the embedding problem, context information of a graph production in the CAGG is represented in the form of context attributes of the nodes involved. Moreover, several properties of a set of confluent CAGG productions are characterized, and then an algorithm based on them is developed to decide whether or not a set of productions is confluent, which provides the foundation for the design of efficient parsing algorithms. It can also be shown through the comparison of CAGG with several typical context-sensitive graph grammars that CAGG is more succinct and, at the same time, more intuitive than the others, making it more suitably and effortlessly applicable to the specification of visual languages.针对目前已有的上下文相关图文法的描述规范过于复杂或不太直观,提出了一个新的上下文相关图文法的形式框架:上下文属性化的图文法CAGG.该文法将产生式的上下文信息刻画成相关结点的上下文属性来解决嵌入问题.而且进一步分析了合流的CAGG产生式集合的基本特征,并基于此设计了合流产生式集合的判定算法,从而为构造高效的语法分析算法奠定了基础.通过与已有上下文相关图文法的对比分析可知,CAGG图文法的形式更为简洁和直观,因而更适于且更易于应用到可视化语言描述领域.

关 键 词：visual language graph grammar context-attributed PARSING CONFLUENCE 

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