Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Implementing Programming Languages Using C# 4.0

, 12 Jul 2012
An introduction to creating programming language tools using C# 4.0.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace Diggins.Jigsaw
{
    public abstract class Rule
    {
        public Rule(IEnumerable<Rule> rules)
        {
            if (rules.Any(r => r == null)) throw new Exception("No child rule can be null");
            Children = new List<Rule>(rules);
        }

        public Rule(params Rule[] rules)
            : this((IEnumerable<Rule>)rules)
        {
        }

        public List<Rule> Children = new List<Rule>();

        public string Name { get; set; }

        public Rule Child { get { return Children[0]; } }

        protected abstract bool InternalMatch(ParserState state);

        public bool Match(ParserState state)
        {
            // HINT: This is a good place to set a conditional break-point when debugging.
            // Using the Name = X as a condition.
            return InternalMatch(state);            
        }

        public static Rule operator +(Rule r1, Rule r2)
        {
            return Grammar.Seq(r1, r2);
        }

        public static Rule operator |(Rule r1, Rule r2)
        {
            return Grammar.Choice(r1, r2);
        }

        public override string ToString()
        {
            return Name ?? Definition;
        }

        public List<Node> Parse(string input)
        {
            var state = new ParserState() { input = input, pos = 0 };
            if (!Match(state))
                throw new Exception(String.Format("Rule {0} failed to match", Name));
            return state.nodes;
        }

        public bool Match(string input)
        {
            var state = new ParserState() { input = input, pos = 0 };
            return Match(state);
        }

        public Rule SetName(string s)
        {
            Name = s;
            return this;
        }

        public abstract string Definition { get; }
    }

    public class AtRule : Rule
    {
        public AtRule(Rule r)
            : base(r)
        { }

        protected override bool InternalMatch(ParserState state)
        {
            var old = state.Clone();
            bool result = Child.Match(state);
            state.Assign(old);
            return result;
        }

        public override string Definition
        {
            get { return String.Format("At({0})", Child.ToString()); }
        }
    }

    public class NotRule : Rule
    {
        public NotRule(Rule r)
            : base(r)
        { }

        protected override bool InternalMatch(ParserState state)
        {
            var old = state.Clone();
            if (Child.Match(state))
            {
                state.Assign(old);
                return false;
            }
            return true;
        }

        public override string Definition
        {
            get { return String.Format("Not({0})", Child.ToString()); }
        }
    }

    public class NodeRule : Rule
    {
        /// <summary>
        /// Set to false to see how long it takes to parse grammars without memoization.
        /// </summary>
        private static readonly bool UseCache = true;

        public NodeRule(Rule r)
            : base(r)
        { }

        protected override bool InternalMatch(ParserState state)
        {
            try
            {
                if (UseCache)
                    return InternalMatchWithCaching(state);
                else
                    return InternalMatchWithoutCaching(state);
            }
            catch (Exception e)
            {
                Console.WriteLine("While parsing rule {0}, an error occured: {1}", Name, e.Message);
                throw;
            }
        }

        private bool InternalMatchWithCaching(ParserState state)
        {
            Node node;

            int start = state.pos;

            if (state.GetCachedResult(this, out node))
            {
                if (node == null)
                    return false;

                state.pos = node.End;
                state.nodes.Add(node);
                return true;
            }

            node = new Node(state.pos, Name, state.input);
            var oldNodes = state.nodes;
            state.nodes = new List<Node>();

            if (Child.Match(state))
            {
                node.End = state.pos;
                node.Nodes = state.nodes;
                oldNodes.Add(node);
                state.nodes = oldNodes;
                state.CacheResult(this, start, node);
                return true;
            }
            else
            {
                state.nodes = oldNodes;
                state.CacheResult(this, start, null);
                return false;                
            }
        }

        private bool InternalMatchWithoutCaching(ParserState state)
        {
            Node node;

            node = new Node(state.pos, Name, state.input);
            var oldNodes = state.nodes;
            state.nodes = new List<Node>();
                
            if (Child.Match(state))
            {
                node.End = state.pos;
                node.Nodes = state.nodes;
                oldNodes.Add(node);
                state.nodes = oldNodes;
                return true;
            }
            else
            {
                state.nodes = oldNodes;
                return false;
            }
        }

        public override string Definition 
        {
            get { return Child.Definition; }
        }
    }

    public class RecursiveRule : Rule
    {
        Func<Rule> ruleGen;

        public RecursiveRule(Func<Rule> ruleGen)
        {
            this.ruleGen = ruleGen;
        }

        protected override bool InternalMatch(ParserState state)
        {
            if (Children.Count == 0)
                Children.Add(ruleGen());
            return Child.Match(state);
        }

        public override string ToString()
        {
            return Name ?? (Children.Count > 0 ? Children[0].ToString() : "recursive");
        }

        public override string Definition 
        {
            get { return ruleGen().Definition; }
        }
    };

    public class SeqRule : Rule
    {
        public SeqRule(params Rule[] rs)
            : base(rs)
        { }

        protected override bool InternalMatch(ParserState state)
        {
            var old = state.Clone();
            foreach (var r in Children)
                if (!r.Match(state))
                {
                    state.Assign(old);
                    return false;
                }
            return true;
        }

        public override string Definition 
        {
            get 
            { 
                var sb = new StringBuilder();               
                sb.Append(Children[0].ToString());
                if (Children.Count == 2 && Children[1] is SeqRule)
                {
                    sb.Append(" + ");
                    sb.Append(Children[1].Definition);
                }
                else
                {
                    for (int i=1; i < Children.Count; ++i) 
                        sb.Append(" + ").Append(Children[i].ToString());
                }
                return sb.ToString();
            }
        }

        public override string ToString()
        {
 	        return String.Format("({0})", base.ToString());
        }
    }

    public class ChoiceRule : Rule
    {
        public ChoiceRule(params Rule[] rs)
            : base(rs)
        {
        }

        protected override bool InternalMatch(ParserState state)
        {
            var old = state.Clone();
            foreach (var r in Children)
            {
                if (r.Match(state)) return true;
                state.Assign(old);
            }
            return false;
        }

        public override string Definition 
        {
            get 
            { 
                var sb = new StringBuilder();               
                sb.Append(Children[0].ToString());
                if (Children.Count == 2 && Children[1] is ChoiceRule)
                {
                    sb.Append(" | ");
                    sb.Append(Children[1].Definition);
                }
                else
                {
                    for (int i=1; i < Children.Count; ++i) 
                        sb.Append(" | ").Append(Children[i].ToString());
                }
                return sb.ToString();
            }
        }

        public override string ToString()
        {
 	        return String.Format("({0})", base.ToString());
        }
    }

    public class EndRule : Rule
    {
        protected override bool InternalMatch(ParserState state)
        {
            return state.pos == state.input.Length;
        }

        public override string Definition
        {
            get { return "_EOF_"; }
        }
    }

    public class ZeroOrMoreRule : Rule
    {
        public ZeroOrMoreRule(Rule r)
            : base(r)
        { }

        protected override bool InternalMatch(ParserState state)
        {
            while (Child.Match(state)) { };
            return true;
        }

        public override string Definition
        {
            get { return String.Format("{0}*", Child.ToString()); }
        }
    }

    public class PlusRule : Rule
    {
        public PlusRule(Rule r)
            : base(r)
        { }

        protected override bool InternalMatch(ParserState state)
        {
            if (!Child.Match(state)) return false;
            while (Child.Match(state)) { }
            return true;
        }

        public override string Definition
        {
            get { return String.Format("{0}+", Child.ToString()); }
        }
    }

    public class OptRule : Rule
    {
        public OptRule(Rule r)
            : base(r)
        { }

        protected override bool InternalMatch(ParserState state)
        {
            Child.Match(state);
            return true;
        }

        public override string Definition
        {
            get { return String.Format("{0}?", Child.ToString()); }
        }
    }

    public class StringRule : Rule
    {
        string s;

        public StringRule(string s)
        {
            this.s = s;
        }

        protected override bool InternalMatch(ParserState state)
        {
            if (!state.input.Substring(state.pos).StartsWith(s))
                return false;
            state.pos += s.Length;
            return true;
        }

        public override string Definition
        {
            get { return String.Format("\"{0}\"", s); }
        }
    }

    public class CharRule : Rule
    {
        Predicate<char> predicate;

        public CharRule(Predicate<char> p)
        {
            predicate = p;
        }

        protected override bool InternalMatch(ParserState state)
        {
            if (state.pos >= state.input.Length)
                return false;
            if (!predicate(state.input[state.pos]))
                return false;
            state.pos++;
            return true;
        }

        public override string Definition
        {
            get { return "f(char)"; }
        }
    }

    public class RegexRule : Rule
    {
        Regex re;

        public RegexRule(Regex re)
        {
            this.re = re;
        }

        protected override bool InternalMatch(ParserState state)
        {
            var m = re.Match(state.input, state.pos);
            if (m == null || m.Index != state.pos) return false;
            state.pos += m.Length;
            return true;
        }

        public override string Definition
        {
            get { return String.Format("regex({0})", re.ToString()); }
        }
    }

}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The MIT License

About the Author

Christopher Diggins
Software Developer Autodesk
Canada Canada
This article was written by Christopher Diggins, a computer science nerd who currently works at Autodesk as an SDK specialist.
Follow on   Twitter   Google+   LinkedIn

| Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 12 Jul 2012
Article Copyright 2011 by Christopher Diggins
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid