[1] Zou Yang, Zeng Xiaoqin, Han Xiuqing, Zhang Kang, et al. Context-attributed graph grammar frameworkfor specifying visual languages [J]. Journal of Southeast University (English Edition), 2008, 24 (4): 455-461. [doi:10.3969/j.issn.1003-7985.2008.04.012]

Copy

Context-attributed graph grammar frameworkfor specifying visual languages()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

24

Issue:

2008 4

Page:

455-461

Research Field:

Computer Science and Engineering

Publishing date:

2008-12-30

Info

Title:

Context-attributed graph grammar frameworkfor specifying visual languages

Author(s):

Zou Yang¹;  Zeng Xiaoqin¹;  Han Xiuqing¹;  Zhang Kang²

¹College of Computer and Information Engineering, Hohai University, Nanjing 210098, China
²Department of Computer Science, University of Texas at Dallas, Texas 75080-3021, USA

Keywords:

visual language;  graph grammar;  context-attributed;  parsing;  confluence

PACS:

TP301.2

DOI:

10.3969/j.issn.1003-7985.2008.04.012

Abstract:

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.

References:

[1] Ferrucci F, Tortora G, Tucci M, et al.A predictive parser for visual languages specified by relation grammars [C]//Proc IEEE Symposium on Visual Languages.St.Louis, Missouri, USA, 1994:245-252.
[2] Wittenburg K, Weitzman L, Talley J.Unification-based grammars and tabular parsing for graphical languages [J].Journal of Visual Languages and Computing, 1991, 2(4):347-370.
[3] Marriott K.Constraint multiset grammars [C]//Proc IEEE Symposium on Visual Languages.St.Louis, Missouri, USA, 1994:118-125.
[4] Rozenberg G.Handbook on graph grammars and computing by graph transformation:foundations[M].World Scientific, 1997:1-94.
[5] Drewes F, Hoffmann B, Janssens D, et al.Adaptive star grammars [C]//ICGT2006, LNCS 4178.Berlin:Springer, 2006:77-91.
[6] Rekers J, Schürr A.Defining and parsing visual languages with layered graph grammars [J].Journal of Visual Languages and Computing, 1997, 8(1):27-55.
[7] Bottoni P, Taentzer G, Schürr A.Efficient parsing of visual languages based on critical pair analysis and contextual layered graph transformation [C]//Proc IEEE Symposium on Visual Languages.Seattle, Washington, USA, 2000:59-60.
[8] Kong J, Zhang K.Parsing spatial graph grammars [C]//Proc IEEE Symposium on Visual Languages and Human-Centric Computing.Rome, Italy, 2004:99-101.
[9] Minas M.Parsing of adaptive star grammars [C]//Proc 2nd International Workshop on Graph and Model Transformation.Brighton, UK, 2006, 4:1-15.
[10] Zhang D Q, Zhang K, Cao J.A context-sensitive graph grammar formalism for the specification of visual languages [J].The Computer Journal, 2001, 44(3):187-200.
[11] Zeng X, Zhang K, Kong J, et al.RGG+:an enhancement to the reserved graph grammar formalism [C]//Proc IEEE Symposium on Visual Languages and Human-Centric Computing. Dallas, TX, USA, 2005:272-274.

Memo

Memo:

Biography: Zou Yang(1976—), male, lecturer, yzou@hhu.edu.cn.
Foundation items: The National Natural Science Foundation of China(No.60571048, 60673186, 60736015), the National High Technology Research and Development Program of China(863 Program)(No.2007AA01Z178).
Citation: Zou Yang, Zeng Xiaoqin, Han Xiuqing, et al.Context-attributed graph grammar framework for specifying visual languages[J].Journal of Southeast University(English Edition), 2008, 24(4):455-461.

Common functions