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 a body for a function or a conditional
 165     def parse_body kind
 166       wrap_exceptions do
 167         body = []
 168         errors = []
 169         case kind
 170         when :function
 171           kind_text = 'function definition'
 172         else
 173           kind_text = kind.to_s
 174         end
 175         done = false
 176         until done
 177           begin
 178             with_position do
 179               statement = parse_top_level_nonvalidating
 180               if statement == nil
 181                 done = true
 182                 parse_error "End of input while inside #{kind_text}", nil
 183
 184               elsif statement[0] == :end
 185                 # Done parsing body
 186                 done = true
 187               elsif kind == :conditional && statement[0] == :else
 188                 # Done parsing body, but there is another one coming up
 189                 body << statement
 190                 done = true
 191               else
 192                 # Should be a normal statement. Validate it, then add it to body
 193                 if statement[0] == :function
 194                   parse_error "Function definitions are only allowed at top-level"
 195                 end
 196                 begin
 197                   Validator.validate_statement statement
 198                   body << statement
 199                 rescue Validator::ValidationError => e
 200                   parse_error e.message
 201                 end
 202               end
 203             end
 204           rescue => e
 205             # Got some kind of error. Still try to parse the rest of the body.
 206             errors << e
 207           end
 208         end
 209
 210         # Raise error if we had just one.
 211         # If we had more than one, raise a MultipleErrors instance.
 212         if errors.length == 1
 213           raise errors[0]
 214         elsif errors.length > 1
 215           raise MultipleErrors.new errors
 216         end
 217
 218         body
 219       end
 220     end
 221
 222     # Parses an escape sequence.
 223     # This method should be called while the lookahead is the escape
 224     # character (backslash). It decodes the escape sequence and returns
 225     # the result as a string.
 226     def parse_escape
 227       wrap_exceptions do
 228         result = nil
 229         consume
 230         case lookahead
 231         when :eof
 232           parse_error "Unexpected end of input in escape sequence", nil
 233         when "\\", "\"", " "
 234           result = lookahead
 235           consume
 236         when "n"
 237           # \n is newline
 238           consume
 239           result = "\n"
 240         when "r"
 241           # \r is carriage return
 242           consume
 243           result = "\r"
 244         when "x"
 245           # \xXX is byte with hex value XX
 246           code = @input.read 2
 247           @column = @column + 2
 248           consume
 249           @text << code
 250           result = [code].pack('H2')
 251         when "\n"
 252           # \<newline> is line continuation character
 253           consume
 254           # Skip indentation of next line
 255           while lookahead =~ /\s/
 256             consume
 257           end
 258           result = ''
 259         else
 260           # Default to just passing on next character
 261           result = lookahead
 262           consume
 263         end
 264         result
 265       end
 266     end
 267
 268     # Parses a number.
 269     # This method should be called while the lookahead is the first
 270     # character of the number.
 271     def parse_number
 272       wrap_exceptions do
 273         text = lookahead
 274         consume
 275         while lookahead =~ /\d/
 276           text << lookahead
 277           consume
 278         end
 279         text.to_i
 280       end
 281     end
 282
 283     # Parses a string.
 284     # This method should be called while the lookahead is the opening
 285     # double quote.
 286     def parse_string
 287       wrap_exceptions do
 288         consume
 289         result = ''
 290         while true
 291           case lookahead
 292           when "\""
 293             consume
 294             break
 295           when "\\"
 296             result << parse_escape
 297           else
 298             result << lookahead
 299             consume
 300           end
 301         end
 302         result
 303       end
 304     end
 305
 306     # Parses a symbol.
 307     # This method should be called while the lookahead is the first
 308     # character of the symbol name.
 309     def parse_symbol
 310       wrap_exceptions do
 311         name = ''
 312         while lookahead != :eof
 313           case lookahead
 314           when "\\"
 315             name << parse_escape
 316           when /\w|-/
 317             name << lookahead
 318             consume
 319           when ':'
 320             # Colon parsed as last character of the symbol name
 321             name << lookahead
 322             consume
 323             break
 324           else
 325             break
 326           end
 327         end
 328         name.to_sym
 329       end
 330     end
 331
 332     #
 333     # Private methods
 334     #
 335     private
 336
 337     # Consumes the current lookahead character.
 338     # The character is appended to @text.
 339     def consume
 340       old = @lookahead
 341       @lookahead = nil
 342       if old == "\n"
 343         @line = @line.succ
 344         @column = 0
 345       end
 346       @text << old
 347       old
 348     end
 349
 350     # Tests if a symbol is a label
 351     def is_label? symbol
 352       symbol.to_s[-1] == ?:
 353     end
 354
 355     # Tests if a symbol is a conditional starter
 356     def is_conditional? symbol
 357       [:ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne].member? symbol
 358     end
 359
 360     # Returns the current lookahead character,
 361     # or +:eof+ when the end of the input has been reached.
 362     def lookahead
 363       if @lookahead == nil
 364         @lookahead = @input.getc
 365         if @lookahead == nil
 366           @lookahead = :eof
 367         else
 368           @lookahead = @lookahead.chr
 369           @column = @column.succ
 370         end
 371       end
 372       @lookahead
 373     end
 374
 375     # Parses a conditional statement
 376     def parse_conditional1 condition, operands
 377       # Parse first clause and condition for next clause
 378       consequent, next_condition = split_if_clause parse_body(:conditional)
 379       if next_condition == nil
 380         # No next clause
 381         alternative = []
 382       elsif next_condition == :else
 383         # Next clause is else without if
 384         alternative = parse_body :conditional
 385       else
 386         # Next clause is else with if
 387         alternative = [parse_conditional1(next_condition[0],
 388                                           next_condition[1])]
 389       end
 390       [condition, operands, consequent, alternative]
 391     end
 392
 393     # Raises a ParseError at the current input position
 394     def parse_error message, text = @text
 395       # Create the error object
 396       error = ParseError.new(message, @input_name, @start_line,
 397                              @start_column, text)
 398
 399       # Set a backtrace to the calling method
 400       error.set_backtrace caller
 401
 402       # If we are not at a new line, skip until the next line
 403       while @column > 1 && lookahead != :eof
 404         consume
 405       end
 406
 407       # Raise the error
 408       raise error
 409     end
 410
 411     # Parses a top-level directive without validating it
 412     def parse_top_level_nonvalidating
 413       # Skip whitespace, comments, and empty lines
 414       skip_to_next_top_level
 415
 416       words = []
 417       while true
 418         # Parse next token
 419         skip_whitespace
 420         word = try_parse_token
 421         if word == nil
 422           # Word is nil; that means we did not get a token
 423           case lookahead
 424           when :eof
 425             # End of input
 426             break
 427           when "\n"
 428             # Newline
 429             consume
 430             # Exit the loop, but only if the line wasn't empty
 431             break unless words.empty?
 432           when "#"
 433             # Skip comment
 434             while lookahead != :eof && lookahead != "\n"
 435               consume
 436             end
 437           else
 438             parse_error "Unexpected character (#{lookahead}) in input"
 439           end
 440         else
 441           # Word is not nil - we got a token
 442           if words.empty? && word.kind_of?(::Symbol) && word.to_s[-1] == ?:
 443             # First word is a label
 444             words = [:label, word.to_s[0..-2].to_sym]
 445             break
 446           end
 447           # Add word to statement
 448           words << word
 449         end
 450         words
 451       end
 452
 453       # We have a line of input. Conditionals and function declarations
 454       # must be handled specially, because they consist of more than one
 455       # line.
 456       if words.empty?
 457         # Nothing to parse; return nil
 458         nil
 459       elsif words[0] == :function
 460         # Function declaration. Parse function body
 461         body = parse_body :function
 462         [:function, words[1..-1]] + body
 463       elsif is_conditional?(words[0])
 464         parse_conditional1 words[0], words[1..-1]
 465       elsif words[0] == :block
 466         body = parse_body :block
 467         [:block] + body
 468       else
 469         # Statement or data declaration; simply return it
 470         words
 471       end
 472     end
 473
 474     # Skips whitespace, newlines, and comments before a top-level directive
 475     def skip_to_next_top_level
 476       while true
 477         case lookahead
 478         when /\s/
 479           # Skip whitespace
 480           consume
 481         when "\n"
 482           # Newline
 483           consume
 484         when "#"
 485           # Skip comment
 486           while lookahead != :eof && lookahead != "\n"
 487             consume
 488           end
 489         else
 490           break
 491         end
 492       end
 493     end
 494
 495     # Consumes characters until a character other than space or tab is
 496     # encountered.
 497     def skip_whitespace
 498       while lookahead == " " || lookahead == "\t"
 499         consume
 500       end
 501     end
 502
 503     # Splits a parsed if-clause into two parts:
 504     # 1. The list of statements making up the clause proper
 505     # 2. The condition for the next clause:
 506     #    - If there is no next clause, nil
 507     #    - If the next clause is introduced by else without a condition, :else
 508     #    - If the next clause is introduced by else iflt x y, [:iflt [:x, :y]]
 509     #    - And so on for other if.. instances
 510     def split_if_clause clause
 511       last = clause[-1]
 512       if last.respond_to?(:[]) && last.length > 0 && last[0] == :else
 513         clause = clause[0..-2]
 514         if last.length > 1
 515           # Else if
 516           [clause, [last[1], last[2..-1]]]
 517         else
 518           # Only else
 519           [clause, :else]
 520         end
 521       else
 522         # No else
 523         [clause, nil]
 524       end
 525     end
 526
 527     # Tries to parse a symbol, number, string, or at-expression. If
 528     # such a token starts at the current position, it is parsed and returned.
 529     # Else, nil is returned.
 530     def try_parse_token
 531       case lookahead
 532       when :eof
 533         nil
 534       when NUMBER_STARTER
 535         # Digit; parse number
 536         parse_number
 537       when SYMBOL_STARTER
 538         # Letter, underscore, or backslash; parse symbol
 539         # Note: \w matches digits, too, so keep this case after \d
 540        parse_symbol
 541       when STRING_STARTER
 542         # Double quote; parse string
 543         parse_string
 544       when '@'
 545         # Parse at-expression.
 546         # '@' must be followed by a number or symbol.
 547         consume
 548         case lookahead
 549         when NUMBER_STARTER
 550           expr = parse_number
 551         when SYMBOL_STARTER
 552           expr = parse_symbol
 553         else
 554           parse_error "Invalid character (#{lookahead}) " +
 555             "in at-expression; expecting number or symbol"
 556         end
 557         [:'@', expr]
 558       when '%'
 559         consume
 560         # Must be followed by a symbol.
 561         if lookahead !~ SYMBOL_STARTER
 562           parse_error "'%' must be followed by a symbol"
 563         end
 564         [:'%', parse_symbol]
 565       else
 566         # No valid starter for a token, return nil
 567         nil
 568       end
 569     end
 570
 571     # Evaluate block and check that the result is a valid top-level
 572     # directive.
 573     def validate_top_level &block
 574       with_position do
 575         result = yield
 576         begin
 577           if result != nil
 578             Validator.validate_top_level result
 579           end
 580           result
 581         rescue Validator::ValidationError => e
 582           parse_error e.message
 583         end
 584       end
 585     end
 586
 587     # Evaluate block, keeping track of @start_line, @start_column
 588     # at the beginning of the block, and @text during the evaluation
 589     # of block.
 590     def with_position &block
 591       # Save old values
 592       old_line = @start_line
 593       old_column = @start_column
 594       old_text = @text
 595
 596       # Evaluate block with new values
 597       begin
 598         @start_line = @line
 599         @start_column = @column
 600         @text = ''
 601         wrap_exceptions do
 602           yield
 603         end
 604       ensure
 605         # Restore old values
 606         @start_line = old_line
 607         @start_column = old_column
 608         @text = old_text + @text
 609       end
 610     end
 611
 612     # Ensures that any exceptions that escape from block are instances of
 613     # Parser::Error.
 614     def wrap_exceptions &block
 615       begin
 616         yield
 617       rescue Parser::Error
 618         # Already an instance of Parser::Error; pass it through.
 619         raise
 620       rescue => e
 621         # Some other error; wrap in ParserInternalError.
 622         wrapped = ParserInternalError.new(e, @input_name, @line,
 623                                           @column, @text)
 624         wrapped.set_backtrace e.backtrace
 625         raise wrapped
 626       end
 627     end
 628
 629   end
 630 end