Loading...
Please wait, while we are loading the content...
Similar Documents
P L ] 2 3 O ct 2 01 7 Graph-Based Shape Analysis Beyond Context-Freeness
| Content Provider | Semantic Scholar |
|---|---|
| Author | Arndt, Hannah Jansen, Christina Matheja, Christoph Noll, Thomas |
| Copyright Year | 2017 |
| Abstract | The aim of shape analysis is to discover precise abstractions of the reachable data structures in a program’s heap. This paper develops a shape analysis for reasoning about relational properties of data structures. Both the concrete and the abstract domain are represented by hypergraphs. The analysis is parameterized by user-supplied indexed graph grammars to guide concretization and abstraction. This novel extension of context-free graph grammars is powerful enough to model complex data structures, such as balanced binary trees with parent pointers, while preserving most desirable properties of context-free graph grammars. One strength of our analysis is that no artifacts apart from grammars are required from the user; it thus offers a high degree of automation. We implemented our analysis and successfully applied it to various programs manipulating AVL trees, (doubly-linked) lists, and combinations of both. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://export.arxiv.org/pdf/1705.03754 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
