{"id":2177,"date":"2015-07-21T16:34:28","date_gmt":"2015-07-21T16:34:28","guid":{"rendered":"https:\/\/www.microsoft.com\/reallifecode\/index.php\/2015\/07\/21\/recursive-descent-formula-parsing-in-c-in-net\/"},"modified":"2020-03-15T16:01:37","modified_gmt":"2020-03-15T23:01:37","slug":"recursive-descent-formula-parsing-in-c-in-net","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/ise\/recursive-descent-formula-parsing-in-c-in-net\/","title":{"rendered":"Recursive Descent Formula Parsing in C# in .NET"},"content":{"rendered":"

Intrinsic to any script-based application is the notion of parsing. In CloudSheet, described in detail in the forthcoming TED Case Study entitled \u201cMassively Scalable Graph-Based Computation in Azure,\u201d a formula parser tokenizes arbitrarily complex Excel-like formulas making subsequent evaluation faster and more efficient. This paper will cover the parsing component.1<\/a><\/p>\n

Overview of the Solution<\/h2>\n

The objective of the parser is to tokenize arbitrarily complex formulas of differing types to enable rapid and accurate evaluation. Example formulas include:<\/p>\n

\n
=1+3\r\n=sum(a1:a3)\r\n=sum(a1:a3,5)+pi()\/2\r\n=pmt(a1\/12,(a2*36),b5)\r\n=stock(ibm)*a5+stock(msft)*a6\r\n=concatenate(\u201ctest\u201d,b12)\r\n=data(sheetcsvssample.op)\r\n=select(a5,3,2,5)\r\n<\/code><\/pre>\n<\/div>\n
And so on. As can be seen, formulas can return either numeric or string-based results, concatenation being an example of the latter. The current implementation supports around 47 numeric functions and 10 string functions (a subset of current Excel functionality), although more are being added as needed.<\/p>\n
The parser, which is contained within the \u201cCell\u201d grain (actor) in CloudSheet, is passed a text string from the client (either typed in by a user or loaded from a file). After tokenizing, the tokens are passed to the evaluator, which calculates a response. As the model is recalculated, the evaluator is called to update its result based on potentially new data. The parser is only invoked when the input formula is changed; the evaluator is called on every recalculation where necessary (i.e., in which a predecessor value is updated).<\/p>\n
Implementation<\/h2>\n
The implementation chosen is a recursive-descent parser.2<\/a> The parsing method is invoked with two arguments:<\/p>\n
\n
private void Parse(List<Formentry> numStack, List<Formentry> opStack)\r\n{\r\n    while (this.index < this.txt.Length)\r\n    {\r\n        Formentry tok = GetToken();\r\n  ...\r\n }\r\n<\/code><\/pre>\n<\/div>\n
The arguments are the number stack and the operator stack. The former holds formula arguments, the latter holds formula operators, such as arithmetic operators or functions.<\/p>\n
The act of tokenizing creates a data structure called a \u201cFormentry\u201d (formula entry) which describes the token. The various types of tokens are enumerated below:<\/p>\n
\n
public enum TokenTypes\r\n{\r\n    UNDEFINED=-1,\r\n    NUMBER = 0,\r\n    CELLREF = 1,\r\n    OPERATOR = 2,\r\n    NAME = 3,\r\n    RANGE = 4,\r\n    SUBSTRING = 5,\r\n    FUNCTION = 6,\r\n    UNARY = 7,\r\n    PRECEDENCE = 8,\r\n    DATE=9,\r\n    ARGSEP=10,\r\n    LPAREN=11,\r\n    RPAREN=12,\r\n    FUNC = 13,\r\n    COMPARISON = 14,\r\n    RESOLVEDRANGE=15,\r\n    STRINGFUNCTION=16,\r\n    STARTPARSE=98,\r\n    ENDPARSE = 99\r\n}\r\n<\/code><\/pre>\n<\/div>\n
Note that a Formentry can describe either arguments or operators. Some descriptions follow:<\/p>\n