Changeset 10051 for branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Grammar.cs

Timestamp:

10/17/13 15:19:45 (11 years ago)

Author:

gkronber

Message:

#2026 worked on a plugin for grammars (work-in-progress)

File:

• branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Grammar.cs (modified) (4 diffs)

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Grammar.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text.RegularExpressions;
 
 namespace HeuristicLab.Grammars {
-  using Sequence = IEnumerable<string>;
+  public class Grammar : IGrammar {
+    public static readonly ISymbol EmptySymbol = new Symbol("EPS");
+    private Dictionary<ISymbol, List<Sequence>> rules = new Dictionary<ISymbol, List<Sequence>>();
+    private HashSet<ISymbol> allSymbols = new HashSet<ISymbol>();
 
-  public class Grammar : IGrammar {
-    private Dictionary<string, List<Sequence>> rules = new Dictionary<string, List<Sequence>>();
-    private HashSet<string> allSymbols = new HashSet<string>();
+    public ISymbol StartSymbol { get; set; }
+    public IEnumerable<ISymbol> TerminalSymbols { get { return allSymbols.Except(NonTerminalSymbols); } }
+    public IEnumerable<ISymbol> NonTerminalSymbols { get { return rules.Keys; } }
+    public IEnumerable<ISymbol> Symbols { get { return allSymbols; } }
 
-    public string StartSymbol { get; set; }
-    public IEnumerable<string> TerminalSymbols { get { return allSymbols.Except(NonTerminalSymbols); } }
-    public IEnumerable<string> NonTerminalSymbols { get { return rules.Keys; } }
-    public IEnumerable<string> Symbols { get { return allSymbols; } }
-
-    public Grammar(string startSymbol) {
+    public Grammar(ISymbol startSymbol) {
+      Debug.Assert(startSymbol != EmptySymbol);
       this.StartSymbol = startSymbol;
     }
 
-    public int NumberOfAlternatives(string ntSymbol) {
+    public int NumberOfAlternatives(ISymbol ntSymbol) {
       return rules[ntSymbol].Count;
     }
 
-    public IEnumerable<Sequence> GetAlternatives(string ntSymbol) {
+    public IEnumerable<Sequence> GetAlternatives(ISymbol ntSymbol) {
       return rules[ntSymbol].AsReadOnly();
     }
 
-    public Sequence GetAlternative(string ntSymbol, int index) {
+    public Sequence GetAlternative(ISymbol ntSymbol, int index) {
       return rules[ntSymbol][index];
     }
 
-    public void AddProductionRule(string ntSymbol, Sequence production) {
+    public void AddProductionRule(ISymbol ntSymbol, Sequence production) {
+      Debug.Assert(ntSymbol != EmptySymbol);
+
       List<Sequence> l;
       if (!rules.TryGetValue(ntSymbol, out l)) {
@@ -61 +64 @@
         allSymbols.Add(ntSymbol); // register new nt-symbol
       }
+      // check if the same production exists already
+      Debug.Assert(!l.Any(s => s.SequenceEqual(production)));
+
       l.Add(production);
 
@@ -66 +72 @@
     }
 
+    public bool IsTerminal(ISymbol symbol) {
+      return !rules.ContainsKey(symbol) && allSymbols.Contains(symbol);
+    }
+    public bool IsNonTerminal(ISymbol symbol) {
+      return rules.ContainsKey(symbol);
+    }
+
+    // checks if a rule exists for each NT symbol
+    public bool IsComplete() {
+      return rules.ContainsKey(StartSymbol) &&
+             NonTerminalSymbols.All(nt => rules.ContainsKey(nt));
+    }
+
     private static Regex ruleExpr = new Regex(@"\s*(?<ntSymbol>\w+)\s*->\s*(?<alternative>\w+(?:\s+\w+)*)(?:\s*\|\s*(?<alternative>\w+(?:\s+\w+)*))*");
     private static Regex empty = new Regex(@"^\s*$");
-    public static IGrammar FromString(string gStr) {
+    public static Grammar FromString(string gStr) {
       var lines = gStr.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
       lines = lines.Where(l => !empty.IsMatch(l)).ToArray(); // remove empty lines
@@ -74 +93 @@
       // first line is the rule for the start-symbol
       var m = ruleExpr.Match(lines.First());
-      var startSymbol = m.Groups["ntSymbol"].Value;
+      var startSymbol = new Symbol(m.Groups["ntSymbol"].Value);
       var g = new Grammar(startSymbol);
       foreach (var alt in m.Groups["alternative"].Captures) {
-        g.AddProductionRule(startSymbol, alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries));
+        g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
       }
       foreach (var line in lines.Skip(1)) {
         m = ruleExpr.Match(line);
-        var ntSymbol = m.Groups["ntSymbol"].Value;
+        var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
         foreach (var alt in m.Groups["alternative"].Captures) {
-          g.AddProductionRule(ntSymbol, alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries));
+          g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
         }
       }
+
       return g;
     }