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