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

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_TOKEN, Constants::INVALID_TOKEN_TYPE, 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

- (Wizard) initialize(options = {})



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

- (Object) adaptor

Returns the value of attribute adaptor



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

def adaptor
  @adaptor
end

- (Object) token_scheme

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

- (Object) create(pattern)



337
338
339
# File 'lib/antlr3/tree/wizard.rb', line 337

def create( pattern )
  PatternParser.parse( pattern, @token_scheme, @adaptor )
end

- (Object) equals(tree_a, tree_b, adaptor = @adaptor)



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

- (Object) find(tree, what)



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

- (Object) find_pattern(tree, pattern)



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

- (Object) find_token_type(tree, type)



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

- (Boolean) in_context?(tree, context)



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

- (Object) index(tree, map = {})



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

- (Object) match(tree, pattern)



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

- (Object) visit(tree, what = nil, &block)



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

- (Object) visit_all(tree, parent = nil) {|tree, parent, index, nil| ... }

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

- (Object) visit_pattern(tree, pattern, &block)



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

- (Object) visit_type(tree, parent, type, &block)



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