Parser.cs

Go to the documentation of this file.

using Mercury.Nucleus.Collections;
using Mercury.Nucleus.Trees;
using Mercury.Scanning;
using System;
using System.Collections.Generic;
using System.Linq;

namespace Mercury.Syntax
{
//=============================================================================
//  IParser
//=============================================================================

    public interface IParser
    {
        Grammar Grammar { get; }

        ParserResult Parse(IList<Token> tokens);

        ParserResult Parse(IList<Token> tokens, IList<Rule> scanresult);
    }

//=============================================================================
//  ChartParserInternal
//=============================================================================

    internal class ChartParserInternal
    {
        //--[  Private classes  ]----------------------------------------------

        #region [  ReferenceComparer  ]

        private class ReferenceComparer : IEqualityComparer<object>
        {
            public new bool Equals(object x, object y)
            { return object.ReferenceEquals(x, y); }

            public int GetHashCode(object obj)
            { return obj.GetHashCode(); }
        }

        #endregion

        //--[  Private fields  ]-----------------------------------------------

        private UniqueListMultiDictionary<Edge, EdgeDerivation> edges    = null;
        private UniqueListMultiDictionary<Edge, Tree<Symbol>>   allTrees = null;

        private List<Edge>  chart  = null;
        private Queue<Edge> agenda = null;

        private List<Edge>         activeEdges   = null; // cache
        private List<Edge>         passiveEdges  = null; // cache
        private List<Tree<Symbol>> finalTrees    = null; // cache
        private List<Tree<Symbol>> terminalTrees = null; // cache

        private List<Token>  input = null;
        private List<Symbol> data  = null;

        private HashSet<EdgeDerivation> explored = null;
        private HashSet<EdgeDerivation> locked   = null;

        //--[  Private methods  ]----------------------------------------------

        private void AddEdge(Edge edge, EdgeDerivation eder)
        {
            if (!edges.ContainsKey(edge)) agenda.Enqueue(edge);
            edges.Add(edge, eder);
        }

        private bool IsFinalEdge(Edge edge)
        {
            return  edge.IsPassive
                && (edge.Left  == 0)
                && (edge.Right == input.Count)
                && (edge.Rule.LHS.Equals(Grammar.Root));
        }

        #region [  Chart Parsing Methods       ]

        private void Initialize()
        {
            edges  = new UniqueListMultiDictionary<Edge, EdgeDerivation>();
            chart  = new List<Edge>();
            agenda = new Queue<Edge>();

            activeEdges  = new List<Edge>();
            passiveEdges = new List<Edge>();

            for (int rix = 0; rix < Grammar.EpsilonRules.Count; ++rix)
                for (int ix = 0; ix <= input.Count; ++ix)
                    AddEdge(new Edge(Grammar.EpsilonRules[rix], 0, ix, ix), EdgeDerivation.Initial());

            for (int rix = 0; rix < Grammar.TerminalRules.Count; ++rix)
            {
                Rule rule = Grammar.TerminalRules[rix];

                for (int ix = 0; ix < input.Count; ++ix)
                    if (data[ix].Name == rule.RHS[0].Name)
                        AddEdge(new Edge(rule, 0, ix, ix), EdgeDerivation.Initial());
            }
        }

        private void CombineEdges(Edge source, Edge additional)
        {
            if ((source.Right == additional.Left) && (source.NextSymbol.Equals(additional.Rule.LHS)))
                AddEdge(new Edge(source.Rule, source.Dot + 1, source.Left, additional.Right), 
                                 EdgeDerivation.Fundamental(source, additional));
        }

        private void FundamentalA(Edge agendaEdge)
        {
            if (agendaEdge.IsActive) return;

            for (int ix = 0; ix < activeEdges.Count; ++ix)
                CombineEdges(activeEdges[ix], agendaEdge);
        }

        private void FundamentalB(Edge agendaEdge)
        {
            if (agendaEdge.IsPassive) return;

            for (int ix = 0; ix < passiveEdges.Count; ++ix)
                CombineEdges(agendaEdge, passiveEdges[ix]);
        }

        private void ScanInput(Edge agendaEdge)
        {
            if (agendaEdge.IsPassive
                ||  (agendaEdge.NextSymbol.Type != SymbolType.Terminal)
                ||  (data.Count <= agendaEdge.Right)
                || !(data[agendaEdge.Right].Name == agendaEdge.NextSymbol.Name))
                return;

            AddEdge(new Edge(agendaEdge.Rule, agendaEdge.Dot + 1, agendaEdge.Left, agendaEdge.Right + 1), 
                    EdgeDerivation.Scanning(agendaEdge));
        }

