GrammarBuilder.cs

Go to the documentation of this file.

using Mercury.Exceptions;
using Mercury.Nucleus.Collections;
using System.Collections.Generic;
using System.Linq;

namespace Mercury.Syntax
{
//=============================================================================
//  GrammarBuilder
//=============================================================================

    public class GrammarBuilder
    {
        //--[  Private fields  ]-----------------------------------------------

        protected HashSet<Symbol> nonterminals = new HashSet<Symbol>();
        protected HashSet<Symbol> terminals    = new HashSet<Symbol>();
        protected HashSet<Rule>   rules        = new HashSet<Rule>();

        //--[  Constructors  ]-------------------------------------------------

        public GrammarBuilder()
            : this(new Symbol(Defaults.Root), new Symbol(Defaults.Epsilon, SymbolType.Epsilon))
        { }

        public GrammarBuilder(Symbol root, Symbol epsilon)
        {
            if (root.Type != SymbolType.Nonterminal)
                throw new SyntaxException("Root must be a nonterminal");

            if (epsilon.Type != SymbolType.Epsilon)
                throw new SyntaxException("Invalid epsilon symbol");

            nonterminals.Add(root);

            Root    = root;
            Epsilon = epsilon;
        }

        //--[  Properties  ]---------------------------------------------------

        public Symbol Root { get; private set; }

        public Symbol Epsilon { get; private set; }

        //--[  Methods  ]------------------------------------------------------

        public GrammarBuilder AddSymbol(Symbol newSymbol)
        {
            if (newSymbol.Name == Epsilon.Name)
                return this;

            switch (newSymbol.Type)
            {
                case SymbolType.Terminal:
                    terminals.Add(newSymbol);
                    break;

                case SymbolType.Nonterminal:
                    nonterminals.Add(newSymbol);
                    break;
            }

            return this;
        }

        public virtual GrammarBuilder AddRule(Rule rule)
        {
            AddSymbol(rule.LHS);

            if (rule.RHS.Any(x => (x.Name == Epsilon.Name) && (!x.IsEpsilon)))
                rule = new Rule(rule.LHS, rule.RHS
                    .Select(x => x.Name != Epsilon.Name ? x : new Symbol(x.Name, SymbolType.Epsilon)));

            foreach (var s in rule.RHS.Where(x => !x.IsEpsilon))
                AddSymbol(s);

            rules.Add(rule);
            return this;
        }

        public GrammarBuilder AddRules(IEnumerable<Rule> rules)
        { foreach (var rule in rules) AddRule(rule); return this; }

        public GrammarBuilder Include(GrammarBuilder other)
        { foreach (var rule in other.rules) AddRule(rule); return this; }

        public Grammar GetGrammar()
        { 
            return new Grammar() 
            {
                Nonterminals  = nonterminals.ToList(),
                Terminals     = terminals.ToList(),
                Rules         = rules.ToList(),
                Root          = this.Root,
                Epsilon       = this.Epsilon,
            }; 
        }
    }

//=============================================================================
//  ExtendedGrammarBuilder
//=============================================================================

    internal class ExtendedGrammarBuilder : GrammarBuilder
    {
        //--[  Private fields  ]-----------------------------------------------

        private List<Rule> epsilonRules;
        private List<Rule> terminalRules;

        private ListMultiDictionary<Symbol, Rule> rulemap;

        //--[  Constructors  ]-------------------------------------------------

        public ExtendedGrammarBuilder(Symbol root, Symbol epsilon)
            : base(root, epsilon)
        {
            epsilonRules  = new List<Rule>();
            terminalRules = new List<Rule>();

            rulemap       = new ListMultiDictionary<Symbol, Rule>();
        }

        public ExtendedGrammarBuilder(Grammar source)
            : this(source.Root, source.Epsilon)
        {
            for(int ix = 0; ix < source.Rules.Count; ++ix)
            {
                Rule r = source.Rules[ix];
                if (r.IsEpsilon) epsilonRules.Add(r);
                else
                {
                    if (r.RHS[0].Type == SymbolType.Terminal) terminalRules.Add(r);
                    rulemap.Add(r.RHS[0], r);
                }

                base.AddRule(r);
            }
        }

        public ExtendedGrammarBuilder(ExtendedGrammar source)
            : this(source.Root, source.Epsilon)
        {
            epsilonRules.AddRange(source.EpsilonRules);
            terminalRules.AddRange(source.TerminalRules);
            rulemap = new ListMultiDictionary<Symbol, Rule>(source.rulemap);
        }

        //--[  Methods  ]------------------------------------------------------

        public static ExtendedGrammar ExtendGrammar(Grammar grammar)
        { return new ExtendedGrammarBuilder(grammar).GetExtendedGrammar(); }

        public ExtendedGrammar GetExtendedGrammar()
        {
            return new ExtendedGrammar()
            {
                Nonterminals  = nonterminals.ToList(),
                Terminals     = terminals.ToList(),
                Rules         = rules.ToList(),
                Root          = this.Root,
                Epsilon       = this.Epsilon,

                EpsilonRules  = epsilonRules.ToList(),
                TerminalRules = terminalRules.ToList(),
                rulemap       = this.rulemap
            };
        }

        //--[  Overriden methods  ]--------------------------------------------

        #region [  GrammarBuilder  ]

        public new ExtendedGrammarBuilder AddRule(Rule rule)
        {
            int cntx = rules.Count;
            base.AddRule(rule);

            if (cntx != rules.Count)
            {
                if (rule.IsEpsilon) epsilonRules.Add(rule);
                else                rulemap.Add(rule.RHS[0], rule);

                if (rule.RHS[0].Type == SymbolType.Terminal)
                    terminalRules.Add(rule);
            }

            return this;
        }

        #endregion

    }
}