benthos.lua(файл создан)
| @@ -0,0 +1,183 @@ | |||
| 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)) | |
Новее
Позже