Das Folgende ist für mein eigenes Memo. Bitte erlauben Sie mir, den Artikel für eine Weile unlesbar zu lassen.
Große frühere Artikel und [Artikel](http://research.microsoft.com/en-us/um/people/daan/download/ Erstellen Sie schnell einen Parser-Kombinator, indem Sie auf papiere / parsc-paper.pdf) verweisen. Innerhalb von ca. 200 Zeilen. Monaden interessieren mich nicht. Ich hoffe, es funktioniert. Das macht meine einfache Sprache.
ParserCombinator.java
public class ParserCombinator {
public static class EndOfInputException extends IOException {private static final long serialVersionUID = 9014321537291324114L;}
public static interface Input<I> {
public I current(); //EOF wird als null ausgedrückt
public Input<I> next() throws EndOfInputException;
public String positionDescription();
}
public static class ParseException extends Exception { //Das Muster "Verwenden Sie weniger außergewöhnliche Ausnahmen". Hauptsächlich verursacht durch,Wirkt als Fahrzeug, das verursacht wird.
private static final long serialVersionUID = -3808983810373258044L;
public static final ParseException singleton = new ParseException(); //Verwenden Sie grundsätzlich nur diesen Singleton
private String causedBy = "", causedAt = "";
public ParseException setCaused(String causedBy_, String causedAt_) {causedBy = causedBy_; causedAt = causedAt_; return this;}
public String getCausedBy() {return causedBy;}
public String getCausedAt() {return causedAt;}
}
public static interface Parser<I, A> {public Tuple2<A, Input<I>> parse(Input<I> input) throws ParseException;}
public static class ParserMemoizer<I, A> implements Parser<I, A> { //Ein Wrapper zum Erstellen von Parser-Memos. Es dient auch als Platzhalter bei der Beschreibung von Wiederholungen.
private Supplier<Parser<I, A>> supplier = null;
public Parser<I, A> defun(Supplier<Parser<I, A>> supplier_) {supplier = supplier_; return this;}
private Parser<I, A> parser = null;
private Map<Input<I>, Tuple2<Tuple2<A, Input<I>>, Tuple2<String, String>>> memo = new HashMap<>();
@Override public Tuple2<A, Input<I>> parse(Input<I> input) throws ParseException {
if (parser == null) parser = supplier.get();
if (! memo.containsKey(input)) {
Tuple2<A, Input<I>> result = null; Tuple2<String, String> error = null;
try {result = parser.parse(input);} catch (ParseException e) {error = Tuple.of(e.getCausedBy(), e.getCausedAt());}
memo.put(input, Tuple.of(result, error));
}
Tuple2<Tuple2<A, Input<I>>, Tuple2<String, String>> result = memo.get(input);
if (result.cdr.car == null) return result.car; else throw ParseException.singleton.setCaused(result.cdr.car.car, result.cdr.car.cdr.car);
}
}
public static <I, A> Parser<I, A> lookahead(Parser<I, A> p) {
return new ParserMemoizer<I, A>().defun(() -> {
return i -> Tuple.of(p.parse(i).car, i); //Gibt das vorgelesene Ergebnis zurück, fährt jedoch nicht mit der Eingabe selbst fort
});
}
public static <I> Parser<I, I> satisfy(Predicate<I> predicate) {
return new ParserMemoizer<I, I>().defun(
() -> i -> {
try { // i.current()Wenn null ist, ist es eof, daher wird dort eine Ausnahme ausgelöst. So oder so, normalerweise ich.Ich sollte als nächstes eine Ausnahme bekommen.
if (i.current() != null && predicate.test(i.current())) return Tuple.of(i.current(), i.next());
} catch (EndOfInputException e) {}
throw ParseException.singleton.setCaused(i.current() == null ? "end of input" : "unsatisfying input " + i.current(), i.positionDescription());
}
);
}
public static <I, A, B> Parser<I, B> apply(Parser<I, A> p, Function<A, B> func) {
return new ParserMemoizer<I, B>().defun(
() -> i -> {
Tuple2<A, Input<I>> result = p.parse(i);
return Tuple.of(func.apply(result.car), result.cdr.car);
}
);
}
public static <I, A, B> Parser<I, B> bind(Parser<I, A> first, Function<A, Parser<I, B>> next) {
return new ParserMemoizer<I, B>().defun(
() -> i -> {
Tuple2<A, Input<I>> result = first.parse(i);
return next.apply(result.car).parse(result.cdr.car);
}
);
}
@SafeVarargs
public static <I, A> Parser<I, A> or(Parser<I, A>... p) {
return new ParserMemoizer<I, A>().defun(
() -> i -> {
for (int idx = 0; idx < p.length; idx ++) try {return p[idx].parse(i);} catch (ParseException e) {}
throw ParseException.singleton.setCaused("no rule matched", i.positionDescription());
}
);
}
public static <I, A, B> Parser<I, B> invert(Parser<I, A> p, Function<Tuple2<A, Input<I>>, ParseException> f0, Function<ParseException, B> f1) { //Gibt eine Ausnahme zurück, wenn p erfolgreich ist, löst eine Ausnahme aus und gibt ein Ergebnis zurück
return new ParserMemoizer<I, B>().defun(
() -> i -> {
B result = null; ParseException ex = null;
try {ex = f0.apply(p.parse(i));} catch (ParseException e) {result = f1.apply(e);}
if (ex == null) return Tuple.of(result, i /*Die Eingabe kann nicht fortgesetzt werden*/); else throw ex;
}
);
}
public static <I, A> Parser<I, Boolean> not(Parser<I, A> p, Function<A, String> errorMessageGenerator) {return invert(p, r -> ParseException.singleton.setCaused(errorMessageGenerator.apply(r.car), r.cdr.car.positionDescription()), e -> true);}
public static <I, A, B> Parser<I, B> reduce(Parser<I, List<A>> src, Supplier<B> identityGenerator, BiFunction<B, A, B> accumulator) {
return new ParserMemoizer<I, B>().defun(
() -> i -> {
Tuple2<List<A>, Input<I>> result = src.parse(i);
B reduced = identityGenerator.get();
for (A item : result.car) reduced = accumulator.apply(reduced, item);
return Tuple.of(reduced, result.cdr.car);
}
);
}
public static <I, A> Parser<I, List<A>> lst(List<Parser<I, A>> p) {
return new ParserMemoizer<I, List<A>>().defun(
() -> i -> {
List<A> result = new ArrayList<>();
Input<I> rest = null;
Tuple2<A, Input<I>> cursor = Tuple.of(null, i);
for (int idx = 0; idx < p.size(); idx ++) {
cursor = p.get(idx).parse(cursor.cdr.car);
result.add(cursor.car);
rest = cursor.cdr.car;
}
return Tuple.of(result, rest); //Ignorieren Sie die Analyse-Ausnahme nicht
}
);
}
@SafeVarargs public static <I, A> Parser<I, List<A>> lst(Parser<I, A>...p) {return lst(Arrays.asList(p));}
public static <I, A, B> Parser<I, List<A>> rep(Supplier<Iterator<B>> iteratorMaker, Parser<I, A> p) {
return new ParserMemoizer<I, List<A>>().defun(
() -> i -> {
Iterator<B> iterator = iteratorMaker.get(); //Erstellen Sie jedes Mal einen neuen Iterator(Andernfalls wird es seltsam, wenn es erneut ausgeführt wird)
List<A> result = new ArrayList<>();
Input<I> rest = null;
try {
for (Tuple2<A, Input<I>> cursor = Tuple.of(null, i); iterator.hasNext();) {
iterator.next(); //Ich benutze nur den Iterator als Trick für Schleifen, also überspringe ihn
cursor = p.parse(cursor.cdr.car);
result.add(cursor.car);
rest = cursor.cdr.car;
}
} catch (ParseException e) {}
return Tuple.of(result, result.size() == 0 ? i : rest); //Gibt die ursprüngliche Eingabe zurück, wenn sie nur 0 Mal übereinstimmt
}
);
}
private static class LoopIterator implements Iterator<Long> {
private long cursor, until, step;
public LoopIterator(long start_, long until_, long step_) {cursor = start_; until = until_; step = step_;}
public boolean hasNext() {return cursor + step <= until;}
public Long next() {try {return cursor;} finally {cursor += step;}} //Entschuldigen Sie, dass Sie den Trick verwendet haben, um die Anzahl der Zeilen zu reduzieren. Das automatische Boxen des Cursors wird "später" über den Inhaltscursor zurückgegeben+=Schritt ausführen.
}
public static <I, A, B> Parser<I, List<A>> rep(long cnt, Parser<I, A> p) {return rep(() -> new LoopIterator(0, cnt, 1), p);}
public static <I, A> Parser<I, List<A>> many(Parser<I, A> p) {return rep(() -> new LoopIterator(0, 1, 0), p);} //Ein Trick, um eine Endlosschleife zu erreichen, indem ein Iterator übergeben wird, der nicht vorrückt
public static <I, A> Parser<I, List<A>> many1(Parser<I, A> p) {return apply(seq(p, many(p)), tpl2 -> {tpl2.cdr.car.add(0, tpl2.car); return tpl2.cdr.car;});}
public static <Z, A, B> Parser<Z, Tuple2<A, B>> seq(Parser<Z, A> a, Parser<Z, B> b) {
return new ParserMemoizer<Z, Tuple2<A, B>>().defun(
() -> i -> {
Tuple2<A, Input<Z>> r0 = a.parse(i);
Tuple2<B, Input<Z>> r1 = b.parse(r0.cdr.car);
return Tuple.of(Tuple.of(r0.car, r1.car), r1.cdr.car);
}
);
}
public static <Z, A, B, C> Parser<Z, Tuple3<A, B, C>> seq(Parser<Z, A> a, Parser<Z, B> b, Parser<Z, C> c) {
return new ParserMemoizer<Z, Tuple3<A, B, C>>().defun(
() -> i -> {
Tuple2<A, Input<Z>> r0 = a.parse(i);
Tuple2<B, Input<Z>> r1 = b.parse(r0.cdr.car);
Tuple2<C, Input<Z>> r2 = c.parse(r1.cdr.car);
return Tuple.of(Tuple.of(r0.car, r1.car, r2.car), r2.cdr.car);
}
);
}
public static <I, A> Parser<I, A> eof() {
return i -> {if (i.current() == null) return Tuple.of(null, i); else throw ParseException.singleton.setCaused("parser stopped while reading", i.positionDescription());};
}
}
Nachtrag (18.01.2017): Nur ein paar Korrekturen und Ergänzungen
Recommended Posts