\BV interpreter in sed (ICFPC 2013)

去年と似たようなネタでこっちの方がはるかにラクでしたけど、まぁまともに参加できる日程でなかったので…

使いかたはプログラムと入力を空白くぎりで入れる感じ。

$ echo '(lambda (x_78920) (fold 0 (not (xor (not (shr1 (not (plus (if0 (plus (not (shr16 (xor (not (or x_78920 (shr4 x_78920))) 0))) x_78920) x_78920 0) x_78920)))) 0)) (lambda (x_78921 x_78922) (or (shr4 x_78921) x_78922)))) 0xFEDCBA9876543210' | sed -f bv.sed
0x91A2B3C4D5E6F7

コード。 GNU sedMacsed で動作確認

h
s/.* //

s/0x//
y/abcdef/ABCDEF/
s/^/0000000000000000/
s/.*\(.\{16\}\)$/\1@/

:hex2bin

s/$/;10;32;54;76;98;BA;DC;FE/
s/\(.\)@\([^;]*\).*;\1\(.\).*/\3@1\2/
s/@\([^;]*\);.*/@0\1/

s/$/;20;64;A8;EC/
s/\(.\)@\([^;]*\).*;\1\(.\).*/\3@1\2/
s/@\([^;]*\);.*/@0\1/

s/$/;40;C8/
s/\(.\)@\([^;]*\).*;\1\(.\).*/\3@1\2/
s/@\([^;]*\);.*/@0\1/

s/8@/;@1/
s/0@/@0/
s/;//

/^@/!b hex2bin
s/^@//

x
s/\(.*\) .*/\1/
s/ 0/ 0000000000000000000000000000000000000000000000000000000000000000/g
s/ 1/ 0000000000000000000000000000000000000000000000000000000000000001/g
G

s/^(lambda (\([a-zA-Z0-9_]*\)) \(.*\))/\1@\2/
:subst
s/^\(.*\)@\(.* \)\1\(.*\n\)\(.*\)/\1@\2\4\3\4/
/^\(.*\)@.* \1/ b subst

s/.*@//
s/\n.*//

h
x
s/.*//
x

:main_loop

# i\
# === main loop pattern space ===
# p
# x
# i\
# === main loop hold space ===
# p
# x

/;fold1  /{
  s/;fold1  //
  s/ .*//
  b ret
}

