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     class ParseError < StandardError
  37       def initialize message, input_name, start_line, start_column, text
  38         @message = message
  39         @input_name = input_name
  40         @start_line = start_line
  41         @start_column = start_column
  42         @text = text
  43       end
  44
  45       attr_reader :message, :input_name, :start_line, :start_column, :text
  46     end
  47
  48     # Parses a top-level element.
  49     # Returns an array containing the parts of the element.
  50     # Each element of the array is a Symbol, a String, or an
  51     # Integer.
  52     #
  53     # For a label, returns:
  54     #   [:label, label_name]
  55     #
  56     # For a function definition, returns:
  57     #   [:function, [formala, formalb, ...], statementa, statementb, ...]
  58     #
  59     # For a conditional, returns:
  60     #   [condition, expression, [truea, trueb, ...], [falsea, falseb, ...]]
  61     #
  62     def parse_top_level
  63       # Skip whitespace, comments, and empty lines
  64       skip_to_next_top_level
  65
  66       validate_top_level do
  67         parse_top_level_nonvalidating
  68       end
  69     end
  70
  71     # Parses a body for a function or a conditional
  72     def parse_body kind
  73       body = []
  74       error = nil
  75       case kind
  76       when :function
  77         kind_text = 'function definition'
  78       else
  79         kind_text = kind.to_s
  80       end
  81       done = false
  82       until done
  83         begin
  84           with_position do
  85             statement = parse_top_level_nonvalidating
  86             if statement == nil
  87               done = true
  88               parse_error "End of input while inside #{kind_text}", nil
  89             elsif statement[0] == :end
  90               # Done parsing body
  91               done = true
  92             elsif kind == :conditional && statement[0] == :else
  93               # Done parsing body, but there is another one coming up
  94               body << statement
  95               done = true
  96             else
  97               # Should be a normal statement. Validate it, then add it to body
  98               if statement[0] == :function
  99                 parse_error "Function definitions are only allowed at top-level"
 100               end
 101               begin
 102                 Validator.validate_statement statement
 103                 body << statement
 104               rescue Validator::ValidationError => e
 105                 parse_error e.message
 106               end
 107             end
 108           end
 109         rescue => e
 110           # Got some kind of error. Still try to parse the rest of the body.
 111           # Save the error if it was the first one.
 112           if error == nil
 113             error = e
 114           end
 115         end
 116       end
 117
 118       if error != nil
 119         raise error
 120       end
 121
 122       body
 123     end
 124
 125     # Parses an escape sequence.
 126     # This method should be called while the lookahead is the escape
 127     # character (backslash). It decodes the escape sequence and returns
 128     # the result as a string.
 129     def parse_escape
 130       result = nil
 131       consume
 132       case lookahead
 133       when :eof
 134         parse_error "Unexpected end of input in escape sequence", nil
 135       when "\\", "\"", " "
 136         result = lookahead
 137         consume
 138       when "n"
 139         # \n is newline
 140         consume
 141         result = "\n"
 142       when "r"
 143         # \r is carriage return
 144         consume
 145         result = "\r"
 146       when "x"
 147         # \xXX is byte with hex value XX
 148         code = @input.read 2
 149         @column = @column + 2
 150         consume
 151         @text << code
 152         result = [code].pack('H2')
 153       when "\n"
 154         # \<newline> is line continuation character
 155         consume
 156         # Skip indentation of next line
 157         while lookahead =~ /\s/
 158           consume
 159         end
 160         result = ''
 161       else
 162         # Default to just passing on next character
 163         result = lookahead
 164         consume
 165       end
 166       result
 167     end
 168
 169     # Parses a number.
 170     # This method should be called while the lookahead is the first
 171     # character of the number.
 172     def parse_number
 173       text = lookahead
 174       consume
 175       while lookahead =~ /\d/
 176         text << lookahead
 177         consume
 178       end
 179       text.to_i
 180     end
 181
 182     # Parses a string.
 183     # This method should be called while the lookahead is the opening
 184     # double quote.
 185     def parse_string
 186       consume
 187       result = ''
 188       while true
 189         case lookahead
 190         when "\""
 191           consume
 192           break
 193         when "\\"
 194           result << parse_escape
 195         else
 196           result << lookahead
 197           consume
 198         end
 199       end
 200       result
 201     end
 202
 203     # Parses a symbol.
 204     # This method should be called while the lookahead is the first
 205     # character of the symbol name.
 206     def parse_symbol
 207       name = ''
 208       while true
 209         case lookahead
 210         when "\\"
 211           name << parse_escape
 212         when /\w|-/
 213           name << lookahead
 214           consume
 215         when ':'
 216           # Colon parsed as last character of the symbol name
 217           name << lookahead
 218           consume
 219           break
 220         else
 221           break
 222         end
 223       end
 224       name.to_sym
 225     end
 226
 227     #
 228     # Private methods
 229     #
 230     private
 231
 232     # Consumes the current lookahead character.
 233     # The character is appended to @text.
 234     def consume
 235       old = @lookahead
 236       if old == 10
 237         @line = @line.succ
 238         @column = 0
 239       end
 240       @lookahead = @input.getc
 241       @lookahead = :eof if @lookahead == nil
 242       @column = @column.succ unless @lookahead == :eof
 243       @text << old
 244       old
 245     end
 246
 247     # Tests if a symbol is a label
 248     def is_label? symbol
 249       symbol.to_s[-1] == ?:
 250     end
 251
 252     # Tests if a symbol is a conditional starter
 253     def is_conditional? symbol
 254       [:ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne].member? symbol
 255     end
 256
 257     # Returns the current lookahead character,
 258     # or +nil+ when the end of the input has been reached.
 259     def lookahead
 260       if @lookahead == nil
 261         @lookahead = @input.getc
 262         @column = @column.succ
 263       end
 264       case @lookahead
 265       when :eof
 266         :eof
 267       else
 268         @lookahead.chr
 269       end
 270     end
 271
 272     # Parses a conditional statement
 273     def parse_conditional1 condition, operands
 274       # Parse first clause and condition for next clause
 275       consequent, next_condition = split_if_clause parse_body(:conditional)
 276       if next_condition == nil
 277         # No next clause
 278         alternative = []
 279       elsif next_condition == :else
 280         # Next clause is else without if
 281         alternative = parse_body :conditional
 282       else
 283         # Next clause is else with if
 284         alternative = [parse_conditional1(next_condition[0],
 285                                           next_condition[1])]
 286       end
 287       [condition, operands, consequent, alternative]
 288     end
 289
 290     # Raises a ParseError at the current input position
 291     def parse_error message, text = @text
 292       # Create the error object
 293       error = ParseError.new(message, @input_name, @start_line,
 294                              @start_column, text)
 295
 296       # Set a backtrace to the calling method
 297       error.set_backtrace caller
 298
 299       # If we are not at a new line, skip until the next line
 300       while @column != 1 && lookahead != :eof
 301         consume
 302       end
 303
 304       # Raise the error
 305       raise error
 306     end
 307
 308     # Parses a top-level directive without validating it
 309     def parse_top_level_nonvalidating
 310       # Skip whitespace, comments, and empty lines
 311       skip_to_next_top_level
 312
 313       words = []
 314       while true
 315         skip_whitespace
 316         word = try_parse_token
 317         if word == nil
 318           # Word is nil; that means we did not get a token
 319           case lookahead
 320           when :eof
 321             # End of input
 322             break
 323           when "\n"
 324             # Newline
 325             consume
 326             # Exit the loop, but only if the line wasn't empty
 327             break unless words.empty?
 328           when "#"
 329             # Skip comment
 330             while lookahead != :eof && lookahead != "\n"
 331               word << lookahead
 332               consume
 333             end
 334           else
 335             parse_error "Unexpected character (#{lookahead}) in input"
 336           end
 337         else
 338           # Word is not nil
 339           if words.empty? && word.kind_of?(::Symbol) && word.to_s[-1] == ?:
 340             # First word is a label
 341             words = [:label, word.to_s[0..-2].to_sym]
 342             break
 343           end
 344           # Add word to statement
 345           words << word
 346         end
 347       end
 348
 349       # We have a line of input. Conditionals and function declarations
 350       # must be handled specially, because they consist of more than one
 351       # line.
 352       if words.empty?
 353         # Nothing to parse; return nil
 354         nil
 355       elsif words[0] == :function
 356         # Function declaration. Parse function body
 357         body = parse_body :function
 358         [:function, words[1..-1]] + body
 359       elsif is_conditional?(words[0])
 360         parse_conditional1 words[0], words[1..-1]
 361       elsif words[0] == :block
 362         body = parse_body :block
 363         [:block] + body
 364       else
 365         # Statement or data declaration; simply return it
 366         words
 367       end
 368     end
 369
 370     # Skips whitespace, newlines, and comments before a top-level directive
 371     def skip_to_next_top_level
 372       while true
 373         case lookahead
 374         when /\s/
 375           # Skip whitespace
 376           consume
 377         when "\n"
 378           # Newline
 379           consume
 380         when "#"
 381           # Skip comment
 382           while lookahead != :eof && lookahead != "\n"
 383             consume
 384           end
 385         else
 386           break
 387         end
 388       end
 389     end
 390
 391     # Consumes characters until a character other than space or tab is
 392     # encountered.
 393     def skip_whitespace
 394       while lookahead == " " || lookahead == "\t"
 395         consume
 396       end
 397     end
 398
 399     # Splits a parsed if-clause into two parts:
 400     # 1. The list of statements making up the clause proper
 401     # 2. The condition for the next clause:
 402     #    - If there is no next clause, nil
 403     #    - If the next clause is introduced by else without a condition, :else
 404     #    - If the next clause is introduced by else iflt x y, [:iflt [:x, :y]]
 405     #    - And so on for other if.. instances
 406     def split_if_clause clause
 407       last = clause[-1]
 408       if last.respond_to?(:[]) && last.length > 0 && last[0] == :else
 409         clause = clause[0..-2]
 410         if last.length > 1
 411           # Else if
 412           [clause, [last[1], last[2..-1]]]
 413         else
 414           # Only else
 415           [clause, :else]
 416         end
 417       else
 418         # No else
 419         [clause, nil]
 420       end
 421     end
 422
 423     # Tries to parse a symbol, number, string, or at-expression. If
 424     # such a token starts at the current position, it is parsed and returned.
 425     # Else, nil is returned.
 426     def try_parse_token
 427       case lookahead
 428       when /\d|-/
 429         # Digit; parse number
 430         parse_number
 431       when /\w|\\/
 432         # Letter, underscore, or backslash; parse symbol
 433         # Note: \w matches digits, too, so keep this case after \d
 434        parse_symbol
 435       when "\""
 436         # Double quote; parse string
 437         parse_string
 438       when '@'
 439         # Parse at-expression.
 440         # '@' must be followed by a number or symbol.
 441         consume
 442         case lookahead
 443         when /\d|-/
 444           expr = parse_number
 445         when /\w|\\/
 446           expr = parse_symbol
 447         else
 448           parse_error "Invalid character (#{lookahead}) " +
 449             "in at-expression; expecting number or symbol"
 450         end
 451         [:'@', expr]
 452       else
 453         # No valid starter for a token, return nil
 454         nil
 455       end
 456     end
 457
 458     # Evaluate block and check that the result is a valid top-level
 459     # directive.
 460     def validate_top_level &block
 461       with_position do
 462         result = yield
 463         begin
 464           if result != nil
 465             Validator.validate_top_level result
 466           end
 467           result
 468         rescue Validator::ValidationError => e
 469           parse_error e.message
 470         end
 471       end
 472     end
 473
 474     # Evaluate block, keeping track of @start_line, @start_column
 475     # at the beginning of the block, and @text during the evaluation
 476     # of block.
 477     def with_position &block
 478       # Save old values
 479       old_line = @start_line
 480       old_column = @start_column
 481       old_text = @text
 482
 483       # Evaluate block with new values
 484       begin
 485         @start_line = @line
 486         @start_column = @column
 487         @text = ''
 488         yield
 489       ensure
 490         # Restore old values
 491         @start_line = old_line
 492         @start_column = old_column
 493         @text = old_text + @text
 494       end
 495     end
 496
 497   end
 498 end