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