1 #!/usr/bin/ruby 2 # encoding: utf-8 3 4 =begin LICENSE 5 6 [The "BSD licence"] 7 Copyright (c) 2009-2010 Kyle Yetter 8 All rights reserved. 9 10 Redistribution and use in source and binary forms, with or without 11 modification, are permitted provided that the following conditions 12 are met: 13 14 1. Redistributions of source code must retain the above copyright 15 notice, this list of conditions and the following disclaimer. 16 2. Redistributions in binary form must reproduce the above copyright 17 notice, this list of conditions and the following disclaimer in the 18 documentation and/or other materials provided with the distribution. 19 3. The name of the author may not be used to endorse or promote products 20 derived from this software without specific prior written permission. 21 22 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 23 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 24 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 25 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 26 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 27 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 31 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 33 =end 34 35 require 'antlr3' 36 37 module ANTLR3 38 39 =begin rdoc ANTLR3::AST 40 41 Name space containing all of the entities pertaining to tree construction and 42 tree parsing. 43 44 =end 45 46 module AST 47 48 autoload :Wizard, 'antlr3/tree/wizard' 49 autoload :Visitor, 'antlr3/tree/visitor' 50 51 #################################################################################################### 52 ############################################ Tree Parser ########################################### 53 #################################################################################################### 54 55 =begin rdoc ANTLR3::AST::TreeParser 56 57 = TreeParser 58 59 TreeParser is the default base class of ANTLR-generated tree parsers. The class 60 tailors the functionality provided by Recognizer to the task of tree-pattern 61 recognition. 62 63 == About Tree Parsers 64 65 ANTLR generates three basic types of recognizers: 66 * lexers 67 * parsers 68 * tree parsers 69 70 Furthermore, it is capable of generating several different flavors of parser, 71 including parsers that take token input and use it to build Abstract Syntax 72 Trees (ASTs), tree structures that reflect the high-level syntactic and semantic 73 structures defined by the language. 74 75 You can take the information encapsulated by the AST and process it directly in 76 a program. However, ANTLR also provides a means to create a recognizer which is 77 capable of walking through the AST, verifying its structure and performing 78 custom actions along the way -- tree parsers. 79 80 Tree parsers are created from tree grammars. ANTLR-generated tree parsers 81 closely mirror the general structure of regular parsers and lexers. 82 83 For more in-depth coverage of the topic, check out the ANTLR documentation 84 (http://www.antlr.org). 85 86 == The Tree Parser API 87 88 Like Parser, the class does not stray too far from the Recognizer API. 89 Mainly, it customizes a few methods specifically to deal with tree nodes 90 (instead of basic tokens), and adds some helper methods for working with trees. 91 92 Like all ANTLR recognizers, tree parsers contained a shared state structure and 93 an input stream, which should be a TreeNodeStream. ANTLR intends to keep its 94 tree features flexible and customizable, and thus it does not make any 95 assumptions about the class of the actual nodes it processes. One consequence of 96 this flexibility is that tree parsers also require an extra tree adaptor object, 97 the purpose of which is to provide a homogeneous interface for handling tree 98 construction and analysis of your tree nodes. 99 100 See Tree and TreeAdaptor for more information. 101 102 =end 103 104 class TreeParser < Recognizer 105 def self.main( argv = ARGV, options = {} ) 106 if ::Hash === argv then argv, options = ARGV, argv end 107 main = ANTLR3::Main::WalkerMain.new( self, options ) 108 block_given? ? yield( main ) : main.execute( argv ) 109 end 110 111 def initialize( input, options = {} ) 112 super( options ) 113 @input = input 114 end 115 116 alias tree_node_stream input 117 alias tree_node_stream= input= 118 119 def source_name 120 @input.source_name 121 end 122 123 def missing_symbol( error, expected_token_type, follow ) 124 name = token_name( expected_token_type ).to_s 125 text = "<missing " << name << '>' 126 tk = create_token do |t| 127 t.text = text 128 t.type = expected_token_type 129 end 130 return( CommonTree.new( tk ) ) 131 end 132 133 def match_any( ignore = nil ) 134 @state.error_recovery = false 135 136 look, adaptor = @input.look, @input.tree_adaptor 137 if adaptor.child_count( look ) == 0 138 @input.consume 139 return 140 end 141 142 level = 0 143 while type = @input.peek and type != EOF 144 #token_type == EOF or ( token_type == UP && level == 0 ) 145 @input.consume 146 case type 147 when DOWN then level += 1 148 when UP 149 level -= 1 150 level.zero? and break 151 end 152 end 153 end 154 155 def mismatch( input, type, follow = nil ) 156 raise MismatchedTreeNode.new( type, input ) 157 end 158 159 def error_header( e ) 160 <<-END.strip! 161 #{ grammar_file_name }: node from #{ 162 e.approximate_line_info? ? 'after ' : '' 163 } line #{ e.line }:#{ e.column } 164 END 165 end 166 167 def error_message( e ) 168 adaptor = e.input.adaptor 169 e.token = adaptor.token( e.node ) 170 e.token ||= create_token do | tok | 171 tok.type = adaptor.type_of( e.node ) 172 tok.text = adaptor.text_of( e.node ) 173 end 174 return super( e ) 175 end 176 177 def trace_in( rule_name, rule_index ) 178 super( rule_name, rule_index, @input.look ) 179 end 180 181 def trace_out( rule_name, rule_index ) 182 super( rule_name, rule_index, @input.look ) 183 end 184 end 185 186 #################################################################################################### 187 ############################################ Tree Nodes ############################################ 188 #################################################################################################### 189 190 =begin rdoc ANTLR3::AST::Tree 191 192 = ANTLR Abstract Syntax Trees 193 194 As ANTLR is concerned, an Abstract Syntax Tree (AST) node is an object that 195 wraps a token, a list of child trees, and some information about the collective 196 source text embodied within the tree and its children. 197 198 The Tree module, like the Token and Stream modules, emulates an abstract base 199 class for AST classes; it specifies the attributes that are expected of basic 200 tree nodes as well as the methods trees need to implement. 201 202 == Terminology 203 204 While much of this terminology is probably familiar to most developers, the 205 following brief glossary is intended to clarify terminology used in code 206 throughout the AST library: 207 208 [payload] either a token value contained within a node or +nil+ 209 [flat list (nil tree)] a tree node without a token payload, but with more 210 than one children -- functions like an array of 211 tree nodes 212 [root] a top-level tree node, i.e. a node that does not have a parent 213 [leaf] a node that does not have any children 214 [siblings] all other nodes sharing the same parent as some node 215 [ancestors] the list of successive parents from a tree node to the root node 216 [error node] a special node used to represent an erroneous series of tokens 217 from an input stream 218 219 =end 220 221 module Tree 222 223 #attr_accessor :parent 224 attr_accessor :start_index 225 attr_accessor :stop_index 226 attr_accessor :child_index 227 attr_reader :type 228 attr_reader :text 229 attr_reader :line 230 attr_reader :column 231 #attr_reader :children 232 attr_reader :token 233 234 235 def root? 236 parent.nil? 237 end 238 alias detached? root? 239 240 def root 241 cursor = self 242 until cursor.root? 243 yield( parent_node = cursor.parent ) 244 cursor = parent_node 245 end 246 return( cursor ) 247 end 248 249 # 250 def leaf? 251 children.nil? or children.empty? 252 end 253 254 def has_child?( node ) 255 children and children.include?( node ) 256 end 257 258 def depth 259 root? ? 0 : parent.depth + 1 260 end 261 262 def siblings 263 root? and return [] 264 parent.children.reject { | c | c.equal?( self ) } 265 end 266 267 def each_ancestor 268 block_given? or return( enum_for( :each_ancestor ) ) 269 cursor = self 270 until cursor.root? 271 yield( parent_node = cursor.parent ) 272 cursor = parent_node 273 end 274 return( self ) 275 end 276 277 def ancestors 278 each_ancestor.to_a 279 end 280 281 def walk 282 block_given? or return( enum_for( :walk ) ) 283 stack = [] 284 cursor = self 285 while true 286 begin 287 yield( cursor ) 288 stack.push( cursor.children.dup ) unless cursor.empty? 289 rescue StopIteration 290 # skips adding children to prune the node 291 ensure 292 break if stack.empty? 293 cursor = stack.last.shift 294 stack.pop if stack.last.empty? 295 end 296 end 297 return self 298 end 299 300 end 301 302 303 =begin rdoc ANTLR3::AST::BaseTree 304 305 A base implementation of an Abstract Syntax Tree Node. It mainly defines the 306 methods and attributes required to implement the parent-node-children 307 relationship that characterize a tree; it does not provide any logic concerning 308 a node's token <i>payload</i>. 309 310 =end 311 312 class BaseTree < ::Array 313 attr_accessor :parent 314 extend ClassMacros 315 include Tree 316 317 def initialize( node = nil ) 318 super() 319 @parent = nil 320 @child_index = 0 321 end 322 323 def children() self end 324 325 alias child at 326 alias child_count length 327 328 def first_with_type( tree_type ) 329 find { | child | child.type == tree_type } 330 end 331 332 def add_child( child_tree ) 333 child_tree.nil? and return 334 if child_tree.flat_list? 335 self.equal?( child_tree.children ) and 336 raise ArgumentError, "attempt to add child list to itself" 337 child_tree.each_with_index do | child, index | 338 child.parent = self 339 child.child_index = length + index 340 end 341 concat( child_tree ) 342 else 343 child_tree.child_index = length 344 child_tree.parent = self 345 self << child_tree 346 end 347 return( self ) 348 end 349 350 def detach 351 @parent = nil 352 @child_index = -1 353 return( self ) 354 end 355 356 alias add_children concat 357 alias each_child each 358 359 def set_child( index, tree ) 360 return if tree.nil? 361 tree.flat_list? and raise ArgumentError, "Can't set single child to a list" 362 tree.parent = self 363 tree.child_index = index 364 self[ index ] = tree 365 end 366 367 def delete_child( index ) 368 killed = delete_at( index ) and freshen( index ) 369 return killed 370 end 371 372 def replace_children( start, stop, new_tree ) 373 start >= length or stop >= length and 374 raise IndexError, ( <<-END ).gsub!( /^\s+\| /,'' ) 375 | indices span beyond the number of children: 376 | children.length = #{ length } 377 | start = #{ start_index.inspect } 378 | stop = #{ stop_index.inspect } 379 END 380 new_children = new_tree.flat_list? ? new_tree : [ new_tree ] 381 self[ start .. stop ] = new_children 382 freshen( start_index ) 383 return self 384 end 385 386 def flat_list? 387 false 388 end 389 390 def freshen( offset = 0 ) 391 for i in offset ... length 392 node = self[ i ] 393 node.child_index = i 394 node.parent = self 395 end 396 end 397 398 def sanity_check( parent = nil, i = -1 ) 399 parent == @parent or 400 raise TreeInconsistency.failed_parent_check!( parent, @parent ) 401 i == @child_index or 402 raise TreeInconsistency.failed_index_check!( i, @child_index ) 403 each_with_index do | child, index | 404 child.sanity_check( self, index ) 405 end 406 end 407 408 def inspect 409 empty? and return to_s 410 buffer = '' 411 buffer << '(' << to_s << ' ' unless flat_list? 412 buffer << map { | c | c.inspect }.join( ' ' ) 413 buffer << ')' unless flat_list? 414 return( buffer ) 415 end 416 417 def walk 418 block_given? or return( enum_for( :walk ) ) 419 stack = [] 420 cursor = self 421 while true 422 begin 423 yield( cursor ) 424 stack.push( Array[ *cursor ] ) unless cursor.empty? 425 rescue StopIteration 426 # skips adding children to prune the node 427 ensure 428 break if stack.empty? 429 cursor = stack.last.shift 430 stack.pop if stack.last.empty? 431 end 432 end 433 return self 434 end 435 436 def prune 437 raise StopIteration 438 end 439 440 abstract :to_s 441 #protected :sanity_check, :freshen 442 443 def root?() @parent.nil? end 444 alias leaf? empty? 445 end 446 447 448 =begin rdoc ANTLR3::AST::CommonTree 449 450 The default Tree class implementation used by ANTLR tree-related code. 451 452 A CommonTree object is a tree node that wraps a token <i>payload</i> (or a +nil+ 453 value) and contains zero or more child tree nodes. Additionally, it tracks 454 information about the range of data collectively spanned by the tree node: 455 456 * the token stream start and stop indexes of tokens contained throughout 457 the tree 458 * that start and stop positions of the character input stream from which 459 the tokens were defined 460 461 Tracking this information simplifies tasks like extracting a block of code or 462 rewriting the input stream. However, depending on the purpose of the 463 application, building trees with all of this extra information may be 464 unnecessary. In such a case, a more bare-bones tree class could be written 465 (optionally using the BaseTree class or the Token module). Define a customized 466 TreeAdaptor class to handle tree construction and manipulation for the 467 customized node class, and recognizers will be able to build, rewrite, and parse 468 the customized lighter-weight trees. 469 470 =end 471 472 class CommonTree < BaseTree 473 def initialize( payload = nil ) 474 super() 475 @start_index = -1 476 @stop_index = -1 477 @child_index = -1 478 case payload 479 when CommonTree then # copy-constructor style init 480 @token = payload.token 481 @start_index = payload.start_index 482 @stop_index = payload.stop_index 483 when nil, Token then @token = payload 484 else raise ArgumentError, 485 "Invalid argument type: %s (%p)" % [ payload.class, payload ] 486 end 487 end 488 489 def initialize_copy( orig ) 490 super 491 clear 492 @parent = nil 493 end 494 495 def copy_node 496 return self.class.new( @token ) 497 end 498 499 def flat_list? 500 @token.nil? 501 end 502 503 def type 504 @token ? @token.type : 0 505 end 506 507 def text 508 @token.text rescue nil 509 end 510 511 def line 512 if @token.nil? or @token.line == 0 513 return ( empty? ? 0 : first.line ) 514 end 515 return @token.line 516 end 517 518 def column 519 if @token.nil? or @token.column == -1 520 return( empty? ? 0 : first.column ) 521 end 522 return @token.column 523 end 524 525 def start_index 526 @start_index == -1 and @token and return @token.index 527 return @start_index 528 end 529 530 def stop_index 531 @stop_index == -1 and @token and return @token.index 532 return @stop_index 533 end 534 535 alias token_start_index= start_index= 536 alias token_stop_index= stop_index= 537 alias token_start_index start_index 538 alias token_stop_index stop_index 539 540 def name 541 @token.name rescue 'INVALID' 542 end 543 544 def token_range 545 unknown_boundaries? and infer_boundaries 546 @start_index .. @stop_index 547 end 548 549 def source_range 550 unknown_boundaries? and infer_boundaries 551 tokens = map do | node | 552 tk = node.token and tk.index >= 0 ? tk : nil 553 end 554 tokens.compact! 555 first, last = tokens.minmax_by { |t| t.index } 556 first.start .. last.stop 557 end 558 559 def infer_boundaries 560 if empty? and @start_index < 0 || @stop_index < 0 561 @start_index = @stop_index = @token.index rescue -1 562 return 563 end 564 for child in self do child.infer_boundaries end 565 return if @start_index >= 0 and @stop_index >= 0 566 567 @start_index = first.start_index 568 @stop_index = last.stop_index 569 return nil 570 end 571 572 def unknown_boundaries? 573 @start_index < 0 or @stop_index < 0 574 end 575 576 def to_s 577 flat_list? ? 'nil' : @token.text.to_s 578 end 579 580 def pretty_print( printer ) 581 text = @token ? @token.text : 'nil' 582 text =~ /\s+/ and 583 text = text.dump 584 585 if empty? 586 printer.text( text ) 587 else 588 endpoints = @token ? [ "(#{ text }", ')' ] : [ '', '' ] 589 printer.group( 1, *endpoints ) do 590 for child in self 591 printer.breakable 592 printer.pp( child ) 593 end 594 end 595 end 596 end 597 598 end 599 600 =begin rdoc ANTLR3::AST::CommonErrorNode 601 602 Represents a series of erroneous tokens from a token stream input 603 604 =end 605 606 class CommonErrorNode < CommonTree 607 include ANTLR3::Error 608 include ANTLR3::Constants 609 610 attr_accessor :input, :start, :stop, :error 611 612 def initialize( input, start, stop, error ) 613 super( nil ) 614 stop = start if stop.nil? or 615 ( stop.token_index < start.token_index and stop.type != EOF ) 616 @input = input 617 @start = start 618 @stop = stop 619 @error = error 620 end 621 622 def flat_list? 623 return false 624 end 625 626 def type 627 INVALID_TOKEN_TYPE 628 end 629 630 def text 631 case @start 632 when Token 633 i = @start.token_index 634 j = ( @stop.type == EOF ) ? @input.size : @stop.token_index 635 @input.to_s( i, j ) # <- the bad text 636 when Tree 637 @input.to_s( @start, @stop ) # <- the bad text 638 else 639 "<unknown>" 640 end 641 end 642 643 def to_s 644 case @error 645 when MissingToken 646 "<missing type: #{ @error.missing_type }>" 647 when UnwantedToken 648 "<extraneous: #{ @error.token.inspect }, resync = #{ text }>" 649 when MismatchedToken 650 "<mismatched token: #{ @error.token.inspect }, resync = #{ text }>" 651 when NoViableAlternative 652 "<unexpected: #{ @error.token.inspect }, resync = #{ text }>" 653 else "<error: #{ text }>" 654 end 655 end 656 657 end 658 659 Constants::INVALID_NODE = CommonTree.new( ANTLR3::INVALID_TOKEN ) 660 661 #################################################################################################### 662 ########################################### Tree Adaptors ########################################## 663 #################################################################################################### 664 665 =begin rdoc ANTLR3::AST::TreeAdaptor 666 667 Since a tree can be represented by a multitude of formats, ANTLR's tree-related 668 code mandates the use of Tree Adaptor objects to build and manipulate any actual 669 trees. Using an adaptor object permits a single recognizer to work with any 670 number of different tree structures without adding rigid interface requirements 671 on customized tree structures. For example, if you want to represent trees using 672 simple arrays of arrays, you just need to design an appropriate tree adaptor and 673 provide it to the parser. 674 675 Tree adaptors are tasked with: 676 677 * copying and creating tree nodes and tokens 678 * defining parent-child relationships between nodes 679 * cleaning up / normalizing a full tree structure after construction 680 * reading and writing the attributes ANTLR expects of tree nodes 681 * providing node access and iteration 682 683 =end 684 685 module TreeAdaptor 686 include TokenFactory 687 include Constants 688 include Error 689 690 def add_child( tree, child ) 691 tree.add_child( child ) if tree and child 692 end 693 694 def child_count( tree ) 695 tree.child_count 696 end 697 698 def child_index( tree ) 699 tree.child_index rescue 0 700 end 701 702 def child_of( tree, index ) 703 tree.nil? ? nil : tree.child( index ) 704 end 705 706 def copy_node( tree_node ) 707 tree_node and tree_node.dup 708 end 709 710 def copy_tree( tree, parent = nil ) 711 tree or return nil 712 new_tree = copy_node( tree ) 713 set_child_index( new_tree, child_index( tree ) ) 714 set_parent( new_tree, parent ) 715 each_child( tree ) do | child | 716 new_sub_tree = copy_tree( child, new_tree ) 717 add_child( new_tree, new_sub_tree ) 718 end 719 return new_tree 720 end 721 722 def delete_child( tree, index ) 723 tree.delete_child( index ) 724 end 725 726 727 def each_child( tree ) 728 block_given? or return enum_for( :each_child, tree ) 729 for i in 0 ... child_count( tree ) 730 yield( child_of( tree, i ) ) 731 end 732 return tree 733 end 734 735 def each_ancestor( tree, include_tree = true ) 736 block_given? or return enum_for( :each_ancestor, tree, include_tree ) 737 if include_tree 738 begin yield( tree ) end while tree = parent_of( tree ) 739 else 740 while tree = parent_of( tree ) do yield( tree ) end 741 end 742 end 743 744 def flat_list?( tree ) 745 tree.flat_list? 746 end 747 748 def empty?( tree ) 749 child_count( tree ).zero? 750 end 751 752 def parent( tree ) 753 tree.parent 754 end 755 756 def replace_children( parent, start, stop, replacement ) 757 parent and parent.replace_children( start, stop, replacement ) 758 end 759 760 def rule_post_processing( root ) 761 if root and root.flat_list? 762 case root.child_count 763 when 0 then root = nil 764 when 1 765 root = root.child( 0 ).detach 766 end 767 end 768 return root 769 end 770 771 def set_child_index( tree, index ) 772 tree.child_index = index 773 end 774 775 def set_parent( tree, parent ) 776 tree.parent = parent 777 end 778 779 def set_token_boundaries( tree, start_token = nil, stop_token = nil ) 780 return unless tree 781 start = stop = 0 782 start_token and start = start_token.index 783 stop_token and stop = stop_token.index 784 tree.start_index = start 785 tree.stop_index = stop 786 return tree 787 end 788 789 def text_of( tree ) 790 tree.text rescue nil 791 end 792 793 def token( tree ) 794 CommonTree === tree ? tree.token : nil 795 end 796 797 def token_start_index( tree ) 798 tree ? tree.token_start_index : -1 799 end 800 801 def token_stop_index( tree ) 802 tree ? tree.token_stop_index : -1 803 end 804 805 def type_name( tree ) 806 tree.name rescue 'INVALID' 807 end 808 809 def type_of( tree ) 810 tree.type rescue INVALID_TOKEN_TYPE 811 end 812 813 def unique_id( node ) 814 node.hash 815 end 816 817 end 818 819 =begin rdoc ANTLR3::AST::CommonTreeAdaptor 820 821 The default tree adaptor used by ANTLR-generated tree code. It, of course, 822 builds and manipulates CommonTree nodes. 823 824 =end 825 826 class CommonTreeAdaptor 827 extend ClassMacros 828 include TreeAdaptor 829 include ANTLR3::Constants 830 831 def initialize( token_class = ANTLR3::CommonToken ) 832 @token_class = token_class 833 end 834 835 def create_flat_list 836 return create_with_payload( nil ) 837 end 838 alias create_flat_list! create_flat_list 839 840 def become_root( new_root, old_root ) 841 new_root = create( new_root ) if new_root.is_a?( Token ) 842 old_root or return( new_root ) 843 844 new_root = create_with_payload( new_root ) unless CommonTree === new_root 845 if new_root.flat_list? 846 count = new_root.child_count 847 if count == 1 848 new_root = new_root.child( 0 ) 849 elsif count > 1 850 raise TreeInconsistency.multiple_roots! 851 end 852 end 853 854 new_root.add_child( old_root ) 855 return new_root 856 end 857 858 def create_from_token( token_type, from_token, text = nil ) 859 from_token = from_token.dup 860 from_token.type = token_type 861 from_token.text = text.to_s if text 862 tree = create_with_payload( from_token ) 863 return tree 864 end 865 866 def create_from_type( token_type, text ) 867 from_token = create_token( token_type, DEFAULT_CHANNEL, text ) 868 create_with_payload( from_token ) 869 end 870 871 def create_error_node( input, start, stop, exc ) 872 CommonErrorNode.new( input, start, stop, exc ) 873 end 874 875 def create_with_payload( payload ) 876 return CommonTree.new( payload ) 877 end 878 879 def create( *args ) 880 n = args.length 881 if n == 1 and args.first.is_a?( Token ) then create_with_payload( args[ 0 ] ) 882 elsif n == 2 and Integer === args.first and String === args[ 1 ] 883 create_from_type( *args ) 884 elsif n >= 2 and Integer === args.first 885 create_from_token( *args ) 886 else 887 sig = args.map { |f| f.class }.join( ', ' ) 888 raise TypeError, "No create method with this signature found: (#{ sig })" 889 end 890 end 891 892 creation_methods = %w( 893 create_from_token create_from_type 894 create_error_node create_with_payload 895 create 896 ) 897 898 for method_name in creation_methods 899 bang_method = method_name + '!' 900 alias_method( bang_method, method_name ) 901 deprecate( bang_method, "use method ##{ method_name } instead" ) 902 end 903 904 def rule_post_processing( root ) 905 if root and root.flat_list? 906 if root.empty? then root = nil 907 elsif root.child_count == 1 then root = root.first.detach 908 end 909 end 910 return root 911 end 912 913 def empty?( tree ) 914 tree.empty? 915 end 916 917 def each_child( tree ) 918 block_given? or return enum_for( :each_child, tree ) 919 tree.each do | child | 920 yield( child ) 921 end 922 end 923 924 end 925 926 927 #################################################################################################### 928 ########################################### Tree Streams ########################################### 929 #################################################################################################### 930 931 =begin rdoc ANTLR3::AST::TreeNodeStream 932 933 TreeNodeStreams flatten two-dimensional tree structures into one-dimensional 934 sequences. They preserve the two-dimensional structure of the tree by inserting 935 special +UP+ and +DOWN+ nodes. 936 937 Consider a hypothetical tree: 938 939 [A] 940 +--[B] 941 | +--[C] 942 | `--[D] 943 `--[E] 944 `--[F] 945 946 A tree node stream would serialize the tree into the following sequence: 947 948 A DOWN B DOWN C D UP E DOWN F UP UP EOF 949 950 Other than serializing a tree into a sequence of nodes, a tree node stream 951 operates similarly to other streams. They are commonly used by tree parsers as 952 the main form of input. #peek, like token streams, returns the type of the token 953 of the next node. #look returns the next full tree node. 954 955 =end 956 957 module TreeNodeStream 958 extend ClassMacros 959 include Stream 960 include Constants 961 962 abstract :at 963 abstract :look 964 abstract :tree_source 965 abstract :token_stream 966 abstract :tree_adaptor 967 abstract :unique_navigation_nodes= 968 abstract :to_s 969 abstract :replace_children 970 end 971 972 =begin rdoc ANTLR3::AST::CommonTreeNodeStream 973 974 An implementation of TreeNodeStream tailed for streams based on CommonTree 975 objects. CommonTreeNodeStreams are the default input streams for tree parsers. 976 977 =end 978 979 class CommonTreeNodeStream 980 include TreeNodeStream 981 982 attr_accessor :token_stream 983 attr_reader :adaptor, :position 984 985 def initialize( *args ) 986 options = args.last.is_a?( ::Hash ) ? args.pop : {} 987 case n = args.length 988 when 1 989 @root = args.first 990 @token_stream = @adaptor = @nodes = @down = @up = @eof = nil 991 when 2 992 @adaptor, @root = args 993 @token_stream = @nodes = @down = @up = @eof = nil 994 when 3 995 parent, start, stop = *args 996 @adaptor = parent.adaptor 997 @root = parent.root 998 @nodes = parent.nodes[ start ... stop ] 999 @down = parent.down 1000 @up = parent.up 1001 @eof = parent.eof 1002 @token_stream = parent.token_stream 1003 when 0 1004 raise ArgumentError, "wrong number of arguments (0 for 1)" 1005 else raise ArgumentError, "wrong number of arguments (#{ n } for 3)" 1006 end 1007 @adaptor ||= options.fetch( :adaptor ) { CommonTreeAdaptor.new } 1008 @token_stream ||= options[ :token_stream ] 1009 @down ||= options.fetch( :down ) { @adaptor.create_from_type( DOWN, 'DOWN' ) } 1010 @up ||= options.fetch( :up ) { @adaptor.create_from_type( UP, 'UP' ) } 1011 @eof ||= options.fetch( :eof ) { @adaptor.create_from_type( EOF, 'EOF' ) } 1012 @nodes ||= [] 1013 1014 @unique_navigation_nodes = options.fetch( :unique_navigation_nodes, false ) 1015 @position = -1 1016 @last_marker = nil 1017 @calls = [] 1018 end 1019 1020 def fill_buffer( tree = @root ) 1021 @nodes << tree unless nil_tree = @adaptor.flat_list?( tree ) 1022 unless @adaptor.empty?( tree ) 1023 add_navigation_node( DOWN ) unless nil_tree 1024 @adaptor.each_child( tree ) { | c | fill_buffer( c ) } 1025 add_navigation_node( UP ) unless nil_tree 1026 end 1027 @position = 0 if tree == @root 1028 return( self ) 1029 end 1030 1031 def node_index( node ) 1032 @position == -1 and fill_buffer 1033 return @nodes.index( node ) 1034 end 1035 1036 def add_navigation_node( type ) 1037 navigation_node = 1038 case type 1039 when DOWN 1040 has_unique_navigation_nodes? ? @adaptor.create_from_type( DOWN, 'DOWN' ) : @down 1041 else 1042 has_unique_navigation_nodes? ? @adaptor.create_from_type( UP, 'UP' ) : @up 1043 end 1044 @nodes << navigation_node 1045 end 1046 1047 def at( index ) 1048 @position == -1 and fill_buffer 1049 @nodes.at( index ) 1050 end 1051 1052 def look( k = 1 ) 1053 @position == -1 and fill_buffer 1054 k == 0 and return nil 1055 k < 0 and return self.look_behind( -k ) 1056 1057 absolute = @position + k - 1 1058 @nodes.fetch( absolute, @eof ) 1059 end 1060 1061 def current_symbol 1062 look 1063 end 1064 1065 def look_behind( k = 1 ) 1066 k == 0 and return nil 1067 absolute = @position - k 1068 return( absolute < 0 ? nil : @nodes.fetch( absolute, @eof ) ) 1069 end 1070 1071 def tree_source 1072 @root 1073 end 1074 1075 def source_name 1076 self.token_stream.source_name 1077 end 1078 1079 def tree_adaptor 1080 @adaptor 1081 end 1082 1083 def has_unique_navigation_nodes? 1084 return @unique_navigation_nodes 1085 end 1086 attr_writer :unique_navigation_nodes 1087 1088 def consume 1089 @position == -1 and fill_buffer 1090 node = @nodes.fetch( @position, @eof ) 1091 @position += 1 1092 return( node ) 1093 end 1094 1095 def peek( i = 1 ) 1096 @adaptor.type_of look( i ) 1097 end 1098 1099 alias >> peek 1100 def <<( k ) 1101 self >> -k 1102 end 1103 1104 def mark 1105 @position == -1 and fill_buffer 1106 @last_marker = @position 1107 return @last_marker 1108 end 1109 1110 def release( marker = nil ) 1111 # do nothing? 1112 end 1113 1114 alias index position 1115 1116 def rewind( marker = @last_marker, release = true ) 1117 seek( marker ) 1118 end 1119 1120 def seek( index ) 1121 @position == -1 and fill_buffer 1122 @position = index 1123 end 1124 1125 def push( index ) 1126 @calls << @position 1127 seek( index ) 1128 end 1129 1130 def pop 1131 pos = @calls.pop and seek( pos ) 1132 return pos 1133 end 1134 1135 def reset 1136 @position = 0 1137 @last_marker = 0 1138 @calls = [] 1139 end 1140 1141 def replace_children( parent, start, stop, replacement ) 1142 parent and @adaptor.replace_children( parent, start, stop, replacement ) 1143 end 1144 1145 def size 1146 @position == -1 and fill_buffer 1147 return @nodes.length 1148 end 1149 1150 def inspect 1151 @position == -1 and fill_buffer 1152 @nodes.map { |nd| @adaptor.type_name( nd ) }.join( ' ' ) 1153 end 1154 1155 def extract_text( start = nil, stop = nil ) 1156 start.nil? || stop.nil? and return nil 1157 @position == -1 and fill_buffer 1158 1159 if @token_stream 1160 from = @adaptor.token_start_index( start ) 1161 to = 1162 case @adaptor.type_of( stop ) 1163 when UP then @adaptor.token_stop_index( start ) 1164 when EOF then to = @nodes.length - 2 1165 else @adaptor.token_stop_index( stop ) 1166 end 1167 return @token_stream.extract_text( from, to ) 1168 end 1169 1170 buffer = '' 1171 for node in @nodes 1172 if node == start ... node == stop # <-- hey look, it's the flip flop operator 1173 buffer << @adaptor.text_of( node ) #|| ' ' << @adaptor.type_of( node ).to_s ) 1174 end 1175 end 1176 return( buffer ) 1177 end 1178 1179 def each 1180 @position == -1 and fill_buffer 1181 block_given? or return enum_for( :each ) 1182 for node in @nodes do yield( node ) end 1183 self 1184 end 1185 1186 include Enumerable 1187 1188 def to_a 1189 return @nodes.dup 1190 end 1191 1192 def extract_text( start = nil, stop = nil ) 1193 @position == -1 and fill_buffer 1194 start ||= @nodes.first 1195 stop ||= @nodes.last 1196 1197 if @token_stream 1198 case @adaptor.type_of( stop ) 1199 when UP 1200 stop_index = @adaptor.token_stop_index( start ) 1201 when EOF 1202 return extract_text( start, @nodes[ - 2 ] ) 1203 else 1204 stop_index = @adaptor.token_stop_index( stop ) 1205 end 1206 1207 start_index = @adaptor.token_start_index( start ) 1208 return @token_stream.extract_text( start_index, stop_index ) 1209 else 1210 start_index = @nodes.index( start ) || @nodes.length 1211 stop_index = @nodes.index( stop ) || @nodes.length 1212 return( 1213 @nodes[ start_index .. stop_index ].map do | n | 1214 @adaptor.text_of( n ) or " " + @adaptor.type_of( n ).to_s 1215 end.join( '' ) 1216 ) 1217 end 1218 end 1219 1220 alias to_s extract_text 1221 1222 #private 1223 # 1224 # def linear_node_index( node ) 1225 # @position == -1 and fill_buffer 1226 # @nodes.each_with_index do |n, i| 1227 # node == n and return(i) 1228 # end 1229 # return -1 1230 # end 1231 end 1232 1233 =begin rdoc ANTLR3::AST::RewriteRuleElementStream 1234 1235 Special type of stream that is used internally by tree-building and tree- 1236 rewriting parsers. 1237 1238 =end 1239 1240 class RewriteRuleElementStream # < Array 1241 extend ClassMacros 1242 include Error 1243 1244 def initialize( adaptor, element_description, elements = nil ) 1245 @cursor = 0 1246 @single_element = nil 1247 @elements = nil 1248 @dirty = false 1249 @element_description = element_description 1250 @adaptor = adaptor 1251 if elements.instance_of?( Array ) 1252 @elements = elements 1253 else 1254 add( elements ) 1255 end 1256 end 1257 1258 def reset 1259 @cursor = 0 1260 @dirty = true 1261 end 1262 1263 def add( el ) 1264 return( nil ) unless el 1265 case 1266 when ! el then return( nil ) 1267 when @elements then @elements << el 1268 when @single_element.nil? then @single_element = el 1269 else 1270 @elements = [ @single_element, el ] 1271 @single_element = nil 1272 return( @elements ) 1273 end 1274 end 1275 1276 def next_tree 1277 if @dirty or @cursor >= length && length == 1 1278 return dup( __next__ ) 1279 end 1280 __next__ 1281 end 1282 1283 abstract :dup 1284 1285 def to_tree( el ) 1286 return el 1287 end 1288 1289 def has_next? 1290 return( @single_element && @cursor < 1 or 1291 @elements && @cursor < @elements.length ) 1292 end 1293 1294 def size 1295 @single_element and return 1 1296 @elements and return @elements.length 1297 return 0 1298 end 1299 1300 alias length size 1301 1302 private 1303 1304 def __next__ 1305 l = length 1306 case 1307 when l.zero? 1308 raise Error::RewriteEmptyStream.new( @element_description ) 1309 when @cursor >= l 1310 l == 1 and return to_tree( @single_element ) 1311 raise RewriteCardinalityError.new( @element_description ) 1312 when @single_element 1313 @cursor += 1 1314 return( to_tree( @single_element ) ) 1315 else 1316 out = to_tree( @elements.at( @cursor ) ) 1317 @cursor += 1 1318 return( out ) 1319 end 1320 end 1321 end 1322 1323 1324 =begin rdoc ANTLR3::AST::RewriteRuleTokenStream 1325 1326 Special type of stream that is used internally by tree-building and tree- 1327 rewriting parsers. 1328 1329 =end 1330 class RewriteRuleTokenStream < RewriteRuleElementStream 1331 def next_node 1332 return @adaptor.create_with_payload( __next__ ) 1333 end 1334 1335 alias :next :__next__ 1336 public :next 1337 1338 def dup( el ) 1339 raise TypeError, "dup can't be called for a token stream" 1340 end 1341 end 1342 1343 =begin rdoc ANTLR3::AST::RewriteRuleSubtreeStream 1344 1345 Special type of stream that is used internally by tree-building and tree- 1346 rewriting parsers. 1347 1348 =end 1349 1350 class RewriteRuleSubtreeStream < RewriteRuleElementStream 1351 def next_node 1352 if @dirty or @cursor >= length && length == 1 1353 return @adaptor.copy_node( __next__ ) 1354 end 1355 return __next__ 1356 end 1357 1358 def dup( el ) 1359 @adaptor.copy_tree( el ) 1360 end 1361 end 1362 1363 =begin rdoc ANTLR3::AST::RewriteRuleNodeStream 1364 1365 Special type of stream that is used internally by tree-building and tree- 1366 rewriting parsers. 1367 1368 =end 1369 1370 class RewriteRuleNodeStream < RewriteRuleElementStream 1371 alias next_node __next__ 1372 public :next_node 1373 def to_tree( el ) 1374 @adaptor.copy_node( el ) 1375 end 1376 1377 def dup( el ) 1378 raise TypeError, "dup can't be called for a node stream" 1379 end 1380 end 1381 end 1382 1383 include AST 1384 end 1385