Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Language.cs @ 15676

Last change on this file since 15676 was 10067, checked in by gkronber, 11 years ago

#2026 worked on brute force solver for GPDL problems.

File size: 4.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections;
24using System.Collections.Generic;
25using System.Diagnostics;
26using System.Linq;
27using System.Text.RegularExpressions;
28
29namespace HeuristicLab.Grammars {
30
31  public class Language : IEnumerable<IEnumerable<string>> {
32    private class PartiallyProcessedSequence {
33      private List<ISymbol> terminalSeq;
34      private Sequence remainingSeq;
35      private IGrammar grammar;
36
37      private PartiallyProcessedSequence parent;
38      private PartiallyProcessedSequence(PartiallyProcessedSequence parent) {
39        this.parent = parent;
40        this.terminalSeq = new List<ISymbol>();
41      }
42
43      public PartiallyProcessedSequence(Sequence seq, IGrammar g) {
44        this.terminalSeq = new List<ISymbol>();
45        this.remainingSeq = seq;
46        this.grammar = g;
47      }
48      public bool ProcessToNextNonTerminal(out ISymbol ntSymbol) {
49        var enumerator = remainingSeq.GetEnumerator();
50        int i = 0;
51        while (enumerator.MoveNext() && grammar.IsTerminal(enumerator.Current)) {
52          terminalSeq.Add(enumerator.Current);
53          i++;
54        }
55        if (enumerator.Current == null) {
56          ntSymbol = null;
57          return false;
58        } else {
59          ntSymbol = enumerator.Current;
60
61          remainingSeq = new Sequence(remainingSeq.Skip(i + 1).ToList());
62          return true;
63        }
64      }
65      public PartiallyProcessedSequence CreateAlternativeSequence(Sequence seq) {
66        var p = new PartiallyProcessedSequence(this);
67        p.grammar = grammar;
68        p.remainingSeq = new Sequence(seq.Concat(remainingSeq).ToList());
69        return p;
70      }
71      public IList<ISymbol> GetSequence() {
72        if (parent == null) return terminalSeq;
73        else {
74          return new Sequence(parent.GetSequence().Concat(terminalSeq).ToList());
75        }
76      }
77    }
78
79    private class LanguageEnumerator : IEnumerator<IEnumerable<string>> {
80      private IGrammar g;
81      private IEnumerable<string> currentSentence;
82      private Queue<PartiallyProcessedSequence> queue = new Queue<PartiallyProcessedSequence>();
83      public LanguageEnumerator(IGrammar g) {
84        this.g = g;
85        Reset();
86      }
87
88      public void Dispose() {
89        // nothing to do
90      }
91
92      public bool MoveNext() {
93        if (!queue.Any()) return false;
94
95        // iterate until a sequence with only non-terminals is found
96        do {
97          var f = queue.Dequeue();
98          ISymbol ntSymbol = null;
99          if (f.ProcessToNextNonTerminal(out ntSymbol) == true) {
100
101            // find first non-terminal and create chains for each alternative
102            foreach (var p in g.GetAlternatives(ntSymbol)) {
103              var chain = f.CreateAlternativeSequence(p);
104              queue.Enqueue(chain);
105            }
106          } else {
107            // only terminals in the chain => return as sentence
108            currentSentence = f.GetSequence().Select(symb => symb.Name);
109            return true;
110          }
111        } while (true);
112      }
113
114      public void Reset() {
115        queue.Clear();
116        foreach (var p in g.GetAlternatives(g.StartSymbol)) {
117          queue.Enqueue(new PartiallyProcessedSequence(p, g));
118        }
119      }
120
121      public IEnumerable<string> Current { get { return currentSentence; } }
122
123      object IEnumerator.Current {
124        get { return Current; }
125      }
126    }
127
128    private readonly IGrammar grammar;
129
130    public Language(IGrammar g) {
131      this.grammar = g;
132    }
133
134    public IEnumerator<IEnumerable<string>> GetEnumerator() {
135      return new LanguageEnumerator(grammar);
136    }
137
138
139    IEnumerator IEnumerable.GetEnumerator() {
140      return GetEnumerator();
141    }
142  }
143}
Note: See TracBrowser for help on using the repository browser.