A general parsing algorithm with context matching for context-sensitive graph grammars.
Saved in:
| Title: | A general parsing algorithm with context matching for context-sensitive graph grammars. |
|---|---|
| Authors: | Zou, Yang1 (AUTHOR) yzou@hhu.edu.cn, Zeng, Xiaoqin1 (AUTHOR), Zhu, Yun1 (AUTHOR) |
| Source: | Multimedia Tools & Applications. Jan2022, Vol. 81 Issue 1, p273-297. 25p. |
| Subjects: | Graph grammars, Graph algorithms, Programming languages, Algorithms |
| Abstract: | 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Multimedia Tools & Applications is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | 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. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 13807501 |
| DOI: | 10.1007/s11042-021-11076-8 |
