Title: A General Parsing Algorithm with Context Matching for Context-Sensitive Graph Grammars
Abstract: Context-sensitive graph grammars have been intuitiveand 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, one is context matching, and the other is production set partitioning.The two strategies can greatly narrow down the search space of redexes and thus considerably improve the parsing performance, even though the worst-case time complexity is not theoretically reduced.Moreover, a case study along with detailed analysis is provided to demonstrate the paring process and parsing performance of the proposed algorithm.