lib/voodoo/parser.rb

   1 require 'voodoo/validator'
   2
   3 module Voodoo
   4   # Voodoo parser.
   5   # The parser reads Voodoo[http://inglorion.net/documents/designs/voodoo/]
   6   # source code and turns it into Ruby[http://www.ruby-lang.org/] objects.
   7   #
   8   # The public interface to Parser consists of the methods #new and
   9   # #parse_top_level
  10   #
  11   # Example usage:
  12   #
  13   #   require 'voodoo/parser'
  14   #
  15   #   File.open('example.voo') do |infile|
  16   #     parser = Voodoo::Parser.new infile
  17   #
  18   #     while (element = parser.parse_top_level)
  19   #       puts element.inspect
  20   #     end
  21   #   end
  22   class Parser
  23     NUMBER_STARTER = /\d|-/
  24     STRING_STARTER = '"'
  25     SYMBOL_STARTER = /[[:alpha:]]|\\/
  26
  27     # Creates a parser using the specified object as input.
  28     # The input object must support a method +getc+, which must
  29     # return the next character of the input, or +nil+ to indicate
  30     # the end of the input has been reached.
  31     def initialize input
  32       @input = input
  33       @input_name = input.respond_to?(:path) ? input.path : nil
  34       @start_line = @line = 1
  35       @start_column = @column = 0
  36       @lookahead = nil
  37       @text = ''
  38     end
  39
  40     # Base class for errors reported from the parser.
  41     # This provides methods to get the name of the input being processed,
  42     # as well as the start_line, start_column, and text of the code
  43     # that triggered the error.
  44     class Error < StandardError
  45       def initialize message, input_name, start_line, start_column, text
  46         super message
  47         @input_name = input_name
  48         @start_line = start_line
  49         @start_column = start_column
  50         @text = text
  51       end
  52
  53       attr_reader :input_name, :start_line, :start_column, :text
  54     end
  55
  56     # Class for parse errors.
  57     # A ParseError indicates an error in the code being parsed.
  58     # For other errors that the parser may raise, see ParserInternalError.
  59     class ParseError < Parser::Error
  60       def initialize message, input_name, start_line, start_column, text
  61         super message, input_name, start_line, start_column, text
  62       end
  63     end
  64
  65     # Class for parser internal errors.
  66     # A ParserInternalError indicates an error in the parser that is not
  67     # flagged as an error in the code being parsed. Possible causes
  68     # include I/O errors while reading code, as well as bugs in the
  69     # parser.
  70     #
  71     # The +cause+ attribute indicates the initial cause for the error.
  72     # The other attributes of ParserInternalError are inherited from
  73     # Parser::Error and indicate the input that was being
  74     # processed when the error occurred.
  75     class ParserInternalError < Parser::Error
  76       def initialize cause, input_name, start_line, start_column, text
  77         super cause.message, input_name, start_line, start_column, text
  78         @cause = cause
  79       end
  80
  81       attr_reader :cause
  82     end
  83
  84     # Class wrapping multiple Parser::Errors.
  85     class MultipleErrors < Parser::Error
  86       def initialize errors
  87         @errors = errors
  88         super(nil, errors[0].input_name, errors[0].start_line,
  89               errors[0].start_column, nil)
  90       end
  91
  92       attr_reader :errors
  93
  94       def message
  95         if @message == nil
  96           msg = "Multiple errors:\n\n"
  97           @errors.each do |error|
  98             msg << error.input_name << ":" if error.input_name
  99             msg << "#{error.start_line}: " << error.message
 100             if error.text != nil
 101               msg << "\n\n  #{error.text.gsub("\n", "\n  ")}"
 102             end
 103             msg << "\n"
 104           end
 105           @message = msg
 106         end
 107         @message
 108       end
 109
 110       def text
 111         if @text == nil
 112           texts = @errors.map {|error| error.text}
 113           @text = texts.join "\n"
 114         end
 115         @text
 116       end
 117     end
 118
 119     # Parses a top-level element.
 120     # Returns an array containing the parts of the element.
 121     #
 122     # Some examples (Voodoo code, Ruby return values in comments):
 123     #
 124     #   section functions
 125     #   # [:section, :functions]
 126     #
 127     #   call foo x 12
 128     #   # [:call, :foo, :x, 12]
 129     #
 130     #   set x add x 42
 131     #   # [:set, :x, :add, :x, 42]
 132     #
 133     #   set-byte @x 1 10
 134     #   # [:"set-byte", [:"@", :x], 1, 10]
 135     #
 136     #   ifeq x y
 137     #       set z equal
 138     #   else
 139     #       set z not-equal
 140     #   end if
 141     #   # [:ifeq, [:x, :y], [[:set, :z, :equal]], [[:set, :z, :"not-equal"]]]
 142     #
 143     #   foo:
 144     #   # [:label, :foo]
 145     #
 146     #   function x y
 147     #       let z add x y
 148     #       return z
 149     #   end function
 150     #   # [:function, [:x, :y], [:let, :z, :add, :x, :y], [:return, :z]]
 151     #
 152     def parse_top_level
 153       wrap_exceptions do
 154         @text = ''
 155         # Skip whitespace, comments, and empty lines
 156         skip_to_next_top_level
 157
 158         validate_top_level do
 159           parse_top_level_nonvalidating
 160         end
 161       end
 162     end
 163
 164     # Parses statements up to "end X". _kind_ should indicate the type
 165     # of body being parsed: :block, :conditional, :function, or :group.
 166     # Returns an array of statements.
 167     def parse_body kind
 168       wrap_exceptions do
 169         body = []
 170         errors = []
 171         case kind
 172         when :function
 173           kind_text = 'function definition'
 174         else
 175           kind_text = kind.to_s
 176         end
 177         # Groups are allowed to contain top-level statements.
 178         # All other kinds aren't.
 179         top_level = kind == :group
 180         done = false
 181         until done
 182           begin
 183             with_position do
 184               statement = parse_top_level_nonvalidating
 185               if statement == nil
 186                 done = true
 187                 parse_error "End of input while inside #{kind_text}", nil
 188
 189               elsif statement[0] == :end
 190                 # Done parsing body
 191                 done = true
 192               elsif kind == :conditional && statement[0] == :else
 193                 # Done parsing body, but there is another one coming up
 194                 body << statement
 195                 done = true
 196               else
 197                 # Should be a normal statement. Validate it, then add it to body
 198                 begin
 199                   if top_level
 200                     Validator.validate_top_level statement
 201                   else
 202                     Validator.validate_statement statement
 203                   end
 204                   body << statement
 205                 rescue Validator::ValidationError => e
 206                   magic_word = statement[0]
 207                   if !top_level &&
 208                       Validator::TOP_LEVELS.member?(magic_word) &&
 209                       !Validator::STATEMENTS.member?(magic_word)
 210                     parse_error "#{magic_word} is only allowed at top-level"
 211                   else
 212                     parse_error e.message
 213                   end
 214                 end
 215               end
 216             end
 217           rescue => e
 218             # Got some kind of error. Still try to parse the rest of the body.
 219             errors << e
 220           end
 221         end
 222
 223         # Raise error if we had just one.
 224         # If we had more than one, raise a MultipleErrors instance.
 225         if errors.length == 1
 226           raise errors[0]
 227         elsif errors.length > 1
 228           raise MultipleErrors.new errors
 229         end
 230
 231         body
 232       end
 233     end
 234
 235     # Parses an escape sequence.
 236     # This method should be called while the lookahead is the escape
 237     # character (backslash). It decodes the escape sequence and returns
 238     # the result as a string.
 239     def parse_escape
 240       wrap_exceptions do
 241         result = nil
 242         consume
 243         case lookahead
 244         when :eof
 245           parse_error "Unexpected end of input in escape sequence", nil
 246         when "\\", "\"", " "
 247           result = lookahead
 248           consume
 249         when "n"
 250           # \n is newline
 251           consume
 252           result = "\n"
 253         when "r"
 254           # \r is carriage return
 255           consume
 256           result = "\r"
 257         when "x"
 258           # \xXX is byte with hex value XX
 259           code = @input.read 2
 260           @column = @column + 2
 261           consume
 262           @text << code
 263           result = [code].pack('H2')
 264         when "\n"
 265           # \<newline> is line continuation character
 266           consume
 267           # Skip indentation of next line
 268           while lookahead =~ /\s/
 269             consume
 270           end
 271           result = ''
 272         else
 273           # Default to just passing on next character
 274           result = lookahead
 275           consume
 276         end
 277         result
 278       end
 279     end
 280
 281     # Parses a number.
 282     # This method should be called while the lookahead is the first
 283     # character of the number.
 284     def parse_number
 285       wrap_exceptions do
 286         text = lookahead
 287         consume
 288         while lookahead =~ /\d/
 289           text << lookahead
 290           consume
 291         end
 292         text.to_i
 293       end
 294     end
 295
 296     # Parses a string.
 297     # This method should be called while the lookahead is the opening
 298     # double quote.
 299     def parse_string
 300       wrap_exceptions do
 301         consume
 302         result = ''
 303         while true
 304           case lookahead
 305           when "\""
 306             consume
 307             break
 308           when "\\"
 309             result << parse_escape
 310           else
 311             result << lookahead
 312             consume
 313           end
 314         end
 315         result
 316       end
 317     end
 318
 319     # Parses a symbol.
 320     # This method should be called while the lookahead is the first
 321     # character of the symbol name.
 322     def parse_symbol
 323       wrap_exceptions do
 324         name = ''
 325         while lookahead != :eof
 326           case lookahead
 327           when "\\"
 328             name << parse_escape
 329           when /\w|-/
 330             name << lookahead
 331             consume
 332           when ':'
 333             # Colon parsed as last character of the symbol name
 334             name << lookahead
 335             consume
 336             break
 337           else
 338             break
 339           end
 340         end
 341         name.to_sym
 342       end
 343     end
 344
 345     #
 346     # Private methods
 347     #
 348     private
 349
 350     # Consumes the current lookahead character.
 351     # The character is appended to @text.
 352     def consume
 353       old = @lookahead
 354       @lookahead = nil
 355       if old == "\n"
 356         @line = @line.succ
 357         @column = 0
 358       end
 359       @text << old
 360       old
 361     end
 362
 363     # Tests if a symbol is a label
 364     def is_label? symbol
 365       symbol.to_s[-1] == ?:
 366     end
 367
 368     # Tests if a symbol is a conditional starter.
 369     def is_conditional? symbol
 370       [:ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne].member? symbol
 371     end
 372
 373     # Returns the current lookahead character,
 374     # or +:eof+ when the end of the input has been reached.
 375     def lookahead
 376       if @lookahead == nil
 377         @lookahead = @input.getc
 378         if @lookahead == nil
 379           @lookahead = :eof
 380         else
 381           @lookahead = @lookahead.chr
 382           @column = @column.succ
 383         end
 384       end
 385       @lookahead
 386     end
 387
 388     # Parses a conditional statement.
 389     def parse_conditional1 condition, operands
 390       # Parse first clause and condition for next clause
 391       consequent, next_condition = split_if_clause parse_body(:conditional)
 392       if next_condition == nil
 393         # No next clause
 394         alternative = []
 395       elsif next_condition == :else
 396         # Next clause is else without if
 397         alternative = parse_body :conditional
 398       else
 399         # Next clause is else with if
 400         alternative = [parse_conditional1(next_condition[0],
 401                                           next_condition[1])]
 402       end
 403       [condition, operands, consequent, alternative]
 404     end
 405
 406     # Raises a ParseError at the current input position.
 407     def parse_error message, text = @text
 408       # Create the error object
 409       error = ParseError.new(message, @input_name, @start_line,
 410                              @start_column, text)
 411
 412       # Set a backtrace to the calling method
 413       error.set_backtrace caller
 414
 415       # If we are not at a new line, skip until the next line
 416       while @column > 1 && lookahead != :eof
 417         consume
 418       end
 419
 420       # Raise the error
 421       raise error
 422     end
 423
 424     # Parses a top-level incantation without validating it.
 425     def parse_top_level_nonvalidating
 426       # Skip whitespace, comments, and empty lines
 427       skip_to_next_top_level
 428
 429       words = []
 430       while true
 431         # Parse next token
 432         skip_whitespace
 433         word = try_parse_token
 434         if word == nil
 435           # Word is nil; that means we did not get a token
 436           case lookahead
 437           when :eof
 438             # End of input
 439             break
 440           when "\n"
 441             # Newline
 442             consume
 443             # Exit the loop, but only if the line wasn't empty
 444             break unless words.empty?
 445           when "#"
 446             # Skip comment
 447             while lookahead != :eof && lookahead != "\n"
 448               consume
 449             end
 450           else
 451             parse_error "Unexpected character (#{lookahead}) in input"
 452           end
 453         else
 454           # Word is not nil - we got a token
 455           if words.empty? && word.kind_of?(::Symbol) && word.to_s[-1] == ?:
 456             # First word is a label
 457             words = [:label, word.to_s[0..-2].to_sym]
 458             break
 459           end
 460           # Add word to statement
 461           words << word
 462         end
 463         words
 464       end
 465
 466       # We have a line of input. Conditionals and function declarations
 467       # must be handled specially, because they consist of more than one
 468       # line.
 469       if words.empty?
 470         # Nothing to parse; return nil
 471         nil
 472       elsif words[0] == :function
 473         # Function declaration. Parse function body
 474         body = parse_body :function
 475         [:function, words[1..-1]] + body
 476       elsif is_conditional?(words[0])
 477         parse_conditional1 words[0], words[1..-1]
 478       elsif words[0] == :block || words[0] == :group
 479         body = parse_body words[0]
 480         [words[0]] + body
 481       else
 482         # Statement or data declaration; simply return it
 483         words
 484       end
 485     end
 486
 487     # Skips whitespace, newlines, and comments before a top-level incantation.
 488     def skip_to_next_top_level
 489       while true
 490         case lookahead
 491         when /\s/
 492           # Skip whitespace
 493           consume
 494         when "\n"
 495           # Newline
 496           consume
 497         when "#"
 498           # Skip comment
 499           while lookahead != :eof && lookahead != "\n"
 500             consume
 501           end
 502         else
 503           break
 504         end
 505       end
 506     end
 507
 508     # Consumes characters until a character other than space or tab is
 509     # encountered.
 510     def skip_whitespace
 511       while lookahead == " " || lookahead == "\t"
 512         consume
 513       end
 514     end
 515
 516     # Splits a parsed if-clause into two parts:
 517     # 1. The list of statements making up the clause proper
 518     # 2. The condition for the next clause:
 519     #    - If there is no next clause, nil
 520     #    - If the next clause is introduced by else without a condition, :else
 521     #    - If the next clause is introduced by else iflt x y, [:iflt [:x, :y]]
 522     #    - And so on for other if.. instances
 523     def split_if_clause clause
 524       last = clause[-1]
 525       if last.respond_to?(:[]) && last.length > 0 && last[0] == :else
 526         clause = clause[0..-2]
 527         if last.length > 1
 528           # Else if
 529           [clause, [last[1], last[2..-1]]]
 530         else
 531           # Only else
 532           [clause, :else]
 533         end
 534       else
 535         # No else
 536         [clause, nil]
 537       end
 538     end
 539
 540     # Tries to parse a symbol, number, string, or at-expression. If
 541     # such a token starts at the current position, it is parsed and returned.
 542     # Else, nil is returned.
 543     def try_parse_token
 544       case lookahead
 545       when :eof
 546         nil
 547       when NUMBER_STARTER
 548         # Digit; parse number
 549         parse_number
 550       when SYMBOL_STARTER
 551         # Letter, underscore, or backslash; parse symbol
 552         # Note: \w matches digits, too, so keep this case after \d
 553        parse_symbol
 554       when STRING_STARTER
 555         # Double quote; parse string
 556         parse_string
 557       when '@'
 558         # Parse at-expression.
 559         # '@' must be followed by a number or symbol.
 560         consume
 561         case lookahead
 562         when NUMBER_STARTER
 563           expr = parse_number
 564         when SYMBOL_STARTER
 565           expr = parse_symbol
 566         else
 567           parse_error "Invalid character (#{lookahead}) " +
 568             "in at-expression; expecting number or symbol"
 569         end
 570         [:'@', expr]
 571       when '%'
 572         consume
 573         # Must be followed by a symbol.
 574         if lookahead !~ SYMBOL_STARTER
 575           parse_error "'%' must be followed by a symbol"
 576         end
 577         [:'%', parse_symbol]
 578       else
 579         # No valid starter for a token, return nil
 580         nil
 581       end
 582     end
 583
 584     # Evaluates _block_ and checks that the result is a valid top-level
 585     # incantation.
 586     def validate_top_level &block
 587       with_position do
 588         result = yield
 589         begin
 590           if result != nil
 591             Validator.validate_top_level result
 592           end
 593           result
 594         rescue Validator::ValidationError => e
 595           parse_error e.message
 596         end
 597       end
 598     end
 599
 600     # Evaluates block, keeping track of @start_line, @start_column
 601     # at the beginning of the block, and @text during the evaluation
 602     # of block.
 603     def with_position &block
 604       # Save old values
 605       old_line = @start_line
 606       old_column = @start_column
 607       old_text = @text
 608
 609       # Evaluate block with new values
 610       begin
 611         @start_line = @line
 612         @start_column = @column
 613         @text = ''
 614         wrap_exceptions do
 615           yield
 616         end
 617       ensure
 618         # Restore old values
 619         @start_line = old_line
 620         @start_column = old_column
 621         @text = old_text + @text
 622       end
 623     end
 624
 625     # Ensures that any exceptions that escape from block are instances of
 626     # Parser::Error.
 627     def wrap_exceptions &block
 628       begin
 629         yield
 630       rescue Parser::Error
 631         # Already an instance of Parser::Error; pass it through.
 632         raise
 633       rescue => e
 634         # Some other error; wrap in ParserInternalError.
 635         wrapped = ParserInternalError.new(e, @input_name, @line,
 636                                           @column, @text)
 637         wrapped.set_backtrace e.backtrace
 638         raise wrapped
 639       end
 640     end
 641
 642   end
 643 end