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
attr_accessor :parent
attr_reader :children
Public Instance Methods
# File lib/antlr3/tree.rb, line 277 def ancestors each_ancestor.to_a end
# File lib/antlr3/tree.rb, line 258 def depth root? ? 0 : parent.depth + 1 end
# 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
# File lib/antlr3/tree.rb, line 254 def has_child?( node ) children and children.include?( node ) end
# File lib/antlr3/tree.rb, line 250 def leaf? children.nil? or children.empty? end
# 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
# File lib/antlr3/tree.rb, line 235 def root? parent.nil? end
# File lib/antlr3/tree.rb, line 262 def siblings root? and return [] parent.children.reject { | c | c.equal?( self ) } end
# 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