Last active
July 22, 2020 20:40
-
-
Save Garciat/46059728a0bfd5f78129a947b1577826 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package example.playground.parsec; | |
import lombok.EqualsAndHashCode; | |
import lombok.Value; | |
import lombok.val; | |
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.Collections; | |
import java.util.HashSet; | |
import java.util.List; | |
import java.util.Objects; | |
import java.util.stream.Collectors; | |
interface F3<A, B, C, R> { | |
R apply(A a, B b, C c); | |
} | |
interface F2<A, B, R> { | |
R apply(A a, B b); | |
} | |
interface F1<A, R> { | |
R apply(A a); | |
default <B, C, S> F3<A, B, C, S> andThen(F3<R, B, C, S> f) { | |
return (a, b, c) -> f.apply(this.apply(a), b, c); | |
} | |
static <T> F1<T, T> id() { | |
return x -> x; | |
} | |
} | |
interface F0<R> { | |
R apply(); | |
} | |
@Value | |
class Unit { | |
private Unit() {} | |
static Unit get() { | |
return new Unit(); | |
} | |
} | |
abstract class Maybe<A> { | |
abstract <R> R match(F0<R> nothing, F1<A, R> just); | |
static <A> Maybe<A> just(A value) { | |
return new Just<>(value); | |
} | |
static <A> Maybe<A> nothing() { | |
return new Nothing<>(); | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class Just<A> extends Maybe<A> { | |
A value; | |
@Override | |
<R> R match(F0<R> nothing, F1<A, R> just) { | |
return just.apply(value); | |
} | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class Nothing<A> extends Maybe<A> { | |
@Override | |
<R> R match(F0<R> nothing, F1<A, R> just) { | |
return nothing.apply(); | |
} | |
} | |
} | |
abstract class Either<A, B> { | |
abstract <C> Either<A, C> map(F1<B, C> f); | |
static <A, B> Either<A, B> left(A a) { | |
return new Left<>(a); | |
} | |
static <A, B> Either<A, B> right(B b) { | |
return new Right<>(b); | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class Left<A, B> extends Either<A, B> { | |
A value; | |
@Override | |
<C> Either<A, C> map(F1<B, C> f) { | |
return new Left<>(value); | |
} | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class Right<A, B> extends Either<A, B> { | |
B value; | |
@Override | |
<C> Either<A, C> map(F1<B, C> f) { | |
return new Right<>(f.apply(value)); | |
} | |
} | |
} | |
abstract class Lists { | |
static <T> List<T> zero() { | |
return Collections.emptyList(); | |
} | |
static <T> List<T> one(T t) { | |
return Collections.singletonList(t); | |
} | |
static <T> List<T> cons(T t, List<T> ts) { | |
ArrayList<T> ts_ = new ArrayList<>(ts.size() + 1); | |
ts_.add(t); | |
ts_.addAll(ts); | |
return ts_; | |
} | |
static <T> List<T> reverse(List<T> ts) { | |
ArrayList<T> copy = new ArrayList<>(ts); | |
Collections.reverse(copy); | |
return copy; | |
} | |
static <T> boolean isEmpty(List<T> ts) { | |
return ts.isEmpty(); | |
} | |
public static <T> List<T> concat(List<T> ts1, List<T> ts2) { | |
ArrayList<T> ts_ = new ArrayList<>(ts1.size() + ts2.size()); | |
ts_.addAll(ts1); | |
ts_.addAll(ts2); | |
return ts_; | |
} | |
public static <A, B> B foldr(List<A> as, B nil, F2<A, B, B> cons) { | |
B curr = nil; | |
for (int i = as.size() - 1; i >= 0; i--) { | |
curr = cons.apply(as.get(i), curr); | |
} | |
return curr; | |
} | |
public static <A, B> B foldl(List<A> as, B nil, F2<B, A, B> cons) { | |
B curr = nil; | |
for (A a : as) { | |
curr = cons.apply(curr, a); | |
} | |
return curr; | |
} | |
public static <A, B> List<B> map(List<A> as, F1<A, B> f) { | |
return as.stream().map(f::apply).collect(Collectors.toList()); | |
} | |
public static String asString(List<Character> cs) { | |
StringBuilder sb = new StringBuilder(); | |
for (Character c : cs) { | |
sb.append(c); | |
} | |
return sb.toString(); | |
} | |
public static List<Character> ofString(String s) { | |
List<Character> cs = new ArrayList<>(); | |
for (int i = 0; i < s.length(); i++) { | |
cs.add(s.charAt(i)); | |
} | |
return cs; | |
} | |
public static Integer sum(List<Integer> is) { | |
return Lists.foldl(is, 0, Integer::sum); | |
} | |
} | |
enum Ordering { | |
LT, EQ, GT | |
} | |
abstract class Prelude { | |
static Ordering compare(int i1, int i2) { | |
switch (Integer.compare(i1, i2)) { | |
case -1: | |
return Ordering.LT; | |
case 0: | |
return Ordering.EQ; | |
case 1: | |
return Ordering.GT; | |
default: | |
throw new IllegalStateException(); | |
} | |
} | |
static String show(Character c) { | |
return String.format("\"%c\"", c); | |
} | |
static String show(Object o) { | |
if (o instanceof Character) { | |
return Prelude.show((Character) o); | |
} else { | |
return Objects.toString(o); | |
} | |
} | |
} | |
@Value | |
class SourcePos { | |
String name; | |
int line; | |
int column; | |
static SourcePos initial(String name) { | |
return new SourcePos(name, 1, 1); | |
} | |
public static SourcePos of(String name, int row, int column) { | |
return new SourcePos(name, row, column); | |
} | |
} | |
@Value | |
class State<S, U> { | |
S input; | |
SourcePos pos; | |
U user; | |
static <S, U> State<S, U> of(S input, SourcePos pos, U user) { | |
return new State<>(input, pos, user); | |
} | |
} | |
abstract class Message { | |
static Message sysUnExpect(String m) { | |
return new SysUnExpect(m); | |
} | |
static Message unExpect(String m) { | |
return new UnExpect(m); | |
} | |
static Message expect(String m) { | |
return new Expect(m); | |
} | |
static Message message(String m) { | |
return new Plain(m); | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class SysUnExpect extends Message { | |
String msg; | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class UnExpect extends Message { | |
String msg; | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class Expect extends Message { | |
String msg; | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class Plain extends Message { | |
String msg; | |
} | |
} | |
@Value | |
class ParseError { | |
SourcePos pos; | |
List<Message> messages; | |
@Override | |
public String toString() { | |
return ErrorMethods.show(this); | |
} | |
static ParseError of(SourcePos pos, List<Message> msgs) { | |
return new ParseError(pos, msgs); | |
} | |
} | |
abstract class Consumed<A> { | |
abstract <R> R match(F1<A, R> yes, F1<A, R> no); | |
A value() { | |
return match(a -> a, a -> a); | |
} | |
static <A> Consumed<A> yes(A value) { | |
return new Yes<>(value); | |
} | |
static <A> Consumed<A> no(A value) { | |
return new No<>(value); | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class Yes<A> extends Consumed<A> { | |
A value; | |
@Override | |
<R> R match(F1<A, R> yes, F1<A, R> no) { | |
return yes.apply(value); | |
} | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class No<A> extends Consumed<A> { | |
A value; | |
@Override | |
<R> R match(F1<A, R> yes, F1<A, R> no) { | |
return no.apply(value); | |
} | |
} | |
} | |
abstract class Reply<S, U, A> { | |
abstract <R> R match(F1<Ok<S, U, A>, R> ok, F1<ParseError, R> err); | |
static <S, U, A> Reply<S, U, A> ok(A value, State<S, U> state, ParseError error) { | |
return new Ok<>(value, state, error); | |
} | |
static <S, U, A> Reply<S, U, A> error(ParseError error) { | |
return new Error<>(error); | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class Ok<S, U, A> extends Reply<S, U, A> { | |
A value; | |
State<S, U> state; | |
ParseError error; | |
@Override | |
<R> R match(F1<Ok<S, U, A>, R> ok, F1<ParseError, R> err) { | |
return ok.apply(this); | |
} | |
} | |
@Value | |
@EqualsAndHashCode(callSuper = false) | |
static class Error<S, U, A> extends Reply<S, U, A> { | |
ParseError error; | |
@Override | |
<R> R match(F1<Ok<S, U, A>, R> ok, F1<ParseError, R> err) { | |
return err.apply(error); | |
} | |
} | |
} | |
interface Rules<S, U, A, R> { | |
R consumedOk(A result, State<S, U> state, ParseError error); | |
R consumedError(ParseError error); | |
R emptyOk(A result, State<S, U> state, ParseError error); | |
R emptyError(ParseError error); | |
default F3<A, State<S, U>, ParseError, R> cok() { | |
return this::consumedOk; | |
} | |
default F1<ParseError, R> cerr() { | |
return this::consumedError; | |
} | |
default F3<A, State<S, U>, ParseError, R> eok() { | |
return this::emptyOk; | |
} | |
default F1<ParseError, R> eerr() { | |
return this::emptyError; | |
} | |
static <S, U, A, R> Rules<S, U, A, R> of( | |
F3<A, State<S, U>, ParseError, R> cok, | |
F1<ParseError, R> cerr, | |
F3<A, State<S, U>, ParseError, R> eok, | |
F1<ParseError, R> eerr) { | |
return new Rules<S, U, A, R>() { | |
@Override | |
public R consumedOk(A result, State<S, U> state, ParseError error) { | |
return cok.apply(result, state, error); | |
} | |
@Override | |
public R consumedError(ParseError error) { | |
return cerr.apply(error); | |
} | |
@Override | |
public R emptyOk(A result, State<S, U> state, ParseError error) { | |
return eok.apply(result, state, error); | |
} | |
@Override | |
public R emptyError(ParseError error) { | |
return eerr.apply(error); | |
} | |
}; | |
} | |
} | |
interface ParsecT<S, U, A> { | |
<R> R parse(State<S, U> state, Rules<S, U, A, R> rules); | |
default <B> ParsecT<S, U, B> map(F1<A, B> f) { | |
return Prim.parsecMap(this, f); | |
} | |
default <B> ParsecT<S, U, B> flatMap(F1<A, ParsecT<S, U, B>> k) { | |
return Prim.parserBind(this, k); | |
} | |
default ParsecT<S, U, List<A>> many() { | |
return Combo.many(this); | |
} | |
default ParsecT<S, U, List<A>> many1() { | |
return Combo.many1(this); | |
} | |
default <B> ParsecT<S, U, B> then(ParsecT<S, U, B> p) { | |
return Methods.apR(this, p); | |
} | |
default <B> ParsecT<S, U, A> followedBy(ParsecT<S, U, B> p) { | |
return Methods.apL(this, p); | |
} | |
default ParsecT<S, U, A> orElse(ParsecT<S, U, A> p) { | |
return Prim.parserPlus(this, p); | |
} | |
default ParsecT<S, U, A> failBack() { | |
return Prim.try_(this); | |
} | |
default ParsecT<S, U, Unit> discard() { | |
return Combo.discard(this); | |
} | |
default <B> ParsecT<S, U, B> emplace(B b) { | |
return Methods.apR(this, Methods.pure(b)); | |
} | |
} | |
interface Stream<S extends Stream<S, T>, T> { | |
Maybe<Next<T, S>> uncons(); | |
} | |
@Value | |
class Next<T, S> { | |
T token; | |
S state; | |
static <T, S> Next<T, S> of(T token, S state) { | |
return new Next<>(token, state); | |
} | |
} | |
abstract class Pos { | |
static SourcePos updatePosChar(SourcePos pos, Character c) { | |
switch (c) { | |
case '\n': | |
return SourcePos.of(pos.getName(), pos.getLine() + 1, 1); | |
default: | |
return SourcePos.of(pos.getName(), pos.getLine(), pos.getColumn() + 1); | |
} | |
} | |
} | |
abstract class Errors { | |
static ParseError newErrorMessage(Message msg, SourcePos pos) { | |
return ParseError.of(pos, Lists.one(msg)); | |
} | |
static ParseError newErrorUnknown(SourcePos pos) { | |
return new ParseError(pos, Lists.zero()); | |
} | |
static ParseError unexpectError(String msg, SourcePos pos) { | |
return newErrorMessage(Message.sysUnExpect(msg), pos); | |
} | |
static <S, U> ParseError unknownError(State<S, U> s) { | |
return newErrorUnknown(s.getPos()); | |
} | |
static ParseError mergeError(ParseError e1, ParseError e2) { | |
if (Lists.isEmpty(e2.getMessages()) && !Lists.isEmpty(e1.getMessages())) { | |
return e1; | |
} else if (Lists.isEmpty(e1.getMessages()) && !Lists.isEmpty(e2.getMessages())) { | |
return e2; | |
} else { | |
switch (ErrorMethods.compare(e1.getPos(), e2.getPos())) { | |
case EQ: | |
return ParseError.of(e1.getPos(), Lists.concat(e1.getMessages(), e2.getMessages())); | |
case GT: | |
return e1; | |
case LT: | |
return e2; | |
default: | |
throw new IllegalStateException(); | |
} | |
} | |
} | |
} | |
abstract class ErrorMethods { | |
static String show(SourcePos pos) { | |
return String.format("\"%s\" (line %d, column %d)", pos.getName(), pos.getLine(), pos.getColumn()); | |
} | |
static String show(ParseError err) { | |
return String.format("%s: %s", ErrorMethods.show(err.getPos()), new HashSet<>(err.getMessages())); | |
} | |
static Ordering compare(SourcePos p1, SourcePos p2) { | |
switch (Prelude.compare(p1.getLine(), p2.getLine())) { | |
case EQ: | |
return Prelude.compare(p1.getColumn(), p2.getColumn()); | |
case LT: | |
return Ordering.LT; | |
case GT: | |
return Ordering.GT; | |
default: | |
throw new IllegalStateException(); | |
} | |
} | |
} | |
abstract class Prim { | |
static <S, U, A, B> ParsecT<S, U, B> parsecMap(ParsecT<S, U, A> p, F1<A, B> f) { | |
return new ParsecT<S, U, B>() { | |
@Override | |
public <R> R parse(State<S, U> state, Rules<S, U, B, R> rules) { | |
return p.parse(state, Rules.of( | |
f.andThen(rules.cok()), | |
rules.cerr(), | |
f.andThen(rules.eok()), | |
rules.eerr())); | |
} | |
}; | |
} | |
static <S, U, A> ParsecT<S, U, A> parserReturn(A a) { | |
return new ParsecT<S, U, A>() { | |
@Override | |
public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) { | |
return rules.emptyOk(a, state, Errors.unknownError(state)); | |
} | |
}; | |
} | |
static <S, U, A, B> ParsecT<S, U, B> parserBind(ParsecT<S, U, A> m, F1<A, ParsecT<S, U, B>> k) { | |
return new ParsecT<S, U, B>() { | |
@Override | |
public <R> R parse(State<S, U> s, Rules<S, U, B, R> rules) { | |
return m.parse(s, Rules.of( | |
// consumed-okay case for m | |
(x, s_, err) -> k.apply(x).parse(s_, Rules.of( | |
// if (k x) consumes, those go straight up | |
rules.cok(), | |
rules.cerr(), | |
// if (k x) doesn't consume input, but is okay, | |
// we still return in the consumed continuation | |
(y, s__, err_) -> rules.consumedOk(y, s__, Errors.mergeError(err, err_)), | |
// if (k x) doesn't consume input, but errors, | |
// we return the error in the 'consumed-error' | |
// continuation | |
(err_) -> rules.consumedError(Errors.mergeError(err, err_)) | |
)), | |
// consumed-error case for m | |
rules.cerr(), | |
// empty-ok case for m | |
(x, s_, err) -> k.apply(x).parse(s_, Rules.of( | |
// in these cases, (k x) can return as empty | |
rules.cok(), | |
rules.cerr(), | |
(y, s__, err_) -> rules.emptyOk(y, s__, Errors.mergeError(err, err_)), | |
(err_) -> rules.emptyError(Errors.mergeError(err, err_)) | |
)), | |
// empty-error case for m | |
rules.eerr() | |
)); | |
} | |
}; | |
} | |
static <S, U, A> ParsecT<S, U, A> parserZero() { | |
return new ParsecT<S, U, A>() { | |
@Override | |
public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) { | |
return rules.emptyError(Errors.unknownError(state)); | |
} | |
}; | |
} | |
static <S, U, A> ParsecT<S, U, A> parserPlus( | |
ParsecT<S, U, A> m, | |
ParsecT<S, U, A> n | |
) { | |
return new ParsecT<S, U, A>() { | |
@Override | |
public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) { | |
return m.parse(state, Rules.of( | |
rules.cok(), | |
rules.cerr(), | |
rules.eok(), | |
(err) -> n.parse(state, Rules.of( | |
rules.cok(), | |
rules.cerr(), | |
(y, s_, err_) -> rules.emptyOk(y, s_, Errors.mergeError(err, err_)), | |
(err_) -> rules.emptyError(Errors.mergeError(err, err_)) | |
)) | |
)); | |
} | |
}; | |
} | |
static <S, U, A> ParsecT<S, U, A> parserFail(String msg) { | |
return new ParsecT<S, U, A>() { | |
@Override | |
public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) { | |
return rules.emptyError(Errors.newErrorMessage(Message.message(msg), state.getPos())); | |
} | |
}; | |
} | |
static <S extends Stream<S, T>, U, A, T> ParsecT<S, U, A> tokenPrim( | |
F1<T, String> showToken, | |
F3<SourcePos, T, S, SourcePos> nextPos, | |
F1<T, Maybe<A>> test | |
) { | |
return new ParsecT<S, U, A>() { | |
@Override | |
public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) { | |
return state.getInput().uncons().match( | |
() -> rules.emptyError(Errors.unexpectError("", state.getPos())), | |
next -> test.apply(next.getToken()).match( | |
() -> rules.emptyError( | |
Errors.unexpectError(showToken.apply(next.getToken()), state.getPos())), | |
x -> { | |
SourcePos newPos = nextPos.apply(state.getPos(), next.getToken(), next.getState()); | |
State<S, U> newState = State.of(next.getState(), newPos, state.getUser()); | |
return rules.consumedOk(x, newState, Errors.newErrorUnknown(newPos)); | |
} | |
) | |
); | |
} | |
}; | |
} | |
static <S, U, A> ParsecT<S, U, A> try_( | |
ParsecT<S, U, A> p | |
) { | |
return new ParsecT<S, U, A>() { | |
@Override | |
public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) { | |
return p.parse(state, Rules.of( | |
rules.cok(), | |
rules.eerr(), // switched 'cerr' with 'eerr' | |
rules.eok(), | |
rules.eerr()) | |
); | |
} | |
}; | |
} | |
static <S extends Stream<S, T>, U, A, T> ParsecT<S, U, A> lookAhead( | |
ParsecT<S, U, A> p | |
) { | |
return new ParsecT<S, U, A>() { | |
@Override | |
public <R> R parse(State<S, U> s, Rules<S, U, A, R> rules) { | |
F3<A, State<S, U>, ParseError, R> eok_ = | |
// purposefully use 's' instead of 's_' | |
(a, s_, err) -> rules.emptyOk(a, s, Errors.unknownError(s)); | |
return p.parse(s, Rules.of( | |
eok_, | |
rules.cerr(), | |
eok_, | |
rules.eerr()) | |
); | |
} | |
}; | |
} | |
static <S, U, A> ParsecT<S, U, List<A>> manyAccum( | |
F2<A, List<A>, List<A>> acc, | |
ParsecT<S, U, A> p | |
) { | |
return new ParsecT<S, U, List<A>>() { | |
@Override | |
public <R> R parse(State<S, U> s, Rules<S, U, List<A>, R> rules) { | |
F1<List<A>, F3<A, State<S, U>, ParseError, R>> walk = | |
new F1<List<A>, F3<A, State<S, U>, ParseError, R>>() { | |
@Override | |
public F3<A, State<S, U>, ParseError, R> apply(List<A> xs) { | |
return (x, s_, err) -> p.parse(s_, Rules.of( | |
// explicitly nested because not lazy | |
(y, s__, err_) -> apply(acc.apply(x, xs)).apply(y, s__, err_), | |
rules.cerr(), | |
(y, s__, err_) -> manyErr(), | |
err_ -> rules.consumedOk(acc.apply(x, xs), s_, err) | |
)); | |
} | |
}; | |
return p.parse(s, Rules.of( | |
walk.apply(Lists.zero()), | |
rules.cerr(), | |
(x, s_, err) -> manyErr(), | |
(err) -> rules.emptyOk(Lists.zero(), s, err) | |
)); | |
} | |
}; | |
} | |
static <T> T manyErr() { | |
throw new RuntimeException("combinator 'many' is applied to a parser that accepts an empty string"); | |
} | |
static <S, U, A> ParsecT<S, U, A> unexpected(String msg) { | |
return new ParsecT<S, U, A>() { | |
@Override | |
public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) { | |
return rules.emptyError(Errors.newErrorMessage(Message.unExpect(msg), state.getPos())); | |
} | |
}; | |
} | |
} | |
abstract class Run { | |
static <S, U, A> Consumed<Reply<S, U, A>> runParsecT(ParsecT<S, U, A> p, State<S, U> s) { | |
return p.parse(s, | |
Rules.of( | |
(a, s_, err) -> Consumed.yes(Reply.ok(a, s_, err)), | |
(err) -> Consumed.yes(Reply.error(err)), | |
(a, s_, err) -> Consumed.no(Reply.ok(a, s_, err)), | |
(err) -> Consumed.no(Reply.error(err)))); | |
} | |
static <S extends Stream<S, T>, U, A, T> Either<ParseError, A> runP( | |
ParsecT<S, U, A> p, | |
U u, | |
String name, | |
S s | |
) { | |
return runParsecT(p, State.of(s, SourcePos.initial(name), u)).value().match( | |
ok -> Either.right(ok.getValue()), | |
err -> Either.left(err) | |
); | |
} | |
} | |
abstract class Methods { | |
static <S, U, A> ParsecT<S, U, A> pure(A a) { | |
return Prim.parserReturn(a); | |
} | |
static <S, U, A, B, C> ParsecT<S, U, C> liftA2( | |
F2<A, B, C> f, | |
ParsecT<S, U, A> p1, | |
ParsecT<S, U, B> p2 | |
) { | |
return Prim.parserBind(p1, a -> p2.map(b -> f.apply(a, b))); | |
} | |
static <S, U, A, B> ParsecT<S, U, A> apL( | |
ParsecT<S, U, A> p1, | |
ParsecT<S, U, B> p2 | |
) { | |
return Methods.liftA2((a, b) -> a, p1, p2); | |
} | |
static <S, U, A, B> ParsecT<S, U, B> apR( | |
ParsecT<S, U, A> p1, | |
ParsecT<S, U, B> p2 | |
) { | |
return Methods.liftA2((a, b) -> b, p1, p2); | |
} | |
static <S, U, A> ParsecT<S, U, List<A>> sequence( | |
List<ParsecT<S, U, A>> ms | |
) { | |
return Methods.mapM(F1.id(), ms); | |
} | |
static <S, U, A, B> ParsecT<S, U, List<B>> mapM( | |
F1<A, ParsecT<S, U, B>> f, | |
List<A> as | |
) { | |
return Lists.foldr( | |
as, | |
Methods.pure(Lists.zero()), | |
(a, r) -> f.apply(a).flatMap(b -> r.map(bs -> Lists.cons(b, bs))) | |
); | |
} | |
} | |
abstract class Combo { | |
static <S, U, A> ParsecT<S, U, Unit> discard(ParsecT<S, U, A> p) { | |
return p.then(Methods.pure(Unit.get())); | |
} | |
static <S, U, A> ParsecT<S, U, List<A>> many(ParsecT<S, U, A> p) { | |
return Prim.manyAccum(Lists::cons, p).map(Lists::reverse); | |
} | |
static <S, U, A> ParsecT<S, U, List<A>> many1(ParsecT<S, U, A> p) { | |
return Methods.liftA2(Lists::cons, p, Combo.many(p)); | |
} | |
@SafeVarargs | |
static <S, U, A> ParsecT<S, U, A> choice(ParsecT<S, U, A>... ps) { | |
return Combo.choice(Arrays.asList(ps)); | |
} | |
static <S, U, A> ParsecT<S, U, A> choice(List<ParsecT<S, U, A>> ps) { | |
return Lists.foldr(ps, Prim.parserZero(), Prim::parserPlus); | |
} | |
static <S, U, A> ParsecT<S, U, A> option(ParsecT<S, U, A> p, A a) { | |
return p.orElse(Methods.pure(a)); | |
} | |
static <S, U, A> ParsecT<S, U, Maybe<A>> optionMaybe(ParsecT<S, U, A> p) { | |
return Combo.option(p.map(Maybe::just), Maybe.nothing()); | |
} | |
static <S, U, A> ParsecT<S, U, Unit> optional(ParsecT<S, U, A> p) { | |
return p.flatMap(a -> Methods.pure(Unit.get())).orElse(Methods.pure(Unit.get())); | |
} | |
static <S, U, A, Sep> ParsecT<S, U, List<A>> sepBy(ParsecT<S, U, A> p, ParsecT<S, U, Sep> sep) { | |
return Combo.sepBy1(p, sep).orElse(Methods.pure(Lists.zero())); | |
} | |
static <S, U, A, Sep> ParsecT<S, U, List<A>> sepBy1(ParsecT<S, U, A> p, ParsecT<S, U, Sep> sep) { | |
return p.flatMap(x -> Combo.many(sep.then(p)).map(xs -> Lists.cons(x, xs))); | |
} | |
static <S extends Stream<S, T>, U, T> ParsecT<S, U, T> anyToken() { | |
return Prim.tokenPrim(Prelude::show, (pos, _t, _ts) -> pos, Maybe::just); | |
} | |
static <S extends Stream<S, T>, U, T> ParsecT<S, U, Unit> eof() { | |
return Combo.notFollowedBy(Combo.<S, U, T>anyToken()); | |
} | |
static <S, U, A> ParsecT<S, U, Unit> notFollowedBy(ParsecT<S, U, A> p) { | |
return p.failBack() | |
.flatMap(c -> Prim.unexpected(Prelude.show(c))) | |
.discard() | |
.orElse(Methods.pure(Unit.get())) | |
.failBack(); | |
} | |
} | |
abstract class Char { | |
static <S extends Stream<S, Character>, U> ParsecT<S, U, Character> of( | |
Character c | |
) { | |
return Char.satisfy(d -> c == d); | |
} | |
static <S extends Stream<S, Character>, U> ParsecT<S, U, Character> digit() { | |
return Char.satisfy(Character::isDigit); | |
} | |
static <S extends Stream<S, Character>, U> ParsecT<S, U, Character> satisfy( | |
F1<Character, Boolean> f | |
) { | |
return Prim.tokenPrim( | |
Prelude::show, | |
(pos, c, s_) -> Pos.updatePosChar(pos, c), | |
c -> f.apply(c) ? Maybe.just(c) : Maybe.nothing() | |
); | |
} | |
static <S extends Stream<S, Character>, U> ParsecT<S, U, String> string( | |
String s | |
) { | |
ParsecT<S, U, List<Character>> p_cs = Methods.sequence(Lists.map(Lists.ofString(s), Char::of)); | |
return p_cs.map(Lists::asString); | |
} | |
} | |
@Value | |
class StringStream implements Stream<StringStream, Character> { | |
String s; | |
int pos; | |
StringStream advanced() { | |
return new StringStream(s, pos + 1); | |
} | |
@Override | |
public Maybe<Next<Character, StringStream>> uncons() { | |
if (pos >= s.length()) { | |
return Maybe.nothing(); | |
} else { | |
return Maybe.just(Next.of(s.charAt(pos), advanced())); | |
} | |
} | |
static StringStream of(String s) { | |
return new StringStream(s, 0); | |
} | |
} | |
@Value | |
class ListStream<T> implements Stream<ListStream<T>, T> { | |
List<T> ts; | |
int pos; | |
ListStream advanced() { | |
return new ListStream<>(ts, pos + 1); | |
} | |
@Override | |
public Maybe<Next<T, ListStream<T>>> uncons() { | |
if (pos >= ts.size()) { | |
return Maybe.nothing(); | |
} else { | |
return Maybe.just(Next.of(ts.get(pos), advanced())); | |
} | |
} | |
static <T> ListStream<T> of(List<T> ts) { | |
return new ListStream<>(ts, 0); | |
} | |
} | |
public class Program { | |
private static <S extends Stream<S, Character>, U> ParsecT<S, U, Character> parser1() { | |
return Char.<S, U>of('c').many1().then(Char.of('b')).failBack().orElse(Char.of('c')); | |
} | |
private static <S extends Stream<S, Character>, U> ParsecT<S, U, Integer> integer() { | |
return Char.<S, U>digit().many1().map(Lists::asString).map(Integer::valueOf); | |
} | |
private static <S extends Stream<S, Character>, U, A> ParsecT<S, U, List<A>> csv(ParsecT<S, U, A> p) { | |
return Combo.sepBy1(p, Char.of(',')); | |
} | |
private static <S extends Stream<S, Character>, U> ParsecT<S, U, String> coolWords() { | |
return Combo.choice( | |
Char.<S, U>string("what").failBack(), | |
Char.string("wild"), | |
Char.string("hello") | |
); | |
} | |
enum Token { | |
LParen, | |
RParen, | |
Plus | |
} | |
private static <S extends Stream<S, Character>, U> ParsecT<S, U, Token> dumbToken() { | |
return Combo.choice( | |
Char.<S, U>of('(').emplace(Token.LParen), | |
Char.<S, U>of(')').emplace(Token.RParen), | |
Char.<S, U>of('+').emplace(Token.Plus) | |
); | |
} | |
private static <S extends Stream<S, Character>, U> ParsecT<S, U, List<Token>> dumbTokens() { | |
val whitespace = Combo.many(Char.<S, U>of(' ')); | |
val token = Program.<S, U>dumbToken().followedBy(whitespace); | |
return whitespace.then(Combo.many(token)).followedBy(Combo.eof()); | |
} | |
public static void main(String[] args) { | |
val result1 = Run.runP( | |
csv(Program.<StringStream, Object>integer()).followedBy(Combo.eof()), | |
new Object(), | |
"<stdin>", | |
StringStream.of("1,2,3,4,5")); | |
System.out.println(result1.map(Lists::sum)); | |
val result2 = Run.runP( | |
coolWords(), | |
new Object(), | |
"<stdin>", | |
StringStream.of("wild")); | |
System.out.println(result2); | |
val result3 = Run.runP( | |
dumbTokens(), | |
new Object(), | |
"<stdin>", | |
StringStream.of(" ( + + ))) + ")); | |
System.out.println(result3); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment