// 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(), 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, className));

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

    }

  }

}