package javakurs.musterloesung.uebung11;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * {@link GrammarBase} is the base class of a context free grammar.
 *
 * @author Bernd Kiefer, DFKI
 * @author Joerg Steffen, DFKI
 * @version $Id: GrammarBase.java,v 1.1 2011/01/26 15:50:16 steffen Exp $
 */
public abstract class GrammarBase {

  /**
   * Contains a collection of rules defining the grammar.
   */
  protected Collection<Rule> rules;

  /**
   * Maps non-terminals to sets of terminals that can occur in the first
   * position.
   */
  protected Map<String, Set<String>> nonTerm2firstTerms;

  /**
   * Contains the set of non-terminal symbols.
   */
  private Set<String> nonTerminals;

  /**
   * Contains the start symbol.
   */
  private String startSymbol;


  /**
   * Contains the pattern that matches syntactically correct rules. We use
   * capturing groups to easily extract lhs and rhs later.
   */
  private Pattern rulePattern =
    Pattern.compile("(\\w+) :(( (\\w+|(\"\\w+\")))+)");


  /**
   * Creates a new instance of {@link GrammarBase}.
   */
  public GrammarBase() {

    this.rules = new ArrayList<Rule>();
    this.nonTerminals = new HashSet<String>();
    this.nonTerm2firstTerms = new HashMap<String, Set<String>>();
  }


  /**
   * Returns the rules of the grammar.
   *
   * @return the rules
   */
  public Collection<Rule> getRules() {

    return this.rules;
  }


  /**
   * Returns the the start symbol.
   *
   * @return the start symbol
   */
  public String getStartSymbol() {

    return this.startSymbol;
  }


  /**
   * Returns {@code true} if the given symbol is a terminal.
   *
   * @param symbol
   *          the symbol to check
   * @return a flag indicating if the symbol is a terminal
   */
  public boolean isTerminal(String symbol) {

    return !this.nonTerminals.contains(symbol);
  }


  /**
   * Reads a grammar from the given file.
   *
   * @param fileName
   *          the file name of the grammar
   * @param encoding
   *          the encoding of the grammar file
   */
  public void readFromFile(String fileName, String encoding) {

    try {

      // init reader
      BufferedReader in = new BufferedReader(
        new InputStreamReader(
          new FileInputStream(fileName),
          encoding));

      String line;
      int lineNum = 0;
      // read lines from file
      while ((line = in.readLine()) != null) {
        lineNum++;
        // check syntax and create rule
        if (!this.createEntries(line)) {
          System.err.println(
              "Syntax error in line " + lineNum + "; line is ignored");
          System.err.println(line);
        }
      }
    } catch (IOException ioe) {
      System.err.println(ioe.getMessage());
    }
  }


  /**
   * Checks if the given line contains a syntactically correct rule. If yes, it
   * creates the corresponding entries in the grammar.
   *
   * @param line
   *          the line to check
   * @return a flag indicating if the line was a syntactically correct rule or
   *         lexicon entry
   */
  private boolean createEntries(String line) {

    // check if line is a rule
    Matcher ruleMatcher = this.rulePattern.matcher(line);
    if (ruleMatcher.matches()) {

      // get lhs of the rule; this is always a non-terminal
      String lhs = ruleMatcher.group(1);
      this.nonTerminals.add(lhs);
      if (null == this.startSymbol) {
        // start symbol is the lhs of the first rule
        this.startSymbol = lhs;
      }

      // collect rhs symbols of rule; the complete rhs is the second capturing
      // group
      List<String> rhs = new ArrayList<String>();
      StringTokenizer tok = new StringTokenizer(ruleMatcher.group(2), " ");
      while (tok.hasMoreTokens()) {
        String rhsSymbol = tok.nextToken();
        // check if the symbol is a terminal or a non-terminal
        if (rhsSymbol.startsWith("\"")) {
          rhsSymbol = rhsSymbol.substring(1, rhsSymbol.length() - 1);
        }
        else {
          this.nonTerminals.add(rhsSymbol);
        }
        rhs.add(rhsSymbol);
      }

      // create new rule
      this.rules.add(new Rule(lhs, rhs));

      return true;
    }

    return false;
  }


  /**
   * Returns for the given non-terminal the set of terminals that can occur in
   * the first position.
   *
   * @param nonTerminal
   *          a non-terminal
   * @return the matching set of terminals
   */
  public Set<String> getFirstTerminals(String nonTerminal) {

    Set<String> result = this.nonTerm2firstTerms.get(nonTerminal);
    if (null == result) {
      result = new HashSet<String>();
    }

    return result;
  }


  /**
   * Initializes nonTerm2firstTerms based on the rules of the grammar.
   */
  public abstract void calculateFirstMap();


  /**
   * Returns the set of rules that has {@code nonTerminal} on the left hand side
   * and whose first (non)terminal on the right hand side has
   * {@code firstTerminal} in the first-relation.
   *
   * @param nonTerminal
   *          the left hand side non-terminal of the rules to select
   * @param firstTerminal
   *          a terminal that has to be present in the first-relation of the
   *          first (non)terminal on the right hand side
   * @return the matching rules
   */
  public abstract List<Rule> getRulesTopDown(
    String nonTerminal, String firstTerminal);


  /**
   * {@inheritDoc}
   */
  @Override
  public String toString() {

    StringBuilder strRep = new StringBuilder();
    String newline = System.getProperty("line.separator");

    // get rules
    for (Rule oneRule : this.rules) {

      strRep.append(oneRule.getLhs()).append(" :");
      for (String oneSymbol : oneRule.getRhs()) {
        strRep.append(" ");
        if (this.isTerminal(oneSymbol)) {
          strRep.append("\"").append(oneSymbol).append("\"");
        }
        else {
          strRep.append(oneSymbol);
        }
      }
      strRep.append(newline);
    }

    // get first mapping
    strRep.append(newline);
    for (Map.Entry<String, Set<String>> oneEntry
        : this.nonTerm2firstTerms.entrySet()) {
      strRep.append(oneEntry.getKey()).append(": (");
      for (String oneTerminal : oneEntry.getValue()) {
        strRep.append("\"").append(oneTerminal).append("\" ");
      }
      strRep.append(")").append(newline);
    }

    return strRep.toString();
  }
}
