Reserved graph grammar: a specification tool for diagrammatic VPLs
- 23 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 284-291
- https://doi.org/10.1109/vl.1997.626596
Abstract
When implementing textual languages, formal grammars are commonly used to facilitate understanding languages and creating parsers. In the implementation of a diagrammatic visual programming language (VPL), this rarely happens, though graph grammars with their well established theoretical background may be used as a natural and powerful syntax definition formalism. Yet all graph grammar parsing algorithms presented up to now are either unable to recognize interesting visual languages or tend to be hopelessly inefficient (with exponential time complexity) when applied to graphs with a large number of nodes and edges. The paper presents a context sensitive graph grammar called reserved graph grammar which can explicitly, efficiently and completely describe the syntax of a wide range of diagrams using labeled graphs. Moreover its parsing algorithm is of polynomial time complexity in most cases.Keywords
This publication has 6 references indexed in Scilit:
- Parsing of graphs in linear timePublished by Springer Nature ,2005
- Earley-style parsing for relational grammarsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Relational Grammars: Theory and Practice in a Visual Language Interface for Process ModelingPublished by Springer Nature ,1998
- Automated Program Recognition by Graph ParsingPublished by Defense Technical Information Center (DTIC) ,1992
- A parser for context free plex grammarsPublished by Springer Nature ,1990
- Boundary NLC graph grammars—Basic definitions, normal forms, and complexityInformation and Control, 1986