Changeset 10051 for branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars

Timestamp:

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

Author:

gkronber

Message:

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

Location:

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

Files:

• Attribute.cs (added)
• AttributedGrammar.cs (added)
• Grammar.cs (modified) (4 diffs)
• HeuristicLab.Grammars-3.3.csproj (modified) (3 diffs)
• Interfaces/IAttribute.cs (modified) (1 diff)
• Interfaces/IAttributedGrammar.cs (modified) (1 diff)
• Interfaces/IGrammar.cs (modified) (1 diff)
• Interfaces/ISymbol.cs (modified) (1 diff)
• Language.cs (added)
• Sequence.cs (added)
• Symbol.cs (added)
• Test.cs (added)

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;
     }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/HeuristicLab.Grammars-3.3.csproj

@@ -7 +7 @@
     <SchemaVersion>2.0</SchemaVersion>
     <ProjectGuid>{A5452B63-B33B-4F9F-9E81-98B75EDB5612}</ProjectGuid>
-    <OutputType>Library</OutputType>
+    <OutputType>Exe</OutputType>
     <AppDesignerFolder>Properties</AppDesignerFolder>
     <RootNamespace>HeuristicLab.Grammars</RootNamespace>
@@ -93 +93 @@
     <CodeAnalysisRuleSet>AllRules.ruleset</CodeAnalysisRuleSet>
   </PropertyGroup>
+  <PropertyGroup>
+    <StartupObject />
+  </PropertyGroup>
   <ItemGroup>
     <Reference Include="HeuristicLab.PluginInfrastructure-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
@@ -115 +118 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="AttributedGrammar.cs" />
+    <Compile Include="Attribute.cs" />
+    <Compile Include="Sequence.cs" />
+    <Compile Include="Test.cs" />
+    <Compile Include="Symbol.cs" />
+    <Compile Include="Language.cs" />
     <Compile Include="Grammar.cs" />
     <Compile Include="Interfaces\IAttribute.cs" />
-    <Compile Include="Interfaces\IAttributedGrammar.cs" />
     <Compile Include="Interfaces\ISymbol.cs" />
     <Compile Include="Interfaces\IGrammar.cs" />

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/IAttribute.cs

@@ -22 +22 @@
 namespace HeuristicLab.Grammars {
   public enum AttributeType { In, Out, Ref };
-  interface IAttribute {
+  public interface IAttribute {
     AttributeType AttributeType { get; }
     string Type { get; }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/IAttributedGrammar.cs

@@ -24 +24 @@
 namespace HeuristicLab.Grammars {
   interface IAttributedGrammar : IGrammar {
-    IEnumerable<IAttribute> GetAttributes(string symbol);
-    void AddAttribute(string symbol, IAttribute attribute);
+    ISymbol StartSymbol { get; set; }
+    IEnumerable<ISymbol> TerminalSymbols { get; }
+    IEnumerable<ISymbol> NonTerminalSymbols { get; }
+    IEnumerable<ISymbol> Symbols { get; }
+    bool IsTerminal(ISymbol symbol);
+    bool IsNonTerminal(ISymbol symbol);
+
+    int NumberOfAlternatives(ISymbol ntSymbol);
+    IEnumerable<Sequence> GetAlternatives(ISymbol ntSymbol);
+    Sequence GetAlternative(ISymbol ntSymbol, int index);
+
+    void AddProductionRule(ISymbol ntSymbol, Sequence production);
   }
 }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/IGrammar.cs

@@ -23 +23 @@
 
 namespace HeuristicLab.Grammars {
-  using Sequence = IEnumerable<string>;
 
   public interface IGrammar {
-    string StartSymbol { get; set; }
-    IEnumerable<string> TerminalSymbols { get; }
-    IEnumerable<string> NonTerminalSymbols { get; }
-    IEnumerable<string> Symbols { get; }
+    ISymbol StartSymbol { get; set; }
+    IEnumerable<ISymbol> TerminalSymbols { get; }
+    IEnumerable<ISymbol> NonTerminalSymbols { get; }
+    IEnumerable<ISymbol> Symbols { get; }
+    bool IsTerminal(ISymbol symbol);
+    bool IsNonTerminal(ISymbol symbol);
 
-    int NumberOfAlternatives(string ntSymbol);
-    IEnumerable<Sequence> GetAlternatives(string ntSymbol);
-    Sequence GetAlternative(string ntSymbol, int index);
+    int NumberOfAlternatives(ISymbol ntSymbol);
+    IEnumerable<Sequence> GetAlternatives(ISymbol ntSymbol);
+    Sequence GetAlternative(ISymbol ntSymbol, int index);
 
-    void AddProductionRule(string ntSymbol, Sequence production);
+    void AddProductionRule(ISymbol ntSymbol, Sequence production);
   }
 }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/ISymbol.cs

@@ -20 +20 @@
 #endregion
 
-/*
 namespace HeuristicLab.Grammars {
-  interface ISymbol {
+  public interface ISymbol {
     string Name { get; }
-    bool IsTerminal { get; }
+    IAttribute Attribute { get; }
   }
 }
-*/