lib/voodoo/parser.rb

   1 module Voodoo
   2   # Voodoo parser.
   3   # The parser reads Voodoo[http://inglorion.net/documents/designs/voodoo/]
   4   # source code and turns it into Ruby[http://www.ruby-lang.org/] objects.
   5   #
   6   # The public interface to Parser consists of the methods #new and
   7   # #parse_top_level
   8   #
   9   # Example usage:
  10   #
  11   #   require 'voodoo/parser'
  12   #
  13   #   File.open('example.voo') do |infile|
  14   #     parser = Voodoo::Parser.new infile
  15   #
  16   #     while (element = parser.parse_top_level)
  17   #       puts element.inspect
  18   #     end
  19   #   end
  20   class Parser
  21     # Creates a parser using the specified object as input.
  22     # The input object must support a method +getc+, which must
  23     # return the next character of the input, or +nil+ to indicate
  24     # the end of the input has been reached.
  25     def initialize input
  26       @input = input
  27       @line = 1
  28       @char = 0
  29       @lookahead = nil
  30     end
  31
  32     attr_reader :line, :char
  33
  34     # Consumes the current lookahead character
  35     def consume
  36       old = @lookahead
  37       if old == 10
  38         @line = @line.succ
  39         @char = 0
  40       end
  41       @lookahead = @input.getc
  42       @lookahead = :eof if @lookahead == nil
  43       @char = @char.succ unless @lookahead == :eof
  44       old
  45     end
  46
  47     # Returns the current lookahead character,
  48     # or +nil+ when the end of the input has been reached.
  49     def lookahead
  50       if @lookahead == nil
  51         @lookahead = @input.getc
  52         @char = @char.succ
  53       end
  54       case @lookahead
  55       when :eof
  56         :eof
  57       else
  58         @lookahead.chr
  59       end
  60     end
  61
  62     # Parses a top-level element.
  63     # Returns an array containing the parts of the element.
  64     # Eeach element of the array is a Symbol, a String, or an
  65     # Integer.
  66     #
  67     # For a label, returns:
  68     #   [:label, label_name]
  69     #
  70     # For a function definition, returns:
  71     #   [:function, [formala, formalb, ...], statementa, statementb, ...]
  72     #
  73     # For a conditional, returns:
  74     #   [condition, expression, [truea, trueb, ...], [falsea, falseb, ...]]
  75     #
  76     def parse_top_level
  77       words = []
  78       word = ""
  79
  80       while true
  81         case lookahead
  82         when :eof
  83           # End of input
  84           break
  85         when "\n"
  86           # Newline
  87           consume
  88           # Exit the loop, but only if the line wasn't empty
  89           break unless words.empty?
  90         when "#"
  91           # Skip comment
  92           while lookahead != :eof && lookahead != "\n"
  93             word << lookahead
  94             consume
  95           end
  96         when /\d|-/
  97           # Digit; parse number
  98           words << parse_number
  99         when /\w|\\/
 100           # Letter, underscore, or backslash; parse symbol
 101           # Note: \w matches digites, too, so keep this case after \d
 102           words << parse_symbol
 103           if words.length == 1 && is_label?(words[-1])
 104             # We have a label; return it
 105             return [:label, words[-1].to_s[0..-2].to_sym]
 106           end
 107         when "\""
 108           # Double quote; parse string
 109           words << parse_string
 110         when /\s/
 111           # Skip whitespace
 112           consume
 113         when '@'
 114           # Parse at-expression.
 115           # '@' must be followed by a number or symbol.
 116           consume
 117           case lookahead
 118           when /\d|-/
 119             expr = parse_number
 120           when /\w|\\/
 121             expr = parse_symbol
 122           else
 123             raise "Invalid character (#{@lookahead.chr.inspect})" +
 124               " at #{@line}:#{@char}; expecting number or symbol"
 125           end
 126           words << [:'@', expr]
 127         else
 128           raise "Invalid character (#{@lookahead.chr.inspect})" +
 129             " at #{@line}:#{@char}"
 130         end
 131       end
 132
 133       # We have a line of input. Conditionals and function declarations
 134       # must be handled specially, because they consist of more than one
 135       # line.
 136       if words.empty?
 137         # Nothing to parse; return nil
 138         nil
 139       elsif words[0] == :function
 140         # Function declaration. Parse function body
 141         body = parse_body :function
 142         [:function, words[1..-1]] + body
 143       elsif is_conditional?(words[0])
 144         parse_conditional1 words[0], words[1..-1]
 145       elsif words[0] == :block
 146         body = parse_body :block
 147         [:block] + body
 148       else
 149         # Statement or data declaration; simply return it
 150         words
 151       end
 152     end
 153
 154     # Parses a body for a function or a conditional
 155     def parse_body kind
 156       body = []
 157       case kind
 158       when :function
 159         kind_text = 'function definition'
 160       else
 161         kind_text = kind.to_s
 162       end
 163       while true
 164         statement = parse_top_level
 165         if statement == nil
 166           raise "End of input while inside #{kind_text}"
 167         elsif statement[0] == :end
 168           # Done parsing body
 169           break
 170         elsif kind == :conditional && statement[0] == :else
 171           # Done parsing body, but there is another one coming up
 172           body << statement
 173           break
 174         else
 175           # Parsed a statement. Add it to body.
 176           body << statement
 177         end
 178       end
 179       body
 180     end
 181
 182     # Parses an escape sequence.
 183     # This method should be called while the lookahead is the escape
 184     # character (backslash). It decodes the escape sequence and returns
 185     # the result as a string.
 186     def parse_escape
 187       result = nil
 188       consume
 189       case lookahead
 190       when :eof
 191         raise "Unexpected end of input in escape sequence"
 192       when "\\", "\"", " "
 193         result = lookahead
 194         consume
 195       when "n"
 196         # \n is newline
 197         consume
 198         result = "\n"
 199       when "r"
 200         # \r is carriage return
 201         consume
 202         result = "\r"
 203       when "x"
 204         # \xXX is byte with hex value XX
 205         code = @input.read 2
 206         @char = @char + 2
 207         consume
 208         result = [code].pack('H2')
 209       when "\n"
 210         # \<newline> is line continuation character
 211         consume
 212         # Skip indentation of next line
 213         while lookahead =~ /\s/
 214           consume
 215         end
 216         result = ''
 217       else
 218         # Default to just passing on next character
 219         result = lookahead
 220         consume
 221       end
 222       result
 223     end
 224
 225     # Parses a number.
 226     # This method should be called while the lookahead is the first
 227     # character of the number.
 228     def parse_number
 229       text = lookahead
 230       consume
 231       while lookahead =~ /\d/
 232         text << lookahead
 233         consume
 234       end
 235       text.to_i
 236     end
 237
 238     # Parses a string.
 239     # This method should be called while the lookahead is the opening
 240     # double quote.
 241     def parse_string
 242       consume
 243       result = ''
 244       while true
 245         case lookahead
 246         when "\""
 247           consume
 248           break
 249         when "\\"
 250           result << parse_escape
 251         else
 252           result << lookahead
 253           consume
 254         end
 255       end
 256       result
 257     end
 258
 259     # Parses a symbol.
 260     # This method should be called while the lookahead is the first
 261     # character of the symbol name.
 262     def parse_symbol
 263       name = ''
 264       while true
 265         case lookahead
 266         when "\\"
 267           name << parse_escape
 268         when /\w|-/
 269           name << lookahead
 270           consume
 271         when ':'
 272           # Colon parsed as last character of the symbol name
 273           name << lookahead
 274           consume
 275           break
 276         else
 277           break
 278         end
 279       end
 280       name.to_sym
 281     end
 282
 283     # Tests if a symbol is a label
 284     def is_label? symbol
 285       symbol.to_s[-1] == ?:
 286     end
 287
 288     # Tests if a symbol is a conditional starter
 289     def is_conditional? symbol
 290       [:ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne].member? symbol
 291     end
 292
 293     #
 294     # Private methods
 295     #
 296     private
 297
 298     # Parses a conditional statement
 299     def parse_conditional1 condition, operands
 300       # Parse first clause and condition for next clause
 301       consequent, next_condition = split_if_clause parse_body(:conditional)
 302       if next_condition == nil
 303         # No next clause
 304         alternative = []
 305       elsif next_condition == :else
 306         # Next clause is else without if
 307         alternative = parse_body :conditional
 308       else
 309         # Next clause is else with if
 310         alternative = [parse_conditional1(next_condition[0],
 311                                           next_condition[1])]
 312       end
 313       [condition, operands, consequent, alternative]
 314     end
 315
 316     # Splits a parsed if-clause into two parts:
 317     # 1. The list of statements making up the clause proper
 318     # 2. The condition for the next clause:
 319     #    - If there is no next clause, nil
 320     #    - If the next clause is introduced by else without a condition, :else
 321     #    - If the next clause is introduced by else iflt x y, [:iflt [:x, :y]]
 322     #    - And so on for other if.. instances
 323     def split_if_clause clause
 324       last = clause[-1]
 325       if last.respond_to?(:[]) && last.length > 0 && last[0] == :else
 326         clause = clause[0..-2]
 327         if last.length > 1
 328           # Else if
 329           [clause, [last[1], last[2..-1]]]
 330         else
 331           # Only else
 332           [clause, :else]
 333         end
 334       else
 335         # No else
 336         [clause, nil]
 337       end
 338     end
 339
 340   end
 341 end