Last active
July 19, 2022 18:01
-
-
Save Shritesh99/0a9d7b1a040249d1b525ab94198a42ac to your computer and use it in GitHub Desktop.
Lua Parser+Interpreter for a given Grammer Defination.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
--[[ | |
A simple Lua Parser + Interpreter using | |
LPegLabel(https://github.com/sqmedeiros/lpeglabel) | |
with an error recovery mechanism for the following | |
grammer. | |
Program -> (Cmd | Exp)* | |
Cmd -> var = Exp | |
Exp -> Exp + Term | Exp - Term | Term | |
Term -> Term * Factor | Term / Factor | Factor | |
Factor -> num | var | (Exp) | |
--]] | |
--> Importing Modules | |
local m = require'lpeglabel' | |
local re = require'relabel' | |
--> AST (Abstract Syntax Tree) | |
local ast = {} | |
function ast.prog_stmnt(lines) | |
return { | |
type = "prog"; | |
lines = lines; | |
} | |
end | |
function ast.cmd_stmnt(var, eq, exp) | |
return { | |
type = "cmd"; | |
var = var; | |
value = exp; | |
} | |
end | |
function ast.op_stmnt(ops) | |
local node = ops[1] | |
for i = 2, #ops, 2 do | |
node = { | |
type = "op"; | |
op = ops[i]; | |
left = node; | |
right = ops[i+1]; | |
} | |
end | |
return node | |
end | |
function ast.num_stmnt(num) | |
return { | |
type = "num"; | |
value = tonumber(num); | |
} | |
end | |
function ast.var_stmnt(var) | |
return { | |
type = "var"; | |
name = var; | |
} | |
end | |
function ast.getstmnt(open, exp, close) | |
return exp | |
end | |
function ast.neg_stmnt(minus, exp) | |
return ast.op_stmnt({ast.num_stmnt(0), "-", exp}) | |
end | |
--> Errors Labels | |
local errors = { | |
assignExp = "Expected expression of '='", | |
operator = "Expecter expression after operator", | |
openParExp = "Expected expression after '('", | |
negExp = "Expected expression after '-'", | |
closePar = "Expected ')'", | |
eof = "Error, expecting EOF", | |
fail = "Undefined Error" | |
} | |
--> Grammer Defination | |
local g = re.compile([[ | |
START <- PROGRAM Sp (!. / %{eof}) | |
PROGRAM <- {| (CMD / EXP)* |} -> prog_stmnt | |
CMD <- (VAR ASSIGNMENT EXP^assignExp) -> cmd_stmnt | |
EXP <- {| TERM ((ADD / SUB) EXP^operator)* |} -> op_stmnt | |
TERM <- {| FACTOR ((DIV / MUL) TERM^operator)* |} -> op_stmnt | |
FACTOR <- (OPENPAR EXP^openParExp CLOSEPAR^closePar) -> getstmnt | |
/ NUMBER -> num_stmnt | |
/ VAR -> var_stmnt | |
/ (SUB FACTOR^negExp) -> neg_stmnt | |
OPENPAR <- Sp { '(' } | |
CLOSEPAR <- Sp { ')' } | |
ADD <- Sp { '+' } | |
SUB <- Sp { '-' } | |
ASSIGNMENT <- Sp { '=' } | |
MUL <- Sp { '*' } | |
DIV <- Sp { '/' } | |
VAR <- Sp { [a-z]+ } | |
NUMBER <- Sp { [0-9]+ } | |
Sp <- (%s / %nl)* | |
]], { | |
prog_stmnt = ast.prog_stmnt; | |
cmd_stmnt = ast.cmd_stmnt; | |
op_stmnt = ast.op_stmnt; | |
num_stmnt = ast.num_stmnt; | |
var_stmnt = ast.var_stmnt; | |
getstmnt = ast.getstmnt; | |
neg_stmnt = ast.neg_stmnt; | |
}) | |
--> Parse Function | |
function parse(g, s) | |
local r, e, pos = g:match(s) | |
if not r then | |
local line, col = re.calcline(s, pos) | |
local msg = "\nError at line " .. line .. " (col " .. col .. "): " | |
print(msg .. errors[e]) | |
return r, msg .. errors[e] .."\n" | |
end | |
return r | |
end | |
--> Interpret Function | |
local function new_var_tbl() | |
var_tbl = {} | |
return var_tbl | |
end | |
function interpret(node, var_tbl) | |
if not var_tbl then var_tbl = new_var_tbl() end | |
if node.type == "prog" then | |
local result, err | |
for i, node in ipairs(node.lines) do | |
result, err = interpret(node, var_tbl) | |
if err then | |
err = "Error: " .. err .. " in line " .. i | |
print(err) | |
return nil, err | |
end | |
if result then | |
print(result) | |
end | |
end | |
return result | |
elseif node.type == "cmd" then | |
local value, err = interpret(node.value, var_tbl) | |
if err then return nil, err end | |
var_tbl[node.var] = value | |
return nil | |
elseif node.type == "op" then | |
local left, err = interpret(node.left, var_tbl) | |
if err then return nil, err end | |
local right, err = interpret(node.right, var_tbl) | |
if err then return nil, err end | |
if node.op == "+" then return left + right | |
elseif node.op == "-" then return left - right | |
elseif node.op == "*" then return left * right | |
elseif node.op == "/" then return left / right | |
else | |
return nil, "unknown operation " .. node.op | |
end | |
elseif node.type == "num" then | |
return node.value | |
elseif node.type == "var" then | |
if var_tbl[node.name] then | |
return var_tbl[node.name] | |
else | |
return nil, "Undefined variable " .. node.name | |
end | |
else | |
return nil, "Unknown node type " .. node | |
end | |
end | |
--> Interpreter | |
local function interpreter(s) | |
local p = parse(g, s) | |
if p then | |
interpret(p) | |
end | |
end | |
--> Sample Strings | |
interpreter("") | |
interpreter("34") | |
interpreter("34 + a") | |
interpreter("10 + 20 *30") | |
interpreter("a = 10 + 20 a") | |
interpreter("a = (5 +(10 - (20 *(30/3)))) a") | |
interpreter("a = 42 / 6 a = 10*a + 4 a") | |
interpreter("a = 9 (-a + 1)") | |
interpreter("-3--7") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Lua Parser+Interpreter
A simple Lua Parser + Interpreter using LPegLabel with an error recovery mechanism for the following grammer.