// Idea: For every position, store the productions recognized to start there, then infer up to higher classes

!752

// a recognition is identified by (startPos, className, endPos)


// key 1 = start position, key 2 = class name, value = end position
static Map<Integer, MultiMap<S, Integer>> recog;

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();
    print(line);
    L<S> tok = javaTok(line);
    //printStructure(tok);
    Pos pos = new Pos(tok);
    L<Integer> x = parseTop(pos, mainProd);
    if (x.contains(l(tok)))
      print("  parsed");
    else if (!empty(x))
      print("  beginning matches");
    else
      print("  not parsed");
    print("  " + structure(recog));
    if (!empty(x)) {
      L out = explainMatch(new Pos(tok), x.get(0), mainProd);
      print("Analysis: " + structure(out));
    }
  }
}

static L<Integer> parseTop(Pos pos, S mainProd) {
  // init structures
  recog = new TreeMap;
  for (int i = pos.i; i < l(pos.tok); i += 2)
    recog.put(i, new MultiMap);

  boolean anyChange;
  do {
    anyChange = false;
    for (int i = pos.i; i < l(pos.tok); i += 2) {
      Pos pos2 = new Pos(pos.tok, i);
      for (S className : productionMap.keySet()) {
        MultiMap<S, Integer> rr = recog.get(i);
        L<Integer> recs = rr.getActual(className);
        L<L<S>> prods = productionMap.get(className);
        for (L<S> prod : prods) {
          int n = l(recs);
          matchProd(pos2, new Pos(prod), className, recs);
          anyChange = anyChange || l(recs) > n;
        }
        rr.clean(className);
      }
    }
  } while (anyChange);
  
  ret recog.get(pos.i).get(mainProd);
}

static class Pos {
  L<S> tok;
  int i = 1;
  
  *() {}
  *(L<S> *tok) {}
  *(L<S> *tok, int *i) {}
  
  boolean end() { ret i >= l(tok)-1; }
  S get() { ret tok.get(i); }
  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));
  }

  Pos plus(int x) { ret new Pos(tok, i + x); }
}

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

static void matchProd(Pos pos, Pos prod, S forClass, L<Integer> out) {
  if (prod.end())
    setAdd(out, pos.i);
  else {
    S p = prod.get();
    
    if (isBracketedID(p) && neq(p, "<quoted>")) {
      L<Integer> r = recog.get(pos.i).get(unbracket(p));
      
      // keep parsing for every option
  
      for (int i : cloneList(r))
        matchProd(new Pos(pos.tok, i), prod.plus(2), forClass, out);
      
    } else {
      // it's a literal
      if (pos.end()) ret; // need a token to match
      S t = pos.get();
      if (!matchToken(p, t))
        ret;
      
      matchProd(pos.plus(2), prod.plus(2), forClass, out);
    }
  }
}

static boolean matchToken(S p, S t) {
  if (eq(p, "<quoted>")) {
    if (!isQuoted(t)) ret false;
  } else if (!(eq(p, "*") || eqic(p, t)))
    ret false; // token mismatch
  ret true;
}

// assumes that there is a match (pos, class, endPos)
// and gives explanations of how it was probably matched
static L explainMatch(Pos pos, int endPos, S forClass) {
  L<L<S>> prods = productionMap.get(forClass);
  new L out;
  for (L<S> prod : prods)
    explainMatch2(pos, new Pos(prod), endPos, forClass, litlist(forClass, join(prod)), out);
  ret out;
}

// same, but with fixed production
static void explainMatch2(Pos pos, Pos prod, int endPos, S forClass, L match, L out) {
  if (prod.end()) {
    if (pos.i == endPos)
      out.add(cloneList(match));
  } else {
    S p = prod.get();
    
    if (isBracketedID(p) && neq(p, "<quoted>")) {
      S className = unbracket(p);
      L<Integer> r = recog.get(pos.i).get(className);

      // keep parsing for every option
  
      for (int i : cloneList(r)) {
        match.add(litlist(pos.i, i));
        explainMatch2(new Pos(pos.tok, i), prod.plus(2), endPos, forClass, match, out);
        removeLast(match);
      }
    } else {
      // it's a literal
      if (pos.end()) ret; // need a token to match
      S t = pos.get();
      if (!matchToken(p, t))
        ret;
      
      //match.add(litlist(pos.i, p, pos.i+2));
      explainMatch2(pos.plus(2), prod.plus(2), endPos, forClass, match, out);
      removeLast(match);
    }
  }
}

Began life as a copy of #1002302