        private void Prediction(Edge agendaEdge)
        {
            if (agendaEdge.IsActive) return;

            foreach(Rule rule in Grammar.RulesWithInitial(agendaEdge.Rule.LHS))
                    AddEdge(new Edge(rule, 0, agendaEdge.Left, agendaEdge.Left), EdgeDerivation.Prediction());
        }

        #endregion

        #region [  Derivation Tree Generators  ]

        private void CreateTrees(Edge edge)
        {
            foreach(var derivation in edges[edge])
            {
                if (explored.Contains(derivation) || !locked.Add(derivation)) continue;

                var temp = new List<Tree<Symbol>>();
                switch(derivation.Derivation)
                {
                    case DerivationType.Initial:
                    case DerivationType.Prediction:
                        Tree<Symbol> newTree = edge.Rule.IsEpsilon
                            ? new Tree<Symbol>(edge.Rule.LHS, new [] { terminalTrees[terminalTrees.Count - 1] })
                            : new Tree<Symbol>(edge.Rule.LHS);

                        allTrees.Add(edge, newTree);
                        break;

                    case DerivationType.Scanning:
                        CreateTrees(derivation.Source);
                        for (int ix = 0; ix < allTrees.GetValuesCount(derivation.Source); ++ix)
                            allTrees.Add(edge, new Tree<Symbol>(allTrees.GetValue(derivation.Source, ix),
                                                                new[] { terminalTrees[edge.Right - 1] }));
                        break;

                    case DerivationType.Fundamental:
                        CreateTrees(derivation.Source);
                        CreateTrees(derivation.Additional);
                        for (int src = 0; src < allTrees.GetValuesCount(derivation.Source); ++src)
                            for (int add = 0; add < allTrees.GetValuesCount(derivation.Additional); ++add)
                                allTrees.Add(edge, new Tree<Symbol>(allTrees.GetValue(derivation.Source, src),
                                                                    new[] { allTrees.GetValue(derivation.Additional, add) }));
                        break;
                }

                explored.Add(derivation);
                locked.Remove(derivation);
            }
        }

        private void CreateDerivationTrees()
        {
            allTrees      = new UniqueListMultiDictionary<Edge, Tree<Symbol>>();
            terminalTrees = new List<Tree<Symbol>>();
            finalTrees    = new List<Tree<Symbol>>();

            locked   = new HashSet<EdgeDerivation>(new ReferenceComparer());
            explored = new HashSet<EdgeDerivation>(new ReferenceComparer());

            input.ForEach(x => terminalTrees.Add(new Tree<Symbol>(new Symbol(x))));
            terminalTrees.Add(new Tree<Symbol>(Grammar.Epsilon));

            foreach (var edge in chart.Where(e => IsFinalEdge(e)))
            {
                CreateTrees(edge);
                finalTrees.AddRange(allTrees[edge]);
            }
        }

        #endregion

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

        public ChartParserInternal(ExtendedGrammar grammar)
        {
            if (grammar == null) throw new ArgumentNullException("grammar");

            Grammar = grammar;
        }

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

        public ExtendedGrammar Grammar { get; private set; }

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

        public ParserResult Parse(IList<Token> tokens)
        {
            input = new List<Token>(tokens);
            data  = input.Select(x => new Symbol(x)).ToList();

            Initialize();

            while (agenda.Count != 0)
            {
                Edge a_edge = agenda.Dequeue();

                FundamentalA(a_edge);
                FundamentalB(a_edge);
                ScanInput(a_edge);
                Prediction(a_edge);

                chart.Add(a_edge);

                if (a_edge.IsActive) activeEdges.Add(a_edge);
                else                 passiveEdges.Add(a_edge);
            }

            CreateDerivationTrees();

            return new ParserResult()
            {
                Accepted    = finalTrees.Count > 0,
                InputTokens = input,
                Chart       = chart,
                Trees       = finalTrees
            };
        }
    }

//=============================================================================
//  ChartParser
//=============================================================================

    public class ChartParser : IParser
    {
        //--[  Private fields  ]-----------------------------------------------

        private ExtendedGrammar extgrammar;

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

        public ChartParser(Grammar grammar)
        {
            Grammar    = grammar;
            extgrammar = ExtendedGrammarBuilder.ExtendGrammar(grammar);
        }

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

        public Grammar Grammar { get; private set; }

        //--[  Interface implementation  ]-------------------------------------

        #region [  IParser  ]

        public ParserResult Parse(IList<Token> tokens)
        { return (new ChartParserInternal(extgrammar)).Parse(tokens); }

        public ParserResult Parse(IList<Token> tokens, IList<Rule> scanresult)
        {
            var gb = new ExtendedGrammarBuilder(extgrammar);

            for (int ix = 0; ix < scanresult.Count; ++ix)
                gb.AddRule(scanresult[ix]);

            return (new ChartParserInternal(gb.GetExtendedGrammar())).Parse(tokens);
        }

        #endregion

    }
}