package name.panitz.parser; import java.util.ArrayList; import java.util.List; import java.util.function.Function; import java.util.function.Supplier; import java.util.function.Predicate; import java.util.function.BinaryOperator; import java.util.stream.Collectors; @FunctionalInterface public interface Parser { static record Result(List rest,R result){} List> parse(List toks); static Parser epsilon(R r) { return (toks) -> List.of(new Result<>(toks, r)); } static Parser terminal(Predicate t) { return (toks) -> !toks.isEmpty()&&t.test(toks.get(0)) ? List.of(new Result<>(toks.subList(1,toks.size()), toks.get(0))) : List.of(); } default Parser alt(Supplier> that) { return (toks) -> { var result = parse(toks); return result.isEmpty() ? that.get().parse(toks) : result; }; } static record Pair(A e1,B e2){} default Parser> seq(Supplier> that) { return (toks)->{ var result1s = parse(toks); List>> r = new ArrayList<>(); for (var r1:result1s){ var result2 = that.get().parse(r1.rest); for (var r2:result2) r.add(new Result<>(r2.rest,new Pair<>(r1.result,r2.result))); } return r; }; } default Parser> seq2(Supplier> that) { return (toks)-> parse(toks).stream() .map( r1 -> that.get() .parse(r1.rest).stream() .map(r2-> new Result<>(r2.rest,new Pair<>(r1.result,r2.result))) .collect(Collectors.toList()) ) .reduce(new ArrayList<>(), (r,r2s) -> {r.addAll(r2s);return r;}) ; } default Parser map(Function f) { return (toks) -> parse(toks).stream() .map(p->new Result<>(p.rest, f.apply(p.result))) .collect(Collectors.toList()); } default Parser> seq3(Supplier> that) { return (toks)-> parse(toks).stream() .map(r1->that.get().map(r->new Pair<>(r1.result,r)).parse(r1.rest)) .reduce(new ArrayList<>(),(r,r2s) -> {r.addAll(r2s);return r;}) ; } default Parser> zeroToN() { return seq(()->zeroToN()).map(p->{p.e2().add(0,p.e1());return p.e2();}) .alt(()->epsilon(new ArrayList())); } static interface Tree{} static record Epsilon() implements Tree {} static record Terminal(String image) implements Tree {} static record Node(String name, List childNodes) implements Tree{} static Parser epsilonTree() { return epsilon(new Epsilon()); } static Parser terminalTree(Predicate t) { return terminal(t).map(x->new Terminal(x.toString())); } static Parser seq (String name,Parser dies, Supplier> that) { return dies.seq(that).map(p->new Node(name,List.of(p.e1(),p.e2()))); } static Parser zeroToN(String name,Parser dies) { return dies.zeroToN().map(xs->new Node(name,xs)); } public static record Token(int l, int c, String image, T token) { @Override public boolean equals(Object obj) { return (obj instanceof Token t)&&t.token==token; } } static Parser, Token> token(T t) { return terminal(tok->tok.token==t); } public static enum Tok { ifT("if\\W"),elseT("else\\W"),thenT("then\\W") ,whileT("while\\W") ,funT("fun\\W"),doT("do\\W") ,lparT("\\(."),rparT("\\).") ,lbraceT("\\{."),rbraceT("\\}.") ,commaT(",."),semicolonT(";.") ,assignT(":=."), eqT("=.") ,plusT("\\+."),minusT("-."),multT("\\*."),divT("/."),modT("%.") ,identT("[\\_a-zA-Z]\\w*\\W") ,intConstantT("(?:\\d+\\.?|\\.\\d)\\d*(?:[Ee][-+]?\\d+)?.") ; public String regEx; private Tok(String regEx) { this.regEx = regEx; } } public static class LTokenizer extends Tokenizer { public LTokenizer() { for (Tok tok:Tok.values()){ put(tok.regEx,tok); } } } static interface AST{} static record OpExpr(AST l,BinOP op,AST r) implements AST{} static record Var(String n) implements AST{} static record IntLiteral(int n) implements AST{} static record Assign(String name,AST r) implements AST{} static record If(AST cond,AST then,AST otherwise) implements AST{} static record While(AST cond,AST body) implements AST{} static record Sequence(List sts) implements AST{} static record FunCall(String name,List args) implements AST{} static record Fun(String name,List args,AST body){} static record Prog(List funs,AST main){} public static enum BinOP{ add ((x,y)->x+y,"+"), sub ((x,y)->x-y,"-"), mult((x,y)->x*y,"*"), div((x,y)->x/y,"/"), mod((x,y)->x%y,"%"), eq ((x,y)->x==y?1:0,"="); BinOP(BinaryOperator op,String name){ this.op = op; this.name = name; } BinaryOperator op; String name; } static class CAF implements Supplier{ CAF(Supplier sup){this.sup=sup;} private X result = null; private Supplier sup; @Override public X get(){ if (result==null) result=sup.get(); return result; } } static Supplier,AST>> ident(){ return new CAF<>(() -> token(Tok.identT).map(x->new Var(x.image))); } static Supplier,AST>> number(){ return new CAF<>(() -> token(Tok.intConstantT) .map(x->new IntLiteral(Integer.parseInt(x.image)))); } static Supplier,AST>> cmpExpr(){return new CAF<>(()-> addExpr().get() .seq(()->token(Tok.eqT)) .seq(addExpr()) .map(x->(AST)new OpExpr(x.e1().e1,BinOP.eq,x.e2())) .alt(addExpr()) .alt(ifStat()) ); } static Supplier,AST>> addExpr(){return new CAF<>(()-> multExpr().get() .seq(()->addOp().get().seq(multExpr()).zeroToN()) .map(x->{ AST r = x.e1; for (var snd:x.e2) r = snd.e1.apply(r, snd.e2); return r; })); } static Supplier, BinaryOperator>> addOp(){ BinaryOperator aop= (AST l,AST r)->(AST)new OpExpr(l,BinOP.add,r); BinaryOperator sop= (AST l,AST r)->(AST)new OpExpr(l,BinOP.sub,r); return new CAF<>(()-> token(Tok.plusT).map(x-> aop) .alt(()->token(Tok.minusT).map(x->sop))); } static Supplier,AST>> multExpr(){return new CAF<>(()-> atom().get() .seq(()->multOp().get().seq(atom()).zeroToN()) .map(x->{ AST r = x.e1; for (var snd:x.e2) { r = new OpExpr(r, BinOP.mult, snd.e2); } return r; }) ); } static Supplier, BinaryOperator>> multOp(){ BinaryOperator muop=(AST l,AST r)->(AST)new OpExpr(l,BinOP.mult,r); BinaryOperator dop= (AST l,AST r)->(AST)new OpExpr(l,BinOP.div,r); BinaryOperator moop=(AST l,AST r)->(AST)new OpExpr(l,BinOP.mod,r); return new CAF<>(()-> token(Tok.multT).map(x-> muop) .alt(()->token(Tok.divT).map(x->dop)) .alt(()->token(Tok.modT).map(x->moop)) ); } static Supplier,AST>> atom(){return new CAF<>(()-> funCall().get() .alt(ident()) .alt(number()) .alt(()->token(Tok.lparT) .seq(addExpr()) .seq(()->token(Tok.rparT)) .map(x->x.e1.e2)) ); } static Supplier,AST>> funCall(){return new CAF<>(()-> token(Tok.identT).map(x->x.image) .seq(()->token(Tok.lparT)) .seq(args()) .seq(()->token(Tok.rparT)) .map(p->(AST)new FunCall(p.e1.e1.e1,p.e1.e2)) ); } static Supplier,List>> args(){ return new CAF<>(()-> cmpExpr().get() .seq(()->token(Tok.commaT).seq(cmpExpr()).map(p->p.e2).zeroToN()) .map(p->{p.e2.add(0,p.e1);return p.e2;}) .alt(()->epsilon(List.of())) ); } static Supplier,AST>> ifStat(){ return new CAF<>(()-> null); } static Supplier,Prog>> program(){ return new CAF<>(()->null); } static Supplier,Fun>> fundef(){ return new CAF<>(()->null); } static Supplier,AST>> statement(){ return new CAF<>(()->null); } }