source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs @ 11727

using System;
using System.Collections.Generic;
using System.Data;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Xml.Linq;
using HeuristicLab.Common;

namespace HeuristicLab.Problems.GrammaticalOptimization {

  // phrases and symbols are both strings
  // spaces are used to separate symbols in phases
  // terminal and non-terminal symbols must not contain white-space
  // white-spaces are not counted when determining the length of a sentence, only the number of terminal symbols is relevant

  public class Grammar : IGrammar {

    private readonly Dictionary<char, List<string>> rules;
    private readonly HashSet<char> terminalSymbols;
    private readonly char sentenceSymbol;
    private readonly HashSet<char> nonTerminalSymbols;
    private readonly Dictionary<string, int> maxPhraseLength = new Dictionary<string, int>();
    private readonly Dictionary<string, int> minPhraseLength = new Dictionary<string, int>();

    public char SentenceSymbol { get { return sentenceSymbol; } }
    public IEnumerable<char> NonTerminalSymbols { get { return nonTerminalSymbols; } }
    public IEnumerable<char> TerminalSymbols { get { return terminalSymbols; } }
    public IEnumerable<char> Symbols { get { return nonTerminalSymbols.Concat(terminalSymbols); } } // ctor guarantees that intersection is empty

    // cloning ctor
    public Grammar(Grammar orig) {
      this.rules = new Dictionary<char, List<string>>(orig.rules);
      this.terminalSymbols = new HashSet<char>(orig.terminalSymbols);
      this.sentenceSymbol = orig.sentenceSymbol;
      this.nonTerminalSymbols = new HashSet<char>(orig.nonTerminalSymbols);
      this.maxPhraseLength = new Dictionary<string, int>(orig.maxPhraseLength);
      this.minPhraseLength = new Dictionary<string, int>(orig.minPhraseLength);
    }

    public Grammar(string grammar) : this((Grammar)FromString(grammar)) { }

    public Grammar(char sentenceSymbol, IEnumerable<char> terminalSymbols, IEnumerable<char> nonTerminalSymbols, IEnumerable<Tuple<char, string>> rules) {
      this.sentenceSymbol = sentenceSymbol;
      this.terminalSymbols = new HashSet<char>(terminalSymbols);
      this.nonTerminalSymbols = new HashSet<char>(nonTerminalSymbols);
      this.rules = new Dictionary<char, List<string>>();
      foreach (var r in rules) {
        if (!this.rules.ContainsKey(r.Item1)) this.rules.Add(r.Item1, new List<string>());
        this.rules[r.Item1].Add(r.Item2); // here we store an array of symbols for a phase
      }

      CheckValidity();
      CalculatePhaseLengthBounds();
    }

    private void CheckValidity() {
      // check validity of parameters
      if (!nonTerminalSymbols.Contains(sentenceSymbol) || // sentence symbol must be a non-terminal
          nonTerminalSymbols.Any(c => c < 'A' || c > 'Z') || // nonterminal symbols \in 'A' .. 'Z'
          terminalSymbols.Intersect(nonTerminalSymbols).Any() || // no overlap between non-terminals and terminal
          rules.Keys.Intersect(nonTerminalSymbols).Count() < nonTerminalSymbols.Count ||
          nonTerminalSymbols.Any(nt => !rules.ContainsKey(nt)) || // each nt must have at least one rule
          rules.Values.Any(alternatives => !alternatives.Any()) || // no eps alternatives
          rules.Any(rule => rule.Value.Any(alternative => alternative.Length == 1 && alternative[0] == rule.Key))
        // no infinite direct recursions
        ) {
        throw new ArgumentException();
      }
    }

    private void CalculatePhaseLengthBounds() {
      minPhraseLength.Clear();
      maxPhraseLength.Clear();
      // cache phrase lengths
      foreach (var nt in nonTerminalSymbols) {
        var min = int.MaxValue;
        var max = int.MinValue;
        foreach (var alt in rules[nt].OrderBy(alt => alt.Length)) {
          minPhraseLength[alt] = MinPhraseLength(alt);
          maxPhraseLength[alt] = MaxPhraseLength(alt);

          min = Math.Min(min, minPhraseLength[alt]);
          max = Math.Max(max, maxPhraseLength[alt]);
        }
        minPhraseLength[nt.ToString()] = min;
        maxPhraseLength[nt.ToString()] = max;
      }
    }


    public IEnumerable<string> GetAlternatives(char nt) {
      return rules[nt];
    }

    public IEnumerable<string> GetTerminalAlternatives(char nt) {
      return GetAlternatives(nt).Where(alt => alt.All(IsTerminal));
    }

    public IEnumerable<string> GetNonTerminalAlternatives(char nt) {
      return GetAlternatives(nt).Where(alt => alt.Any(IsNonTerminal));
    }

    // caches for this are build in construction of object
    public int MinPhraseLength(string phrase) {
      int l;
      if (minPhraseLength.TryGetValue(phrase, out l)) return l;
      l = 0;
      minPhraseLength[phrase] = short.MaxValue; // mark

      foreach (var symb in phrase) {
        if (IsNonTerminal(symb)) {
          l += MinSymbolLength(symb);
        } else {
          l++;
        }
      }

      l = Math.Min(short.MaxValue, l); // maximal allowed value is short.MaxValue
      minPhraseLength[phrase] = l; // update 
      return l;
    }

    // caches for this are build in construction of object
    public int MaxPhraseLength(string phrase) {
      int l;
      if (maxPhraseLength.TryGetValue(phrase, out l)) return l;
      l = 0;
      maxPhraseLength[phrase] = short.MaxValue; // mark

      foreach (var symb in phrase) {
        if (IsNonTerminal(symb)) {
          l += MaxSymbolLength(symb);
        } else {
          l++;
        }
      }
      l = Math.Min(short.MaxValue, l); // maximal allowed value is short.MaxValue
      maxPhraseLength[phrase] = l; // update 
      return l;
    }

