BNF in itself in.lua

BNF = { }

-- create definition
BNF["::="] = function (stack)
  local non_terminal = pop(stack) ;
  push(BNF,non_terminal) ; end

-- add words to definition
BNF[";"] = function (stack)
  local non_terminal = pop(BNF)
  local list_of_words = stack; -- FIX: treats stack as list, rather than stack, so values aren't pop-off
  BNF[non_terminal] = {  table.concat(list_of_words,",") } ; end

forth_core.lua

push = function (stack, x) return table.insert(stack, x); end
pop = function (stack) local x = stack[#stack]; table.remove(stack,#stack); return x; end

lookup = function (dict,word) return dict[word]; end
execute = function (dict,word,stack) return dict[word](stack); end
interpret = function (dict,stack,x) if lookup(dict,x) then push(stack,execute(dict,x,stack)) else push(stack,x) end; end
                                    -- lookup(dict,x) and push(stack,execute(dict,x,stack)) or push(stack,x)

show_input = function (dict,x) return string.format("input:\t%s\ttype:%s",x,lookup(dict,x)); end
show_stack = function (stack) return table.concat(stack," "); end
show_dict = function (dict) local s = ""; for k,v in pairs(dict) do s = s .. string.format("[%s]\t=\t%s,\n", k, v); end; return s; end
print_env = function (dict,stack,x) io.write(string.format("%s\nstack:\t%s\ndict:\n%s\n\n", show_input(dict,x), show_stack(stack), show_dict(dict))); end
repl = function (dict,stack,code) for word in code:gmatch("%S+") do interpret(dict,stack,word); print_env(dict,stack,word); end; end;

my grammar.adoc

What it looks like in BNF

<myword> ::= "hello" "world" ;

What it looks like in lua, with data-structures

production_rules = { "<myword>", "::=", "hello", "world", ";"  }
production_rules = { ["<myword>"]={"hello", "world"} }

terminals = { "hello ", "world" }
non_terminals = { "<myword>" }

---

ASIDE:

This would actually be a bit easier if BNF was defined with postfix: (since forth is a post fix language)

"world" "hello" ; <myword> ::=

with:

-- add words to definition
BNF[";"] = function (stack)
  local non_terminal = pop(BNF)
  BNF[non_terminal] = {}
  repeat push(BNF[non_terminal], pop(stack)) until #stack == 0 ; end

In this case the termination symbol ;, wouldn’t be as neccesary. Since ::= would pop the string at the top of the stack (myword), we could choose to either have what remains on the stack as being the definition (of myword), or specify the amount of words that are whithin the defintion, for example:

"world" "hello" 2 <myword> ::=
"everything" "is" "how" "world" "hello" 5 <anotherword> ::=

The reason stack-based languages don’t define their words like this (in postfix), is that the intrepreter would execute the words that are part of a definition, for example:

: add5andthenprint ( num -- ) 5 + . ;                       (1)
5 + . 3 add5andthenprint ::=                                (2)
5 + . ; add5andthenprint ::=                                (3)

1. a word defined, as its usually defined in forth, the : tells it to stop executing and enter compilation mode

2. a word defined with our weird postfix notation

3. another word defined with our weird postfix notation, here’s lets assume that ; pushes the number 3 onto the stack

my grammar.lua

-- initiate the needed data-structures 
data_stack = {}
dictionary = {}

-- import the BNF vocabulary to our dictionary
dictionary = BNF

my_program = [[
  <greetings> ::= hello world ;
  <farewell> ::= see you soon ;
  <conversation> ::= <greetings> <farewell> ;
]]

repl(dictionary,data_stack,my_program)

https://www.lua.org/cgi-bin/demo

interpret = function (dict,stack,x)
if type(lookup(dict,x)) == "function" then push(stack,execute(dict,x,stack))
elseif type(lookup(dict,x)) == "table" then repeat push(stack, pop(lookup(dict,x))) until #lookup(dict,x) == 0       -- 1
else push(stack,x)
end; end

1. the problem with pop-ing, is that if we have <greetings> ::= hello world ; afterwards we have <greetings> ::= ;

unfortunately since formal grammars are defined in terms of sets (𝐍, 𝚺, 𝐏, 𝐒), this code is failing a bit. Elements in sets are unordered & unique, and while that may be true of 𝐍 and 𝚺 (as they are defined), when considering 𝐏 this becomes problematic. 𝐏 is defined as the sets of production rules, but what a production rule is is normally rather informally defined as simply string rewriting.

one of these things is not like the others

consider: <generic> ::= hello world bye world ; (or if you want written: S → hello world bye world), we see that world is used twice, and the order matters here.

repl(dictionary,data_stack,my_program)
print("================================================")
print(
pop(BNF["<conversation>"]),
pop(BNF["<conversation>"]),
pop(BNF["<conversation>"]),
pop(BNF["<conversation>"]),
pop(BNF["<conversation>"])
)

redefine as: ;; the termination and printing of the S rule