{"id":275,"date":"2014-02-01T04:59:44","date_gmt":"2014-02-01T04:59:44","guid":{"rendered":"http:\/\/burnt-traces.com\/?p=275"},"modified":"2014-03-27T04:31:17","modified_gmt":"2014-03-27T04:31:17","slug":"dynamic-methods-and-recursive-descent-parsing","status":"publish","type":"post","link":"https:\/\/burnt-traces.com\/?p=275","title":{"rendered":"Dynamic Methods and Recursive Descent Parsing"},"content":{"rendered":"

For some reason, the Reflection namespace in .Net is one of my favorites. Particularly interesting is the Reflection.Emit namespace. If your not familiar, it’s a collection of classes that allows you to create new assemblies, classes, and methods at run time. The DynamicMethod class gives you a way to generate a method and create a delegate to call it. This requires some knowledge of MSIL, an assembly style language that .Net languages compile to before they are converted to true machine language. Since I was bored this week at work, I combined this with a something I learned from back in my college days. Recursive Descent Parsing<\/a> is a method often used for compiling expressions into assembly style instructions.<\/p>\n

The use case for this is simple, you have some need for users to input simple numerical formula into your system, and quickly execute those functions against various inputs and store the results. The following code takes a standard math expression, combined with variables and functions, and compiles it into a dynamic method that can be executed. Variable values and function calls are handled by a callback function that receives the name of the symbol and any arguments supplied.<\/p>\n

The most difficult part of working with IL is generating valid code. The most common error messages are usually ‘This operation could destabilize the runtime.’ or ‘An invalid program was detected.’ Neither of which is very helpful. The most common way trouble shoot IL generation is to write the code you want to simulate in C# or VB, compile it, and use the ILDASM disassembly tool that comes with Visual Studio to examine the code. All I can suggest is to look at your code carefully and be sure of the state of the stack, and what type all your values are at each point. I attempted to comment most of the code below in the IL generation portion so you can follow what I was doing.<\/p>\n

One last note about the below code, I wrote it quick and didn’t put any verification into the parser. That is, it will likely accept badly formed expressions, generating invalid code or throwing meaningless errors. I’ll leave adding proper error messages to the parsing section an exercise for the reader. Have fun.<\/p>\n

\r\n\r\nusing System;\r\nusing System.Collections.Generic;\r\nusing System.Linq;\r\nusing System.Text;\r\nusing System.Text.RegularExpressions;\r\nusing System.Reflection;\r\nusing System.Reflection.Emit;\r\n \r\n\/*\r\n* This is a simple example of a recursive descent parser combined\r\n* with dynamic methods to Compile simple expressions stored in a string.\r\n* This example lacks error feedback for invalid expressions (invalid expressions may generate invalid code)\r\n* This example handles limited numeric types only (would need additional type conversion logic added to handle strings etc.).\r\n*\/\r\n \r\nnamespace ExpressionEvaluatorExample\r\n{\r\n \r\n    class Program\r\n    {\r\n        static void Main(string[] args)\r\n        {\r\n \r\n            \/\/Callback delegate for resolving Variables and functions\r\n            Func<string, Array, object > resolve = (String name, Array arg) =>\r\n                {\r\n                    switch (name)\r\n                    {\r\n                        case "Var1":\r\n                            return 5;\r\n                        case "Var2":\r\n                            return 6;\r\n                        case "Pow":\r\n                            return System.Math.Pow((double)arg.GetValue(0), (double)arg.GetValue(1));\r\n \r\n                    }\r\n                    return 0;\r\n                };\r\n \r\n            var FE = new functionEvaluator();\r\n \r\n            FE.Tokenize("Pow(4, 2)+Var2*(10+5)"); \/\/106\r\n            var fx = FE.Compile();\r\n \r\n            Console.WriteLine("Result: " + fx(resolve).ToString());\r\n \r\n            Console.ReadLine();\r\n \r\n        }\r\n \r\n      \r\n    }\r\n \r\n \r\n \r\n    class functionEvaluator\r\n    {\r\n        \/* Supported Grammar\r\n         * Sum      = Mul [+|- Mul]\r\n         * Mul      = Factor [*|\/ Factor]\r\n         * Factor   = Number | (Sum)\r\n         *\/\r\n \r\n        private List<string> _tokens;\r\n        private int index = 0;\r\n \r\n \r\n        private string token           \r\n        {\r\n            get {\r\n                if(index < _tokens.Count )\r\n                        return _tokens[index];\r\n                else\r\n                        return null;\r\n            }\r\n        }\r\n \r\n        private string peek()\r\n        {\r\n            if (index < _tokens.Count)\r\n                return _tokens[index+1];\r\n            else\r\n                return null;\r\n        }\r\n \r\n        private bool next()\r\n        {\r\n            if (index < _tokens.Count)\r\n            {\r\n                index++;\r\n                return true;\r\n            }\r\n            else\r\n                return false;\r\n        }\r\n \r\n              \r\n        public void Tokenize(string expr)\r\n        {\r\n            \/\/Tokenize regex adapted from: http:\/\/www.codeproject.com\/Tips\/371647\/Converting-InFix-to-PostFix-by-Recursive-Descenden\r\n            string syntax = @"\\s*(\\d+|'.*?'|[-+*\/%(),]|[^\\s-+*\/%(),]+)\\s*";\r\n            _tokens = Regex.Matches(expr, syntax, RegexOptions.Compiled)\r\n                .Cast<Match>().Select(t => t.Groups[1].Value.Trim()).ToList() ;\r\n        }\r\n \r\n        private ILGenerator ilgen;\r\n \r\n \r\n        public Func<Func<string, Array, object>, object> Compile()\r\n        {\r\n            var method = new DynamicMethod("calculate", typeof(object), new Type[] { typeof(Func<string, Array, object>) });\r\n            ilgen = method.GetILGenerator();\r\n \r\n            Sum();\r\n \r\n            ilgen.Emit(OpCodes.Box, typeof(double));    \/\/box the return type\r\n            ilgen.Emit(OpCodes.Ret);                    \/\/return\r\n \r\n            return (Func<Func<string, Array, object>, object>)method.CreateDelegate(typeof(Func<Func<string, Array, object>, object>));\r\n           \r\n        }\r\n \r\n        public void Sum()\r\n        {\r\n            Mul();\r\n            if (token == "+")\r\n            {\r\n                next();\r\n                Mul();\r\n                ilgen.Emit(OpCodes.Add);\r\n            }\r\n            else if (token == "-")\r\n            {\r\n                next();\r\n                Mul();\r\n                ilgen.Emit(OpCodes.Sub);\r\n            }\r\n        }\r\n \r\n        public void Mul()\r\n        {\r\n            Factor();\r\n            if (token == "*")\r\n            {\r\n                next();\r\n                Factor();\r\n                ilgen.Emit(OpCodes.Mul);\r\n            }\r\n            else if (token == "\/")\r\n            {\r\n                next();\r\n                Factor();\r\n                ilgen.Emit(OpCodes.Div);\r\n            }\r\n        }\r\n \r\n        public void Factor()\r\n        {\r\n            if (token == "(")\r\n            {\r\n                next();\r\n                Sum();\r\n            }\r\n            else\r\n            {\r\n                Symbol();\r\n            }\r\n \r\n        }\r\n \r\n        public void Symbol()\r\n        {\r\n            double value;\r\n            if (double.TryParse(token, out value))\r\n            {\r\n                ilgen.Emit(OpCodes.Ldc_R8, value);  \/\/load numeric literal to the stack as a double\r\n                next();\r\n            }\r\n            else\r\n            {\r\n                ilgen.Emit(OpCodes.Ldarg_0);        \/\/load first argument (pointer to delegate)\r\n                ilgen.Emit(OpCodes.Ldstr, token);   \/\/load token name to stack\r\n \r\n                if (peek() == "(")\r\n                {\r\n                    \/\/function arguments\r\n                    next();\r\n                    int args = Arguments();\r\n                   \r\n                    if (args > 0)\r\n                    {\r\n                        var arry = ilgen.DeclareLocal(typeof(Array ));\r\n                        var argval = ilgen.DeclareLocal(typeof(double));\r\n \r\n                        ilgen.Emit(OpCodes.Ldtoken, typeof(object));                                    \/\/load type token\r\n                        ilgen.Emit(OpCodes.Call, typeof(System.Type).GetMethod("GetTypeFromHandle"));   \/\/get type from handle\r\n                        ilgen.Emit(OpCodes.Ldc_I4 , args);                                              \/\/load number of elements\r\n                        ilgen.Emit(OpCodes.Call, typeof(Array).GetMethod("CreateInstance", new Type[] { typeof(Type), typeof(int) })); \/\/call array object factory\r\n \r\n                        ilgen.Emit(OpCodes.Stloc, arry.LocalIndex);     \/\/ store array in local\r\n                        for(int i=0;i<args;i++)\r\n                        {\r\n                            ilgen.Emit(OpCodes.Stloc, argval.LocalIndex );  \/\/pop argument from stack\r\n                           \r\n                            ilgen.Emit(OpCodes.Ldloc, arry.LocalIndex);     \/\/load array on stack\r\n                            ilgen.Emit(OpCodes.Castclass, typeof(object[])); \/\/cast to object array\r\n                            ilgen.Emit(OpCodes.Ldc_I4, i);                  \/\/load index on stack\r\n                            ilgen.Emit(OpCodes.Ldloc, argval.LocalIndex );  \/\/load local back on stack\r\n                            ilgen.Emit(OpCodes.Box, typeof(double));        \/\/box value\r\n                            ilgen.Emit(OpCodes.Stelem_Ref);                  \/\/store in array\r\n                            \r\n                        }\r\n                        ilgen.Emit(OpCodes.Ldloc, arry.LocalIndex);      \/\/ push array to stack\r\n                       \r\n                    }\r\n                    else\r\n                    {\r\n                        ilgen.Emit(OpCodes.Ldnull); \/\/load null reference\r\n                    }\r\n                }\r\n                else\r\n                {\r\n                    ilgen.Emit(OpCodes.Ldnull); \/\/load null reference\r\n                }\r\n \r\n                \/\/call the delegate\r\n                ilgen.Emit(OpCodes.Callvirt, typeof(Func<string, Array, object>).GetMethod("Invoke", new Type[] {typeof(string), typeof(object[])}));\r\n               \r\n                \/\/store result in local var\r\n                var retval = ilgen.DeclareLocal(typeof(object));\r\n                ilgen.Emit(OpCodes.Stloc, retval);      \/\/ store local\r\n                ilgen.Emit(OpCodes.Ldloc, retval);      \/\/ put it back on the stack\r\n \r\n                var intToFloat = ilgen.DefineLabel();   \/\/ Label for branching\r\n                var done = ilgen.DefineLabel();         \/\/ Label for branching\r\n \r\n                \/\/test type, branch to conversion\r\n                ilgen.Emit(OpCodes.Isinst, typeof(Int32 )); \/\/Test if boxed type is integer\r\n                ilgen.Emit(OpCodes.Brtrue, intToFloat);     \/\/Branch to int32 conversion if true\r\n               \r\n                \/\/case else\r\n                ilgen.Emit(OpCodes.Ldloc, retval);              \/\/load from local\r\n                ilgen.Emit(OpCodes.Unbox_Any, typeof(double));  \/\/unbox double\r\n                ilgen.Emit(OpCodes.Br, done);                   \/\/branch to end of block\r\n               \r\n                \/\/convert int32 to fload\r\n                ilgen.MarkLabel(intToFloat);\r\n                ilgen.Emit(OpCodes.Ldloc, retval);              \/\/load local to stack\r\n                ilgen.Emit(OpCodes.Unbox_Any, typeof(Int32));   \/\/unbox int32\r\n                ilgen.Emit(OpCodes.Conv_R8);                    \/\/convert to float64\r\n                               \r\n                ilgen.MarkLabel(done);      \/\/ end of block lable\r\n                next();\r\n            }\r\n               \r\n        }\r\n \r\n        public int Arguments()\r\n        {\r\n            int i = 0;\r\n            if (token == "(") next();\r\n \r\n            while (token != ")" && token != null)\r\n            {\r\n                Sum();\r\n                i++;\r\n                if (token == ",") next();\r\n            }\r\n \r\n \r\n            return i;\r\n        }\r\n \r\n \r\n \r\n \r\n \r\n    }\r\n \r\n}\r\n \r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
For some reason, the Reflection namespace in .Net is one of my favorites. Particularly interesting is the Reflection.Emit namespace. If your not familiar, it’s a collection of classes that allows you to create new assemblies, classes, and methods at run time. The DynamicMethod class gives you a way to generate a method and create a… Read More »Dynamic Methods and Recursive Descent Parsing<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"neve_meta_sidebar":"","neve_meta_container":"","neve_meta_enable_content_width":"","neve_meta_content_width":0,"neve_meta_title_alignment":"","neve_meta_author_avatar":"","neve_post_elements_order":"","neve_meta_disable_header":"","neve_meta_disable_footer":"","neve_meta_disable_title":"","footnotes":""},"categories":[48,49],"tags":[55,54,50,51,52,53],"class_list":["post-275","post","type-post","status-publish","format-standard","hentry","category-net","category-csharp","tag-il","tag-msil","tag-parser","tag-recursive-descent","tag-reflection","tag-reflection-emit"],"_links":{"self":[{"href":"https:\/\/burnt-traces.com\/index.php?rest_route=\/wp\/v2\/posts\/275","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/burnt-traces.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/burnt-traces.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/burnt-traces.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/burnt-traces.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=275"}],"version-history":[{"count":5,"href":"https:\/\/burnt-traces.com\/index.php?rest_route=\/wp\/v2\/posts\/275\/revisions"}],"predecessor-version":[{"id":318,"href":"https:\/\/burnt-traces.com\/index.php?rest_route=\/wp\/v2\/posts\/275\/revisions\/318"}],"wp:attachment":[{"href":"https:\/\/burnt-traces.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=275"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/burnt-traces.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=275"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/burnt-traces.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=275"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}