| Title | Partial Precedence of Context-sensitive Graph Grammars |
| Publication Type | Conference Paper |
| Year of Publication | 2017 |
| Authors | Zou, Yang, Zeng, Xiaoqin, Liu, Yufeng, Liu, Huiyi |
| Conference Name | Proceedings of the 10th International Symposium on Visual Information Communication and Interaction |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-5292-5 |
| Keywords | composability, confinement, context-sensitive graph grammars, Cyber-physical systems, efficiency, parsing algorithms, partial precedence graph, privacy, pubcrawl, resilience, Resiliency, visual languages |
| Abstract | Context-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. |
| URL | http://doi.acm.org/10.1145/3105971.3105983 |
| DOI | 10.1145/3105971.3105983 |
| Citation Key | zou_partial_2017 |
Partial Precedence of Context-sensitive Graph Grammars