The Computer Journal · 2001 · 115 citations · 10 references
ComputingComputer ScienceComputational LinguisticsFormal MethodsSyntaxFormal Language FoundationsGraph TheorySpecification LanguagesVisual LanguageVisual Syntax
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.
10
Kim Marriott · 2002 · 133 citations
Language Studies, Computer Science, Natural Language Processing +12
Automatic generation of visual programming environments
Gennaro Costagliola, Genoveffa Tortora, Sergio Orefice et al. · Computer · 1995 · 90 citations