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