benthos.lua
· 5.5 KiB · Lua
Brut
Playground
local LEFT, RIGHT, LABEL, SYMBOL = 1, 2, 1, 2
local pprint = require "pprint"
local function read_symbol(stream)
local char, symbol = stream(), {}
if not char then return nil end
while char:match("%s") do char = stream() end
while char:match("%S") do table.insert(symbol, char) char = stream() end
return table.concat(symbol)
end
local function print_stacks(stacks)
for key, stack in pairs(stacks) do
io.write(key) io.write(":")
for i = #stack, 1, -1 do
local symbol = stack[i]
io.write(" ") io.write(symbol)
end
io.write("\n")
end
end
local function parse_program(program)
local side, rules, stream = LEFT, {{{}, {}}}, program:gmatch(".")
local label, rule_delimiter
local function push_pair(label, symbol)
table.insert(rules[#rules][side], {label, symbol})
end
while true do
local symbol = read_symbol(stream)
if not symbol then
if label then push_pair(label, "") end
break
elseif not rule_delimiter then
rule_delimiter = symbol
elseif rule_delimiter == symbol then
if label then push_pair(label, "") end
if side == RIGHT then table.insert(rules, {{}, {}}) end
label, side = nil, side == LEFT and RIGHT or LEFT
elseif not label and symbol:sub(1,1) == "/" then
push_pair(symbol:sub(2), "")
elseif not label then
label = symbol
else
push_pair(label, symbol)
label = nil
end
end
if label then push_pair(label, "") end
return rules
end
local function run(rules)
local stacks = {}
for i = #rules, 1, -1 do
local rule = rules[i]
if #rule[LEFT] == 0 then
for _, pair in ipairs(rule[RIGHT]) do
if not stacks[pair[LABEL]] then stacks[pair[LABEL]] = {} end
table.insert(stacks[pair[LABEL]], 1, pair[SYMBOL])
end
table.remove(rules, i)
end
end
local rewrite_happened repeat
rewrite_happened = false
for _, rule in ipairs(rules) do
local retain, bindings, success = {}, {}, true
for _, pattern in ipairs(rule[LEFT]) do
local label, pat = pattern[LABEL], pattern[SYMBOL]
if not stacks[label] then success = false break end
if #stacks[label] == 0 then success = false break end
local symbol = stacks[label][#stacks[label]]
table.remove(stacks[label])
table.insert(retain, {label, symbol})
if pat:sub(1, 1) == "$" then
if not bindings[pat] then
bindings[pat] = symbol
elseif bindings[pat] ~= symbol then
success = false break
end
elseif pat ~= symbol then
success = false break
end
end
rewrite_happened = success
while #retain ~= 0 do
if not success then
local pair = retain[#retain]
table.remove(retain)
table.insert(stacks[pair[LABEL]], pair[SYMBOL])
else
retain = {}
end
end
if success then
for i = #rule[RIGHT], 1, -1 do
local pair = rule[RIGHT][i]
local r_label, r_symbol, binding = pair[LABEL], pair[SYMBOL], bindings[pair[SYMBOL]]
if not stacks[r_label] then stacks[r_label] = {} end
table.insert(stacks[r_label], binding and binding or r_symbol)
end
break
end
end
until not rewrite_happened
print_stacks(stacks)
end
local program = [[
=== === # bubble # sort /#
#list 2
#list 3
#list 1
#list 4
#list 0
=== # bubble # sort /# #list $x #list $y ===
# ord # $x # $y /#
# sort # $x # $y /#
# bubble # sort /#
=== # bubble # sort /# /request.sort ===
# move # ~list # to # list /#
# bubble # sort /#
=== # bubble # sort /# ===
# move # ~list # to # list /#
=== # move # ~list # to # list /# ~list $x ===
# move # ~list # to # list /# #list $x
=== # move # ~list # to # list /# ===
=== # sort # $x # $y /# #ord gt ===
~list $y #list $x
# request # another # sort /#
=== # sort # $x # $y /# #ord eq ===
~list $y ~list $x
=== # sort # $x # $y /# #ord lt ===
~list $x #list $y
=== # request # another # sort /# /request.sort ===
/request.sort
=== # request # another # sort /# ===
/request.sort
=== # ord # 0 # 0 /# === #ord eq
=== # ord # 0 # 1 /# === #ord lt
=== # ord # 0 # 2 /# === #ord lt
=== # ord # 0 # 3 /# === #ord lt
=== # ord # 0 # 4 /# === #ord lt
=== # ord # 1 # 1 /# === #ord eq
=== # ord # 1 # 2 /# === #ord lt
=== # ord # 1 # 3 /# === #ord lt
=== # ord # 1 # 4 /# === #ord lt
=== # ord # 2 # 2 /# === #ord eq
=== # ord # 2 # 3 /# === #ord lt
=== # ord # 2 # 4 /# === #ord lt
=== # ord # 3 # 3 /# === #ord eq
=== # ord # 3 # 4 /# === #ord lt
=== # ord # 4 # 4 /# === #ord eq
=== # ord # $x # $y /# ===
# ord # $y # $x /#
# is # gt /#
=== # is # gt /# #ord lt ===
#ord gt
]]
run(parse_program(program))
| 1 | local LEFT, RIGHT, LABEL, SYMBOL = 1, 2, 1, 2 |
| 2 | local pprint = require "pprint" |
| 3 | local function read_symbol(stream) |
| 4 | local char, symbol = stream(), {} |
| 5 | if not char then return nil end |
| 6 | while char:match("%s") do char = stream() end |
| 7 | while char:match("%S") do table.insert(symbol, char) char = stream() end |
| 8 | return table.concat(symbol) |
| 9 | end |
| 10 | |
| 11 | local function print_stacks(stacks) |
| 12 | for key, stack in pairs(stacks) do |
| 13 | io.write(key) io.write(":") |
| 14 | for i = #stack, 1, -1 do |
| 15 | local symbol = stack[i] |
| 16 | io.write(" ") io.write(symbol) |
| 17 | end |
| 18 | io.write("\n") |
| 19 | end |
| 20 | end |
| 21 | |
| 22 | local function parse_program(program) |
| 23 | local side, rules, stream = LEFT, {{{}, {}}}, program:gmatch(".") |
| 24 | local label, rule_delimiter |
| 25 | |
| 26 | local function push_pair(label, symbol) |
| 27 | table.insert(rules[#rules][side], {label, symbol}) |
| 28 | end |
| 29 | |
| 30 | while true do |
| 31 | local symbol = read_symbol(stream) |
| 32 | if not symbol then |
| 33 | if label then push_pair(label, "") end |
| 34 | break |
| 35 | elseif not rule_delimiter then |
| 36 | rule_delimiter = symbol |
| 37 | elseif rule_delimiter == symbol then |
| 38 | if label then push_pair(label, "") end |
| 39 | if side == RIGHT then table.insert(rules, {{}, {}}) end |
| 40 | label, side = nil, side == LEFT and RIGHT or LEFT |
| 41 | elseif not label and symbol:sub(1,1) == "/" then |
| 42 | push_pair(symbol:sub(2), "") |
| 43 | elseif not label then |
| 44 | label = symbol |
| 45 | else |
| 46 | push_pair(label, symbol) |
| 47 | label = nil |
| 48 | end |
| 49 | end |
| 50 | |
| 51 | if label then push_pair(label, "") end |
| 52 | |
| 53 | return rules |
| 54 | end |
| 55 | |
| 56 | local function run(rules) |
| 57 | local stacks = {} |
| 58 | for i = #rules, 1, -1 do |
| 59 | local rule = rules[i] |
| 60 | if #rule[LEFT] == 0 then |
| 61 | for _, pair in ipairs(rule[RIGHT]) do |
| 62 | if not stacks[pair[LABEL]] then stacks[pair[LABEL]] = {} end |
| 63 | table.insert(stacks[pair[LABEL]], 1, pair[SYMBOL]) |
| 64 | end |
| 65 | table.remove(rules, i) |
| 66 | end |
| 67 | end |
| 68 | local rewrite_happened repeat |
| 69 | rewrite_happened = false |
| 70 | for _, rule in ipairs(rules) do |
| 71 | local retain, bindings, success = {}, {}, true |
| 72 | for _, pattern in ipairs(rule[LEFT]) do |
| 73 | local label, pat = pattern[LABEL], pattern[SYMBOL] |
| 74 | if not stacks[label] then success = false break end |
| 75 | if #stacks[label] == 0 then success = false break end |
| 76 | |
| 77 | local symbol = stacks[label][#stacks[label]] |
| 78 | table.remove(stacks[label]) |
| 79 | table.insert(retain, {label, symbol}) |
| 80 | if pat:sub(1, 1) == "$" then |
| 81 | if not bindings[pat] then |
| 82 | bindings[pat] = symbol |
| 83 | elseif bindings[pat] ~= symbol then |
| 84 | success = false break |
| 85 | end |
| 86 | elseif pat ~= symbol then |
| 87 | success = false break |
| 88 | end |
| 89 | end |
| 90 | rewrite_happened = success |
| 91 | while #retain ~= 0 do |
| 92 | if not success then |
| 93 | local pair = retain[#retain] |
| 94 | table.remove(retain) |
| 95 | table.insert(stacks[pair[LABEL]], pair[SYMBOL]) |
| 96 | else |
| 97 | retain = {} |
| 98 | end |
| 99 | end |
| 100 | if success then |
| 101 | for i = #rule[RIGHT], 1, -1 do |
| 102 | local pair = rule[RIGHT][i] |
| 103 | local r_label, r_symbol, binding = pair[LABEL], pair[SYMBOL], bindings[pair[SYMBOL]] |
| 104 | if not stacks[r_label] then stacks[r_label] = {} end |
| 105 | table.insert(stacks[r_label], binding and binding or r_symbol) |
| 106 | end |
| 107 | break |
| 108 | end |
| 109 | end |
| 110 | until not rewrite_happened |
| 111 | print_stacks(stacks) |
| 112 | end |
| 113 | |
| 114 | local program = [[ |
| 115 | === === # bubble # sort /# |
| 116 | #list 2 |
| 117 | #list 3 |
| 118 | #list 1 |
| 119 | #list 4 |
| 120 | #list 0 |
| 121 | |
| 122 | === # bubble # sort /# #list $x #list $y === |
| 123 | # ord # $x # $y /# |
| 124 | # sort # $x # $y /# |
| 125 | # bubble # sort /# |
| 126 | |
| 127 | === # bubble # sort /# /request.sort === |
| 128 | # move # ~list # to # list /# |
| 129 | # bubble # sort /# |
| 130 | |
| 131 | === # bubble # sort /# === |
| 132 | # move # ~list # to # list /# |
| 133 | |
| 134 | === # move # ~list # to # list /# ~list $x === |
| 135 | # move # ~list # to # list /# #list $x |
| 136 | |
| 137 | === # move # ~list # to # list /# === |
| 138 | |
| 139 | === # sort # $x # $y /# #ord gt === |
| 140 | ~list $y #list $x |
| 141 | # request # another # sort /# |
| 142 | |
| 143 | === # sort # $x # $y /# #ord eq === |
| 144 | ~list $y ~list $x |
| 145 | |
| 146 | === # sort # $x # $y /# #ord lt === |
| 147 | ~list $x #list $y |
| 148 | |
| 149 | === # request # another # sort /# /request.sort === |
| 150 | /request.sort |
| 151 | |
| 152 | === # request # another # sort /# === |
| 153 | /request.sort |
| 154 | |
| 155 | === # ord # 0 # 0 /# === #ord eq |
| 156 | === # ord # 0 # 1 /# === #ord lt |
| 157 | === # ord # 0 # 2 /# === #ord lt |
| 158 | === # ord # 0 # 3 /# === #ord lt |
| 159 | === # ord # 0 # 4 /# === #ord lt |
| 160 | |
| 161 | === # ord # 1 # 1 /# === #ord eq |
| 162 | === # ord # 1 # 2 /# === #ord lt |
| 163 | === # ord # 1 # 3 /# === #ord lt |
| 164 | === # ord # 1 # 4 /# === #ord lt |
| 165 | |
| 166 | === # ord # 2 # 2 /# === #ord eq |
| 167 | === # ord # 2 # 3 /# === #ord lt |
| 168 | === # ord # 2 # 4 /# === #ord lt |
| 169 | |
| 170 | === # ord # 3 # 3 /# === #ord eq |
| 171 | === # ord # 3 # 4 /# === #ord lt |
| 172 | |
| 173 | === # ord # 4 # 4 /# === #ord eq |
| 174 | |
| 175 | === # ord # $x # $y /# === |
| 176 | # ord # $y # $x /# |
| 177 | # is # gt /# |
| 178 | |
| 179 | === # is # gt /# #ord lt === |
| 180 | #ord gt |
| 181 | ]] |
| 182 | |
| 183 | run(parse_program(program)) |