/;fold1/{
  s/\(;fold1 [01]* \)\([01]*\)\( .*\)/\1@\3 #\2/

  H
  x
  s/ #.*//
  x

  :acc_subst_loop
  s/!//
  s/\(@ [a-zA-Z0-9_]* \)\([a-zA-Z0-9_]*\)\( .*\) \2\([^a-zA-Z0-9_].* #\(.*\)\)/\1\2\3 \5\4!/
  /!/ b acc_subst_loop
  s/ #.*//

  :iter_subst_loop
  s/!//
  s/\([01]\{8\}\) @ \([a-zA-Z0-9_]*\)\( .*\) \2\([^a-zA-Z0-9_].*\)/\1 @ \2\3 00000000000000000000000000000000000000000000000000000000\1\4!/
  /!/ b iter_subst_loop

  s/[^(]*(/(/
  b main_loop
}

s/(if0 0\{64\} \([01]\{64\}\) [01]\{64\})/\1/
s/(if0 0*1[01]* [01]\{64\} \([01]\{64\}\))/\1/

s/(not \([01]*\))\(.*\)/@\2;not \1/
/;not/{
  H
  s/.*;not //
  y/01/10/
  b ret
}

s/(shl1 \([01]*\))\(.*\)/@\2;shl1 \1/
/;shl1/{
  H
  s/.*;shl1 //
  s/^.//
  s/$/0/
  b ret
}

s/(shr1 \([01]*\))\(.*\)/@\2;shr1 \1/
/;shr1/{
  H
  s/.*;shr1 //
  s/.$//
  s/^/0/
  b ret
}

s/(shr4 \([01]*\))\(.*\)/@\2;shr4 \1/
/;shr4/{
  H
  s/.*;shr4 //
  s/....$//
  s/^/0000/
  b ret
}

s/(shr16 \([01]*\))\(.*\)/@\2;shr16 \1/
/;shr16/{
  H
  s/.*;shr16 //
  s/................$//
  s/^/0000000000000000/
  b ret
}

s/(and \([01]*\) \([01]*\))\(.*\)/@\3;and \1 \2/
/;and/{
  H
  s/.*;and //
  s/$/;/

  :and_loop
  s/1\( .*\)1;/\1;1/
  s/0\( .*\).;/\1;0/
  s/.\( .*\)0;/\1;0/
  /^ ;/ ! b and_loop

  s/ ;//
  b ret
}

s/(or \([01]*\) \([01]*\))\(.*\)/@\3;or \1 \2/
/;or/{
  H
  s/.*;or //
  s/$/;/

  :or_loop
  s/0\( .*\)0;/\1;0/
  s/1\( .*\).;/\1;1/
  s/.\( .*\)1;/\1;1/
  /^ ;/ ! b or_loop

  s/ ;//
  b ret
}

s/(xor \([01]*\) \([01]*\))\(.*\)/@\3;xor \1 \2/
/;xor/{
  H
  s/.*;xor //
  s/$/;/

  :xor_loop
  s/\([01]\)\( .*\)\1;/\2;0/
  s/1\( .*\)0;/\1;1/
  s/0\( .*\)1;/\1;1/
  /^ ;/ ! b xor_loop

  s/ ;//
  b ret
}

s/(plus \([01]*\) \([01]*\))\(.*\)/@\3;plus \1 \2/
/;plus/{
  H
  s/.*;plus //
  s/$/;/

  :plus_loop
  s/0\( .*\)0;/\1;0/
  s/1\( .*\)0;/\1;1/
  s/0\( .*\)1;/\1;1/
  s/1\( .*\)1;/\1:0/
  s/0\( .*\)0:/\1;1/
  s/1\( .*\)0:/\1:0/
  s/0\( .*\)1:/\1:0/
  s/1\( .*\)1:/\1:1/
  /^ [;:]/ ! b plus_loop

  s/ .//
  b ret
}

s/(fold \([01]*\) \([01]*\) (lambda (\([a-zA-Z0-9_]*\) \([a-zA-Z0-9_]*\)) \(.*\)/@\5;fold \1 \2 \3 \4 !/
/;fold/{
  :paren_match_loop
  s/@\([^()]*(\)\(.*\)!\(.*\)/@\2!!\3\1/
  s/@\([^()]*)\)\(.*\)!\(.*\)/@\2\3\1/
  /!!/ b paren_match_loop
  s/@))/@/
  s/!//
  H

  s/.*;fold/;fold1/
  b main_loop
}

/(/{
  s/.*/Unknown operation/
  q
}

x
/;fold1/{
  s/\(;fold1 [01]*\)[01]\{8\}/\1/
  s/$/;/
  x
  b ret
}
x

s/$/@/
:bin2hex
s/0000@/@0/
s/0001@/@1/
s/0010@/@2/
s/0011@/@3/
s/0100@/@4/
s/0101@/@5/
s/0110@/@6/
s/0111@/@7/
s/1000@/@8/
s/1001@/@9/
s/1010@/@A/
s/1011@/@B/
s/1100@/@C/
s/1101@/@D/
s/1110@/@E/
s/1111@/@F/

/^@/! b bin2hex

s/^@0*/0x/
s/x$/x0/

q

:ret
G
s/\(.*\)\n\n\(.*\n\)*\(.*\)@\(.*\);.*$/\3\1\4/
x
y/\n/!/
s/![^!]*$//
y/!/\n/
x
s/\n//
b main_loop

成績自体は 3 時間くらいで作ったやつで遊んで

    "contestScore": 281,
    "lightningScore": 198,
    "trainingScore": 1,
    "mismatches": 31,
    "numRequests": 753,
    "cpuTotalTime": 737.843
なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h