Parses a FEEL expression (DMN 1.6, grammar rules 1 and 2) from tokens.

This is a hand-written precedence-climbing parser. The grammar is ambiguous and gives precedence only by the order of its alternatives, so the levels below are the reading in the specification notes (01 §6). The parser reads the tokens of Feel.Syntax.Lexer and returns a Feel.AST expression node; it does not analyze or run anything.

The parser reads the whole expression grammar: literals, names, arithmetic, comparison, and, or, between, in, prefix tests, intervals, lists, context literals, if, for, some, every, function definitions, and the postfix forms (path, descendant, filter, call, instance of). parse_unary_tests/2 reads the other entry point, a list of unary tests. Types such as list<number> are read inside other nodes by Feel.Syntax.TypeParser, and on their own by Feel.Type.parse/2. The parser reads FEEL whatever the dialect: S-FEEL is checked on the tree it returns (Feel.Syntax.SFeel, D-49), and B-FEEL has the same grammar.

Precedence

From the loosest to the tightest. All binary operators are left associative.

The right operand of a comparison, and the bounds of between, are parsed at level 4 and above, so x < a + b is x < (a + b), a < b and c is (a < b) and c, and x between 1 and 10 and y is (x between 1 and 10) and y (notes 01, A27). A prefix test such as < a + b reads its operand the same way.

Brackets

(, [ and ] can start a parenthesized expression, a list, or an interval, and the tokens that tell them apart come after the first expression. The parser reads that expression once, and the token after it decides, so it never backtracks:

An interval ends with ), ] or [. After in (, a comma makes a list of tests, so x in (1, 2) is {:in, meta, x, [1, 2]}; x in (a) and x in a are the same tree.

A [ right after the upper end of an interval is ambiguous (notes 01, A35): it opens a filter in [1..xs[i]] and closes the interval in ]1..5[. The token after it decides, as in the grammar of lezer-feel (decision D-28): a filter when that token can begin an expression, except ] and the comparison operators, which close the interval. ]1..a[ - 1 is therefore read with a filter and fails; write (]1..a[) - 1.

Names

A name is a run of tokens, and where it ends depends on the names in scope (decision D-05, D-06). At the start of an operand the parser takes the longest run of name tokens that is a name in the :scope or a built-in function (Feel.Builtin), so with a-b in scope, a - b is that name, and (a) - (b) is a subtraction. A longest match is dropped for a shorter one when the token after it could not follow an operand, which is the specification's "the longest match is preferred" without a full backtrack. A name that matches nothing is its first token alone, and the analyzer reports it.

After . and ..., and inside the brackets of a filter, names are keys of a context that exists only at run time (decision D-27). There a name is a name start word followed by further words that are not keywords, and x.age and y stops at and.

Constructs and bound names

if, for, some, every and function start an operand, and the last part of each (the else branch, the body, the test) is read at the lowest precedence, so it extends as far right as the enclosing brackets allow: 1 + if c then 2 else 3 is 1 + (if c then 2 else 3) (notes 01, A28).

The variables of for, some and every, and the parameters of a function, are names in the parts they scope, so for first name in xs return first name reads first name as one name in the body. A variable is visible in the domains after it, not in its own. A binding name ends at the first in (A23), so a variable cannot be called is in stock. Only a for domain can be from..to.

Context literals

The keys of a context are names and strings. A value can use any key of its context, including one that comes after it (notes 01, A22), so the keys are found first, by a scan of the tokens up to the closing brace, and are names while the values are read. A key cannot start with a keyword ({"if": 1} is the way to write it). Duplicate keys, cycles, and self-references are kept in the tree; the analyzer reports them.

Errors

The error is a list of Feel.Diagnostic with the code :syntax_error, :nesting_too_deep when the expression nests deeper than the :limits allow (the nesting of a type counts, D-154), or :name_too_long when a name that the expression gives (to a parameter, a variable, or a key) has more tokens than they allow. The parser never raises for its input.

Example

iex> {:ok, tokens} = Feel.Syntax.Lexer.tokenize("1 + 2")
iex> {:ok, {:binary, meta, :add, _left, _right}} = Feel.Syntax.Parser.parse(tokens)
iex> meta.span
{0, 5}