RegEx- Umwandlung von String in ausführbares Objekt/ Befehl

Fodoboo131 · 8. Jun 2022

Guten Abend,

Grober Kontext: Ich sollte objektorientiert ein Turtle Programm schreiben, welches die Turtle über ein Feld laufen lässt.

Problem: Wir bekommen Strings mit ganz vielen Objektaufrufen, z.B.:

Java:

public static final String PROG_2 = "Subroutine(arc Repeat(10 Go(5) Turn(-5)))" + LS +
                                        "Subroutine(petal Call(arc) Turn(-130) Call(arc))" + LS +
                                        "Subroutine(flower Turn(90) PenDown() Repeat(10 Go(30) Turn(-5)) Repeat(9 Call(petal) Turn(30)) PenUp() Turn(208) Go(290) Turn(112))" + LS +
                                        "Repeat(5 Call(flower) Go(100))";

Diesen sollen wir in eine ausführbare Sequence umwandeln. Eine Sequence ist eine Abfolge von beliebig vielen Befehlen(realisiert durch unterschiedliche Klassen)

Repeat(int n, Sequence seq) <--- seq wird n mal ausgeführt.
Subroutine(String name, Sequence seq) <--- seq wird ausgeführt, wenn ihr name aufgerufen wird.
Call(String name) <--- ruft eine Subroutine mit Namen auf / führt diese aus

So soll meine Zielvariable am Ende aussehen:

Java:

final Stmt meadow = new Sequence(new Subroutine("arc",
            new Repeat(10, new Go(5), new Turn(-5))),
            new Subroutine("petal",
                    new Call("arc"),
                    new Turn(-130),
                    new Call("arc")),
            new Subroutine("flower",
                    new Turn(90),
                    new PenDown(),
                    new Repeat(10, new Go(30), new Turn(-5)),
                    new Repeat(9, new Call("petal"), new Turn(30)),
                    new PenUp(),
                    new Turn(208),
                    new Go(290),
                    new Turn(112)),
            new Repeat(5, new Call("flower"), new Go(100)));

Ich hab das ganze jetzt mit RegEx probiert, aber ich struggle, die Repeat und Subroutine Klassen gescheit zu implementieren:

Java:

package turtle.parser;

import turtle.stmt.Go;
import turtle.stmt.PenDown;
import turtle.stmt.PenUp;
import turtle.stmt.Repeat;
import turtle.stmt.Sequence;
import turtle.stmt.Turn;
import turtle.stmt.Subroutine;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.*;

public class LogoParser{
    String program;
    List<Object> seq= new ArrayList<>();
    String[] l1;

    public LogoParser(String program){
        this.program = program;
        l1 = program == null ? null : program.split("\s");
    }

    public Sequence run() throws ParseException {

        checkProgram();

        return seq==null ? null:  new Sequence(seq.toArray());
    }

    private void checkProgram() throws ParseException{
        Pattern turnPattern = Pattern.compile("Turn\\( \\d+\\)");
        String turn = "Turn\\( \\d+\\)";
        Pattern goPattern = Pattern.compile("Go\\(\\d+\\)"); //unlimited amount of digits
        Pattern repeatPattern = Pattern.compile("Repeat\\(\\d+\s([A-Za-z]+|\s| \\( | \\d+ \\))+ \\)\\) ");
        Pattern subroutinePattern = Pattern.compile("Subroutine\\([A-Za-z]+\s.+\\)");
        Pattern callPattern = Pattern.compile("Call\\(.+\\)");
        Pattern penUpPattern = Pattern.compile("PenUp\\(\\)");
        Pattern penDownPattern = Pattern.compile("PenDown\\(\\)");
        Pattern repeatEnd = Pattern.compile(".+\\)\\)");

        for (int i = 0; i < l1.length; i++) {
            Matcher goMatcher = goPattern.matcher(l1[i]);
            Matcher turnMatcher = turnPattern.matcher(l1[i]);
            Matcher repeatMatcher = repeatPattern.matcher(l1[i]);
            Matcher subroutineMatcher = subroutinePattern.matcher(l1[i]);
            Matcher callMatcher = callPattern.matcher(l1[i]);
            Matcher penUpMatcher = penUpPattern.matcher(l1[i]);
            Matcher penDownMatcher = penDownPattern.matcher(l1[i]);
            Matcher repeatEndMatcher = repeatEnd.matcher(l1[i]);

            if (goMatcher.find()){
                seq.add(new Go(Integer.parseInt(l1[i].replaceAll("[^0-9]", ""))));
                //deletes programm which is already in Sequence
                l1[i].replaceAll(goPattern.toString(), "");
            }
            else if (turnMatcher.find()){
                seq.add(new Turn(Integer.parseInt(l1[i].replaceAll("^\\d", ""))));
            }
            else if (penUpMatcher.find()){
                seq.add(new PenUp());
            }
            else if (penDownMatcher.find()){
                seq.add(new PenDown());
            }
            else if (subroutineMatcher.find()){
                //leider noch kein Ansatz
            }
            else if (repeatMatcher.find()){
                List<Object> subList = new ArrayList<>();
                int index = Integer.parseInt(l1[i].replaceAll("^\\d", ""));
                //wie füge ich alle elemente in meine subList ?
                seq.add(new Repeat(index, subList.toArray()));
            }
            else throw new ParseException("wrong sequence, try again");
        }
    }

}

