--[[ LPEG Arithmetic Expression Parser with Captures
     H. Conrad Cunningham, Professor
     Computer and Information Science
     University of Mississippi

Developed for CSci 658, Software Language Engineering, Fall 2013

1234567890123456789012345678901234567890123456789012345678901234567890

2013-10-08: Completed prototype

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. Instead of just sine and
cosine (as in the evaluation and differentiation example), this
program parses general function applications with at least one
argument.

  Exp      ::=  Term { TermOp Term }^*
  Term     ::=  Factor { FactorOp Factor }^*
  Factor   ::=  Func | Variable | Number | - Exp | ( Exp )
  Func     ::=  Variable ( [ Exp { , Exp }^* ] )
  TermOp   ::=  + | -
  FactorOp ::=  * | /
  Variable ::=  Leading alpabetic or underscore followed by zero or
                more alphabetic, numeric, or underscore characters
  Number   ::=  One or more decimal digits with optional leading -

--]]


-- UTILITY FUNCTIONS

-- Function "treeConcat" takes a recursive list of lists in argument
-- "t" and returns the corresponding parenthesized traversal string.
-- A list is stored in the low positive integer indices of an
-- array-style Lua table. This function is intended for formatting
-- error messages, debugging, and testing. (This code was borrowed
-- from the author's KILT parser utility module.)

local function treeConcat(t)
  if type(t) ~= "table" then return tostring(t) end
  local res = {}
  for i = 1, #t do
    res[i] = treeConcat(t[i])
  end
  return "(" .. table.concat(res," ") .. ")"
end


-- PARSER

-- Load 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

-- Lexical Elements

local Space     = S(" \n\t")^0
local Alpha     = R("az") + R("AZ") + P("_")
local Num       = R("09")
local AlphaNum  = Alpha + Num
local NegSym    = P("-")

local Open     = P("(") * Space
local Close    = P(")") * Space
local ItemSep  = P(",") * Space
local Number   = C(NegSym^-1 * Num^1)  * Space  -- capture string
local Variable = C(Alpha * AlphaNum^0) * Space  -- capture string
local TermOp   = C(S("+-")) * Space  -- capture string
local FactorOp = C(S("*/")) * Space  -- capture string
local Neg      = C(NegSym) * Space   -- capture string

-- Grammar rules

local Exp, Term, Factor, Func = V"Exp", V"Term", V"Factor", V"Func"

local G = P { Exp;
  Exp    = Ct(Term * (TermOp * Term)^0) ;
  Term   = Ct(Factor * (FactorOp * Factor)^0) ;
  Factor = Func + Variable +  Number + Ct(Neg * Exp) +
           (Open * Exp * Close) ;
  Func   = Ct(Variable * Open * (Exp * (ItemSep * Exp)^0)^-1 * Close)
}
-- Notes:
-- (1) Func must precede Variable in Factor for Func to be parseD.
-- (2) Number must precede Neg Exp for negative number to be parsed.
-- (3) Collects captured entities as list-style tables using Ct

-- 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.")
  return lpeg.match(G, s)
end


-- SOME TESTING

local int370 = " 370 "
print("parse(int370)     = " .. treeConcat(parse(int370)))

local neg9   = " -9 "
print("parse(neg9)       = " .. treeConcat(parse(neg9)))

-- This is Neg(9) rather than -9
local negs9   = " -  9 "
print("parse(negs9)      = " .. treeConcat(parse(negs9)))

local varxyz = " xyz "
print("parse(varxyz)     = " .. treeConcat(parse(varxyz)))

local term2 = "a + 24"
print("parse(term2)      = " .. treeConcat(parse(term2)))

local term3 = "a + 24 - xyz"
print("parse(term3)      = " .. treeConcat(parse(term3)))

local factor2 = "a * 24 "
print("parse(factor2)    = " .. treeConcat(parse(factor2)))

local factor3 = "a * 24 / xyz"
print("parse(factor3)    = " .. treeConcat(parse(factor3)))

local mix1 = " 2 + 3 * 4 * 6 "
print("parse(mix1)       = " .. treeConcat(parse(mix1)))

local mix2 = " (xx * 2 + 3 * (y - z))"
print("parse(mix2)       = " .. treeConcat(parse(mix2)))

local xyz0 = "xyz()"
print("parse(xyz())      = " .. treeConcat(parse(xyz0)))

local abc1 = "abc(1)"
print("parse(abc(1))     = " .. treeConcat(parse(abc1)))

local f3 = "f(a, b, 13)"
print("parse(f(a, b,13)) = " .. treeConcat(parse(f3)))

local negx = "-x"
print("-x                = " .. treeConcat(parse(negx)))

local negmix2 = "-" .. mix2
print("-mix2             = " .. treeConcat(parse(negmix2)))