class ANTLR3::AST::Wizard

AST::Wizard is an extra utility class that allows quick creation of AST objects using definitions writing in ANTLR-style tree definition syntax. It can also define tree patterns, objects that are conceptually similar to regular expressions. Patterns allow a simple method for recursively searching through an AST for a particular node structure. These features make tree wizards useful while testing and debugging AST constructing parsers and tree parsers. This library has been ported to Ruby directly from the ANTLR Python runtime API.

See www.antlr.org/wiki/display/~admin/2007/07/02/Exploring+Concept+of+TreeWizard for more background on the concept of a tree wizard.

Usage

# setting up and creating a tree wizard
token_names = Array.new(4, '') + %w(VAR NUMBER EQ PLUS MINUS MULT DIV)
adaptor     = ANTLR3::AST::CommonTreeAdaptor.new
wizard      = ANTLR3::AST::Wizard.new(adaptor, token_names)

# building trees
lone_node = wizard.create "VAR[x]"   # => x
lone_node.type                       # => 4  # = VAR
lone_node.text                       # => "x"

expression_node = wizard.create "(MINUS VAR NUMBER)"
  # => (MINUS VAR NUMBER)
statement_node = wizard.create "(EQ[=] VAR[x] (PLUS[+] NUMBER[1] NUMBER[2]))" 
  # => (= x (+ 1 2))
deep_node = wizard.create(<<-TREE)
  (MULT[*] NUMBER[1] 
    (MINUS[-] 
      (MULT[*] NUMBER[3]    VAR[x])
      (DIV[/]  VAR[y] NUMBER[3.14])
      (MULT[*] NUMBER[4]    VAR[z])
    )
  )
TREE
  # => (* 1 (- (* 3 x) (/ y 3.14) (* 4 z))

bad_tree_syntax = wizard.create "(+ 1 2)"
  # => nil - invalid node names

# test whether a tree matches a pattern
wizard.match(expression_node, '(MINUS VAR .)') # => true
wizard.match(lone_node, 'NUMBER NUMBER')       # => false

# extract nodes matching a pattern
wizard.find(statement_node, '(PLUS . .)')
# => [(+ 1 2)]
wizard.find(deep_node, 4)  # where 4 is the value of type VAR
# => [x, y, z]

# iterate through the tree and extract nodes with pattern labels
wizard.visit(deep_node, '(MULT %n:NUMBER %v:.)') do |node, parent, local_index, labels|
  printf "n = %p\n, v = %p\n", labels['n'], labels['v']
end
  # => prints out:
  # n = 3, v = x
  # n = 4, v = z

Tree Construction Syntax

Simple Token Node:     TK
Token Node With Text:  TK[text]
Flat Node List:        (nil TK1 TK2)
General Node:          (RT TK1 TK2)
Complex Nested Node:   (RT (SUB1[sometext] TK1) TK2 (SUB2 TK3 TK4[moretext]))

Additional Syntax for Tree Matching Patterns

Match Any Token Node:  .
Label a Node:          %name:TK

Constants

DOT_DOT_PATTERN
DOUBLE_ETC_PATTERN

Attributes

adaptor[RW]
token_scheme[RW]

Public Class Methods

new( options = {} ) click to toggle source
# File lib/antlr3/tree/wizard.rb, line 328
def initialize( options = {} )
  @token_scheme = options.fetch( :token_scheme ) do
    TokenScheme.build( options[ :token_class ], options[ :tokens ] )
  end
  @adaptor = options.fetch( :adaptor ) do
    CommonTreeAdaptor.new( @token_scheme.token_class )
  end
end

Public Instance Methods

create( pattern ) click to toggle source
# File lib/antlr3/tree/wizard.rb, line 337
def create( pattern )
  PatternParser.parse( pattern, @token_scheme, @adaptor )
end
equals( tree_a, tree_b, adaptor = @adaptor ) click to toggle source
# File lib/antlr3/tree/wizard.rb, line 444
def equals( tree_a, tree_b, adaptor = @adaptor )
  tree_a && tree_b or return( false )
  
  adaptor.type_of( tree_a ) == adaptor.type_of( tree_b ) or return false
  adaptor.text_of( tree_a ) == adaptor.text_of( tree_b ) or return false
  
  child_count_a = adaptor.child_count( tree_a )
  child_count_b = adaptor.child_count( tree_b )
  child_count_a == child_count_b or return false
  
  child_count_a.times do | i |
    child_a = adaptor.child_of( tree_a, i )
    child_b = adaptor.child_of( tree_b, i )
    equals( child_a, child_b, adaptor ) or return false
  end
  return true
end
find( tree, what ) click to toggle source
# File lib/antlr3/tree/wizard.rb, line 350
def find( tree, what )
  case what
  when Integer then find_token_type( tree, what )
  when String  then find_pattern( tree, what )
  when Symbol  then find_token_type( tree, @token_scheme[ what ] )
  else raise ArgumentError, "search subject must be a token type (integer) or a string"
  end
