camerooni
11/5/2006 4:07:00 PM
The simplest way I found to do this problem was to let Ruby do the
legwork of parsing the expression for me, so I didn't have to worry
about things like parens or operator precedence.
I defined a Const and an Expr class and defined operators inside of
them to create a parse tree, added a to_const method to Fixum and
created a regular expression to convert an expression 1+1 to
'1.to_const() + 1.to_const()', so evaluating that expression would
produce a parse tree for that experssion.
Emitting the bytescodes is then a post-order traversal of the parse
tree.
---- Compiler.rb
# Operator overrides to create an expression tree. Mixed into
# Const and Expr so:
# Const <op> Const => Expr
# Const <op> Expr => Expr
# Expr <op> Const => Expr
module CreateExpressions
def +(other) Expr.new(:add, self, other) end
def -(other) Expr.new(:sub, self, other) end
def *(other) Expr.new(:mul, self, other) end
def /(other) Expr.new(:div, self, other) end
def %(other) Expr.new(:mod, self, other) end
def **(other) Expr.new(:pow, self, other) end
end
# Add a method to fixnum to create a const from an integer
class Fixnum
def to_const
Const.new(self)
end
end
# An integer value
class Const
include CreateExpressions
# Opcodes to push shorts or longs respectively onto the stack
OPCODES = {2 => 0x01, 4 => 0x02}
def initialize(i)
@value = i
end
def to_s
@value
end
# Emits the bytecodes to push a constant on the stack
def emit
# Get the bytes in network byte order
case @value
when (-32768..32767): bytes = [@value].pack("n").unpack("C*")
else bytes = [@value].pack("N").unpack("C*")
end
bytes.insert 0, OPCODES[bytes.size]
end
end
# A binary expression
class Expr
include CreateExpressions
OPCODES = {:add => 0x0a, :sub => 0x0b, :mul => 0x0c, :pow => 0x0d,
:div => 0x0e, :mod => 0x0f}
def initialize(op, a, b)
@op = op
@first = a
@second = b
end
# Emits a human-readable s-expression for testing
# (preorder traversal of parse tree)
def to_s
"(#{@op.to_s} #{@first.to_s} #{@second.to_s})"
end
# Bytecode emitter for an expression (postorder traversal of parse
tree)
def emit
# emit LHS, RHS, opcode
@first.emit << @second.emit << OPCODES[@op]
end
end
# Compile and print out parse tree for expressions
class Compiler
# Creates bytecodes from an arithmatic expression
def self.compile(expr)
self.mangle(expr).emit.flatten
end
# Prints a representation of the parse tree as an S-Expression
def self.explain(expr)
self.mangle(expr).to_s
end
private
# Name-mangles an expression so we create a parse tree when calling
# Kernel#eval instead of evaluating the expression:
# [number] => [number].to_const()
def self.mangle(expr)
eval(expr.gsub(/\d+/) {|s| "#{s}.to_const()"})
end
end