source: branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL/3.4/Grammar.cs

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Grammar {
  private class Sequence : List<string> {
    public override string ToString() {
      var sb = new StringBuilder();
      foreach (var e in this) {
        sb.Append(e).Append(" ");
      }
      return sb.ToString();
    }
  }
  private class Alternatives : List<Sequence> {
    public override string ToString() {
      var sb = new StringBuilder();
      if (Count == 0)
        sb.Append("EPS");
      else
        sb.Append(this[0]);
      foreach (var e in this.Skip(1)) {
        sb.Append("| ").Append(e);
      }
      return sb.ToString();
    }
  }

  private Dictionary<string, Alternatives> alternatives = new Dictionary<string, Alternatives>();
  private Dictionary<string, string> localDefinitions = new Dictionary<string, string>();
  private Dictionary<string, List<IEnumerable<RuleExprNode>>> seqWithActions = new Dictionary<string, List<IEnumerable<RuleExprNode>>>();
  public string RootSymbol { get; private set; }
  public IEnumerable<string> Symbols { get; private set; }

  public Grammar(IEnumerable<SymbolNode> ntSymbols, IEnumerable<SymbolNode> tSymbols, List<RuleNode> ruleNodes) {
    CheckGrammarConstraints(ntSymbols, tSymbols, ruleNodes);
    foreach (var ruleNode in ruleNodes) {
      alternatives[ruleNode.NtSymbol] = ToAlternatives(ruleNode.RuleExpr);
      localDefinitions[ruleNode.NtSymbol] = ruleNode.LocalCode;
      seqWithActions[ruleNode.NtSymbol] = ToAlternativesWithActions(ruleNode.RuleExpr);
    }
    RootSymbol = ruleNodes.First().NtSymbol;
    Symbols = ntSymbols.Select(n => n.Ident).Concat(tSymbols.Select(n => n.Ident)).ToList();
  }

  private List<IEnumerable<RuleExprNode>> ToAlternativesWithActions(RuleExprNode ruleExprNode) {
    var l = new List<IEnumerable<RuleExprNode>>();
    var altNode = ruleExprNode as AlternativesNode;
    if (altNode != null) {
      l.AddRange(altNode.Alternatives.Select(expr => Flatten(expr)));
    } else {
      l.Add(Flatten(ruleExprNode));
    }
    return l;
  }

  private IEnumerable<RuleExprNode> Flatten(RuleExprNode expr) {
    var seqNode = expr as SequenceNode;
    var callNode = expr as CallSymbolNode;
    var actionNode = expr as RuleActionNode;
    if (seqNode != null) {
      return seqNode.Sequence;
    } else if (callNode != null) {
      return Enumerable.Repeat(callNode, 1);
    } else if (actionNode != null) {
      return Enumerable.Repeat(actionNode, 1);
    } else {
      throw new NotSupportedException();
    }
  }

  public IEnumerable<List<string>> GetAlternatives(string sy) {
    if (!alternatives.ContainsKey(sy)) return Enumerable.Empty<List<string>>();
    return alternatives[sy];
  }

  public string GetLocalDefinitions(string sy) {
    if (!localDefinitions.ContainsKey(sy)) return string.Empty;
    return localDefinitions[sy];
  }

  private Alternatives ToAlternatives(RuleExprNode ruleExprNode) {
    var alt = new Alternatives();
    var altNode = ruleExprNode as AlternativesNode;
    if (altNode != null) {
      alt.AddRange(altNode.Alternatives.Select(expr => ToSequence(expr)));
    } else {
      alt.Add(ToSequence(ruleExprNode));
    }
    return alt;
  }

  private Sequence ToSequence(RuleExprNode ruleExprNode) {
    var seqNode = ruleExprNode as SequenceNode;
    var callNode = ruleExprNode as CallSymbolNode;
    var actionNode = ruleExprNode as RuleActionNode;
    var seq = new Sequence();
    if (seqNode != null) {
      // keep only the nodes refering to symbols
      seq.AddRange(seqNode.Sequence.OfType<CallSymbolNode>().Select(n => n.Ident));
    } else if (callNode != null) {
      seq.Add(callNode.Ident);
    } else if (actionNode != null) {
      throw new NotSupportedException();
    } else {
      throw new NotSupportedException();
    }
    return seq;
  }

  public IEnumerable<RuleExprNode> GetSequenceWithSemanticActions(string sy, int altIdx) {
    return seqWithActions[sy][altIdx];
  }

  // should be checked when reading the grammar?
  private void CheckGrammarConstraints(IEnumerable<SymbolNode> ntSymbols, IEnumerable<SymbolNode> tSymbols, List<RuleNode> rules) {
    /* rules: 
     *  - one rule for each non-terminal symbol 
     *  - LL(1)
     *  - alternatives have to be single-symbol chains
     *  - all symbols used on the right hand side have to be defined
     */

    //// only one rule for non-terminal symbols
    //var dupSymbols = rules.GroupBy(r => r.NtSymbol).Where(g => g.Count() > 1);
    //if (dupSymbols.Count() > 0) throw new ArgumentException("Two grammar rules for " + dupSymbols.Select(g => g.Key).Aggregate("", (s, s1) => s + ", " + s1));

    //// a rule for all non-terminal symbols
    //foreach (var ntSymbol in ntSymbols) {
    //  if (rules.All(r => r.NtSymbol != ntSymbol.Ident)) throw new ArgumentException("No grammar rule for NTSymbol " + ntSymbol);
    //}

    //foreach (var r in rules) {

    //}
  }

  public override string ToString() {
    var sb = new StringBuilder();
    foreach (var entry in alternatives) {
      sb.Append(entry.Key).Append(" -> ").AppendLine(entry.Value.ToString());
    }
    return sb.ToString();
  }

}