Eine Parser Kombinator Bibliothek in Java
Studieren Sie das PDF zu Parserlkombinatoren und lösen Sie die darin enthaltenen Aufgaben.
Es gibt für die Aufgabe drei verschiedene JUnit Testdateien.
- eine öffentliche Datei, mit der Sie lokal Ihren Pasrer testen können.
- eine versteckte Datei, deren Tests bei jeder Abgabe ausgefühtr werden.
- eine dritte Testdatei, dieren Tests nicht bei der Abgabe ausgeführt werden, sondern erst, bei Abnahme der Aufgabe.
Grundlage der Bewertung sind die Ergebnisse der drei Testklassen.
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<T,R> {
static record Result<T,R>(List<T> rest,R result){}
List<Result<T, R>> parse(List<T> toks);
static<T,R> Parser<T, R> epsilon(R r) {
return (toks) -> List.of(new Result<>(toks, r));
}
static<T> Parser<T, T> terminal(Predicate<T> 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<T, R> alt(Supplier<Parser<T, R>> that) {
return (toks) -> {
var result = parse(toks);
return result.isEmpty() ? that.get().parse(toks) : result;
};
}
static record Pair<A, B>(A e1,B e2){}
default <R2> Parser<T, Pair<R,R2>> seq(Supplier<Parser<T, R2>> that) {
return (toks)->{
var result1s = parse(toks);
List<Result<T, Pair<R,R2>>> 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 <R2> Parser<T, Pair<R,R2>> seq2(Supplier<Parser<T, R2>> 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 <R2> Parser<T, R2> map(Function<R,R2> f) {
return (toks) ->
parse(toks).stream()
.map(p->new Result<>(p.rest, f.apply(p.result)))
.collect(Collectors.toList());
}
default <R2> Parser<T, Pair<R,R2>> seq3(Supplier<Parser<T, R2>> 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<T, List<R>> zeroToN() {
return
seq(()->zeroToN()).map(p->{p.e2().add(0,p.e1());return p.e2();})
.alt(()->epsilon(new ArrayList<R>()));
}
static interface Tree{}
static record Epsilon() implements Tree {}
static record Terminal(String image) implements Tree {}
static record Node(String name, List<Tree> childNodes) implements Tree{}
static<T> Parser<T,Tree> epsilonTree() {
return epsilon(new Epsilon());
}
static<T> Parser<T,Tree> terminalTree(Predicate<T> t) {
return terminal(t).map(x->new Terminal(x.toString()));
}
static<T> Parser<T,Tree> seq
(String name,Parser<T,Tree> dies, Supplier<Parser<T,Tree>> that) {
return dies.seq(that).map(p->new Node(name,List.of(p.e1(),p.e2())));
}
static<T> Parser<T, Tree> zeroToN(String name,Parser<T,Tree> dies) {
return dies.zeroToN().map(xs->new Node(name,xs));
}
public static record Token<T>(int l, int c, String image, T token) {
@Override public boolean equals(Object obj) {
return (obj instanceof Token t)&&t.token==token;
}
}
static<T> Parser<Token<T>, Token<T>> 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<Tok> {
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<AST> sts) implements AST{}
static record FunCall(String name,List<AST> args) implements AST{}
static record Fun(String name,List<String> args,AST body){}
static record Prog(List<Fun> 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<Integer> op,String name){
this.op = op;
this.name = name;
}
BinaryOperator<Integer> op;
String name;
}
static class CAF<X> implements Supplier<X>{
CAF(Supplier<X> sup){this.sup=sup;}
private X result = null;
private Supplier<X> sup;
@Override public X get(){
if (result==null) result=sup.get();
return result;
}
}
static Supplier<Parser<Token<Tok>,AST>> ident(){
return new CAF<>(() -> token(Tok.identT).map(x->new Var(x.image)));
}
static Supplier<Parser<Token<Tok>,AST>> number(){
return new CAF<>(() ->
token(Tok.intConstantT)
.map(x->new IntLiteral(Integer.parseInt(x.image))));
}
static Supplier<Parser<Token<Tok>,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<Parser<Token<Tok>,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<Parser<Token<Tok>, BinaryOperator<AST>>> addOp(){
BinaryOperator<AST> aop= (AST l,AST r)->(AST)new OpExpr(l,BinOP.add,r);
BinaryOperator<AST> 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<Parser<Token<Tok>,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<Parser<Token<Tok>, BinaryOperator<AST>>> multOp(){
BinaryOperator<AST> muop=(AST l,AST r)->(AST)new OpExpr(l,BinOP.mult,r);
BinaryOperator<AST> dop= (AST l,AST r)->(AST)new OpExpr(l,BinOP.div,r);
BinaryOperator<AST> 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<Parser<Token<Tok>,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<Parser<Token<Tok>,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<Parser<Token<Tok>,List<AST>>> 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<Parser<Token<Tok>,AST>> ifStat(){
return new CAF<>(()-> null);
}
static Supplier<Parser<Token<Tok>,Prog>> program(){
return new CAF<>(()->null);
}
static Supplier<Parser<Token<Tok>,Fun>> fundef(){
return new CAF<>(()->null);
}
static Supplier<Parser<Token<Tok>,AST>> statement(){
return new CAF<>(()->null);
}
}
java
You are not logged in and therefore you cannot submit a solution.
Subato
