A general parsing algorithm with context matching for context-sensitive graph grammars

Context-sensitive graph grammars have been intuitive and rigorous formalisms for specifying visual programming languages, as they are sufficient expressive and equipped with parsing mechanisms. Parsing has been a fundamental issue in the research of context-sensitive graph grammars. However, the existent parsing algorithms are either inefficient or confined to a minority of graph grammars. This paper proposes a general parsing algorithm with two embedded strategies, context matching and production-set partitioning. The two strategies can greatly narrow down the search space of redexes and thus significantly improve parsing efficiency, even though the worst-case time complexity is not theoretically reduced. Moreover, a detailed case study and an experiment are provided accordingly to demonstrate the paring process and performance of the proposed algorithm.