Ce qui suit est pour mon propre mémo. Veuillez me permettre de laisser l'article illisible pendant un certain temps.
Grands articles antérieurs et [Articles](http://research.microsoft.com/en-us/um/people/daan/download/ Créez rapidement un combinateur d'analyseur en vous référant à papers / parsc-paper.pdf). Dans environ 200 lignes. Je me fiche des monades. J'espère que ça marche. Cela rend mon langage simple.
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 est exprimé comme nul
public Input<I> next() throws EndOfInputException;
public String positionDescription();
}
public static class ParseException extends Exception { //Le modèle «utiliser des exceptions moins exceptionnelles». Principalement causé,Agit comme un véhicule transportant causé
private static final long serialVersionUID = -3808983810373258044L;
public static final ParseException singleton = new ParseException(); //En gros, n'utilisez que ce 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> { //Un wrapper utilisé pour créer des mémos Parser. Il sert également d'espace réservé lors de la description de la récurrence.
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); //Renvoie le résultat de la pré-lecture, mais ne procède pas à l'entrée elle-même
});
}
public static <I> Parser<I, I> satisfy(Predicate<I> predicate) {
return new ParserMemoizer<I, I>().defun(
() -> i -> {
try { // i.current()Si est nul, c'est eof, donc une exception y est levée. De toute façon, généralement je.Je devrais obtenir une exception sur la prochaine.
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) { //Renvoie une exception si p réussit, lève une exception et renvoie un résultat
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 /*L'entrée ne peut pas continuer*/); 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); //N'ignorez pas l'exception d'analyse
}
);
}
@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(); //créer un nouvel itérateur à chaque fois(Sinon, ce sera étrange lors de la réexécution)
List<A> result = new ArrayList<>();
Input<I> rest = null;
try {
for (Tuple2<A, Input<I>> cursor = Tuple.of(null, i); iterator.hasNext();) {
iterator.next(); //J'utilise juste l'itérateur comme une astuce pour les boucles, alors sautez-le
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); //Renvoie l'entrée d'origine si elle ne correspond qu'à 0 fois
}
);
}
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;}} //Désolé d'utiliser l'astuce pour réduire le nombre de lignes. A propos du contenu "plus tard" après le retour de la boxing automatique du curseur+=Exécutez l'étape.
}
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);} //Une astuce pour réaliser une boucle infinie en passant un itérateur qui n'avance pas
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());};
}
}
Addendum (2017/1/18): Juste quelques corrections et ajouts
Recommended Posts