1 files changed, 75 insertions, 0 deletions
diff --git a/grammar.lua b/grammar.lua
new file mode 100644
index 0000000..27e75f7
--- /dev/null
+++ b/grammar.lua
@@ -0,0 +1,75 @@
+local module = {}
+setmetatable(module, {__index=_G})
+setfenv(1, module)
+
+
+local Grammar = {}
+
+function module.createGrammar(nonterminals, functions, terminals)
+  local self = {
+    nonterminals = nonterminals,
+    functions = functions,
+    terminals = terminals,
+  }
+  setmetatable(self, {__index=Grammar})
+  return self
+end
+
+
+function Grammar.expandSymbol(self, sequence, index, expansion)
+  table.remove(sequence, index)
+  for i=1,#expansion do
+    table.insert(sequence, index+i-1, expansion[i])
+  end
+end
+
+
+function Grammar.expandSequence(self, sequence, n)
+  local i = 1
+  while i <= #sequence do
+    local choices = self.nonterminals[sequence[i]]
+    if choices then
+      if #choices == 1 then
+        self:expandSymbol(sequence, i, choices[1])
+        return true, 0
+      else
+        local choice = choices[1 + (n % #choices)]
+        self:expandSymbol(sequence, i, choice)
+        return true, 1
+      end
+    else
+      i = i+1
+    end
+  end
+  return false, 0
+end
+
+
+function Grammar.expand(self, genome, maxLength)
+  maxLoops = maxLoops or 2
+  local sequence = { '<start>' }
+  local geneIndex = 0
+  local count = 0
+  local continue = true
+  while continue do
+    local gene
+    if (count > maxLoops * #genome) then
+      gene = 0
+    else
+      gene = genome[1 + (geneIndex % #genome)]
+    end
+    local increment
+    continue, increment = self:expandSequence(sequence, gene)
+    if not continue then break end
+    geneIndex = geneIndex+increment
+    count = count + 1
+  end
+  local result = ''
+  for _, s in ipairs(sequence) do
+    result = result .. s .. ' '
+  end
+  return result
+end
+
+
+return module