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))