end
find_pattern( tree, pattern ) click to toggle source
# File lib/antlr3/tree/wizard.rb, line 365
def find_pattern( tree, pattern )
  subtrees = []
  visit_pattern( tree, pattern ) { | t, | subtrees << t }
  return( subtrees )
end
find_token_type( tree, type ) click to toggle source
# File lib/antlr3/tree/wizard.rb, line 359
def find_token_type( tree, type )
  nodes = []
  visit( tree, type ) { | t, | nodes << t }
  return nodes
end
in_context?( tree, context ) click to toggle source
# File lib/antlr3/tree/wizard.rb, line 466
def in_context?( tree, context )
  case context
  when DOT_DOT_PATTERN then raise ArgumentError, "invalid syntax: .."
  when DOUBLE_ETC_PATTERN then raise ArgumentError, "invalid syntax: ... ..."
  end
  
  context = context.gsub( /([^\.\s])\.{3}([^\.])/, '\1 ... \2' )
  context.strip!
  nodes = context.split( /\s+/ )
  
  while tree = @adaptor.parent( tree ) and node = nodes.pop
    if node == '...'
      node = nodes.pop or return( true )
      tree = @adaptor.each_ancestor( tree ).find do | t |
        @adaptor.type_name( t ) == node
      end or return( false )
    end
    @adaptor.type_name( tree ) == node or return( false )
  end
  
  return( false ) if tree.nil? and not nodes.empty?
  return true
end
index( tree, map = {} ) click to toggle source
# File lib/antlr3/tree/wizard.rb, line 341
def index( tree, map = {} )
  tree or return( map )
  type = @adaptor.type_of( tree )
  elements = map[ type ] ||= []
  elements << tree
  @adaptor.each_child( tree ) { | child | index( child, map ) }
  return( map )
end
match( tree, pattern ) click to toggle source
# File lib/antlr3/tree/wizard.rb, line 416
def match( tree, pattern )
  pattern = Pattern.parse( pattern, @token_scheme )
  
  return( match!( tree, pattern ) )
end
visit( tree, what = nil, &block ) click to toggle source
# File lib/antlr3/tree/wizard.rb, line 371
  def visit( tree, what = nil, &block )
    block_given? or return enum_for( :visit, tree, what )
    Symbol === what and what = @token_scheme[ what ]
    case what
    when nil then visit_all( tree, &block )
    when Integer then visit_type( tree, nil, what, &block )
    when String  then visit_pattern( tree, what, &block )
    else raise( ArgumentError, tidy( <<-'END', true ) )
      | The 'what' filter argument must be a tree
      | pattern (String) or a token type (Integer)
      | -- got #{ what.inspect }
      END
    end
  end
visit_all( tree, parent = nil ) { |tree, parent, index, nil| ... } click to toggle source
# File lib/antlr3/tree/wizard.rb, line 386
def visit_all( tree, parent = nil, &block )
  index = @adaptor.child_index( tree )
  yield( tree, parent, index, nil )
  @adaptor.each_child( tree ) do | child |
    visit_all( child, tree, &block )
  end
end
visit_pattern( tree, pattern ) { |tree, parent, child_index, labels| ... } click to toggle source
# File lib/antlr3/tree/wizard.rb, line 403
def visit_pattern( tree, pattern, &block )
  pattern = Pattern.parse( pattern, @token_scheme )
  
  if pattern.nil? or pattern.flat_list? or pattern.is_a?( WildcardPattern )
    return( nil )
  end
  
  visit( tree, pattern.type ) do | tree, parent, child_index, labels |
    labels = match!( tree, pattern ) and
      yield( tree, parent, child_index, labels )
  end
end
visit_type( tree, parent, type ) { |tree, parent, index, nil| ... } click to toggle source
# File lib/antlr3/tree/wizard.rb, line 394
def visit_type( tree, parent, type, &block )
  tree.nil? and return( nil )
  index = @adaptor.child_index( tree )
  @adaptor.type_of( tree ) == type and yield( tree, parent, index, nil )
  @adaptor.each_child( tree ) do | child |
    visit_type( child, tree, type, &block )
  end
end

Private Instance Methods

match!( tree, pattern, labels = {} ) click to toggle source
# File lib/antlr3/tree/wizard.rb, line 422
def match!( tree, pattern, labels = {} )
  tree.nil? || pattern.nil? and return false
  unless pattern.is_a? WildcardPattern
    @adaptor.type_of( tree ) == pattern.type or return false
    pattern.has_text_arg && ( @adaptor.text_of( tree ) != pattern.text ) and
      return false
  end
  labels[ pattern.label ] = tree if labels && pattern.label
  
  number_of_children = @adaptor.child_count( tree )
  return false unless number_of_children == pattern.child_count
  
  number_of_children.times do |index|
    actual_child = @adaptor.child_of( tree, index )
    pattern_child = pattern.child( index )
    
    return( false ) unless match!( actual_child, pattern_child, labels )
  end
  
  return labels
end