[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Re: [QUIZ] Bytecode Compiler (#100

Ken Allen

11/6/2006 8:40:00 PM

This is my first post to ruby-talk and my first stab at a ruby quiz!
Hooray!
I used rparsec because I was too lazy to write a simple parser. And I
used some cute monkey patching that I shouldn't have.
But it works!

require 'rparsec/rparsec'

class Fixnum def to_bytes
if self >= -32768 && self <= 32767
a = [0x01]
a << ((self & 0x0000FF00) >> 8) a << ((self &
0x000000FF)) else
a = [0x02] a << ((self &
0xFF000000) >> 24) a << ((self & 0x00FF0000) >> 16)
a << ((self & 0x0000FF00) >> 8) a << ((self &
0x000000FF)) end
end end
class Symbol
def to_bytes
case self
when :+
[0x0a]
when :-
[0x0b]
when :*
[0x0c]
when :**
[0x0d]
when :/
[0x0e]
when :%
[0x0f]
end
end

def to_proc
proc { |x| x.send self }
end
end

class Array
alias to_bytes to_a
end

class Compiler
include Parsers
include Functors
def self.compile str
new.parser.parse str
end

def func sym
proc { |x, y| [x,y,sym].map(&:to_bytes).flatten }
end

def parser
ops = OperatorTable.new do |t|
t.infixl(char(?+) >> func(:+), 20)
t.infixl(char(?-) >> func(:-), 20)
t.infixl(char(?*) >> func(:*), 40)
t.infixl(char(?/) >> func(:/), 40)
t.infixl(char(?%) >> func(:%), 40)
t.infixl(string('**') >> func(:**), 60)
t.prefix(char(?-) >> Neg, 80)
end
expr = nil
term = integer.map(&To_i) | char('(') >> lazy{expr} << char(')')
delim = whitespace.many_
expr = delim >> Expressions.build(term, ops, delim)
end
end
2 Answers

Ken Allen

11/6/2006 8:44:00 PM

0

Aaaargh formatting explosion! Here's that first bit all nice and unexploded.

class Fixnum
def to_bytes
if self >= -32768 && self <= 32767
a = [0x01]
a << ((self & 0x0000FF00) >> 8)
a << ((self & 0x000000FF))
else
a = [0x02]
a << ((self & 0xFF000000) >> 24)
a << ((self & 0x00FF0000) >> 16)
a << ((self & 0x0000FF00) >> 8)
a << ((self & 0x000000FF))
end
end
end

class Symbol
def to_bytes
case self
when :+
[0x0a]
when :-
[0x0b]
when :*
[0x0c]
when :**
[0x0d]
when :/
[0x0e]
when :%
[0x0f]
end
end

def to_proc
proc { |x| x.send self }
end
end

Adam Shelly

11/6/2006 11:53:00 PM

0

Here is my solution. I tried to keep it short and simple.
Unfortunately, it got a little more complicated when I added code to
pass Marcel's test cases. But now it can handle '--++-++-2+-2'....


module Compiler

# The whole thing wrapped up into one function....
#
# The first half tokenizes into single chars or fixnums: it uses gsub
# to convert '**' to '^', binary '-'' to '~', and to remove pointless '+'s.
# Digits and most remaining '-'s are collected and converted using to_i.
# A few pesky unary '-'s are converted to the token 'n'
#
# The second half uses the shunting yard algorithm to build the RPN,
# and does the token->bytecode translation inline.
#
# The Tokens array contains 4 items: the character token, the bytecode,
# and two precedence values - one for a token on the stack,
# and another for a token in the stream. The values are only different
# if the operator is right-associative - this simplifies the conditional
# for deciding when to pop operators.
# The 'n' token is expanded to [0,swap,sub]

Tokens = [['+',10,3,3],['~',11,3,3],['*',12,2,2],['/',14,2,2],['%',15,2,2],
['^',13,1,0],['n',[1,0,0,0xa0,11],-1,-2],[nil,'(',9,9]]

def self.compile expr
num,tokens,output,stack='',[],[],[]

expr.gsub(/(\d|\))-/,'\1~').gsub(/(^|[^\d)])\++/,'\1').gsub("**","^").each_byte{|b|
if /\d|-/ =~ c=b.chr
num+=c
num.gsub!('--','')
else
tokens << (/\d/=~num ? num.to_i : 'n') and num='' unless num.empty?
tokens << c
end
}
tokens << num.to_i unless num.empty?

tokens.each{|token|
case token
when Integer
output += (-2**15...2**15)===token ?
[1]+[token].pack('n').unpack('C*') :
[2]+[token].pack('N').unpack('C*')
when '('
stack << token
when ')'
output << stack.pop until stack.last == '('
stack.pop
else
tokdef = Tokens.assoc(token)
output << stack.pop while t=stack.last and Tokens.rassoc(t)[2]
<= tokdef[3]
stack << tokdef[1]
end
}
(output+stack.reverse).flatten
end
end


--Adam