Parsing a Complex string in C#.

Question

I am Currently maintaining an application written in C#. There is a new feature I need to code and I have hit a wall.

I am pulling data from a database for a different application written in VB6. There is a field that holds data for a tree list. I need to recreate this tree in my application. The data looks like this:

{
    {
        table1~col_b^table1~colc^= 
    }|
    {
        {
            table1~col_b^table2~col_b^=
        }|{
            table2~col_a^table3~cola^=
        }|AND
    }|OR
}

I don't even know where to start. What I need to accomplish is this. {} denote an expression, | separate expressions. basically this tree should look like this:

OR
-- table1~col_b^table1~colc^= 
-- AND
---- table1~col_b^table2~col_b^=
---- table2~col_a^table3~cola^=

Any help or direction in solving this problem would be great!

Thanks,

Doug

Answer 1

You can use regexp to tokenize and a stack to parse recursively like this

        internal class Node
        {
            public string Terminal { get; set; }
            public List<Node> Operands { get; set; }
        }

        internal static readonly Regex TokensPattern = new Regex(@"(?<ws>\s+)|{\s*(?<value>[^\s}]+)\s*}|(?<token>OR|AND|.)", RegexOptions.Compiled);

        static Node parseData(string str)
        {
            // init stack
            var stack = new Stack<Node>();
            stack.Push(new Node() { Operands = new List<Node>() });
            // define parser
            var parser = new Dictionary<string, Action<string>>();
            parser.Add("{", _ => stack.Push(new Node() { Operands = new List<Node>() }));
            parser.Add("}", _ => { var top = stack.Pop(); stack.Peek().Operands.Add(top); });
            parser.Add("|", _ => { });
            parser.Add("AND", _ => stack.Peek().Terminal = "AND");
            parser.Add("OR", _ => stack.Peek().Terminal = "OR");
            parser.Add("", value => stack.Peek().Operands.Add(new Node { Terminal = value }));
            // execute parser
            TokensPattern.Matches(str).Cast<Match>()
                .Where(m => string.IsNullOrEmpty(m.Groups["ws"].Value))
                .Count(m => { parser[m.Groups["token"].Value](m.Groups["value"].Value); return false; });
            // return top of the tree
            return stack.Peek().Operands[0];
        }

        static void Main(string[] args)
        {
            const string str = @"{
    {
        table1~col_b^table1~colc^= 
    }|
    {
        {
            table1~col_b^table2~col_b^=
        }|{
            table2~col_a^table3~cola^=
        }|{cccc}|AND
    }|OR
}";            
            // print tree function
            Action<int, Node> dump = null;
            dump = new Action<int, Node>((level, node) =>
            {
                Console.WriteLine("{0}{1}", new string(' ', level * 2), node.Terminal);
                if (node.Operands != null)
                    node.Operands.ForEach(el => dump(level + 1, el));
            });
            dump(0, parseData(str));
        }

Answer 2

Without any additional libraries, it's not too hard to parse this into an expression tree in pure C# code:

class TreeNode
{
    private enum ParseState
    {
        Operator,
        Expression
    }
    public static TreeNode ParseTree(string treeData)
    {
        Stack<TreeNode> parsed = new Stack<TreeNode>();
        StringBuilder nodeData = new StringBuilder();
        ParseState state = ParseState.Operator;

        for (int charIndex = 0; charIndex < treeData.Length; charIndex++)
        {
            switch (treeData[charIndex])
            {
                case '{':
                    nodeData.Clear();
                    state = ParseState.Expression;
                    break;
                case '\t':
                case ' ':
                case '\r':
                case '\n':
                case '|':
                    // ignore whitespace and |
                    break;
                case '}':
                    {
                        if (state == ParseState.Expression)
                        {
                            state = ParseState.Operator;
                            parsed.Push(new TreeNodeData(nodeData.ToString()));
                        }
                        else // Operator
                        {
                            TreeNodeOperators op = (TreeNodeOperators)(Enum.Parse(typeof(TreeNodeOperators), nodeData.ToString()));
                            TreeNodeExpression exp = new TreeNodeExpression();
                            exp.Operator = op;
                            exp.Right = parsed.Pop();
                            exp.Left = parsed.Pop();
                            parsed.Push(exp);
                        }
                        nodeData.Clear();
                    }
                    break;
                default:
                    nodeData.Append(treeData[charIndex]);
                    break;
            }
        }
        return parsed.Pop();
    }
}

enum TreeNodeOperators
{
    AND,
    OR
}

class TreeNodeExpression : TreeNode
{
    public TreeNodeOperators Operator {get; set;}
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }
}

class TreeNodeData : TreeNode
{
    public string Data {get; set;}
    public TreeNodeData(string data)
    {
        Data = data;
    }
}

Answer 3

When you would define a grammar I suggest you looking at Irony.net. It allows to write parsers very easily. Sample.

And this is rough grammar for your code:

    [Language("ExpressionEvaluator", "1.0", "Multi-line expression evaluator")]
    public class ExpressionEvaluatorGrammar : Grammar
    {
        public ExpressionEvaluatorGrammar()
        {
            // 1. Terminals

            var identifier = new RegexBasedTerminal("identifier", "[a-z\\d_^~]+");


            // 2. Non-terminals
            var root = new NonTerminal("root");
            var block = new NonTerminal("block");
            var expression = new NonTerminal("expression");
            var expressions = new NonTerminal("expressions");

            var prop = new NonTerminal("prop");
            var op = new NonTerminal("op");

            // 3. BNF rules
            op.Rule = ToTerm("OR") | "AND";
            prop.Rule = identifier + "=" ;


            expression.Rule = "{" + (prop | block) + "}" + "|" ;
            expressions.Rule = MakeStarRule(expressions,  expression);
            block.Rule = expressions  + op;
            root.Rule = "{" + block +"}";

            Root = root;
            //automatically add NewLine before EOF so that our BNF rules work correctly when there's no final line break in source
            this.LanguageFlags =  LanguageFlags.NewLineBeforeEOF;
        }
    }
} //namespace

It parses ok, all you need to do is add AST tree and use it.