Ich wäre über jeden Hinweis dankbar

MfG

httpdigest · 8. Jun 2022

Ich würde dir hier empfehlen, einen ganz einfachen Recursive Decent Parser zu schreiben, also nicht mit regulären Ausdrücken. Ein Parser ist für diese sehr einfache Sprache schnell geschrieben.

httpdigest · 8. Jun 2022

Zum Beispiel so:

Java:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Function;
public class Parser {
    interface Command {}
    record PenUp() implements Command {}
    record PenDown() implements Command {}
    record Turn(int angle) implements Command {}
    record Go(int steps) implements Command {}
    record Call(String name) implements Command {}
    record Subroutine(String name, List<Command> sequence) implements Command {}
    record Repeat(int n, List<Command> sequence) implements Command {}

    private final byte[] input;
    private int pos;

    public Parser(String input) {
        this.input = input.getBytes();
    }

    private void skipWhitespace() {
        while (Character.isWhitespace(input[pos]))
            pos++;
    }

    private boolean startsWithAndConsume(String begin) {
        int n = begin.length();
        if (input.length - pos >= n && Arrays.equals(input, pos, pos + n, begin.getBytes(), 0, n)) {
            pos += n;
            return true;
        }
        return false;
    }

    private String parseName() {
        int start = pos;
        while (Character.isAlphabetic(input[pos]))
            pos++;
        return new String(input, start, pos-start);
    }

    private int parseNumber() {
        int start = pos;
        if (input[pos] == '-')
            pos++;
        while (Character.isDigit(input[pos]))
            pos++;
        return Integer.parseInt(new String(input, start, pos-start));
    }

    private Command parseWithNumber(Function<Integer, Command> factory) {
        int n = parseNumber();
        pos++;
        return factory.apply(n);
    }

    private Command parse() {
        if (startsWithAndConsume("Subroutine(")) {
            return new Subroutine(parseName(), parseSequence());
        } else if (startsWithAndConsume("Repeat(")) {
            return new Repeat(parseNumber(), parseSequence());
        } else if (startsWithAndConsume("Go(")) {
            return parseWithNumber(Go::new);
        } else if (startsWithAndConsume("Turn(")) {
            return parseWithNumber(Turn::new);
        } else if (startsWithAndConsume("Call(")) {
            String name = parseName();
            pos++;
            return new Call(name);
        } else if (startsWithAndConsume("PenUp()")) {
            return new PenUp();
        } else if (startsWithAndConsume("PenDown()")) {
            return new PenDown();
        } else {
            throw new IllegalStateException("unexpected input");
        }
    }

    public List<Command> parseSequence() {
        List<Command> seq = new ArrayList<>();
        do {
            skipWhitespace();
            seq.add(parse());
        } while (pos < input.length && input[pos++] != ')');
        return seq;
    }

