ExpressionParser.js

/*!
 * ${copyright}
 */
sap.ui.define([
	"sap/base/Log",
	"sap/base/strings/escapeRegExp",
	"sap/base/util/deepEqual",
	"sap/base/util/JSTokenizer",
	"sap/ui/performance/Measurement",
	"sap/ui/thirdparty/URI"
], function (Log, escapeRegExp, deepEqual, JSTokenizer, Measurement, URI) {
	"use strict";

	//SAP's Independent Implementation of "Top Down Operator Precedence" by Vaughan R. Pratt,
	//    see http://portal.acm.org/citation.cfm?id=512931
	//Inspired by "TDOP" of Douglas Crockford which is also an implementation of Pratt's article
	//    see https://github.com/douglascrockford/TDOP
	//License granted by Douglas Crockford to SAP, Apache License 2.0
	//    (http://www.apache.org/licenses/LICENSE-2.0)
	//
	//led = "left denotation"
	//lbp = "left binding power", for values see
	//https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Operator_Precedence
	//nud = "null denotation"
	//rbp = "right binding power"
	var fnUndefined = CONSTANT.bind(null, undefined),
		mDefaultGlobals = {
			"Array": Array,
			"Boolean": Boolean,
			"Date": Date,
			"encodeURIComponent": encodeURIComponent,
			"Infinity": Infinity,
			"isFinite": isFinite,
			"isNaN": isNaN,
			"JSON": JSON,
			"Math": Math,
			"NaN": NaN,
			"Number": Number,
			"Object": Object,
			"odata": {
				"collection": function (aElements) {
					return aElements.filter(function (vElement) {
						return vElement !== undefined;
					});
				},
				"compare": function () {
					var oODataUtils = sap.ui.require("sap/ui/model/odata/v4/ODataUtils");

					/** @deprecated As of version 1.120.0 */
					if (!oODataUtils) {
						oODataUtils = sap.ui.requireSync("sap/ui/model/odata/v4/ODataUtils");
					}
					if (!oODataUtils) {
						throw new TypeError("Expression uses 'odata.compare' which requires to"
							+ " import 'sap/ui/model/odata/v4/ODataUtils' in advance");
					}

					return oODataUtils.compare.apply(oODataUtils, arguments);
				},
				"fillUriTemplate": function (sExpression, mData) {
					/** @deprecated As of version 1.120.0 */
					if (!URI.expand) {
						// probing is not required since the presence of URI.expand is the indicator
						// that URITemplate has been loaded already
						/* URITemplate = */ sap.ui.requireSync("sap/ui/thirdparty/URITemplate");
					}
					if (!URI.expand) {
						throw new TypeError("Expression uses 'odata.fillUriTemplate' which requires"
							+ " to import 'sap/ui/thirdparty/URITemplate' in advance");
					}

					return URI.expand(sExpression.trim(), mData).toString();
				},
				"uriEncode": function () {
					var oODataUtils = sap.ui.require("sap/ui/model/odata/ODataUtils");

					/** @deprecated As of version 1.120.0 */
					if (!oODataUtils) {
						oODataUtils = sap.ui.requireSync("sap/ui/model/odata/ODataUtils");
					}
					if (!oODataUtils) {
						throw new TypeError("Expression uses 'odata.uriEncode' which requires to"
							+ " import 'sap/ui/model/odata/ODataUtils' in advance");
					}

					return oODataUtils.formatValue.apply(oODataUtils, arguments);
				}
			},
			"parseFloat": parseFloat,
			"parseInt": parseInt,
			"RegExp": RegExp,
			"String": String,
			"undefined": undefined
		},
		rDigit = /\d/,
		sExpressionParser = "sap.ui.base.ExpressionParser",
		rIdentifier = /[a-z_$][a-z0-9_$]*/i,
		rIdentifierStart = /[a-z_$]/i,
		aPerformanceCategories = [sExpressionParser],
		sPerformanceParse = sExpressionParser + "#parse",
		mSymbols = { //symbol table
			"BINDING": {
				led: unexpected, // Note: cannot happen due to lbp: 0
				nud: function (oToken, oParser) {
					return BINDING.bind(null, oToken.value);
				}
			},
			"ERROR": {
				lbp: Infinity,
				led: function (oToken, oParser, fnLeft) {
					error(oToken.value.message, oToken.value.text, oToken.value.at);
				},
				nud: function (oToken, oParser) {
					error(oToken.value.message, oToken.value.text, oToken.value.at);
				}
			},
			"IDENTIFIER": {
				led: unexpected, // Note: cannot happen due to lbp: 0
				nud: function (oToken, oParser) {
					if (!(oToken.value in oParser.globals)) {
						Log.warning("Unsupported global identifier '" + oToken.value
								+ "' in expression parser input '" + oParser.input + "'",
							undefined,
							sExpressionParser);
					}
					return CONSTANT.bind(null, oParser.globals[oToken.value]);
				}
			},
			"CONSTANT": {
				led: unexpected, // Note: cannot happen due to lbp: 0
				nud: function (oToken, oParser) {
					return CONSTANT.bind(null, oToken.value);
				}
			},
			".": {
				lbp: 18,
				led: function (oToken, oParser, fnLeft) {
					return DOT.bind(null, fnLeft, oParser.advance("IDENTIFIER").value);
				},
				nud: unexpected
			},
			"(": {
				lbp: 17,
				led: function (oToken, oParser, fnLeft) {
					var aArguments = [],
						bFirst = true;

					while (oParser.current().id !== ")") {
						if (bFirst) {
							bFirst = false;
						} else {
							oParser.advance(","); //consume "," from predecessor argument
						}
						aArguments.push(oParser.expression(0));
					}
					oParser.advance(")");
					return FUNCTION_CALL.bind(null, fnLeft, aArguments);
				},
				nud: function (oToken, oParser) {
					var fnValue = oParser.expression(0);

					oParser.advance(")");
					return fnValue;
				}
			},
			"[": {
				lbp: 18,
				led: function (oToken, oParser, fnLeft) {
					var fnName = oParser.expression(0);

					oParser.advance("]");
					return PROPERTY_ACCESS.bind(null, fnLeft, fnName);
				},
				nud: function (oToken, oParser) {
					var aElements = [],
						bFirst = true;

					while (oParser.current().id !== "]") {
						if (bFirst) {
							bFirst = false;
						} else {
							oParser.advance(","); //consume "," from predecessor element
						}
						aElements.push(
							oParser.current().id === "," ? fnUndefined : oParser.expression(0));
					}
					oParser.advance("]");
					return ARRAY.bind(null, aElements);
				}
			},
			"!": {
				lbp: 15,
				led: unexpected,
				nud: function (oToken, oParser) {
					return UNARY.bind(null, oParser.expression(this.lbp), function (x) {
							return !x;
						});
				}
			},
			"typeof": {
				lbp: 15,
				led: unexpected,
				nud: function (oToken, oParser) {
					return UNARY.bind(null, oParser.expression(this.lbp), function (x) {
							return typeof x;
						});
				}
			},
			"?": {
				lbp: 4,
				led: function (oToken, oParser, fnLeft) {
					var fnElse, fnThen;

					fnThen = oParser.expression(this.lbp - 1);
					oParser.advance(":");
					fnElse = oParser.expression(this.lbp - 1);
					return CONDITIONAL.bind(null, fnLeft, fnThen, fnElse);
				},
				nud: unexpected
			},
			")": {
				led: unexpected,
				nud: unexpected
			},
			"]": {
				led: unexpected,
				nud: unexpected
			},
			"{": {
				led: unexpected,
				nud: function (oToken, oParser) {
					var bFirst = true,
						sKey,
						mMap = {},
						fnValue;

					while (oParser.current().id !== "}") {
						if (bFirst) {
							bFirst = false;
						} else {
							oParser.advance(",");
						}
						if (oParser.current() && oParser.current().id === "CONSTANT"
								&& typeof oParser.current().value === "string") {
							sKey = oParser.advance().value;
						} else {
							sKey = oParser.advance("IDENTIFIER").value;
						}
						oParser.advance(":");
						fnValue = oParser.expression(0);
						mMap[sKey] = fnValue;
					}
					oParser.advance("}");
					return MAP.bind(null, mMap);
				}
			},
			"}": {
				lbp: -1, // Note: also terminates end of our input!
				led: unexpected,
				nud: unexpected
			},
			",": {
				led: unexpected,
				nud: unexpected
			},
			":": {
				led: unexpected,
				nud: unexpected
			}
		},
		//Fix length tokens. A token being a prefix of another must come last, e.g. ! after !==
		aTokens = ["===", "!==", "!", "||", "&&", ".", "(", ")", "{", "}", ":", ",", "?", "*",
			"/", "%", "+", "-", "<=", "<", ">=", ">", "[", "]"],
		rTokens;

	aTokens.forEach(function (sToken, i) {
		// Note: this function is executed at load time only!
		aTokens[i] = escapeRegExp(sToken);
	});
	rTokens = new RegExp(aTokens.join("|"), "g");

	addInfix("*", 14, function (x, y) {
		return x * y;
	});
	addInfix("/", 14, function (x, y) {
		return x / y;
	});
	addInfix("%", 14, function (x, y) {
		return x % y;
	});
	addInfix("+", 13, function (x, y) {
		return x + y;
	}).nud = function (oToken, oParser) {
		return UNARY.bind(null, oParser.expression(this.lbp), function (x) {
			return +x;
		});
	};
	addInfix("-", 13, function (x, y) {
		return x - y;
	}).nud = function (oToken, oParser) {
		return UNARY.bind(null, oParser.expression(this.lbp), function (x) {
			return -x;
		});
	};
	addInfix("<=", 11, function (x, y) {
		return x <= y;
	});
	addInfix("<", 11, function (x, y) {
		return x < y;
	});
	addInfix(">=", 11, function (x, y) {
		return x >= y;
	});
	addInfix(">", 11, function (x, y) {
		return x > y;
	});
	addInfix("in", 11, function (x, y) {
		return x in y;
	});
	addInfix("===", 10, function (x, y) {
		return x === y;
	});
	addInfix("!==", 10, function (x, y) {
		return x !== y;
	});
	addInfix("&&", 7, function (x, fnY) {
		return x && fnY();
	}, true);
	addInfix("||", 6, function (x, fnY) {
		return x || fnY();
	}, true);

	//Formatter functions to evaluate symbols like literals or operators in the expression grammar
	/**
	 * Formatter function for an array literal.
	 * @param {function[]} aElements - array of formatter functions for the array elements
	 * @param {any[]} aParts - the array of binding values
	 * @return {any[]} - the resulting array value
	 */
	function ARRAY(aElements, aParts) {
		return aElements.map(function (fnElement) {
			return fnElement(aParts);
		});
	}

	/**
	 * Formatter function for an embedded binding.
	 * @param {int} i - the index of the binding as it appears when reading the
	 *   expression from the left
	 * @param {any[]} aParts - the array of binding values
	 * @returns {any} the binding value
	 */
	function BINDING(i, aParts) {
		return clean(aParts[i]);
	}

	/**
	 * Formatter function for executing the conditional operator with the given condition, "then"
	 * and "else" clause.
	 * @param {function} fnCondition - formatter function for the condition
	 * @param {function} fnThen - formatter function for the "then" clause
	 * @param {function} fnElse - formatter function for the "else" clause
	 * @param {any[]} aParts - the array of binding values
	 * @return {any} - the value of the "then" or "else" clause, depending on the value of the
	 *   condition
	 */
	function CONDITIONAL(fnCondition, fnThen, fnElse, aParts) {
		return fnCondition(aParts) ? fnThen(aParts) : fnElse(aParts);
	}

	/**
	 * Formatter function for any constant value such as a literal or identifier.
	 * @param {any} v - any value
	 * @returns {any} the given value
	 */
	function CONSTANT(v) {
		return v;
	}

	/**
	 * Formatter function for member access via the dot operator.
	 * @param {function} fnLeft - formatter function for the left operand
	 * @param {string} sIdentifier - the identifier on the dot's right side
	 * @param {any[]} aParts - the array of binding values
	 * @param {object} [oReference]
	 *   optional side channel to return the base value (left operand) of the reference
	 * @return {any} - the left operand's member with the name
	 */
	function DOT(fnLeft, sIdentifier, aParts, oReference) {
		var oParent = fnLeft(aParts),
			vChild = oParent[sIdentifier];

		if (oReference) {
			oReference.base = oParent;
		}
		return clean(vChild);
	}

	/**
	 * Formatter function for a call to the function returned by fnLeft.
	 * @param {function} fnLeft - formatter function for the left operand: the function to call
	 * @param {function[]} aArguments - array of formatter functions for the arguments
	 * @param {any[]} aParts - the array of binding values
	 * @return {any} - the return value of the function applied to the arguments
	 */
	function FUNCTION_CALL(fnLeft, aArguments, aParts) {
		var oReference = {};

		// evaluate function expression and call it
		return clean(fnLeft(aParts, oReference).apply(oReference.base,
			aArguments.map(function (fnArgument) {
				return fnArgument(aParts); // evaluate argument
			})));
	}

	/**
	 * Formatter function for an infix operator.
	 *
	 * @param {function} fnLeft - formatter function for the left operand
	 * @param {function} fnRight - formatter function for the right operand
	 * @param {function} fnOperator
	 *   function taking two arguments which evaluates the infix operator
	 * @param {boolean} bLazy - whether the right operand is e
	 * @param {any[]} aParts - the array of binding values
	 * @return {any} - the result of the operator function applied to the two operands
	 */
	function INFIX(fnLeft, fnRight, fnOperator, bLazy, aParts) {
		return fnOperator(fnLeft(aParts),
			bLazy ? fnRight.bind(null, aParts) : fnRight(aParts));
	}

	/**
	 * Formatter function for an object literal.
	 * @param {object} mMap - map from key to formatter functions for the values
	 * @param {any[]} aParts - the array of binding values
	 * @return {object} - the resulting map
	 */
	function MAP(mMap, aParts) {
		var sKey, mResult = {};

		for (sKey in mMap) {
			mResult[sKey] = mMap[sKey](aParts); // evaluate value
		}
		return mResult;
	}

	/**
	 * Formatter function for a property access.
	 * @param {function} fnLeft - formatter function for the left operand: the array or object to
	 *   access
	 * @param {function} fnName - formatter function for the property name
	 * @param {any[]} aParts - the array of binding values
	 * @param {object} [oReference]
	 *   optional side channel to return the base value (left operand) of the reference
	 * @return {any} - the array element or object property
	 */
	function PROPERTY_ACCESS(fnLeft, fnName, aParts, oReference) {
		var oParent = fnLeft(aParts),
			sIdentifier = fnName(aParts), // BEWARE: evaluate propertyNameValue AFTER baseValue!
			vChild = oParent[sIdentifier];

		if (oReference) {
			oReference.base = oParent;
		}
		return clean(vChild);
	}

	/**
	 * Formatter function for a unary operator.
	 *
	 * @param {function} fnRight - formatter function for the operand
	 * @param {function} fnOperator
	 *   function to evaluate the unary operator taking one argument
	 * @param {any[]} aParts - the array of binding values
	 * @return {any} - the result of the operator function applied to the operand
	 */
	function UNARY(fnRight, fnOperator, aParts) {
		return fnOperator(fnRight(aParts));
	}

	/**
	 * Adds the infix operator with the given id, binding power and formatter function to the
	 * symbol table.
	 * @param {string} sId - the id of the infix operator
	 * @param {int} iBindingPower - the binding power = precedence of the infix operator
	 * @param {function} fnOperator - the function to evaluate the operator
	 * @param {boolean} [bLazy=false] - whether the right operand is lazily evaluated
	 * @return {object} the newly created symbol for the infix operator
	 */
	function addInfix(sId, iBindingPower, fnOperator, bLazy) {
		// Note: this function is executed at load time only!
		mSymbols[sId] = {
			lbp: iBindingPower,
			led: function (oToken, oParser, fnLeft) {
				//lazy evaluation is right associative: performance optimization for guard and
				//default operator, e.g. true || A || B || C does not execute the || for B and C
				var rbp = bLazy ? this.lbp - 1 : this.lbp;

				return INFIX.bind(null, fnLeft, oParser.expression(rbp),
					fnOperator, bLazy);
			},
			nud: unexpected
		};
		return mSymbols[sId];
	}

	/**
	 * Cleans the given <code>vValue</code>.
	 *
	 * @param {any} vValue - the value to be cleaned
	 * @returns {any} the cleaned value
	 */
	function clean(vValue) {
		return vValue === Function ? undefined : vValue;
	}

	/**
	 * Throws a SyntaxError with the given <code>sMessage</code> as <code>message</code>, its
	 * <code>at</code> property set to <code>iAt</code> and its <code>text</code> property to
	 * <code>sInput</code>.
	 * In addition, logs a corresponding error message to the console with <code>sInput</code>
	 * as details.
	 *
	 * @param {string} sMessage - the error message
	 * @param {string} sInput - the input string
	 * @param {int} [iAt] - the index in the input string where the error occurred; the index
	 *   starts counting at 1 to be consistent with positions provided in tokenizer error messages.
	 */
	function error(sMessage, sInput, iAt) {
		var oError = new SyntaxError(sMessage);

		oError.at = iAt;
		oError.text = sInput;
		if (iAt !== undefined) {
			sMessage += " at position " + iAt;
		}
		Log.error(sMessage, sInput, sExpressionParser);
		throw oError;
	}

	/**
	 * Throws and logs an error for the unexpected token oToken.
	 * @param {object} oToken - the unexpected token
	 */
	function unexpected(oToken) {
		// Note: position for error starts counting at 1
		error("Unexpected " + oToken.id, oToken.input, oToken.start + 1);
	}

	/**
	 * Computes the tokens according to the expression grammar in sInput starting at iStart and
	 * uses fnResolveBinding to resolve bindings embedded in the expression.
	 * @param {function} fnResolveBinding - the function to resolve embedded bindings
	 * @param {string} sInput - the string to be parsed
	 * @param {int} [iStart=0] - the index to start parsing
	 * @returns {object} Tokenization result object with the following properties
	 *   at: the index after the last character consumed by the tokenizer in the input string
	 *   parts: array with parts corresponding to resolved embedded bindings
	 *   tokens: the array of tokens where each token is a tuple of ID, optional value, and
	 *   optional source text
	 */
	function tokenize(fnResolveBinding, sInput, iStart) {
		var aParts = [], // the resulting parts (corresponds to aPrimitiveValueBindings)
			aPrimitiveValueBindings = [], // the bindings with primitive values only
			aTokens = [],
			oTokenizer = new JSTokenizer();

		/**
		 * Saves the binding as a part. Reuses an existing part if the binding is identical.
		 * @param {object} oBinding
		 *   the binding to save
		 * @param {int} iStart
		 *   the binding's start index in the input string
		 * @param {boolean} [bTargetTypeAny=false]
		 *   whether the binding's "targetType" should default to "any" (recursively, for all parts)
		 * @returns {int}
		 *   the index at which it has been saved/found in aParts
		 */
		function saveBindingAsPart(oBinding, iStart, bTargetTypeAny) {
			var bHasNonPrimitiveValue = false,
				sKey,
				oPrimitiveValueBinding,
				i;

			/*
			 * Sets the target type of the given binding to the default "any", if applicable.
			 *
			 * @param {object} oBinding
			 *   A binding
			 */
			function setTargetType(oBinding) {
				if (bTargetTypeAny) {
					if (oBinding.parts) {
						oBinding.parts.forEach(setTargetType);
						// Note: targetType not allowed here, see BindingParser.mergeParts
					} else {
						oBinding.targetType = oBinding.targetType || "any";
					}
				}
			}

			for (sKey in oBinding) {
				if (sKey === "parameters") {
					// parameters are not converted from name to object, but even a simple binding
					// may have the implicit object parameter "scope"
					continue;
				}
				switch (typeof oBinding[sKey]) {
					case "boolean":
					case "number":
					case "string":
					case "undefined":
						break;
					default:
						// binding has at least one property of non-primitive value
						bHasNonPrimitiveValue = true;
				}
			}
			setTargetType(oBinding);
			if (bHasNonPrimitiveValue) {
				// the binding must be a complex binding; property "type" (and poss. others) are
				// newly created objects and thus incomparable -> parse again to have the names
				oPrimitiveValueBinding = JSTokenizer.parseJS(sInput, iStart).result;
				setTargetType(oPrimitiveValueBinding);
			} else {
				// only primitive values; easily comparable
				oPrimitiveValueBinding = oBinding;
			}
			for (i = 0; i < aParts.length; i += 1) {
				// Note: order of top-level properties must not matter for equality!
				if (deepEqual(aPrimitiveValueBindings[i], oPrimitiveValueBinding)) {
					return i;
				}
			}
			aPrimitiveValueBindings[i] = oPrimitiveValueBinding;
			aParts[i] = oBinding;
			return i;
		}

		/**
		 * Consumes the next token in the input string and pushes it to the array of tokens.
		 *
		 * @returns {boolean} whether a token is recognized
		 * @throws {Error|Object|SyntaxError}
		 *   <code>fnResolveBinding</code> may throw <code>SyntaxError</code>;
		 *   <code>oTokenizer.setIndex()</code> may throw <code>Error</code>;
		 *   <code>oTokenizer</code> may also throw <code>{name: 'SyntaxError', ...}</code>
		 */
		function consumeToken() {
			var ch, oBinding, iIndex, aMatches, oToken;

			oTokenizer.white();
			ch = oTokenizer.getCh();
			iIndex = oTokenizer.getIndex();

			if ((ch === "$" || ch === "%") && sInput[iIndex + 1] === "{") { //binding
				oBinding = fnResolveBinding(sInput, iIndex + 1);
				oToken = {
					id: "BINDING",
					value: saveBindingAsPart(oBinding.result, iIndex + 1, ch === "%")
				};
				oTokenizer.setIndex(oBinding.at); //go to first character after binding string
			} else if (rIdentifierStart.test(ch)) {
				aMatches = rIdentifier.exec(sInput.slice(iIndex));
				switch (aMatches[0]) {
				case "false":
				case "null":
				case "true":
					oToken = {id: "CONSTANT", value: oTokenizer.word()};
					break;
				case "in":
				case "typeof":
					oToken = {id: aMatches[0]};
					oTokenizer.setIndex(iIndex + aMatches[0].length);
					break;
				default:
					oToken = {id: "IDENTIFIER", value: aMatches[0]};
					oTokenizer.setIndex(iIndex + aMatches[0].length);
				}
			} else if (rDigit.test(ch)
					|| ch === "." && rDigit.test(sInput[iIndex + 1])) {
				oToken = {id: "CONSTANT", value: oTokenizer.number()};
			} else if (ch === "'" || ch === '"') {
				oToken = {id: "CONSTANT", value: oTokenizer.string()};
			} else {
				rTokens.lastIndex = iIndex;
				aMatches = rTokens.exec(sInput);
				if (!aMatches || aMatches.index !== iIndex) {
					return false; // end of input or unrecognized character
				}
				oToken = {id: aMatches[0]};
				oTokenizer.setIndex(iIndex + aMatches[0].length);
			}
			oToken.input = sInput;
			oToken.start = iIndex;
			oToken.end = oTokenizer.getIndex();
			aTokens.push(oToken);
			return true;
		}

		oTokenizer.init(sInput, iStart);

		try {
			/* eslint-disable no-empty */
			while (consumeToken()) { /* deliberately empty */ }
			/* eslint-enable no-empty */
		} catch (e) {
			// Note: new SyntaxError().name === "SyntaxError"
			if (e.name === "SyntaxError") { // remember tokenizer error
				aTokens.push({
					id: "ERROR",
					value: e
				});
			} else {
				throw e;
			}
		}

		return {
			at: oTokenizer.getIndex(),
			parts: aParts,
			tokens: aTokens
		};
	}

	/**
	 * Returns a function which wraps the given formatter function into a try/catch block.
	 * In case of an error it is caught, a warning containing the given original input is issued,
	 * and <code>undefined</code> is returned instead.
	 *
	 * @param {function} fnFormatter - any (formatter) function
	 * @param {string} sInput - the expression string (used when logging errors)
	 * @returns {function} - the wrapped function
	 */
	function tryCatch(fnFormatter, sInput) {
		return function () {
			try {
				return fnFormatter.apply(this, arguments);
			} catch (ex) {
				Log.warning(String(ex), sInput, sExpressionParser);
			}
		};
	}

	/**
	 * Parses expression tokens to a result object as specified to be returned by
	 * {@link sap.ui.base.ExpressionParser#parse}.
	 * @param {object[]} aTokens - the array with the tokens
	 * @param {string} sInput - the expression string (used when logging errors)
	 * @param {object} mGlobals - the map of global variables
	 * @returns {object} the parse result with the following properties
	 *   formatter: the formatter function to evaluate the expression which
	 *     takes the parts corresponding to bindings embedded in the expression as
	 *     parameters; undefined in case of an invalid expression
	 *   at: the index of the first character after the expression in sInput, or
	 *     <code>undefined</code> if all tokens have been consumed
	 */
	function parse(aTokens, sInput, mGlobals) {
		var fnFormatter,
			iNextToken = 0,
			oParser = {
				advance: advance,
				current: current,
				expression: expression,
				globals: mGlobals,
				input: sInput
			},
			oToken;

		/**
		 * Returns the next token in the array of tokens and advances the index in this array.
		 * Throws an error if the next token's ID is not equal to the optional
		 * <code>sExpectedTokenId</code>.
		 * @param {string} [sExpectedTokenId] - the expected id of the next token
		 * @returns {object|undefined} - the next token or undefined if all tokens have been read
		 */
		function advance(sExpectedTokenId) {
			var oToken = aTokens[iNextToken];

			if (sExpectedTokenId) {
				if (!oToken) {
					error("Expected " + sExpectedTokenId + " but instead saw end of input",
						sInput);
				} else if (oToken.id !== sExpectedTokenId) {
					error("Expected " + sExpectedTokenId + " but instead saw "
							+ sInput.slice(oToken.start, oToken.end),
						sInput,
						oToken.start + 1);
				}
			}
			iNextToken += 1;
			return oToken;
		}

		/**
		 * Returns the next token in the array of tokens, but does not advance the index.
		 * @returns {object|undefined} - the next token or undefined if all tokens have been read
		 */
		function current() {
			return aTokens[iNextToken];
		}

		/**
		 * Parse an expression starting at the current token. Throws an error if there are no more
		 * tokens and
		 *
		 * @param {number} rbp
		 *   a "right binding power"
		 * @returns {function} The formatter function for the expression
		 */
		function expression(rbp) {
			var fnLeft;

			oToken = advance();
			if (!oToken) {
				error("Expected expression but instead saw end of input", sInput);
			}
			fnLeft = mSymbols[oToken.id].nud(oToken, oParser);

			while (iNextToken < aTokens.length) {
				oToken = current();
				if (rbp >= (mSymbols[oToken.id].lbp || 0)) {
					break;
				}
				advance();
				fnLeft = mSymbols[oToken.id].led(oToken, oParser, fnLeft);
			}

			return fnLeft;
		}

		fnFormatter = expression(0); // do this before calling current() below!
		return {
			at: current() && current().start,
			// call separate function to reduce the closure size of the formatter
			formatter: tryCatch(fnFormatter, sInput)
		};
	}

	/**
	 * The parser to parse expressions in bindings.
	 *
	 * @alias sap.ui.base.ExpressionParser
	 * @private
	 */
	return {
		/**
		 * Parses a string <code>sInput</code> with an expression based on the syntax sketched
		 * below.
		 *
		 * If a start index <code>iStart</code> for parsing is provided, the input string is parsed
		 * starting from this index and the return value contains the index after the last
		 * character belonging to the expression.
		 *
		 * The expression syntax is a subset of JavaScript expression syntax with the
		 * enhancement that the only "variable" parts in an expression are bindings.
		 * The following expression constructs are supported: <ul>
		 * <li> String literal enclosed in single or double quotes, e.g. 'foo' </li>
		 * <li> Null and Boolean literals: null, true, false </li>
		 * <li> Object and number literals, e.g. {foo:'bar'} and 3.141 </li>
		 * <li> Grouping, e.g. a * (b + c)</li>
		 * <li> Unary operators !,  +, -, typeof </li>
		 * <li> Multiplicative Operators: *, /, % </li>
		 * <li> Additive Operators: +, - </li>
		 * <li> Relational Operators: <, >, <=, >= </li>
		 * <li> Strict Equality Operators: ===, !== </li>
		 * <li> Binary Logical Operators: &&, || </li>
		 * <li> Conditional Operator: ? : </li>
		 * <li> Member access via . operator </li>
		 * <li> Function call </li>
		 * <li> Embedded binding to refer to model contents, e.g. ${myModel>/Address/city} </li>
		 * <li> Global functions and objects: encodeURIComponent, Math, RegExp </li>
		 * <li> Property Access, e.g. ['foo', 'bar'][0] or Math['PI']</li>
		 * <li> Array literal, e.g. ['foo', 'bar'] </li>
		 * </ul>
		 *
		 * @param {function} fnResolveBinding - the function to resolve embedded bindings
		 * @param {string} sInput - the string to be parsed
		 * @param {int} [iStart=0] - the index to start parsing
		 * @param {object} [mGlobals]
		 *   global variables allowed in the expression as map of variable name to its value;
		 *   note that there is a default map of known global variables
		 * @param {object} [mLocals={}]
		 *   local variables additionally allowed in the expression (shadowing global ones)
		 *   as map of variable name to its value
		 * @returns {object} the parse result with the following properties
		 *   result: object with the properties
		 *     formatter: the formatter function to evaluate the expression which
		 *       takes the parts corresponding to bindings embedded in the expression as
		 *       parameters
		 *     parts: the array of parts contained in the expression string which is
		 *       empty if no parts exist
		 *   at: the index of the first character after the expression in sInput
		 * @throws SyntaxError
		 *   If the expression string is invalid or unsupported. The at property of
		 *   the error contains the position where parsing failed.
		 */
		parse: function (fnResolveBinding, sInput, iStart, mGlobals, mLocals) {
			var oResult, oTokens;

			Measurement.average(sPerformanceParse, "", aPerformanceCategories);
			oTokens = tokenize(fnResolveBinding, sInput, iStart);
			mGlobals = mGlobals || mDefaultGlobals;
			if (mLocals) {
				mGlobals = Object.assign({}, mGlobals, mLocals);
			}
			oResult = parse(oTokens.tokens, sInput, mGlobals);
			Measurement.end(sPerformanceParse);
			if (!oTokens.parts.length) {
				return {
					constant: oResult.formatter(),
					at: oResult.at || oTokens.at
				};
			}

			function formatter() {
				//turn separate parameters for parts into one (array like) parameter
				return oResult.formatter(arguments);
			}
			formatter.textFragments = true; //use CompositeBinding even if there is only one part
			return {
				result: {
					formatter: formatter,
					parts: oTokens.parts
				},
				at: oResult.at || oTokens.at
			};
		}
	};
}, /* bExport= */ true);