A context-sensitive graph grammar formalism for the specification of visual languages

Da Qian Zhang, Kang Zhang, Jiannong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

96 Citations (Scopus)

Abstract

Graph grammars may be used as natural and powerful syntax-definition formalisms for visual programming languages. Yet most graph-grammar parsing algorithms presented so far are either unable to recognize interesting visual languages or tend to be inefficient (with exponential time complexity) when applied to graphs with a large number of nodes and edges. This paper presents a context-sensitive graph grammar called reserved graph grammar, which can explicitly and completely describe the syntax of a wide range of diagrams using labeled graphs. The parsing algorithm of a reserved graph grammar uses a marking mechanism to avoid ambiguity in parsing and has polynomial time complexity in most cases. The paper defines a constraint condition under which a graph defined in a reserved graph grammar can be parsed in polynomial time. An algorithm for checking the condition is also provided.
Original languageEnglish
Pages (from-to)186-200
Number of pages15
JournalComputer Journal
Volume44
Issue number3
DOIs
Publication statusPublished - 1 Dec 2001

ASJC Scopus subject areas

  • Computer Science(all)

Cite this