Visible to the public Partial Precedence of Context-sensitive Graph Grammars

TitlePartial Precedence of Context-sensitive Graph Grammars
Publication TypeConference Paper
Year of Publication2017
AuthorsZou, Yang, Zeng, Xiaoqin, Liu, Yufeng, Liu, Huiyi
Conference NameProceedings of the 10th International Symposium on Visual Information Communication and Interaction
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-5292-5
Keywordscomposability, confinement, context-sensitive graph grammars, Cyber-physical systems, efficiency, parsing algorithms, partial precedence graph, privacy, pubcrawl, resilience, Resiliency, visual languages
AbstractContext-sensitive graph grammars have been rigorous formalisms for specifying visual programming languages, as they possess sufficient expressive powers and intuitive forms. Efficient parsing mechanisms are essential to these formalisms. However, the existent parsing algorithms are either inefficient or confined to a minority of graph grammars. This paper introduces the notion of partial precedence, defines the partial precedence graph of a graph grammar and theoretically unveils the existence of a valid parsing path conforming to the topological orderings of the partial precedence graph. Then, it provides algorithms for computing the partial precedence graph and presents an approach to improving general parsing algorithms with the graph based on the drawn conclusion. It is shown that the approach can considerably improve the efficiency of general parsing algorithms.
Citation Keyzou_partial_2017