# Re: Bytecode Compiler (#100)

**URL:** <https://www.ruby-forum.com/t/re-bytecode-compiler-100/75043>\
**Category:** Ruby\
**Created:** [November 7, 2006, 11:07am UTC](https://www.ruby-forum.com/t/re-bytecode-compiler-100/75043 "2006-11-07T11:07:54Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ken\_Allen](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/e95f7d/32.png) [@Ken\_Allen](https://www.ruby-forum.com/u/Ken_Allen)\
**Post date:** [November 7, 2006, 11:07am UTC](https://www.ruby-forum.com/t/re-bytecode-compiler-100/75043/1 "2006-11-07T11:07:54Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Ken\_Allen](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/e95f7d/32.png) [@Ken\_Allen](https://www.ruby-forum.com/u/Ken_Allen)\
**Post date:** [November 7, 2006, 11:07am UTC](https://www.ruby-forum.com/t/re-bytecode-compiler-100/75043/2 "2006-11-07T11:07:55Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Ken\_Allen](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/e95f7d/32.png) [@Ken\_Allen](https://www.ruby-forum.com/u/Ken_Allen)\
**Post date:** [November 7, 2006, 11:08am UTC](https://www.ruby-forum.com/t/re-bytecode-compiler-100/75043/3 "2006-11-07T11:08:26Z")

</div>

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