Skip to content

Predefined Data Structures

Jump to bottom
Christoph Matheja edited this page Apr 4, 2018 · 1 revision

This page lists and briefly explains all built-in graph grammars of Attestor. These grammars can be used without providing a grammar file (see command line options). Every predefined grammar makes certain assumptions about the the underlying classes, e.g. the names of selectors. These assumptions can be modified using the renaming option.

Furthermore, notice that a collection of customized graph grammars is found in the examples repository.

Structure

For each predefined grammar, we collect the name of the grammar, which is used to tell Attestor to use the grammar's rules for abstraction. Moreover, we provide a grammar file that can be modified to create a customized grammar. We also describe a class definition of the underlying data structure and key figures about types, selectors, nonterminals, and external nodes belonging to the grammar.

Singly-linked list segments

Name of the grammar:
RefSLL

A complete grammar file is found here.

Java class
 class ListNode {
      public ListNode next;
 }
Key data
  • Node types: 1
    • ListNode
  • Selectors: 1
    • next: pointer to successor of a list element
  • Nonterminals: 1
    • RefSLList
  • External nodes: 2
    • 0: head of the list segment
    • 1: tail of the list segment

Doubly-linked list segments

Name of the grammar:
RefDLL

A complete grammar file is found here.

Java class
 class DLListNode {
      public DLListNode next;
      public DLListNode prev;
 }
Key data
  • Node types: 1
    • DLListNode
  • Selectors: 2
    • next: pointer to successor of a list element
    • prev: pointer to predecessor of a list element
  • Nonterminals: 1
    • RefDLList
  • External nodes: 4
    • 0: predecessor of the head of the list segment
    • 1: head of the list segment
    • 2: tail of the list segment
    • 3: successor of the tail of the list segment

Binary Trees

Name of the grammar:
RefBT

A complete grammar file is found here.

Java class
 class BTNode {
      public BTNode left;
      public BTNode right;
 }
Key data
  • Node types: 2
    • NULL: null location
    • BTNode: element of the binary tree
  • Selectors: 2
    • left: pointer to left child of a node in the tree
    • right: pointer to right child of a node in the tree
  • Nonterminals: 2
    • RefBT: Binary tree
    • RefTP: Binary tree segment
  • External nodes: 2
    • 0: null location
    • 1: root of the tree
Clone this wiki locally