!752 static MultiMap> 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 lr = splitAtJavaToken(rule, "="); if (l(lr) != 2) { print("Weird rule: " + rule); continue; } S l = lr.get(0), r = lr.get(1); L tokr = javaTok(r); assertEquals(structure(tokr), 3, l(tokr)); S className = assertIdentifier(get(tokr, 1)); L 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 tok = javaTok(line); Pos pos = new Pos(tok); if (parseClass(pos, mainProd) != null) print(" parsed"); else print(" not parsed"); } } static class Pos { L tok; int i = 1; *() {} *(L *tok) {} *(L *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 haltClasses; static O parseClass(Pos pos, S name) { if (debug) debug("parseClass " + name, pos); if (checkHalt(pos, name)) ret null; L> prods = productionMap.get(name); if (empty(prods)) ret null; // weird, unknown class name for (L 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 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 static L mergeBracketThingies(L 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; }