# xparse - flexible expression parsing library for user defined conditionals

This is the source code for parsing and evaluating general conditional expressions.

The parser is based on the [Comparse](http://github.com/llhotka/comparse) library.

    P = require('comparse')

## Separators

First, we define two scanners for separators, *mandatory* and
*optional*, that permit any combination of whitespace characters.

    # Mandatory separator
    sep = P.space.skipMany 1

    # Optional separator
    optSep = P.space.skipMany()

We also we add a *convenience extension* to the parser to simplify
expression of elements enclosed by a common pattern, such as being
`between` same separators.

    P::within = (p) -> @between p, p

## Entities

In a given conditional expression, you can have numbers, variables,
quoted strings, and functions (with or without arguments).

A number can begin with a negative character and contain any sequence
of digits, with at most one decimal dot in between. A decimal number
**must** have at least one number before/after the `.`, such as
`0.1`. The parser will *reject* `.1` and `0.` as a valid number.

    number = P.char('-').option('').bind (neg) ->
      P.digit.concat(1).bind (head) ->
        (P.char('.').bind (dot) ->
          P.digit.concat(1).bind (tail) ->
            P.unit Number (neg + head + dot + tail)
        ).orElse P.unit Number (neg + head)

A variable must begin with a letter or `_` character and be followed
by sequence of alphanumeric characters.
        
    variable = (P.letter.orElse P.char '_').bind (fst) ->
      P.alphanum.concat().bind (rest) ->
        P.unit fst + rest

A single-quoted string is matched as-is. Need to support double-quoted
strings...

    quote = P.noneOf("'").concat().between P.char("'"),P.char("'")

An argument to a method can contain variable, quoted string, or a
number. Nesting of expressions and methods within a method argument is
currently not supported.
    
    argument = P.choice(variable, quote, number).between optSep, optSep

A method is a function declaration which will produce a result to be
used during expression evaluation. It must be a `variable` identifier
followed immediately by an `(` and closed with `)`. It can have at
most one argument expression, or left blank.
    
    method = variable.bind (name) ->
      P.char('(').bind ->
        argument.option().bind (arg) ->
          P.char(')').bind ->
            P.unit [ name, arg ]

## Operations

A map object of available `operator` primitives and the associated
evaluation function.

    operators =
      '*':   (x, y=1) -> x * y
      '/':   (x, y=1) -> x / y
      '%':   (x, y=1) -> x % y
      '+':   (x, y=0) -> x + y
      '-':   (x, y=0) -> x - y
      '<':   (x, y) -> x < y
      '<=':  (x, y) -> x <= y
      '>':   (x, y) -> x > y
      '>=':  (x, y) -> x >= y
      '=':   (x, y) -> x == y
      '==':  (x, y) -> x == y
      'div': (x, y=1) -> x / y
      'mod': (x, y=1) -> x % y
      'or':  (x, y) -> Boolean (x or y)
      '||':  (x, y) -> Boolean (x or y)
      'and': (x, y) -> Boolean (x and y)
      '&&':  (x, y) -> Boolean (x and y)
      '!':   (x) -> not x
      'not': (x) -> not x

A helper routine to return a matching operator function from the
`operators` map object. Each of the scanned operator keywords returns
a `function` as the immediate result of parsing.

    opf = (op) -> P.unit operators[op]

### Computations

Computational expressions perform expected behaviors depending on the
types of entity (number, string, etc.) being evaluated. 

    multiply = P.char('*').within(optSep).bind opf
    divide   = (P.char('/').within(optSep).orElse P.string('div').within(sep)).bind opf
    modulo   = (P.char('%').within(optSep).orElse P.string('mod').within(sep)).bind opf
    plus     = P.char('+').within(optSep).bind opf
    minus    = P.char('-').within(optSep).bind opf

### Comparisons

Comparison expressions perform equality checks and evaluates to a Boolean result.

    lt       = P.char('<').within(optSep).bind opf
    lte      = P.string('<=').within(optSep).bind opf
    gt       = P.char('>').within(optSep).bind opf
    gte      = P.string('>=').within(optSep).bind opf
    equal    = (P.string('==').within(optSep).orElse P.char('=').within(optSep)).bind opf

### Conditionals

Conditional expressions evalutes to a Boolean result.
    
    negate  = (P.char('!').orElse P.string('not').between optSep, sep).bind opf
    union   = (P.char('|').concat(2).within(optSep).orElse P.string('or').within(sep)).bind opf
    combine = (P.char('&').concat(2).within(optSep).orElse P.string('and').within(sep)).bind opf

## Evaluator

The expression parsing result produces a composition of nested
*functions* that are bound with operands (which themselves can be
generated functions).

The *magic* happens when you execute the function generated by
`xparse`. When you execute the generated function, you can optionally
pass in a `resolver` function which can be used to supply values for
`variable` and `method` entities in a given expression.

Please refer to the main package [README](../README) for examples.

    evaluate = (x, y, resolver) ->
      x = if typeof x is 'function' then x(resolver) else x
      y = if typeof y is 'function' then y(resolver) else y
      this?(x,y) ? resolver?(x,y)

    wrap = (func, x, y=null) ->
      kind = switch
        when func?     then "#{x} #{func.name} #{y}"
        when x? and y? then "#{x}(#{y})"
        when x?        then "#{x}"
      f = evaluate.bind func, x, y
      f[k] = v for k, v of arguments
      Object.defineProperty f, 'toString', value: -> kind
      return P.unit f

Here we add an *extension* to the parser to simplify expression of
recursive precedence handling.  See below [Grammer](#grammer) section
for usage.

    P::step = (before, after) ->
      before().bind (x) =>
        next = @bind (op) ->
          after().bind (y) -> wrap op, x, y
        next.option x

## Grammer

Highest precedence to lowest precedence:
- union (logical OR)
- combine (logical AND)
- equal
- lt, lte, gt, gte
- plus, minus
- multiply, divide, modulo
- negate, grouping

    expr  = -> union.step(term1, expr)
    term1 = -> combine.step(term2, term1)
    term2 = -> equal.step(term3, term2)
    term3 = -> P.choice(lt, lte, gt, gte).step(term4, term3)
    term4 = -> P.choice(plus, minus).step(term5, term4)
    term5 = -> P.choice(multiply, divide, modulo).step(factor, term5)

Describing the top-level `factor` is a bit more complicated. We handle
the negate and grouping case, while scanning for various [entities](#entities).
    
    factor = ->
      P.choice(
        negate.bind (op) -> factor().bind (f) -> wrap op, f
        P.char('(').bind ->
          optSep.bind -> expr().bind (e) -> optSep.bind ->
            P.char(')').bind -> P.unit e
        method.bind (kv=[]) -> wrap null, kv[0], kv[1]
        variable.bind (k)   -> wrap null, k
        number
        quote
      )

## Parsing Function

The public API of this module consists of a single parsing function as
the `default` export.

It's called with `text` to parse. The result of `parse` is an
executable function that can then be executed to perform the
*evaluation* of the expression.

    factory = (f) -> p = f(); p.parse.bind p
    xparse  = factory -> expr().within(optSep)
    
    exports = module.exports = xparse['default'] = xparse

Here we expose the various expression parsing rules as a new
`ExpressionParser` class for making other parsers.
    
    exports.Parser =
      class ExpressionParser extends P
        @create: factory
        @wrap: wrap

        # entities
        @number:    number
        @variable:  variable
        @quote:     quote
        @argument:  argument
        @method:    method

        # operators
        @operators: operators
        @multiply:  multiply
        @divide: divide
        @modulo: modulo
        @plus:   plus
        @minus:  minus
        @lt:  lt
        @lte: lte
        @gt:  gt
        @gte: gte
        @equal: equal
        @negate: negate
        @union: union
        @combine: combine