module ANTLR3::AST::Tree

ANTLR Abstract Syntax Trees

As ANTLR is concerned, an Abstract Syntax Tree (AST) node is an object that wraps a token, a list of child trees, and some information about the collective source text embodied within the tree and its children.

The Tree module, like the Token and Stream modules, emulates an abstract base class for AST classes; it specifies the attributes that are expected of basic tree nodes as well as the methods trees need to implement.

Terminology

While much of this terminology is probably familiar to most developers, the following brief glossary is intended to clarify terminology used in code throughout the AST library:

payload

either a token value contained within a node or nil

flat list (nil tree)

a tree node without a token payload, but with more than one children – functions like an array of tree nodes

root

a top-level tree node, i.e. a node that does not have a parent

leaf

a node that does not have any children

siblings

all other nodes sharing the same parent as some node

ancestors

the list of successive parents from a tree node to the root node

error node

a special node used to represent an erroneous series of tokens from an input stream

Attributes

child_index[RW]
column[R]
line[R]
start_index[RW]

attr_accessor :parent

stop_index[RW]
text[R]
token[R]

attr_reader :children

type[R]

Public Instance Methods

ancestors() click to toggle source
# File lib/antlr3/tree.rb, line 277
def ancestors
  each_ancestor.to_a
end
depth() click to toggle source
# File lib/antlr3/tree.rb, line 258
def depth
  root? ? 0 : parent.depth + 1
end
detached?()
Alias for: root?
each_ancestor() { |parent_node = parent| ... } click to toggle source
# File lib/antlr3/tree.rb, line 267
def each_ancestor
  block_given? or return( enum_for( :each_ancestor ) )
  cursor = self
  until cursor.root?
    yield( parent_node = cursor.parent )
    cursor = parent_node
  end
  return( self )
end
has_child?( node ) click to toggle source
# File lib/antlr3/tree.rb, line 254
def has_child?( node )
  children and children.include?( node )
end
leaf?() click to toggle source
# File lib/antlr3/tree.rb, line 250
def leaf?
  children.nil? or children.empty?
end
root() { |parent_node = parent| ... } click to toggle source
# File lib/antlr3/tree.rb, line 240
def root
  cursor = self
  until cursor.root?
    yield( parent_node = cursor.parent )
    cursor = parent_node
  end
  return( cursor )
end
root?() click to toggle source
# File lib/antlr3/tree.rb, line 235
def root?
  parent.nil?
end
Also aliased as: detached?
siblings() click to toggle source
# File lib/antlr3/tree.rb, line 262
def siblings
  root? and return []
  parent.children.reject { | c | c.equal?( self ) }
end
walk() { |cursor| ... } click to toggle source
# File lib/antlr3/tree.rb, line 281
def walk
  block_given? or return( enum_for( :walk ) )
  stack = []
  cursor = self
  while true
    begin
      yield( cursor )
      stack.push( cursor.children.dup ) unless cursor.empty?
    rescue StopIteration
      # skips adding children to prune the node
    ensure
      break if stack.empty?
      cursor = stack.last.shift
      stack.pop if stack.last.empty?
    end
  end
  return self
end