    // Test mit deinem Beispiel-Input
    public static void main(String[] args) {
        String LS = " ";
        System.out.println(new Parser("Subroutine(arc Repeat(10 Go(5) Turn(-5)))" + LS +
                "Subroutine(petal Call(arc) Turn(-130) Call(arc))" + LS +
                "Subroutine(flower Turn(90) PenDown() Repeat(10 Go(30) Turn(-5)) " +
                "Repeat(9 Call(petal) Turn(30)) PenUp() Turn(208) Go(290) Turn(112))" + LS +
                "Repeat(5 Call(flower) Go(100))").parseSequence());
    }
}

sascha-sphw · 9. Jun 2022

Ich mach sowas gerne mit Antlr (https://www.antlr.org/). Kommt aber auch drauf an wie Komplex es wird.

httpdigest · 9. Jun 2022

Jo, Antlr ist nice. Mein Favorit bisher war immer https://javacc.github.io/javacc/ , weil der generierte Parser keine Laufzeitabhängigkeiten zu externen Libs (z.B. javacc runtime - gibt's nicht) hat. Aber die Toolings rings um Antlr sind besser (wie dieser Parse Tree Visualizer).

httpdigest · 9. Jun 2022

@Fodoboo131 aber um nochmal auf dein Problem mit den regulären Ausdrücken zurückzukommen und warum du noch keine Idee für Subroutine und Repeat haben konntest:
Einzelne reguläre Ausdrücke können eben nur reguläre Sprachen definieren. Diese Sprache hier ist aber nicht regulär, sondern lediglich kontext-frei.
Das kann man auf den ersten Blick leicht daran erkennen, wenn es Rekursionen gibt und die Sprache im Prinzip der Dyck-Sprache entspricht: Man muss also für ein Vorkommen von Subroutine bzw. Repeat die öffnende "Klammer" bzw. Beginn des Subroutine/Repeat mit deren schließender "Klammer" bzw. Ende dieser Subroutine/Repeat-Instanz auf derselben Ebene matchen. Das geht mit regulären Ausdrücken nicht. Hierfür braucht es einen Kellerautomaten bzw. einen Stack.

Fodoboo131 · 9. Jun 2022

httpdigest hat gesagt.:

Zum Beispiel so:

Java:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Function;
public class Parser {
    interface Command {}
    record PenUp() implements Command {}
    record PenDown() implements Command {}
    record Turn(int angle) implements Command {}
    record Go(int steps) implements Command {}
    record Call(String name) implements Command {}
    record Subroutine(String name, List<Command> sequence) implements Command {}
    record Repeat(int n, List<Command> sequence) implements Command {}

    private final byte[] input;
    private int pos;

    public Parser(String input) {
        this.input = input.getBytes();
    }

    private void skipWhitespace() {
        while (Character.isWhitespace(input[pos]))
            pos++;
    }

    private boolean startsWithAndConsume(String begin) {
        int n = begin.length();
        if (input.length - pos >= n && Arrays.equals(input, pos, pos + n, begin.getBytes(), 0, n)) {
            pos += n;
            return true;
        }
        return false;
    }

    private String parseName() {
        int start = pos;
        while (Character.isAlphabetic(input[pos]))
            pos++;
        return new String(input, start, pos-start);
    }

    private int parseNumber() {
        int start = pos;
        if (input[pos] == '-')
            pos++;
        while (Character.isDigit(input[pos]))
            pos++;
        return Integer.parseInt(new String(input, start, pos-start));
    }

    private Command parseWithNumber(Function<Integer, Command> factory) {
        int n = parseNumber();
        pos++;
        return factory.apply(n);
    }

    private Command parse() {
        if (startsWithAndConsume("Subroutine(")) {
            return new Subroutine(parseName(), parseSequence());
        } else if (startsWithAndConsume("Repeat(")) {
            return new Repeat(parseNumber(), parseSequence());
        } else if (startsWithAndConsume("Go(")) {
            return parseWithNumber(Go::new);
        } else if (startsWithAndConsume("Turn(")) {
            return parseWithNumber(Turn::new);
        } else if (startsWithAndConsume("Call(")) {
            String name = parseName();
            pos++;
            return new Call(name);
        } else if (startsWithAndConsume("PenUp()")) {
            return new PenUp();
        } else if (startsWithAndConsume("PenDown()")) {
            return new PenDown();
        } else {
            throw new IllegalStateException("unexpected input");
        }
    }

    public List<Command> parseSequence() {
        List<Command> seq = new ArrayList<>();
        do {
            skipWhitespace();
            seq.add(parse());
        } while (pos < input.length && input[pos++] != ')');
        return seq;
    }

    // Test mit deinem Beispiel-Input
    public static void main(String[] args) {
        String LS = " ";
        System.out.println(new Parser("Subroutine(arc Repeat(10 Go(5) Turn(-5)))" + LS +
                "Subroutine(petal Call(arc) Turn(-130) Call(arc))" + LS +
                "Subroutine(flower Turn(90) PenDown() Repeat(10 Go(30) Turn(-5)) " +
                "Repeat(9 Call(petal) Turn(30)) PenUp() Turn(208) Go(290) Turn(112))" + LS +
                "Repeat(5 Call(flower) Go(100))").parseSequence());
    }
}

Moin,
Vielen, vielen Dank auf jeden Fall für den Ansatz und die ganze Mühe , ich hätt bei der parseNumber Methode noch ne Frage:

Java:

if (program[pos] == '-')
            pos++;

was genau bringt mir diese if-bedingung, bzw. die wird ja eigentlich nie aufgerufen, oder ? die variable program besteht ja nur aus Bytes.

Danke im Vorraus und Grüße

httpdigest · 9. Jun 2022

Naja, das prüft, ob das Byte an Stelle pos (nach int konvertiert) dem int entspricht, der entsteht, wenn man den char '-' nach int konvertiert. Also letztlich ist das der Codepoint des '-' Zeichens.
Du kannst byte mit char vergleichen, weil char letztlich nur ein 2-byte Integer ist. Beide werden dann aufgrund der Java-Regeln nach 4-byte int konvertiert und verglichen.
Dass man in Java char-Literale hat (also dass man '-' statt 45 schreiben kann) ist letztlich nur ein Convenience-Feature von Java.

Fodoboo131 · 11. Jun 2022

httpdigest hat gesagt.:
@Fodoboo131 aber um nochmal auf dein Problem mit den regulären Ausdrücken zurückzukommen und warum du noch keine Idee für Subroutine und Repeat haben konntest:
Einzelne reguläre Ausdrücke können eben nur reguläre Sprachen definieren. Diese Sprache hier ist aber nicht regulär, sondern lediglich kontext-frei.
Das kann man auf den ersten Blick leicht daran erkennen, wenn es Rekursionen gibt und die Sprache im Prinzip der Dyck-Sprache entspricht: Man muss also für ein Vorkommen von Subroutine bzw. Repeat die öffnende "Klammer" bzw. Beginn des Subroutine/Repeat mit deren schließender "Klammer" bzw. Ende dieser Subroutine/Repeat-Instanz auf derselben Ebene matchen. Das geht mit regulären Ausdrücken nicht. Hierfür braucht es einen Kellerautomaten bzw. einen Stack.

Das erklärt so einiges, jetzt macht ja sogar die Formale Sprachen Vorlesung Sinn 😀

Fodoboo131 · 11. Jun 2022

httpdigest hat gesagt.:
Naja, das prüft, ob das Byte an Stelle pos (nach int konvertiert) dem int entspricht, der entsteht, wenn man den char '-' nach int konvertiert. Also letztlich ist das der Codepoint des '-' Zeichens.
Du kannst byte mit char vergleichen, weil char letztlich nur ein 2-byte Integer ist. Beide werden dann aufgrund der Java-Regeln nach 4-byte int konvertiert und verglichen.
Dass man in Java char-Literale hat (also dass man '-' statt 45 schreiben kann) ist letztlich nur ein Convenience-Feature von Java.

Alles klar, vielen Dank für die Hilfe.
Ich hab die Records weggelassen, weil ich das als Klassen alles schon implementiert hatte, aber dein Code hat mir echt geholfen, vielen Dank !!!😃

RegEx- Umwandlung von String in ausführbares Objekt/ Befehl

Fodoboo131

Mitglied

Anhänge

httpdigest

Top Contributor

httpdigest

Top Contributor

sascha-sphw

Top Contributor

httpdigest

Top Contributor

httpdigest

Top Contributor

Fodoboo131

Mitglied

httpdigest

Top Contributor

Fodoboo131

Mitglied

Fodoboo131

Mitglied

Aktuelle Jobs

Neue Themen

Ähnliche Themen