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

Last change on this file since 11732 was 11732, checked in by gkronber, 5 years ago

#2283: refactoring and bug fixes

File size: 12.1 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Data;
4using System.Diagnostics;
5using System.IO;
6using System.Linq;
7using System.Text;
8using System.Text.RegularExpressions;
9using System.Xml.Linq;
10using HeuristicLab.Common;
11
12namespace HeuristicLab.Problems.GrammaticalOptimization {
13
14  // phrases and symbols are both strings
15  // spaces are used to separate symbols in phases
16  // terminal and non-terminal symbols must not contain white-space
17  // white-spaces are not counted when determining the length of a sentence, only the number of terminal symbols is relevant
18
19  public class Grammar : IGrammar {
20
21    private readonly Dictionary<char, List<Sequence>> rules;
22    private readonly HashSet<char> terminalSymbols;
23    private readonly char sentenceSymbol;
24    private readonly HashSet<char> nonTerminalSymbols;
25    private readonly Dictionary<Sequence, int> maxPhraseLength = new Dictionary<Sequence, int>();
26    private readonly Dictionary<Sequence, int> minPhraseLength = new Dictionary<Sequence, int>();
27
28    public char SentenceSymbol { get { return sentenceSymbol; } }
29    public IEnumerable<char> NonTerminalSymbols { get { return nonTerminalSymbols; } }
30    public IEnumerable<char> TerminalSymbols { get { return terminalSymbols; } }
31    public IEnumerable<char> Symbols { get { return nonTerminalSymbols.Concat(terminalSymbols); } } // ctor guarantees that intersection is empty
32
33    // cloning ctor
34    public Grammar(Grammar orig) {
35      this.rules = new Dictionary<char, List<Sequence>>();
36      foreach (var r in orig.rules)
37        this.rules.Add(r.Key, new List<Sequence>(r.Value.Select(v => new ReadonlySequence(v)))); // clone sequences
38      this.terminalSymbols = new HashSet<char>(orig.terminalSymbols);
39      this.sentenceSymbol = orig.sentenceSymbol;
40      this.nonTerminalSymbols = new HashSet<char>(orig.nonTerminalSymbols);
41      this.maxPhraseLength = new Dictionary<Sequence, int>();
42      foreach (var p in orig.maxPhraseLength) this.maxPhraseLength.Add(new ReadonlySequence(p.Key), p.Value);
43      this.minPhraseLength = new Dictionary<Sequence, int>();
44      foreach (var p in orig.minPhraseLength) this.minPhraseLength.Add(new ReadonlySequence(p.Key), p.Value);
45    }
46
47    public Grammar(string grammar) : this((Grammar)FromString(grammar)) { }
48
49    public Grammar(char sentenceSymbol, IEnumerable<char> terminalSymbols, IEnumerable<char> nonTerminalSymbols, IEnumerable<Tuple<char, string>> rules) {
50      this.sentenceSymbol = sentenceSymbol;
51      this.terminalSymbols = new HashSet<char>(terminalSymbols);
52      this.nonTerminalSymbols = new HashSet<char>(nonTerminalSymbols);
53      this.rules = new Dictionary<char, List<Sequence>>();
54      foreach (var r in rules) {
55        if (!this.rules.ContainsKey(r.Item1)) this.rules.Add(r.Item1, new List<Sequence>());
56        this.rules[r.Item1].Add(new ReadonlySequence(r.Item2)); // here we store an array of symbols for a phase
57      }
58
59      CheckValidity();
60      CalculatePhraseLengthBounds();
61    }
62
63    private void CheckValidity() {
64      // check validity of parameters
65      if (!nonTerminalSymbols.Contains(sentenceSymbol) || // sentence symbol must be a non-terminal
66          nonTerminalSymbols.Any(c => c < 'A' || c > 'Z') || // nonterminal symbols \in 'A' .. 'Z'
67          terminalSymbols.Intersect(nonTerminalSymbols).Any() || // no overlap between non-terminals and terminal
68          rules.Keys.Intersect(nonTerminalSymbols).Count() < nonTerminalSymbols.Count ||
69          nonTerminalSymbols.Any(nt => !rules.ContainsKey(nt)) || // each nt must have at least one rule
70          rules.Values.Any(alternatives => !alternatives.Any()) || // no eps alternatives
71          rules.Any(rule => rule.Value.Any(alternative => alternative.Length == 1 && alternative[0] == rule.Key))
72        // no infinite direct recursions
73        ) {
74        throw new ArgumentException();
75      }
76    }
77
78    private void CalculatePhraseLengthBounds() {
79      // cache phrase lengths
80      foreach (var nt in nonTerminalSymbols) {
81        var min = int.MaxValue;
82        var max = int.MinValue;
83        foreach (var alt in rules[nt].OrderBy(alt => alt.Length)) {
84          CalcAndSetMinPhraseLength(alt);
85          CalcAndSetMaxPhraseLength(alt);
86
87          min = Math.Min(min, minPhraseLength[alt]);
88          max = Math.Max(max, maxPhraseLength[alt]);
89        }
90        minPhraseLength[new ReadonlySequence(nt)] = min;
91        maxPhraseLength[new ReadonlySequence(nt)] = max;
92      }
93    }
94
95    public IEnumerable<Sequence> GetAlternatives(char nt) {
96      return rules[nt];
97    }
98
99    public IEnumerable<Sequence> GetTerminalAlternatives(char nt) {
100      return GetAlternatives(nt).Where(alt => alt.All(IsTerminal));
101    }
102
103    public IEnumerable<Sequence> GetNonTerminalAlternatives(char nt) {
104      return GetAlternatives(nt).Where(alt => alt.Any(IsNonTerminal));
105    }
106
107    #region population of minphraselength cache
108    private int CalcAndSetMinSymbolLength(char symb) {
109      if (IsTerminal(symb)) return 1;
110      else return Math.Min(short.MaxValue, rules[symb].Min(alt => CalcAndSetMinPhraseLength(alt))); // maximal allowed value is short.MaxValue
111    }
112    private int CalcAndSetMinPhraseLength(Sequence phrase) {
113      Debug.Assert(phrase is ReadonlySequence);
114      int l;
115      if (minPhraseLength.TryGetValue(phrase, out l)) return l;
116      l = 0;
117      minPhraseLength[phrase] = short.MaxValue; // mark
118
119      foreach (var symb in phrase) {
120        l += CalcAndSetMinSymbolLength(symb);
121      }
122
123      l = Math.Min(short.MaxValue, l); // maximal allowed value is short.MaxValue
124      minPhraseLength[phrase] = l; // update
125      return l;
126    }
127    #endregion
128
129    // read only access to caches
130    private int MinSymbolLength(char symb) {
131      if (IsTerminal(symb)) return 1;
132      else return Math.Min(short.MaxValue, rules[symb].Min(alt => MinPhraseLength(alt))); // maximal allowed value is short.MaxValue
133    }
134    public int MinPhraseLength(Sequence phrase) {
135      var minLen = 0;
136      if (minPhraseLength.TryGetValue(phrase, out minLen)) return minLen;
137      foreach (var s in phrase) {
138        minLen += MinSymbolLength(s);
139      }
140      return Math.Min(short.MaxValue, minLen); // maximal allowed value is short.MaxValue
141    }
142
143    #region population of maxphraselength cache
144    private int CalcAndSetMaxSymbolLength(char symb) {
145      if (IsTerminal(symb)) return 1;
146      else return Math.Min(short.MaxValue, rules[symb].Max(alt => CalcAndSetMaxPhraseLength(alt))); // maximal allowed value is short.MaxValue
147    }
148    // caches for this are build in construction of object
149    private int CalcAndSetMaxPhraseLength(Sequence phrase) {
150      Debug.Assert(phrase is ReadonlySequence);
151      int l;
152      if (maxPhraseLength.TryGetValue(phrase, out l)) return l;
153      l = 0;
154      maxPhraseLength[phrase] = short.MaxValue; // mark
155
156      foreach (var symb in phrase) {
157        l += CalcAndSetMaxSymbolLength(symb);
158      }
159      l = Math.Min(short.MaxValue, l); // maximal allowed value is short.MaxValue
160      maxPhraseLength[phrase] = l; // update
161      return l;
162    }
163    #endregion
164
165    // read only access to caches
166    public int MaxSymbolLength(char symb) {
167      if (IsTerminal(symb)) return 1;
168      else return Math.Min(short.MaxValue, rules[symb].Max(alt => MaxPhraseLength(alt))); // maximal allowed value is short.MaxValue
169    }
170    public int MaxPhraseLength(Sequence phrase) {
171      var maxLen = 0;
172      if (maxPhraseLength.TryGetValue(phrase, out maxLen)) return maxLen;
173      foreach (var s in phrase) {
174        maxLen += MaxSymbolLength(s);
175      }
176      return Math.Min(short.MaxValue, maxLen); // maximal allowed value is short.MaxValue
177    }
178
179    public Sequence CompleteSentenceRandomly(Random random, Sequence phrase, int maxLen) {
180      if (phrase.Length > maxLen) throw new ArgumentException();
181      if (MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
182      while (!phrase.IsTerminal) {
183        char nt = phrase.FirstNonTerminal;
184
185        int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
186        Debug.Assert(maxLenOfReplacement > 0);
187
188        var alts = GetAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
189        Debug.Assert(alts.Any());
190
191        // replace nt with random alternative
192        var selectedAlt = alts.SelectRandom(random);
193        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
194
195      }
196      return phrase;
197    }
198
199    public bool IsTerminal(char symbol) {
200      return terminalSymbols.Contains(symbol);
201    }
202
203    public bool IsNonTerminal(char symbol) {
204      return nonTerminalSymbols.Contains(symbol);
205    }
206
207    private static readonly string symbRegex = @"(?<symb>[^\s\|\.])";
208    private static readonly string altRegex = @"(?<alt>[^\s\|\.]+)";
209    private static readonly string altListRegex = altRegex + @"(\s*\|\s*" + altRegex + @")*";
210    // private static readonly string terminalClassRegex = @"[^\s\|\.]\s*\.\.\s*[^\s\|\.]";
211    private static readonly string terminalClassRegex = symbRegex + @"\s*\.\.\s*" + symbRegex + @"\s*";
212
213    private static readonly Regex sentenceSymbRegex = new Regex(@"\s*G\(" + symbRegex + @"\):\s*$", RegexOptions.ExplicitCapture);
214    private static readonly Regex ruleRegex = new Regex(@"\s*" + symbRegex + @"\s*->\s*(" + altListRegex + "|" + terminalClassRegex + @")\s*$", RegexOptions.ExplicitCapture);
215
216
217    // supports only meta-symbol for alternatives (syntax of formal grammars)
218    // epsilon-alternatives are not supported
219    public static IGrammar FromString(string grammar) {
220      char sentenceSymbol;
221      var nonTerminals = new List<char>();
222      var terminals = new List<char>();
223      var rules = new List<Tuple<char, string>>();
224
225      using (var reader = new StringReader(grammar)) {
226        var line = reader.ReadLine();
227        while (string.IsNullOrWhiteSpace(line)) line = reader.ReadLine();
228        // first line contains "G(...):"
229        var match = sentenceSymbRegex.Match(line);
230        if (!match.Success) throw new ArgumentException();
231        sentenceSymbol = match.Groups["symb"].Value[0]; // only a single symbol is in the capture group
232
233        line = reader.ReadLine();
234        while (!string.IsNullOrWhiteSpace(line)) {
235          match = ruleRegex.Match(line);
236          if (match.Length != line.Length) throw new ArgumentException();
237          var nt = match.Groups["symb"].Captures[0].Value[0];
238          if (!nonTerminals.Contains(nt)) nonTerminals.Add(nt);
239
240          // contains alternatives?
241          if (match.Groups["alt"].Captures.Count > 0) {
242            foreach (var m in match.Groups["alt"].Captures) {
243              rules.Add(Tuple.Create(nt, m.ToString()));
244            }
245          } else if (match.Groups["symb"].Captures.Count == 3) {
246            // contains terminal range
247            var fromSymb = match.Groups["symb"].Captures[1].Value[0];
248            var toSymb = match.Groups["symb"].Captures[2].Value[0];
249            if (fromSymb > toSymb) throw new ArgumentException("left symbol is larger than right symbol in range");
250
251            for (byte b = Convert.ToByte(fromSymb); b <= Convert.ToByte(toSymb); b++) {
252              rules.Add(Tuple.Create(nt, Convert.ToChar(b).ToString()));
253            }
254          }
255
256          line = reader.ReadLine();
257        }
258      }
259
260      foreach (var r in rules) {
261        foreach (var s in r.Item2) {
262          if (!nonTerminals.Contains(s) && !terminals.Contains(s)) terminals.Add(s);
263        }
264      }
265      return new Grammar(sentenceSymbol, terminals, nonTerminals, rules);
266    }
267
268    public override string ToString() {
269      // for debugging
270      var sb = new StringBuilder();
271      sb.AppendFormat("G({0}):", sentenceSymbol).AppendLine();
272      foreach (var r in rules) {
273        foreach (var alt in r.Value) {
274          sb.AppendFormat("  {0} -> {1} (min: {2}, max {3})", r.Key, alt, MinPhraseLength(alt), MaxPhraseLength(alt))
275            .AppendLine();
276        }
277      }
278      return sb.ToString();
279    }
280  }
281}
Note: See TracBrowser for help on using the repository browser.