positive binary number

binnum.rb

# positive binary number
# Compilers 2nd ed. ex. 5.4.3 (p. 337)
# https://gist.github.com/yamasushi/c5b79764bdbf8af995c5782c4bacc105

# B -> B1 0 { B.syn = 2 * B1.syn }
#    | B1 1 { B.syn = 2 * B1.syn + 1}
#    | 1 {B.syn = 1}

# B -> 1 {R.inh = 1} R {B.syn = R.syn}
# R -> 0 {R1.inh = R.inh * 2} R1 {R.syn = R1.syn}
# R -> 1 {R1.inh = R.inh * 2 + 1} R1 {R.syn = R1.syn}
# R -> ε {R.syn = R.inh}

def test(str)
  n,xs = B(str.chars)
  printf "result=%d( %#b ) xs=%s\n" ,n ,n ,xs
end

# B -> 1 {R.inh = 1} R {B.syn = R.syn}
def B(xs)
  raise "B: error xs=",xs if xs.empty?
  xs=match_terminal("1",xs)
  syn,xs=R(1,xs)
  return [syn,xs]
end

# R -> 0 {R1.inh = R.inh * 2} R1 {R.syn = R1.syn}
# R -> 1 {R1.inh = R.inh * 2 + 1} R1 {R.syn = R1.syn}
# R -> ε {R.syn = R.inh}
def R(inh,xs)
  return [inh,xs] if xs.empty? # ε
  case xs[0]
  when "0"
    return R( inh*2 , xs[1..] )
  when "1"
    return R( inh*2 + 1  , xs[1..] )
  else
    return [inh,xs] # ε
  end
end

def match_terminal(t,xs)
  raise "match_terminal: error t=#{t} xs=#{xs}" if xs.empty? or t!=xs[0]
  return xs[1..]
end