Tetszik 0
Fork 0

Utoljára aktív 3 months ago

capitalex's Avatar capitalex gist felülvizsgálása 3 months ago. Revízióhoz ugrás

1 file changed, 183 insertions

benthos.lua(fájl létrehozva)

@@ -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))
Újabb Régebbi

Ez az oldal Opengist alapú ⋅ Load: 17ms⋅

Magyar