!752

static MultiMap<S, L<S>> productionMap = new MultiMap;

static boolean debug = false;

p {
  S rulesText = loadSnippet("#1002281");
  S inputText = loadSnippet("#1002286") + "\n" + loadSnippet("#1002280");
  S mainProd = "line";
  
  for (S rule : toLinesFullTrim(rulesText)) pcall {
    printF("Processing rule: *", rule);
    L<S> lr = splitAtJavaToken(rule, "=");
    if (l(lr) != 2) {
      print("Weird rule: " + rule);
      continue;
    }
    S l = lr.get(0), r = lr.get(1);
    L<S> tokr = javaTok(r);
    assertEquals(structure(tokr), 3, l(tokr));
    S className = assertIdentifier(get(tokr, 1));
    L<S> tok = javaTok(l);
    tok = mergeBracketThingies(tok);
    //printStructure(tok);
    productionMap.put(className, tok);
  }
  
  print(n(productionMap.size(), "production") + ".");
  print();
  
  for (S line : toLinesFullTrim(inputText)) {
    print(line);
    L<S> tok = javaTok(line);
    Pos pos = new Pos(tok);
    if (parseClass(pos, mainProd) != null)
      print("  parsed");
    else
      print("  not parsed");
  }
}

static class Pos {
  L<S> tok;
  int i = 1;
  
  *() {}
  *(L<S> *tok) {}
  *(L<S> *tok, int *i) {}
  
  boolean end() { ret i >= l(tok)-1; }
  public Pos clone() { ret new Pos(tok, i); }
  public boolean equals(O o) {
    if (!(o instanceof Pos)) ret false;
    Pos pos = cast o;
    ret tok == pos.tok && i == pos.i;
  }
  
  S rest() {
    ret join(subList(tok, i));
  }
}

static void copy(Pos a, Pos b) {
  b.tok = a.tok;
  b.i = a.i;
}

static void debug(S bla, Pos pos) {
  if (debug)
    print(bla + " on " + quote(pos.rest()));
}

// endless loop detector
static Pos haltPos;
static new HashSet<S> haltClasses;

static O parseClass(Pos pos, S name) {
  if (debug) debug("parseClass " + name, pos);
  if (checkHalt(pos, name)) ret null;
  L<L<S>> prods = productionMap.get(name);
  if (empty(prods)) ret null; // weird, unknown class name
  
  for (L<S> prod : prods) {
    Pos _pos = pos.clone();
    O x = parseProd(_pos, prod);
    if (x != null) { copy(_pos, pos); ret x; }
  }
  
  ret null;
}

// returns true if we should halt because of endless looping
static boolean checkHalt(Pos pos, S className) {
  if (!eq(haltPos, pos)) {
    haltPos = pos.clone();
    haltClasses = lithashset(className);
    return false;
  } else {
    if (haltClasses.contains(className)) {
      if (debug)
        print("Endless loop: " + structure(pos) + " " + structure(haltClasses));
      ret true;
    } else {
      haltClasses.add(className);
      print("checkHalt: same pos, classes now: " + structure(haltClasses));
      ret false;
    }
  }
}

static O parseProd(Pos pos, L<S> prod) {
  if (debug)
    debug("parseProd " + structure(prod), pos);
  
  for (int i = 1; i < l(prod); i += 2) {
    S p = prod.get(i);
    S t = pos.tok.get(pos.i);
    if (isBracketedID(p)) {
      Pos _pos = pos.clone();
      O x = parseClass(_pos, unbracket(p));
      if (x == null) ret null;
      copy(_pos, pos);
      // keep parsing production
    } else {
      // it's a literal
      if (pos.end()) ret null; // need a token to match
      if (!(eq(p, "*") || eqic(p, t)))
        ret null; // token mismatch
      pos.i += 2; // consume & keep parsing
    }
  }
  
  if (debug)
    debug("ok " + structure(prod), pos);
  ret true; // production succeeded
}

static boolean isBracketedID(S s) {
  ret s.startsWith("<") && s.endsWith(">");
}

static S unbracket(S s) {
  ret isBracketedID(s) ? s.substring(1, l(s)-1) : s;
}

// angle bracket things like <quoted>
static L<S> mergeBracketThingies(L<S> tok) {
  tok = cloneList(tok);
  for (int i = 1; i+4 < l(tok); i += 2)
    if (eq(get(tok, i), "<") && eq(get(tok, i+1), "") && isIdentifier(get(tok, i+2)) && eq(get(tok, i+3), "") && eq(get(tok, i+4), ">")) {
      tok.set(i, "<" + tok.get(i+2) + ">");
      tok.remove(i+4);
      tok.remove(i+3);
      tok.remove(i+2);
      tok.remove(i+1);
    }
  ret tok;
}