--[[ Expression Language 1 Prefix Parser Module (LPEG)
     H. Conrad Cunningham, Professor
     Computer and Information Science
     University of Mississippi

Developed for CSci 450/503, Organization of Programming Languaages,
Fall 2016

1234567890123456789012345678901234567890123456789012345678901234567890

2016-09-21: Expression Language 1 prefix parser adapted from 
            infix parser

This program uses the Lua Parsing Expression Grammar (LPEG) library to
parse the following grammar for arithmetic expression trees and to
capture significant strings during parsing.

  Exp      ::=  Value | (Op1 Exp) | (Op2 Exp Exp) | 
                (if Exp Exp Exp)  
  Value    ::=  Number | Variable
  Op1      ::=  neg
  Op2      ::=  + | - | * | / | == | ~= | < | > | <= | >=
  Variable ::=  Leading alpabetic or underscore followed by zero or
                more alphabetic, numeric, or underscore characters
  Number   ::=  One or more decimal digits with optional leading -

--]]

--[[
local UTILITIES   = "utilities"
local ABS_SYNTAX  = "abs_syn_01"
local ENVIRONMENT = "environment"
local VALUES      = "values_01"
--]]

-- Import Utilities module

local util = require(UTILITIES)

local treeConcat = util.treeConcat
      -- show_data, printTree not currently used

-- PARSER

-- Import LPEG module

local lpeg = require("lpeg")

-- For convenience, define local names for LPEG functions
local C, Ct, P, R, S, V = 
  lpeg.C, lpeg.Ct, lpeg.P, lpeg.R, lpeg.S, lpeg.V


-- Import Abstract Syntax module

local absyn = require(ABS_SYNTAX)

-- For convenience, define local names for constructors
local Nop = absyn.Nop
local Int = absyn.Int
local Var = absyn.Var
local Neg = absyn.Neg
local Add = absyn.Add
local Sub = absyn.Sub
local Mul = absyn.Mul
local Div = absyn.Div
local Eq  = absyn.Eq
local Ne  = absyn.Ne
local Lt  = absyn.Lt
local Gt  = absyn.Gt
local Le  = absyn.Le
local Ge  = absyn.Ge
local If  = absyn.If

-- Semantic Actions

-- Table to map from binary operator symbols in concrete syntax
-- to constructor functions in abstract syntax module.

local BinOpCons = {}

-- Trap any attempts to use invalid operator
setmetatable(BinOpCons,BinOpCons)

BinOpCons.__index = function(_,key)
   error("Attempt to reference invalid operator '"
	    .. treeConcat(key) .."'",2)
end

BinOpCons["+"]  = Add
BinOpCons["-"]  = Sub
BinOpCons["*"]  = Mul
BinOpCons["/"]  = Div
BinOpCons["=="] = Eq
BinOpCons["~="] = Ne
BinOpCons["<"]  = Lt
BinOpCons["<="] = Le
BinOpCons[">"]  = Gt
BinOpCons[">="] = Ge

-- The following functions are called by the LPEG parsing machine
-- to process the captures. They call the appropriare abstract
-- syntax constructors.

-- Argument s = integer as string of numerals
local function xNum(s)
   return Int(tonumber(s))
end

-- Argument s = variable name as string
local function xVar(s)
   return Var(s)
end

-- Argument t = { operator, expression }
local function xOp1(t)
   if t[1] == "neg" then
      return Neg(t[2])
   else
      error("unsupported unary operator " .. treeConcat(t))
   end
end

-- Argument t = { operator, expr1, expr2 }
local function xOp2(t)
   return BinOpCons[t[1]]( t[2], t[3] )
end

-- Argument t = {"if", expr1, expr2, expr3 }
local function xIf(t)
   if #t ~= 4 then
      error("syntax error for IF expression: " .. treeConcat(t))
   end
   return If(t[2],t[3],t[4])
end

-- Lexical Elements

  -- keyword (reserved word) patterns
local Kif        = P("if")
local Kneg       = P("neg")
local Keyword    = Kif + Kneg

local Plus       = P("+") 
local Minus      = P("-") 
local Times      = P("*") 
local Divide     = P("/") 
local Equals     = P("==")
local NotEq      = P("~=")
local Less       = P("<") 
local LessEq     = P("<=")
local Greater    = P(">") 
local GreaterEq  = P(">=")

  -- operator symbol patterns
local Space      = S(" \n\t")^0
local Alpha      = R("az") + R("AZ") + P("_")
local Num        = R("09")
local AlphaNum   = Alpha + Num
local Id         = (Alpha  * AlphaNum^0) - Keyword

  -- lexical parsers, most with string captures
local Open       = P("(") * Space
local Close      = P(")") * Space
local Variable   = C(Id)  * Space                 -- capture string
local Number     = C(Minus^-1 * Num^1) * Space    -- capture string
local Op1        = C(Kneg) * Space                -- capture string
local Op2        = C(Plus + Minus + Times + Divide +
		     Equals + NotEq + LessEq + Less +
		     GreaterEq + Greater) * Space -- capture string
  -- above requires LessEq before Less, GreaterEq before Greater
local If         = C(Kif) * Space               -- capture string

-- Grammar

  -- nonterminals
local Exp, Value =  V("Exp"), V("Value")

  -- rules 
local G = P {
   Exp;
   Exp   = Value + 
           Ct(Open * Op1 * Exp * Close)             / xOp1 +
           Ct(Open * Op2 * Exp * Exp * Close)       / xOp2 +
           Ct(Open * If * Exp * Exp * Exp * Close)  / xIf  ;
   Value = Variable  / xVar +
           Number    / xNum ;
}

-- Allow leading spaces and disallow any trailing non-space characters
G = Space * G * -1

-- Main parser function

local function parse(s)
   assert(type(s) == "string",
	  "parse requires string argument, but has " .. treeConcat(s))
  return lpeg.match(G, s)
end

-- Export module table

return { parse = parse }