From: Robert Conn <bob.conn@...>
Date: 2006-11-08T06:23:06+09:00
Subject: Re: [QUIZ] Bytecode Compiler (#100)

Here's my effort.  I really enjoyed this quiz but spent way more than  
the 1 hour on it (and it's still not correct)!

I tokenized the expression with a regex and then used the Shunting  
Yard Algorithm to do the parsing.  However, I fail some of tests -

1.  Unary minus  [-2+(2-2)]

2.  Order of evaluation in this expression is right-->left as opposed  
to left-->right and gives wrong result  [(1+3)/(2/2)*(10-8)]

3.  The optional efficient storage test.

I'll try to fix these if I have more time.

Thanks

Bob

require "Interpreter.rb"

class Compiler

   @PRECEDENCE = {
     '(' => -1,
     ')' => -1,
     '+' => 0,
     '-' => 0,
     '*' => 1,
     '/' => 1,
     '**' => 3,
     '%' => 3
   }

   @BYTECODE = {
     'CONST' => 0x01,
     'LCONST' => 0x02,
     '+' => 0x0a,
     '-' => 0x0b,
     '*' => 0x0c,
     '**' => 0x0d,
     '/' => 0x0e,
     '%' => 0x0f,
     'SWAP' => 0xa0
   }

   def Compiler.compile(expression)
     te = self.tokenize(expression)
     be = self.parse(te)
     self.to_bytecode(be)
   end

   def Compiler.tokenize(expression)
     tokenized_expression = []

     expression.gsub!(/\s+/, "")
     expression.scan(/(\d+|\(|\)|\+|-|\*\*|\*|\/|\%)/) { |e|  
tokenized_expression.push(e) }
     tokenized_expression
   end

   def Compiler.parse(tokenized_expression)
     output_queue, operator_stack = [], []
     operator = nil

     tokenized_expression.each { |token|

       # If token is a number, place on output queue
       if (token[0] =~ /^\d+$/)
         output_queue.push(token[0].to_i)
       elsif (token[0] == '(')
         operator_stack.push(token[0])
       elsif (token[0] == ')')
         # Pop operators off stack and onto output queue until left
         # bracket encountered
         while (operator != '(')
           if ((operator = operator_stack.pop) != '(')
               output_queue.push(operator)
           end
         end
       else
         # If there are any operators, check precedence of current token
         # against last operator on queue.  If the operator on queue is
         # more important, add it to the output before pushing the  
current
         # operator on
         if (operator_stack.any? && (@PRECEDENCE[token[0]] <=  
@PRECEDENCE[operator_stack.last]))
           output_queue.push(operator_stack.pop)
         end
         operator_stack.push(token[0])
       end
     }

     # Add the remaining operators to end of the output queue
     operator_stack.reverse_each { |operator|
       output_queue.push(operator)
     }

     output_queue
   end

   def Compiler.to_bytecode(bnf_expression)
     stack = []

     bnf_expression.delete("(")
     bnf_expression.each { |token|
       case token
         when Integer
            # If number is small enough, use smaller 2 byte storage

           if ((token >= -32768) && (token <= 32767))
             stack.push(@BYTECODE['CONST'])
             stack.push(token >> 8, token)
           else
             stack.push(@BYTECODE['LCONST'])
             stack.push(token >> 24, token >> 16, token >> 8, token)
           end
         else
           stack.push(@BYTECODE[token])
       end
     }
     stack
   end

end

require "TestByteCode.rb"