    private int MinSymbolLength(char nt) {
      if (IsTerminal(nt)) return 1;
      else return Math.Min(short.MaxValue, rules[nt].Min(alt => MinPhraseLength(alt))); // maximal allowed value is short.MaxValue
    }
    private int MaxSymbolLength(char nt) {
      if (IsTerminal(nt)) return 1;
      else return Math.Min(short.MaxValue, rules[nt].Max(alt => MaxPhraseLength(alt))); // maximal allowed value is short.MaxValue
    }

    public string CompleteSentenceRandomly(Random random, string phrase, int maxLen) {
      if (phrase.Length > maxLen) throw new ArgumentException();
      if (MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
      bool done = phrase.All(IsTerminal); // terminal phrase means we are done
      while (!done) {
        int ntIdx; char nt;
        FindFirstNonTerminal(this, phrase, out nt, out ntIdx);

        int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
        Debug.Assert(maxLenOfReplacement > 0);

        var alts = GetAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
        Debug.Assert(alts.Any());

        // replace nt with random alternative
        var selectedAlt = alts.SelectRandom(random);
        phrase = phrase.Remove(ntIdx, 1);
        phrase = phrase.Insert(ntIdx, selectedAlt);

        done = phrase.All(IsTerminal); // terminal phrase means we are done
      }
      return phrase;
    }

    public static void FindFirstNonTerminal(IGrammar g, string phrase, out char nt, out int ntIdx) {
      ntIdx = 0;
      while (ntIdx < phrase.Length && g.IsTerminal(phrase[ntIdx])) ntIdx++;
      if (ntIdx >= phrase.Length) {
        ntIdx = -1;
        nt = '\0';
      } else {
        nt = phrase[ntIdx];
      }
    }

    public bool IsTerminal(char symbol) {
      return terminalSymbols.Contains(symbol);
    }

    public bool IsNonTerminal(char symbol) {
      return nonTerminalSymbols.Contains(symbol);
    }

    private static readonly string symbRegex = @"(?<symb>[^\s\|\.])";
    private static readonly string altRegex = @"(?<alt>[^\s\|\.]+)";
    private static readonly string altListRegex = altRegex + @"(\s*\|\s*" + altRegex + @")*";
    // private static readonly string terminalClassRegex = @"[^\s\|\.]\s*\.\.\s*[^\s\|\.]";
    private static readonly string terminalClassRegex = symbRegex + @"\s*\.\.\s*" + symbRegex + @"\s*";

    private static readonly Regex sentenceSymbRegex = new Regex(@"\s*G\(" + symbRegex + @"\):\s*$", RegexOptions.ExplicitCapture);
    private static readonly Regex ruleRegex = new Regex(@"\s*" + symbRegex + @"\s*->\s*(" + altListRegex + "|" + terminalClassRegex + @")\s*$", RegexOptions.ExplicitCapture);


    // supports only meta-symbol for alternatives (syntax of formal grammars)
    // epsilon-alternatives are not supported
    public static IGrammar FromString(string grammar) {
      char sentenceSymbol;
      var nonTerminals = new List<char>();
      var terminals = new List<char>();
      var rules = new List<Tuple<char, string>>();

      using (var reader = new StringReader(grammar)) {
        var line = reader.ReadLine();
        while (string.IsNullOrWhiteSpace(line)) line = reader.ReadLine();
        // first line contains "G(...):"
        var match = sentenceSymbRegex.Match(line);
        if (!match.Success) throw new ArgumentException();
        sentenceSymbol = match.Groups["symb"].Value[0]; // only a single symbol is in the capture group

        line = reader.ReadLine();
        while (!string.IsNullOrWhiteSpace(line)) {
          match = ruleRegex.Match(line);
          if (match.Length != line.Length) throw new ArgumentException();
          var nt = match.Groups["symb"].Captures[0].Value[0];
          if (!nonTerminals.Contains(nt)) nonTerminals.Add(nt);

          // contains alternatives?
          if (match.Groups["alt"].Captures.Count > 0) {
            foreach (var m in match.Groups["alt"].Captures) {
              rules.Add(Tuple.Create(nt, m.ToString()));
            }
          } else if (match.Groups["symb"].Captures.Count == 3) {
            // contains terminal range
            var fromSymb = match.Groups["symb"].Captures[1].Value[0];
            var toSymb = match.Groups["symb"].Captures[2].Value[0];
            if (fromSymb > toSymb) throw new ArgumentException("left symbol is larger than right symbol in range");

            for (byte b = Convert.ToByte(fromSymb); b <= Convert.ToByte(toSymb); b++) {
              rules.Add(Tuple.Create(nt, Convert.ToChar(b).ToString()));
            }
          }

          line = reader.ReadLine();
        }
      }

      foreach (var r in rules) {
        foreach (var s in r.Item2) {
          if (!nonTerminals.Contains(s) && !terminals.Contains(s)) terminals.Add(s);
        }
      }
      return new Grammar(sentenceSymbol, terminals, nonTerminals, rules);
    }

    public override string ToString() {
      // for debugging
      var sb = new StringBuilder();
      sb.AppendFormat("G({0}):", sentenceSymbol).AppendLine();
      foreach (var r in rules) {
        foreach (var alt in r.Value) {
          var phrase = string.Join(" ", alt);
          sb.AppendFormat("  {0} -> {1} (min: {2}, max {3})", r.Key, phrase, MinPhraseLength(phrase), MaxPhraseLength(phrase))
            .AppendLine();
        }
      }
      return sb.ToString();
    }
  }
}