Class: ANTLR3::AST::Wizard

Inherits:
Object
  • Object
show all
Includes:
Constants, Util
Defined in:
lib/antlr3/tree/wizard.rb

Overview

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

Defined Under Namespace

Classes: Pattern, PatternAdaptor, PatternLexer, PatternParser, WildcardPattern

Constant Summary collapse

DOT_DOT_PATTERN = 
/.*[^\.]\\.{2}[^\.].*/
DOUBLE_ETC_PATTERN = 
/.*\.{3}\s+\.{3}.*/

Constants included from Constants

Constants::BUILT_IN_TOKEN_NAMES, Constants::DEFAULT, Constants::DOWN, Constants::EOF, Constants::EOF_TOKEN, Constants::EOR_TOKEN_TYPE, Constants::HIDDEN, Constants::INVALID, Constants::INVALID_NODE, Constants::INVALID_TOKEN, Constants::MEMO_RULE_FAILED, Constants::MEMO_RULE_UNKNOWN, Constants::MIN_TOKEN_TYPE, Constants::SKIP_TOKEN, Constants::UP

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Util

parse_version, silence_warnings, snake_case, tidy

Constructor Details

#initialize(options = {}) ⇒ Wizard

Returns a new instance of Wizard.



328
329
330
331
332
333
334
335
 
# 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

Instance Attribute Details

#adaptor ⇒ Object

Returns the value of attribute adaptor.



326
327
328
 
# File 'lib/antlr3/tree/wizard.rb', line 326

def adaptor
  @adaptor
end

#token_scheme ⇒ Object

Returns the value of attribute token_scheme.



326
327
328
 
# File 'lib/antlr3/tree/wizard.rb', line 326

def token_scheme
  @token_scheme
end

Instance Method Details

#create(pattern) ⇒ Object 



337
338
339
 
# 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) ⇒ Object 



444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
 
# 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) ⇒ Object 



350
351
352
353
354
355
356
357
 
# 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) ⇒ Object 



365
366
367
368
369
 
# 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) ⇒ Object 



359
360
361
362
363
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
 
# 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 = {}) ⇒ Object 



341
342
343
344
345
346
347
348
 
# 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) ⇒ Object 



416
417
418
419
420
 
# 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) ⇒ Object 



371
372
373
374
375
376
377
378
379
380
381
382
383
384
 
# 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| ... } ⇒ Object

Yields:

  • (tree, parent, index, nil) 


386
387
388
389
390
391
392
 
# 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, &block) ⇒ Object 



403
404
405
406
407
408
409
410
411
412
413
414
 
# 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, &block) ⇒ Object 



394
395
396
397
398
399
400
401
 
# 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