thue.lua

#!/bin/env lua

local function trim(s)
	local l = 1
	while s:sub(l, l):find "%s" do
		l = l + 1
	end
	local r = #s
	while s:sub(r, r):find "%s" do
		r = r - 1
	end
	return s:sub(l, r)
end

local function die(s, ...)
	io.stderr:write(s:format(...), '\n')
	os.exit(-1)
end

local debug = false
if arg[1] == '-debug' then
	debug = true
	table.remove(arg, 1)
end

if arg[1] then
	local f, e = io.open(arg[1], "rb")
	if not f then die(e) end
	io.input(arg[1])
end

local rules = {}

local line = 1
while true do
	local l = io.read()
	if not l then die "no starting state" end
	local a, b = l:match '(.-)::=(.*)'
	if a then
		a, b = trim(a), trim(b)
		if a == "" then
			if b == "" then break end
			die("line %d has empty left-hand side\n", line)
		end
		if a == "" and b == "" then break end
		rules[#rules + 1] = { a, b }
	end
	line = line + 1
end

local input = io.read()
while input and trim(input) == "" do input = io.read() end

if not input then die "no starting state" end

repeat
	local applied = false
	for _, r in ipairs(rules) do
		local s, e = input:find(r[1])
		if s and e then
			local b = r[2]
			if b:sub(1, 1) == '~' then
				io.write(b:sub(2), "\n")
				r[2] = ""
			elseif b == ":::" then
				local i = io.read()
				if not i then os.exit() end
				r[2] = i
			end
			local oldinput = input
			input = input:sub(1, s - 1) .. r[2] .. input:sub(e + 1)
			if debug then
				io.stderr:write(string.format(
					"dbg: %s -> %s\n",
					oldinput, input
				))
			end
			applied = true
		end
	end
until not applied

io.write(input, '\n')